/* * list.h -- macros for doubly-linked split-ring lists * * (C) 2001 Tony Finch * * $dotat: things/macrolist.h,v 1.7 2001/12/17 16:26:58 fanf Exp $ */ #ifndef LIST_H #define LIST_H /* * This file defines a data structure that I call a doubly-linked * split-ring list. * * For a given list there are three types: the element structure, * which is defined by the user and contains an instance of the link * structure; the link structure, which contains pointers to the * previous and next element structures; and the list root structure, * which contains two link structures, one for the head end of the * list and one for the tail end. The prev pointer of the head and the * next pointer of the tail are initialized to NULL so that a program * can know when it has reached either end of a list, without knowing * the address of the list root beforehand as is required for unsplit * rings. The following diagram illustrates the structure. Note that * the head and tail of the list are stored adjacent to each other in * the list root and unlike the elements they do not have other data * attached; also, the pointers in the link structure point to the * start of the element structure, not to the links inside the element. * * head first second last X-|prev | * +------+ +------+ +------+ +------+ + - - + * | next|--->| next|--->| next|-- ... ->| next|--->| next|-X * X-|prev |<---|prev |<---|prev |<- ... --|prev |<---|prev | * + - - + | data | | data | | data | +------+ * | next|-X +------+ +------+ +------+ tail * * The links in an element don't have to be at the start of the * element structure (e.g. to allow a structure to be an element of * more than one list), so we play evil games with the first element's * prev pointer and the last element's next pointer so that we can * treat the links in the list root as if they were part of a normal * list element. Macros with names that contain a double underscore * are internal to this file and not for public consumption. */ /* * Given a struct src_type * this macro adjusts the pointer and * returns a struct dst_type * such that dereferencing dst_field * relative to the result accesses the same memory location as * dereferencing src_field relative to the original pointer. */ #define LIST__MAGIC(pointer, src_type, src_field, dst_type, dst_field) \ ((struct dst_type *)((char *)(pointer) \ + offsetof(struct src_type, src_field) \ - offsetof(struct dst_type, dst_field))) /* * These macros convert a struct roottype * into a struct elemtype * * such that if there were an element structure at that location * (which there isn't) its link pointers would coincide with the list * root's head or tail link pointers respectively, and vice versa. */ #define LIST__HEAD2ELEM(root, roottype, elemtype, link) \ LIST__MAGIC(root, roottype, head, elemtype, link) #define LIST__TAIL2ELEM(root, roottype, elemtype, link) \ LIST__MAGIC(root, roottype, tail, elemtype, link) #define LIST__ELEM2HEAD(elem, roottype, elemtype, link) \ LIST__MAGIC(elem, elemtype, link, roottype, head) #define LIST__ELEM2TAIL(elem, roottype, elemtype, link) \ LIST__MAGIC(elem, elemtype, link, roottype, tail) /* * List root declaration and initialization. */ #define LIST_ROOT(roottype, elemtype) \ struct roottype { \ struct { \ struct elemtype *next, *prev; \ } head, tail; \ } /* * The magic in LIST_INIT() is derived from LIST__HEAD2ELEM() and * LIST__TAIL2ELEM() using (root)->head.prev etc. as a convenient * replacement for the explicitly typed NULL pointer in offsetof(), * so that the user doesn't have to specify the typenames. */ #define LIST_INIT(root, link) do { \ (root)->head.prev = NULL; \ (root)->head.next = (void *)((char *)&(root)->tail - \ (size_t)&(root)->head.prev->link) \ (root)->tail.next = NULL; \ (root)->tail.prev = (void *)((char *)&(root)->head - \ (size_t)&(root)->tail.next->link) \ } while(0) /* * Element link declaration and initialization. */ #define LIST_LINK(elemtype) \ struct { \ struct elemtype *next, *prev; \ } /* * Ensure that elements not on a list are distinct from elements that * are on a list and from the list head and tail. */ #define LIST_LINK_INIT(elem, link) do { \ (elem)->link.next = (elem)->link.prev = NULL; \ } while(0) /* * Accessor macros and predicates. */ #define LIST_FIRST(root) ((root)->head.next) #define LIST_LAST(root) ((root)->tail.prev) #define LIST_NEXT(elem, link) ((elem)->link.next) #define LIST_PREV(elem, link) ((elem)->link.prev) #define LIST_EMPTY(root, link) ((root)->head.next->link.next == NULL) #define LIST_ISHEAD(elem, link) ( (elem)->link.next && !(elem)->link.prev) #define LIST_ISTAIL(elem, link) (!(elem)->link.next && (elem)->link.prev) #define LIST_ISELEM(elem, link) ( (elem)->link.next && (elem)->link.prev) #define LIST_SINGLE(elem, link) (!(elem)->link.next && !(elem)->link.prev) #define LIST_GETROOT(roottype, elem, link) ((struct roottype *)( \ (elem)->link.next \ ? (elem)->link.prev \ ? NULL \ : (char *)&(elem)->link - offsetof(struct roottype, head) \ : (elem)->link.prev \ ? (char *)&(elem)->link - offsetof(struct roottype, tail) \ : NULL )) /* * Basic operations. */ #define LIST_FOREACH(elem, root, link) \ for((elem) = (root)->head.next; \ (elem)->link.next; \ (elem) = (elem)->link.next) #define LIST_REMOVE(elem, link) do { \ (elem)->link.prev->link.next = (elem)->link.next; \ (elem)->link.next->link.prev = (elem)->link.prev; \ (elem)->link.next = (elem)->link.prev = NULL; \ } while(0) #define LIST_INSERT_AFTER(new, elem, link) do { \ (new)->link.next = (elem)->link.next; \ (new)->link.prev = (elem); \ (elem)->link.next->link.prev = (new); \ (elem)->link.next = (new); \ } while(0) #define LIST_INSERT_BEFORE(new, elem, link) do { \ (new)->link.prev = (elem)->link.prev; \ (new)->link.next = (elem); \ (elem)->link.prev->link.next = (new); \ (elem)->link.prev = (new); \ } while(0) /* * Note that LIST_INSERT_HEAD(new, root, link) isn't quite the same as * LIST_INSERT_BEFORE(new, LIST_FIRST(root), link) because the side- * effects of the macro cause the value of LIST_FIRST() to change * partway through LIST_INSERT_BEFORE() causing a cock-up. */ #define LIST_INSERT_HEAD(new, root, link) do { \ (new)->link.prev = (root)->head.next->link.prev; \ (new)->link.next = (root)->head.next; \ (root)->head.next->link.prev = (new); \ (root)->head.next = (new); \ } while(0) #define LIST_INSERT_TAIL(new, root, link) do { \ (new)->link.next = (root)->tail.prev->link.next; \ (new)->link.prev = (root)->tail.prev; \ (root)->tail.prev->link.next = (new); \ (root)->tail.prev = (new); \ } while(0) /* * Some assistance for debugging. */ #define LIST_NEXTOK(elem, link) ((elem)->link.next->link.prev == (elem)) #define LIST_PREVOK(elem, link) ((elem)->link.prev->link.next == (elem)) #define LIST_HEADOK(root, link) (&(root)->head.next->link.prev->link == &(root)->head) #define LIST_TAILOK(root, link) (&(root)->tail.prev->link.next->link == &(root)->tail) #endif /* ifndef LIST_H */