dlist.h

   1 #ifndef LIBNAGIOS_dlist_h__
   2 #define LIBNAGIOS_dlist_h__
   3
   4 #include <errno.h>
   5
   6 /**
   7  * @file  dlist.h
   8  * @brief Doubly linked list (with container) API for libnagios
   9  *
  10  * This is a pretty basic doubly-linked list API. Note that we
  11  * have no separate list type, but deal only in entries. To get
  12  * a subset of a list, you can start iterating over it from
  13  * anywhere in the middle.
  14  *
  15  * To append entries last in the list, retain a pointer to the
  16  * head of it and keep issuing "dlist_append()" with the same
  17  * variable, like so:
  18 @code
  19 void *data;
  20 struct dlist_entry *head, *entry;
  21
  22 head = entry = dlist_create_entry(some_data);
  23 while ((data = get_more_data(random_resource))) {
  24         entry = dlist_append(entry, data);
  25 }
  26
  27 dlist_foreach(head, entry) {
  28         do_stuff(entry->data);
  29 }
  30 @endcode
  31  *
  32  * To insert entries first in the list, retain a pointer to the
  33  * tail of it and keep issuing "dlist_insert()" with the same
  34  * variable, like so:
  35 @code
  36 void *data;
  37 struct dlist_entry *tail, *entry;
  38
  39 tail = entry = dlist_create_entry(some_data);
  40 while ((data = get_more_data(random_resource))) {
  41         entry = dlist_append(entry, data);
  42 }
  43
  44 dlist_foreach_reverse(tail, entry) {
  45         do_stuff(entry->data);
  46 }
  47 @endcode
  48  *
  49  * Note that you can also create circular lists by appending the head
  50  * to the tail of the list. In that case, dlist_foreach*() macros
  51  * will require a break statement in order to not loop forever, and
  52  * dlist_destroy() will not work properly.
  53  *
  54  * @{
  55  */
  56
  57 #define DLIST_OK        0
  58 #define DLIST_EDUPE     1
  59 #define DLIST_ENOMEM    -ENOMEM
  60 #define DLIST_ENOMEDIUM -ENOMEDIUM
  61
  62 /** dlist data entry */
  63 struct dlist_entry {
  64         void *data;             /**< The data for this entry */
  65         struct dlist_entry *dlist_next;  /**< Next entry in the list */
  66         struct dlist_entry *dlist_prev;  /**< Previous entry in the list */
  67 };
  68 typedef struct dlist_entry dlist;
  69
  70 /**
  71  * Traverse a dlist forwards from entry__.
  72  * Use like so:
  73 @code
  74 dlist_entry *list, *cur;
  75
  76 dlist_foreach(list, cur) {
  77         data_type_in_list *data = cur->data;
  78         do_stuff(data);
  79         // calling dlist_remove(cur, (flags)); is NOT legal
  80 }
  81 @endcode
  82  *
  83  * @param entry__ dlist_entry: The entry to traverse from
  84  * @param it1__ dlist_emtry: The first iterator (may be same as entry__)
  85  */
  86 #define dlist_foreach(entry__, it1__) \
  87         for (it1__ = entry__; it1__; it1__ = it1__->dlist_next)
  88
  89
  90 /**
  91  * Traverse a dlist backwards from entry__
  92  * Use like so:
  93 @code
  94 dlist_entry *list, *cur;
  95
  96 dlist_foreach_reverse(list, cur) {
  97         data_type_in_list *data = cur->data;
  98         do_stuff(data);
  99         // calling dlist_remove(cur, (flags)); is NOT legal
 100 }
 101 @endcode
 102  *
 103  * @param entry__ dlist_entry: The entry to traverse from
 104  * @param it1__ dlist_emtry: The first iterator (may be same as entry__)
 105  */
 106 #define dlist_foreach_reverse(entry__, it1__) \
 107         for (it1__ = entry__; it1__; it1__ = it1__->dlist_prev)
 108
 109
 110 /**
 111  * Safely traverse a list forwards from entry__.
 112  * Use like so:
 113 @code
 114 dlist_entry *list, *cur, *next;
 115 entry = do_stuff_that_creates_the_list();
 116
 117 dlist_foreach_safe(list, cur, next) {
 118         data_type_in_list *data = cur->data;
 119         do_stuff(data);
 120         free(data);
 121         dlist_destroy_entry(cur, DLIST_FREEDATA); // this is safe
 122 }
 123 @endcode
 124  *
 125  * @param entry__ dlist_entry: The entry to traverse from
 126  * @param it1__ dlist_emtry: The first iterator (may be same as entry__)
 127  * @param it2__ dlist_entry: The second iterator
 128  */
 129 #define dlist_foreach_safe(entry__, it1__, it2__) \
 130         for (it1__ = entry__, it2__ = it1__ ? it1__->dlist_next : NULL; \
 131                  it1__; \
 132                  it1__ = it2__, it2__ = it1__ ? it1__->dlist_next : NULL)
 133
 134
 135 /**
 136  * Safely traverse a list backwards from entry__.
 137  * Use like so:
 138 @code
 139 dlist_entry *list, *cur, *next;
 140 list = do_stuff_that_creates_the_list();
 141
 142 dlist_foreach_safe(list, cur, next) {
 143         data_type_in_list *data = cur->data;
 144         do_stuff(data);
 145         free(data);
 146         dlist_destroy_entry(cur, DLIST_FREEDATA); // this is safe
 147 }
 148 @endcode
 149  *
 150  * @param entry__ dlist_entry: The entry to traverse from
 151  * @param it1__ dlist_emtry: The first iterator (may be same as entry__)
 152  * @param it2__ dlist_entry: The second iterator
 153  */
 154 #define dlist_foreach_safe_reverse(entry__, it1__, it2__) \
 155         for (it1__ = entry__, it2__ = it1__ ? it1__->dlist_prev : NULL; \
 156                  it1__; \
 157                  it1__ = it2__, it2__ = it1__ ? it1__->dlist_prev : NULL)
 158
 159
 160 /**
 161  * Create a new list (entry)
 162  *
 163  * @param data Pointer to the data to store in the list entry
 164  * @return An allocated dlist_entry, containing 'data'
 165  */
 166 struct dlist_entry *dlist_create(void *data);
 167
 168 /**
 169  * Insert an item before **list
 170  * If *list is NULL, we'll create a new list.
 171  *
 172  * @param list The entry the new entry will precede
 173  * @param data Pointer to the data to store in the list entry
 174  * @return An allocated dlist_entry, containing 'data'
 175  */
 176 struct dlist_entry *dlist_insert(struct dlist_entry *list, void *data);
 177
 178 /**
 179  * Append an item directly after *list
 180  *
 181  * @note This function doesn't append to the *very* end of the list,
 182  * but only after the current entry pointed to by *list.
 183  * @param list The entry the new entry will follow
 184  * @param data Pointer to the data to store in the list entry
 185  * @return An allocated dlist_entry, containing 'data'
 186  */
 187 struct dlist_entry *dlist_append(struct dlist_entry *list, void *data);
 188
 189 /**
 190  * Remove an entry from the dlist (free()'ing the entry) and return
 191  * its data.
 192  * @param[ref] head The head of the list to operate on
 193  * @param[in] entry Entry to remove
 194  */
 195 void *dlist_remove(struct dlist_entry **head, struct dlist_entry *entry);
 196
 197 /**
 198  * Locate an item preceding or following 'entry' in the list
 199  * @note This function does a linear scan. Use it sparingly if you're
 200  * interested in performance.
 201  *
 202  * @param entry Entry to start searching from
 203  * @param data Data to look for
 204  * @param cmp Comparison function (memcmp() will do a nice job)
 205  * @param size Size of the data we're looking for
 206  * @return Located dlist_entry on success; NULL on errors.
 207  */
 208 struct dlist_entry *dlist_find(struct dlist_entry *entry, void *data, int (*cmp)(void *, void *, size_t), size_t size);
 209
 210 /**
 211  * Insert a unique entry into the dlist
 212  * @note Using this function is almost always an error, since it causes a
 213  * linear scan for each call.
 214  *
 215  * @param list The entry the new entry will precede
 216  * @param data Pointer to the data to store in the list entry
 217  * @param cmp The comparison function (memcmp() will do a nice job)
 218  * @param size The size of the data we're looking for
 219  * @return DLIST_OK on success; < 0 on errors.
 220  */
 221 struct dlist_entry *dlist_insert_unique(struct dlist_entry *list, void *data, int (*cmp)(void *, void *, size_t), size_t size);
 222
 223 /**
 224  * Append a unique entry after the entry pointed to by *list
 225  *
 226  * @note Using this function is almost always an error, since it causes a
 227  * linear scan of ALL elements in the list for each call.
 228  * @param list The entry the new entry will precede
 229  * @param data Pointer to the data to store in the list entry
 230  * @param cmp The comparison function (memcmp() will do a nice job)
 231  * @param size The size of the data we're looking for
 232  * @return DLIST_OK on success; < 0 on errors.
 233  */
 234 struct dlist_entry *dlist_append_unique(struct dlist_entry *list, void *data, int (*cmp)(void *, void *, size_t), size_t size);
 235
 236 /**
 237  * Destroy and remove a single dlist entry
 238  * @note You need to maintain a pointer to elsewhere in the list in
 239  * order to preserve it.
 240  * @note Don't use this to destroy lists while looping over them.
 241  *
 242  * @param[ref] head The head of the list we're operating on
 243  * @param entry The entry to remove
 244  * @param destructor Destructor to call with entry data (free() will do)
 245  */
 246 void dlist_destroy_entry(struct dlist_entry **head, struct dlist_entry *entry, void (*destructor)(void *));
 247
 248 /**
 249  * Destroy the list that *list is a member of
 250  * @note This also sets *list to NULL
 251  *
 252  * @param list The list to destroy
 253  * @param destructor Destructor to call with entry data (free() will do)
 254  */
 255 void dlist_destroy_list(struct dlist_entry **list, void (*destructor)(void *));
 256
 257 #endif /* DLIST_H */
 258 /** @} */