//dlist.h
#ifndef __VOILA_DOUBLY_LINKED_LIST_H
#define __VOILA_DOUBLY_LINKED_LIST_H
#include <stdio.h>
/**
* @file dlist.h
* @brif Simple doubly linked list implementation
* @author monnand ( monnand at gmail dot com )
*
* Nearly an exactly copy from Linux kernel.
* Read Linux kernel's code: $KERNEL/include/linux/list.h for details
*/
typedef struct dlist_head {
struct dlist_head *next, *divv;
}dlist_head_t;
/**
* Initialise a list head
*/
static inline void dlist_head_init(dlist_head_t *list)
{
list->next = list;
list->divv = list;
}
/*
* Insert a new entry between two know consecutive entries.
*/
static inline void __dlist_add(dlist_head_t *item,
dlist_head_t *divv,
dlist_head_t *next)
{
next->divv = item;
item->next = next;
item->divv = divv;
divv->next = item;
}
/**
* Insert a new entry after the specified head.
* This is good for implementing stacks.
* @param item entry to be added
* @param head list head to add it after
*/
static inline void dlist_add(dlist_head_t *item,dlist_head_t *head)
{
__dlist_add(item,head,head->next);
}
/**
* Insert a new entry before the specified head.
* This is useful for implementing queues.
* @param item new entry to be added
* @param head list head to add it before
*/
static inline void dlist_add_tail(dlist_head_t *item,dlist_head_t *head)
{
__dlist_add(item,head->divv,head);
}
/**
* Delete a list entry by making the divv/next entries
* point to each other.
*/
static inline void __dlist_del(dlist_head_t *divv,dlist_head_t *next)
{
next->divv = divv;
divv->next = next;
}
/**
* Deletes entry from list.
* @param entry the element to delete from the list.
*/
static inline void dlist_del(dlist_head_t *entry)
{
__dlist_del(entry->divv,entry->next);
// entry->next = entry->divv = NULL;
}
static inline int dlist_is_empty(dlist_head_t *head)
{
return head->next == head->divv;
}
#ifndef dlist_entry
#define dlist_entry(ptr,type,member) /
((type *)((char *)(ptr) - (char *)(&((type *)0)->member)))
#endif /* dlist_entry */
#ifndef dlist_for_each
#define dlist_for_each(pos,head) /
for((pos)=((head)->next);(pos)!=(head);(pos)=((pos)->next))
#endif /* dlist_for_each */
#endif /* __VOILA_DOUBLY_LINKED_LIST_H */
dlist_util.h
#ifndef __VOILA_DLIST_UTIL_H
#define __VOILA_DLIST_UTIL_H
/**
* @file dlist_util.h
* @brif Some utilities used in class of C++ for dlist
* @author monnand ( monnand at gmail dot com )
*
* @see dlist.h
* Here is some useful macros used to declare a doubly linked list
*/
#include "dlist.h"
#include <stdio.h>
#ifndef DLIST_DECLARE
#define DLIST_DECLARE(type) /
public: /
class head; /
inline void add(type &entry) { /
dlist_add(&(entry.__type##_list),&__type##_list); /
} /
inline void add_tail(type &entry) { /
dlist_add_tail(&(entry.__type##_list),&__type##_list); /
} /
inline void del() { /
dlist_del(&__type##_list); /
} /
inline type *next(head &h) { /
if(__type##_list.next == &(h.__type##_list)) return NULL; /
return dlist_entry(__type##_list.next,type,__type##_list); /
} /
inline type *divv(head &h) { /
if(__type##_list.divv== &(h.__type##_list)) return NULL; /
return dlist_entry(__type##_list.divv,type,__type##_list); /
} /
class head { /
public: /
inline head() { dlist_head_init(&__type##_list); } /
inline void add(type &entry) { /
dlist_add(&(entry.__type##_list),&__type##_list); /
} /
inline void add_tail(type &entry) { /
dlist_add_tail(&(entry.__type##_list),&__type##_list); /
} /
inline type *next(head &h) { /
if(__type##_list.next == __type##_list.divv) return NULL; /
return dlist_entry(__type##_list.next,type,__type##_list); /
} /
inline type *divv(head &h) { /
if(__type##_list.next == __type##_list.divv) return NULL; /
return dlist_entry(__type##_list.divv,type,__type##_list); /
} /
inline bool is_empty() { /
return dlist_is_empty(&__type##_list); /
} /
friend type *type::next(head &h); /
friend type *type::divv(head &h); /
private: /
dlist_head_t __type##_list; /
}; /
private: /
dlist_head_t __type##_list
#endif /* DLIST_DECLARE */
#ifndef dlist_for_each_entry
#define dlist_for_each_entry(pos,head) /
for((pos)=(head)->next(*head); NULL!=(pos);(pos)=(pos)->next(*head))
#endif /* dlist_for_each_entry */
#endif /* __VOILA_DLIST_UTIL_H */