src/include/lib/dllist.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * dllist.h
   4  *              simple doubly linked list primitives
   5  *              the elements of the list are void* so the lists can contain anything
   6  *              Dlelem can only be in one list at a time
   7  *
   8  *
   9  *       Here's a small example of how to use Dllists:
  10  *
  11  *       Dllist *lst;
  12  *       Dlelem *elt;
  13  *       void   *in_stuff;        -- stuff to stick in the list
  14  *       void   *out_stuff
  15  *
  16  *       lst = DLNewList();                                -- make a new dllist
  17  *       DLAddHead(lst, DLNewElem(in_stuff)); -- add a new element to the list
  18  *                                                                                       with in_stuff as the value
  19  *        ...
  20  *       elt = DLGetHead(lst);                     -- retrieve the head element
  21  *       out_stuff = (void*)DLE_VAL(elt);  -- get the stuff out
  22  *       DLRemove(elt);                                    -- removes the element from its list
  23  *       DLFreeElem(elt);                                  -- free the element since we don't
  24  *                                                                                use it anymore
  25  *
  26  *
  27  * It is also possible to use Dllist objects that are embedded in larger
  28  * structures instead of being separately malloc'd.  To do this, use
  29  * DLInitElem() to initialize a Dllist field within a larger object.
  30  * Don't forget to DLRemove() each field from its list (if any) before
  31  * freeing the larger object!
  32  *
  33  *
  34  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  35  * Portions Copyright (c) 1994, Regents of the University of California
  36  *
  37  * $PostgreSQL$
  38  *
  39  *-------------------------------------------------------------------------
  40  */
  41
  42 #ifndef DLLIST_H
  43 #define DLLIST_H
  44
  45 struct Dllist;
  46 struct Dlelem;
  47
  48 typedef struct Dlelem
  49 {
  50         struct Dlelem *dle_next;        /* next element */
  51         struct Dlelem *dle_prev;        /* previous element */
  52         void       *dle_val;            /* value of the element */
  53         struct Dllist *dle_list;        /* what list this element is in */
  54 } Dlelem;
  55
  56 typedef struct Dllist
  57 {
  58         Dlelem     *dll_head;
  59         Dlelem     *dll_tail;
  60 } Dllist;
  61
  62 extern Dllist *DLNewList(void); /* allocate and initialize a list header */
  63 extern void DLInitList(Dllist *list);   /* init a header alloced by caller */
  64 extern void DLFreeList(Dllist *list);   /* free up a list and all the nodes in
  65                                                                                  * it */
  66 extern Dlelem *DLNewElem(void *val);
  67 extern void DLInitElem(Dlelem *e, void *val);
  68 extern void DLFreeElem(Dlelem *e);
  69 extern void DLRemove(Dlelem *e);        /* removes node from list */
  70 extern void DLAddHead(Dllist *list, Dlelem *node);
  71 extern void DLAddTail(Dllist *list, Dlelem *node);
  72 extern Dlelem *DLRemHead(Dllist *list); /* remove and return the head */
  73 extern Dlelem *DLRemTail(Dllist *list);
  74 extern void DLMoveToFront(Dlelem *e);   /* move node to front of its list */
  75
  76 /* These are macros for speed */
  77 #define DLGetHead(list)  ((list)->dll_head)
  78 #define DLGetTail(list)  ((list)->dll_tail)
  79 #define DLGetSucc(elem)  ((elem)->dle_next)
  80 #define DLGetPred(elem)  ((elem)->dle_prev)
  81 #define DLGetListHdr(elem)      ((elem)->dle_list)
  82
  83 #define DLE_VAL(elem)   ((elem)->dle_val)
  84
  85 #endif   /* DLLIST_H */