osi/src/list.c

   1 #include <assert.h>
   2
   3 #include "list.h"
   4 #include "osi.h"
   5
   6 typedef struct list_node_t {
   7   struct list_node_t *next;
   8   void *data;
   9 } list_node_t;
  10
  11 typedef struct list_t {
  12   list_node_t *head;
  13   list_node_t *tail;
  14   size_t length;
  15   list_free_cb free_cb;
  16 } list_t;
  17
  18 static list_node_t *list_free_node_(list_t *list, list_node_t *node);
  19
  20 // Returns a new, empty list. Returns NULL if not enough memory could be allocated
  21 // for the list structure. The returned list must be freed with |list_free|. The
  22 // |callback| specifies a function to be called whenever a list element is removed
  23 // from the list. It can be used to release resources held by the list element, e.g.
  24 // memory or file descriptor. |callback| may be NULL if no cleanup is necessary on
  25 // element removal.
  26 list_t *list_new(list_free_cb callback) {
  27   list_t *list = (list_t *)calloc(sizeof(list_t), 1);
  28   if (list)
  29     list->free_cb = callback;
  30   return list;
  31 }
  32
  33 // Frees the list. This function accepts NULL as an argument, in which case it
  34 // behaves like a no-op.
  35 void list_free(list_t *list) {
  36   if (list != NULL)
  37     list_clear(list);
  38
  39   free(list);
  40 }
  41
  42 // Returns true if the list is empty (has no elements), false otherwise.
  43 // Note that a NULL list is not the same as an empty list. This function
  44 // does not accept a NULL list.
  45 bool list_is_empty(const list_t *list) {
  46   assert(list != NULL);
  47   return (list->length == 0);
  48 }
  49
  50 bool list_contains(const list_t *list, const void *data) {
  51   assert(list != NULL);
  52   assert(data != NULL);
  53
  54   for (const list_node_t *node = list_begin(list); node != list_end(list); node = list_next(node)) {
  55     if (list_node(node) == data)
  56       return true;
  57   }
  58
  59   return false;
  60 }
  61
  62 // Returns the length of the list. This function does not accept a NULL list.
  63 size_t list_length(const list_t *list) {
  64   assert(list != NULL);
  65   return list->length;
  66 }
  67
  68 // Returns the first element in the list without removing it. |list| may not
  69 // be NULL or empty.
  70 void *list_front(const list_t *list) {
  71   assert(list != NULL);
  72   assert(!list_is_empty(list));
  73
  74   return list->head->data;
  75 }
  76
  77 // Returns the last element in the list without removing it. |list| may not
  78 // be NULL or empty.
  79 void *list_back(const list_t *list) {
  80   assert(list != NULL);
  81   assert(!list_is_empty(list));
  82
  83   return list->tail->data;
  84 }
  85
  86 bool list_insert_after(list_t *list, list_node_t *prev_node, void *data) {
  87   assert(list != NULL);
  88   assert(node != NULL);
  89   assert(data != NULL);
  90
  91   list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t));
  92   if (!node)
  93     return false;
  94
  95   node->next = prev_node->next;
  96   node->data = data;
  97   prev_node->next = node;
  98   if (list->tail == prev_node)
  99     list->tail = node;
 100   ++list->length;
 101   return true;
 102 }
 103
 104 // Inserts |data| at the beginning of |list|. Neither |data| nor |list| may be NULL.
 105 // This function does not make a copy of |data| so the pointer must remain valid
 106 // at least until the element is removed from the list or the list is freed.
 107 // Returns true if |data| could be inserted, false otherwise (e.g. out of memory).
 108 bool list_prepend(list_t *list, void *data) {
 109   assert(list != NULL);
 110   assert(data != NULL);
 111
 112   list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t));
 113   if (!node)
 114     return false;
 115   node->next = list->head;
 116   node->data = data;
 117   list->head = node;
 118   if (list->tail == NULL)
 119     list->tail = list->head;
 120   ++list->length;
 121   return true;
 122 }
 123
 124 // Inserts |data| at the end of |list|. Neither |data| nor |list| may be NULL.
 125 // This function does not make a copy of |data| so the pointer must remain valid
 126 // at least until the element is removed from the list or the list is freed.
 127 // Returns true if |data| could be inserted, false otherwise (e.g. out of memory).
 128 bool list_append(list_t *list, void *data) {
 129   assert(list != NULL);
 130   assert(data != NULL);
 131
 132   list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t));
 133   if (!node)
 134     return false;
 135   node->next = NULL;
 136   node->data = data;
 137   if (list->tail == NULL) {
 138     list->head = node;
 139     list->tail = node;
 140   } else {
 141     list->tail->next = node;
 142     list->tail = node;
 143   }
 144   ++list->length;
 145   return true;
 146 }
 147
 148 // Removes |data| from the list. Neither |list| nor |data| may be NULL. If |data|
 149 // is inserted multiple times in the list, this function will only remove the first
 150 // instance. If a free function was specified in |list_new|, it will be called back
 151 // with |data|. This function returns true if |data| was found in the list and removed,
 152 // false otherwise.
 153 bool list_remove(list_t *list, void *data) {
 154   assert(list != NULL);
 155   assert(data != NULL);
 156
 157   if (list_is_empty(list))
 158     return false;
 159
 160   if (list->head->data == data) {
 161     list_node_t *next = list_free_node_(list, list->head);
 162     if (list->tail == list->head)
 163       list->tail = next;
 164     list->head = next;
 165     return true;
 166   }
 167
 168   for (list_node_t *prev = list->head, *node = list->head->next; node; prev = node, node = node->next)
 169     if (node->data == data) {
 170       prev->next = list_free_node_(list, node);
 171       if (list->tail == node)
 172         list->tail = prev;
 173       return true;
 174     }
 175
 176   return false;
 177 }
 178
 179 // Removes all elements in the list. Calling this function will return the list to the
 180 // same state it was in after |list_new|. |list| may not be NULL.
 181 void list_clear(list_t *list) {
 182   assert(list != NULL);
 183   for (list_node_t *node = list->head; node; )
 184     node = list_free_node_(list, node);
 185   list->head = NULL;
 186   list->tail = NULL;
 187   list->length = 0;
 188 }
 189
 190 // Iterates through the entire |list| and calls |callback| for each data element.
 191 // If the list is empty, |callback| will never be called. It is safe to mutate the
 192 // list inside the callback. If an element is added before the node being visited,
 193 // there will be no callback for the newly-inserted node. Neither |list| nor
 194 // |callback| may be NULL.
 195 void list_foreach(const list_t *list, list_iter_cb callback) {
 196   assert(list != NULL);
 197   assert(callback != NULL);
 198
 199   for (list_node_t *node = list->head; node; ) {
 200     list_node_t *next = node->next;
 201     callback(node->data);
 202     node = next;
 203   }
 204 }
 205
 206 // Returns an iterator to the first element in |list|. |list| may not be NULL.
 207 // The returned iterator is valid as long as it does not equal the value returned
 208 // by |list_end|.
 209 list_node_t *list_begin(const list_t *list) {
 210   assert(list != NULL);
 211   return list->head;
 212 }
 213
 214 // Returns an iterator that points past the end of the list. In other words,
 215 // this function returns the value of an invalid iterator for the given list.
 216 // When an iterator has the same value as what's returned by this function, you
 217 // may no longer call |list_next| with the iterator. |list| may not be NULL.
 218 list_node_t *list_end(UNUSED_ATTR const list_t *list) {
 219   assert(list != NULL);
 220   return NULL;
 221 }
 222
 223 // Given a valid iterator |node|, this function returns the next value for the
 224 // iterator. If the returned value equals the value returned by |list_end|, the
 225 // iterator has reached the end of the list and may no longer be used for any
 226 // purpose.
 227 list_node_t *list_next(const list_node_t *node) {
 228   assert(node != NULL);
 229   return node->next;
 230 }
 231
 232 // Returns the value stored at the location pointed to by the iterator |node|.
 233 // |node| must not equal the value returned by |list_end|.
 234 void *list_node(const list_node_t *node) {
 235   assert(node != NULL);
 236   return node->data;
 237 }
 238
 239 static list_node_t *list_free_node_(list_t *list, list_node_t *node) {
 240   assert(list != NULL);
 241   assert(node != NULL);
 242
 243   list_node_t *next = node->next;
 244
 245   if (list->free_cb)
 246     list->free_cb(node->data);
 247   free(node);
 248   --list->length;
 249
 250   return next;
 251 }