git.maemo.org Git - xmlrpc-c/blob - lib/util/include/linklist.h

   1 #ifndef LINKLIST_H_INCLUDED
   2 #define LINKLIST_H_INCLUDED
   3
   4 #include "inline.h"
   5
   6 struct list_head {
   7 /*----------------------------------------------------------------------------
   8   This is a header for an element of a doubly linked list, or an anchor
   9   for such a list.
  10
  11   itemP == NULL means it's an anchor; otherwise it's a header.
  12
  13   Initialize a list header with list_init_header().  You don't have to
  14   do anything to terminate a list header.
  15
  16   Initialize an anchor with list_make_emtpy().  You don't have to do anything
  17   to terminate a list header.
  18 -----------------------------------------------------------------------------*/
  19     struct list_head * nextP;
  20         /* For a header, this is the address of the list header for
  21            the next element in the list.  If there is no next element,
  22            it points to the anchor.  If the header is not in a list at
  23            all, it is NULL.
  24
  25            For an anchor, it is the address of the list header of the
  26            first element.  If the list is empty, it points to the
  27            anchor itself.
  28         */
  29     struct list_head * prevP;
  30         /* For a header, this is the address of the list header for
  31            the previous element in the list.  If there is no previous element,
  32            it points to the anchor.  If the header is not in a list at
  33            all, it is NULL.
  34
  35            For an anchor, it is the address of the list header of the
  36            last element.  If the list is empty, it points to the
  37            anchor itself.
  38         */
  39     void * itemP;
  40         /* For a header, this is the address of the list element to which it
  41            belongs.  For an anchor, this is NULL.
  42         */
  43 };
  44
  45 static __inline__ void
  46 list_init_header(struct list_head * const headerP,
  47                  void *             const itemP) {
  48
  49     headerP->prevP = NULL;
  50     headerP->nextP = NULL;
  51     headerP->itemP = itemP;
  52 }
  53
  54
  55
  56 static __inline__ int
  57 list_is_linked(struct list_head * headerP) {
  58     return headerP->prevP != NULL;
  59 }
  60
  61
  62
  63 static __inline__ int
  64 list_is_empty(struct list_head * const anchorP)  {
  65     return anchorP->nextP == anchorP;
  66 }
  67
  68
  69
  70 static __inline__ unsigned int
  71 list_count(struct list_head * const anchorP) {
  72     unsigned int count;
  73
  74     struct list_head * p;
  75
  76     for (p = anchorP->nextP, count = 0;
  77          p != anchorP;
  78          p = p->nextP, ++count);
  79
  80     return count;
  81 }
  82
  83
  84
  85 static __inline__ void
  86 list_make_empty(struct list_head * const anchorP) {
  87     anchorP->prevP = anchorP;
  88     anchorP->nextP = anchorP;
  89     anchorP->itemP = NULL;
  90 }
  91
  92 static __inline__ void
  93 list_insert_after(struct list_head * const beforeHeaderP,
  94                   struct list_head * const newHeaderP) {
  95     newHeaderP->prevP = beforeHeaderP;
  96     newHeaderP->nextP = beforeHeaderP->nextP;
  97
  98     beforeHeaderP->nextP = newHeaderP;
  99     newHeaderP->nextP->prevP = newHeaderP;
 100 }
 101
 102
 103
 104 static __inline__ void
 105 list_add_tail(struct list_head * const anchorP,
 106               struct list_head * const headerP) {
 107     list_insert_after(anchorP->prevP, headerP);
 108 }
 109
 110
 111
 112 static __inline__ void
 113 list_add_head(struct list_head * const anchorP,
 114               struct list_head * const headerP) {
 115     list_insert_after(anchorP, headerP);
 116 }
 117
 118
 119
 120 static __inline__ void
 121 list_remove(struct list_head * const headerP) {
 122     headerP->prevP->nextP = headerP->nextP;
 123     headerP->nextP->prevP = headerP->prevP;
 124     headerP->prevP = NULL;
 125     headerP->nextP = NULL;
 126 }
 127
 128
 129
 130 static __inline__ struct list_head *
 131 list_remove_head(struct list_head * const anchorP) {
 132     struct list_head * retval;
 133
 134     if (list_is_empty(anchorP))
 135         retval = NULL;
 136     else {
 137         retval = anchorP->nextP;
 138         list_remove(retval);
 139     }
 140     return retval;
 141 }
 142
 143
 144
 145 static __inline__ struct list_head *
 146 list_remove_tail(struct list_head * const anchorP) {
 147     struct list_head * retval;
 148
 149     if (list_is_empty(anchorP))
 150         retval = NULL;
 151     else {
 152         retval = anchorP->prevP;
 153         list_remove(retval);
 154     }
 155     return retval;
 156 }
 157
 158
 159
 160 static __inline__ void *
 161 list_foreach(struct list_head * const anchorP,
 162              void * functionP(struct list_head *, void *),
 163              void *             const context) {
 164
 165     struct list_head * p;
 166     struct list_head * nextP;
 167     void * result;
 168
 169     for (p = anchorP->nextP, nextP = p->nextP, result=NULL;
 170          p != anchorP && result == NULL;
 171          p = nextP, nextP = p->nextP)
 172         result = (*functionP)(p, context);
 173
 174     return result;
 175 }
 176
 177
 178
 179 static __inline__ void
 180 list_append(struct list_head * const newAnchorP,
 181             struct list_head * const baseAnchorP) {
 182
 183     if (!list_is_empty(newAnchorP)) {
 184         baseAnchorP->prevP->nextP = newAnchorP->nextP;
 185         newAnchorP->nextP->prevP = baseAnchorP->prevP;
 186         newAnchorP->prevP->nextP = baseAnchorP;
 187         baseAnchorP->prevP = newAnchorP->prevP;
 188     }
 189 }
 190
 191 #endif
 192
 193