/* $Cambridge: hermes/src/2hermes/list.h,v 1.4 2004/02/04 19:06:01 fanf2 Exp $ */ /*! * \file libdotat/list.h * * \brief Doubly-linked split-ring lists. * * This header 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). * * \note Unlike normal linked list terminology, the head isn't the * first element of the list, it is a dummy entry before the first * element; similarly the tail is a dummy entry after the last element * of the list. * * 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. * * \code * * root * (head) first second last X-|prev | * +------+ +------+ +------+ +------+ + - - + * | next|--->| next|--->| next|-- ... ->| next|--->| next|-X * X-|prev |<---|prev |<---|prev |<- ... --|prev |<---|prev | * + - - + | data | | data | | data | +------+ * | next|-X +------+ +------+ +------+ (tail) * root * \endcode * * 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, i.e. we guarantee that first->prev->next == first and * last->next->prev == last. However, first->prev != root (and anyway * the types are incompatible) so instead you must use NAME_getroot(). * * Each list that uses this structure must be instantiated by invoking * one of the list_types() or list_typedefs() macros, followed by the * list_functions() macro. The former define the list link and root * structures and types respectively, and the latter defines a number * of static inline functions that implement the various list * operations. Functions with a double underscore in the name are * internal to the implementation and shouldn't be called by the user. * * $Copyright: (C) 2001-2003 Tony Finch $ * * $dotat: progetc/libdotat/list.h,v 1.55 2003/11/06 13:44:48 fanf2 Exp $ */ #ifndef LIST_H #define LIST_H /*! * \brief Pointer magic helper macro for internal use. * * \invariant * \code * dst = list__magic(src, t_src, src_field, t_dst, dst_field); * assert(&src->src_field == &dst->dst_field); * \endcode * * \hideinitializer */ #define list__magic(ptr, t_src, src_field, t_dst, dst_field) \ ((t_dst *)( (char *)(ptr) \ + offsetof(t_src, src_field) \ - offsetof(t_dst, dst_field) )) /*! * \brief Define a list's root and link structures. * * \param root_tag The \c struct tag of the list's root. * \param elem_tag The \c struct tag of the list's elements. * \param link_tag The \c struct tag of the list's links. * * \hideinitializer */ #define list_types(root_tag, elem_tag, link_tag) \ \ struct link_tag { struct elem_tag *next, *prev; }; \ struct root_tag { struct link_tag head, tail; }; \ \ struct list__hack /*! * \brief Define a list's operations. * * \param NAME The function name prefix of the list * \param t_root The type of the list's root. * \param t_elem The type of the list's elements. * \param link The name of the link structure in each element. * * \hideinitializer */ #define list_functions(NAME, t_root, t_elem, link) \ \ /* internal pointer magic utilities */ \ static inline t_elem *NAME##__head2elem(t_root *root) { \ return(list__magic(root, t_root, head, t_elem, link)); \ } \ static inline t_elem *NAME##__tail2elem(t_root *root) { \ return(list__magic(root, t_root, tail, t_elem, link)); \ } \ static inline t_root *NAME##__elem2head(t_elem *elem) { \ return(list__magic(elem, t_elem, link, t_root, head)); \ } \ static inline t_root *NAME##__elem2tail(t_elem *elem) { \ return(list__magic(elem, t_elem, link, t_root, tail)); \ } \ \ /* initializers */ \ static inline void NAME##_init(t_root *root) { \ root->head.next = NAME##__tail2elem(root); \ root->head.prev = root->tail.next = NULL; \ root->tail.prev = NAME##__head2elem(root); \ } \ static inline void NAME##_init_link(t_elem *elem) { \ elem->link.next = elem->link.prev = NULL; \ } \ \ /* accessor functions */ \ static inline t_elem *NAME##_first(t_root *root) { \ return(root->head.next); \ } \ static inline t_elem *NAME##_last(t_root *root) { \ return(root->tail.prev); \ } \ static inline t_elem *NAME##_next(t_elem *elem) { \ return(elem->link.next); \ } \ static inline t_elem *NAME##_prev(t_elem *elem) { \ return(elem->link.prev); \ } \ \ /* predicates */ \ static inline bool NAME##_empty(t_root *root) { \ return(root->head.next->link.next == NULL); \ } \ static inline bool NAME##_ytpme(t_root *root) { \ return(root->tail.prev->link.prev == NULL); \ } \ static inline bool NAME##_iselem(t_elem *elem) { \ return(elem->link.next != NULL && elem->link.prev != NULL); \ } \ static inline bool NAME##_ishead(t_elem *elem) { \ return(elem->link.next != NULL && elem->link.prev == NULL); \ } \ static inline bool NAME##_istail(t_elem *elem) { \ return(elem->link.next == NULL && elem->link.prev != NULL); \ } \ static inline bool NAME##_isunlinked(t_elem *elem) { \ return(elem->link.next == NULL && elem->link.prev == NULL); \ } \ /* faster but less safe predicates for looping */ \ static inline bool NAME##_athead(t_elem *elem) { \ return(elem->link.prev == NULL); \ } \ static inline bool NAME##_attail(t_elem *elem) { \ return(elem->link.next == NULL); \ } \ /* slightly more complicated predicates */ \ static inline bool NAME##_isfirst(t_elem *elem) { \ return(NAME##_athead(NAME##_prev(elem))); \ } \ static inline bool NAME##_islast(t_elem *elem) { \ return(NAME##_attail(NAME##_next(elem))); \ } \ \ /* internal list manipulation */ \ static inline void NAME##__splice_before \ (t_elem *elem, t_elem *new0, t_elem *newN) { \ new0->link.prev = elem->link.prev; \ newN->link.next = elem; \ elem->link.prev->link.next = new0; \ elem->link.prev = newN; \ } \ static inline void NAME##__splice_after \ (t_elem *elem, t_elem *new0, t_elem *newN) { \ newN->link.next = elem->link.next; \ new0->link.prev = elem; \ elem->link.next->link.prev = newN; \ elem->link.next = new0; \ } \ static inline void NAME##__unsplice(t_elem *old0, t_elem *oldN) { \ old0->link.prev->link.next = oldN->link.next; \ oldN->link.next->link.prev = old0->link.prev; \ } \ \ /* single element manipulation */ \ static inline void NAME##_insert_before(t_elem *elem, t_elem *new) { \ NAME##__splice_before(elem, new, new); \ } \ static inline void NAME##_insert_after(t_elem *elem, t_elem *new) { \ NAME##__splice_after(elem, new, new); \ } \ static inline void NAME##_insert_first(t_root *root, t_elem *new) { \ NAME##_insert_before(root->head.next, new); \ /* or NAME##_insert_after(NAME##__head2elem(root), new); */ \ } \ static inline void NAME##_insert_last(t_root *root, t_elem *new) { \ NAME##_insert_after(root->tail.prev, new); \ /* or NAME##_insert_before(NAME##__tail2elem(root), new); */ \ } \ static inline void NAME##_remove(t_elem *elem) { \ NAME##__unsplice(elem, elem); \ NAME##_init_link(elem); \ } \ static inline t_elem *NAME##_remove_first(t_root *root) { \ t_elem *elem = NAME##_first(root); \ if(NAME##_attail(elem)) return(NULL); \ NAME##_remove(elem); \ return(elem); \ } \ static inline t_elem *NAME##_remove_last(t_root *root) { \ t_elem *elem = NAME##_last(root); \ if(NAME##_athead(elem)) return(NULL); \ NAME##_remove(elem); \ return(elem); \ } \ static inline void NAME##_remove_next(t_elem *elem) { \ elem = NAME##_next(elem); \ if(!NAME##_attail(elem)) NAME##_remove(elem); \ } \ static inline void NAME##_remove_prev(t_elem *elem) { \ elem = NAME##_prev(elem); \ if(!NAME##_athead(elem)) NAME##_remove(elem); \ } \ \ /* concatenation etc. */ \ static inline void NAME##_concat(t_root *dst, t_root *src) { \ t_elem *elem0 = NAME##_first(src); \ t_elem *elemN = NAME##_last(src); \ if(NAME##_attail(elem0)) return; \ NAME##__unsplice(elem0, elemN); \ NAME##__splice_after(dst->tail.prev, elem0, elemN); \ } \ \ /* safe magic for the user */ \ static inline t_root *NAME##_getroot(t_elem *elem) { \ if(NAME##_ishead(elem)) return(NAME##__elem2head(elem)); \ if(NAME##_istail(elem)) return(NAME##__elem2tail(elem)); \ return(NULL); \ } \ \ /* looping operations */ \ static t_root *NAME##_findroot(t_elem *elem) { \ while(!NAME##_attail(elem)) \ elem = NAME##_next(elem); \ return(NAME##__elem2tail(elem)); \ } \ static t_root *NAME##_toordnif(t_elem *elem) { \ while(!NAME##_athead(elem)) \ elem = NAME##_prev(elem); \ return(NAME##__elem2head(elem)); \ } \ static int NAME##_length(t_root *root) { \ t_elem *elem; int i; \ for(elem = NAME##_first(root), i = 0; \ !NAME##_attail(elem); \ elem = NAME##_next(elem), i++); \ return(i); \ } \ static t_elem *NAME##_find(t_elem *elem, const void *arg, \ int (*cmp)(t_elem *elem, const void *arg)) { \ while(!NAME##_attail(elem)) \ if(cmp(elem, arg) == 0) \ return(elem); \ else \ elem = NAME##_next(elem); \ return(NULL); \ } \ static t_elem *NAME##_dnif(t_elem *elem, const void *arg, \ int (*cmp)(t_elem *elem, const void *arg)) { \ while(!NAME##_athead(elem)) \ if(cmp(elem, arg) == 0) \ return(elem); \ else \ elem = NAME##_prev(elem); \ return(NULL); \ } \ static void NAME##_qsort_r(t_root *root, void *arg, \ int (*cmp)(void *, t_elem *, t_elem *)) { \ t_elem *pivot, *elem; \ t_root one, two, three; \ int c; \ \ NAME##_init(&one); \ NAME##_init(&two); \ NAME##_init(&three); \ \ pivot = NAME##_remove_first(root); \ if(pivot == NULL) return; \ NAME##_insert_last(&two, pivot); \ \ while(elem = NAME##_remove_first(root), elem != NULL) { \ c = cmp(arg, pivot, elem); \ if(c > 0) \ NAME##_insert_last(&one, elem); \ else if(c == 0) \ NAME##_insert_last(&two, elem); \ else \ NAME##_insert_last(&three, elem); \ } \ NAME##_qsort_r(&one, arg, cmp); \ NAME##_qsort_r(&three, arg, cmp); \ NAME##_concat(root, &one); \ NAME##_concat(root, &two); \ NAME##_concat(root, &three); \ } \ static int NAME##_qsort_cmp(void *a, t_elem *e1, t_elem *e2) { \ /* function pointers can't be portably cast to void pointers */ \ int (**arg)(t_elem *, t_elem *) = a; \ int (*cmp)(t_elem *, t_elem *) = *arg; \ return(cmp(e1, e2)); \ } \ static inline void NAME##_qsort \ (t_root *root, int (*cmp)(t_elem *, t_elem *)) { \ NAME##_qsort_r(root, &cmp, NAME##_qsort_cmp); \ } \ \ struct list__hack #ifdef FOR_DOCUMENTATION_ONLY void NAME_init(t_root *root); /*!< * \brief Initialize a list's root. * \param root Pointer to the list's root. */ void NAME_init_link(t_elem *elem); /*!< * \brief Initialize an element's links. * \param elem Pointer to the element. */ t_elem *NAME_first(t_root *root); /*!< * \brief Get the first element of a list. * \param root Pointer to the list's root. * \return A pointer to the first element. */ t_elem *NAME_last(t_root *root); /*!< * \brief Get the last element of a list. * \param root Pointer to the list's root. * \return A pointer to the last element. */ t_elem *NAME_next(t_elem *elem); /*!< * \brief Get the next element of a list. * \pre not NAME_istail(elem) * \param elem Pointer to an element. * \return A pointer to the next element. */ t_elem *NAME_prev(t_elem *elem); /*!< * \brief Get the previous element of a list. * \pre not NAME_ishead(elem) * \param elem Pointer to an element. * \return A pointer to the previous element. */ bool NAME_empty(t_root *root); /*!< * \brief Find out if a list is empty. * \param root Pointer to the list's root. * \return Non-zero if true; zero if false. */ bool NAME_iselem(t_elem *elem); /*!< * \brief Find out if an element is part of a list. * \param elem Pointer to an element. * \return Non-zero if true; zero if false. */ bool NAME_ishead(t_elem *elem); /*!< * \brief Find out if an element is the head of a list. * \param elem Pointer to an element. * \return Non-zero if true; zero if false. */ bool NAME_istail(t_elem *elem); /*!< * \brief Find out if an element is the tail of a list. * \param elem Pointer to an element. * \return Non-zero if true; zero if false. */ bool NAME_isunlinked(t_elem *elem); /*!< * \brief Find out if an element is not part of a list. * \param elem Pointer to an element. * \return Non-zero if true; zero if false. */ bool NAME_athead(t_elem *elem); /*!< * \brief Find out if an element is the head of a list. * Fast version for use in loops. * \pre not NAME_isunlinked(elem) * \param elem Pointer to an element. * \return Non-zero if true; zero if false. */ bool NAME_attail(t_elem *elem); /*!< * \brief Find out if an element is the tail of a list. * Fast version for use in loops. * \pre not NAME_isunlinked(elem) * \param elem Pointer to an element. * \return Non-zero if true; zero if false. */ bool NAME_isfirst(t_elem *elem); /*!< * \brief Find out if an element is the first in a list. * \pre not NAME_ishead(elem) * \param elem Pointer to an element. * \return Non-zero if true; zero if false. */ bool NAME_islast(t_elem *elem); /*!< * \brief Find out if an element is the last in a list. * \pre not NAME_istail(elem) * \param elem Pointer to an element. * \return Non-zero if true; zero if false. */ void NAME_insert_before(t_elem *elem, t_elem *new); /*!< * \brief Insert an element before another. * \pre not NAME_ishead(elem) * \pre NAME_isunlinked(new) * \param elem Pointer to an element in a list. * \param new Pointer to the element to add. */ void NAME_insert_after(t_elem *elem, t_elem *new); /*!< * \brief Insert an element after another. * \pre not NAME_istail(elem) * \pre NAME_isunlinked(new) * \param elem Pointer to an element in a list. * \param new Pointer to the element to add. */ void NAME_insert_first(t_root *root, t_elem *new); /*!< * \brief Insert an element at the start of a list. * \pre NAME_isunlinked(new) * \param root Pointer to the list's root. * \param new Pointer to the element to add. */ void NAME_insert_last(t_root *root, t_elem *new); /*!< * \brief Insert an element at the end of a list. * \pre NAME_isunlinked(new) * \param root Pointer to the list's root. * \param new Pointer to the element to add. */ void NAME_remove(t_elem *elem); /*!< * \brief Remove an element from a list. * \pre NAME_iselem(elem) * \param elem Pointer to the element. */ t_elem *NAME_remove_first(t_root *root); /*!< * \brief Remove the first element from a list. * \param root Pointer to the list's root. * \return The element that was removed, or NULL if the list was empty. */ t_elem *NAME_remove_last(t_root *root); /*!< * \brief Remove the last element from a list. * \param root Pointer to the list's root. * \return The element that was removed. * \return The element that was removed, or NULL if the list was empty. */ void NAME_remove_next(t_elem *elem); /*!< * \brief Remove the next element from a list. * \pre not NAME_istail(elem) * \param elem Pointer to the element. */ void NAME_remove_prev(t_elem *elem); /*!< * \brief Remove the previous element from a list. * \pre not NAME_ishead(elem) * \param elem Pointer to the element. */ void NAME_concat(t_root *dst, t_root *src); /*!< * \brief Insert all the elements of one list at the end of another. * \post The source list is left empty. * \param dst Pointer to the destination list's root. * \param src Pointer to the source list's root. */ t_root *NAME_getroot(t_elem *elem); /*!< * \brief Turn an element pointer into a root pointer. * \param elem Pointer to the element. * \return A pointer to the root if the element is * the head or the tail of the list, otherwise NULL. */ t_root *NAME_findroot(t_elem *elem); /*!< * \brief Search for a list's root. * \param elem Pointer to an element. * \return A pointer to the list's root. */ int NAME_length(t_root *root); /*!< * \brief Count the number of elements in a list. * \param root Pointer to the list's root. * \return The number of elements. */ t_elem *NAME_find(t_elem *elem, void *arg, int (*cmp)(t_elem *, void *)); /*!< * \brief Find the first element in a list that matches a condition. * \param root Pointer to the element to start searching from. * \param arg Extra data passed down to comparison function. * \param cmp Element comparison function similar to ANSI C qsort() and bsearch(). * \return The matching element, or NULL if none found. */ void NAME_qsort_r(t_root *root, void *arg, int (*cmp)(void *, t_elem *, t_elem *)); /*!< * \brief Sort a list in place (extended version). * This is a stable sort. * \param root Pointer to the list's root. * \param arg Extra data passed down to comparison function. * \param cmp Element comparison function similar to ANSI C qsort() and bsearch(). */ void NAME_qsort(t_root *root, int (*cmp)(t_elem *, t_elem *)); /*!< * \brief Sort a list in place. * \param root Pointer to the list's root. * \param cmp Element comparison function same as ANSI C qsort() and bsearch(). */ #endif /* FOR_DOCUMENTATION_ONLY */ #endif /* ! LIST_H */