src/util/container_slist.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2009 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 2, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file util/container_slist.c
  23  * @brief Implementation of a singly-linked list
  24  * @author Nils Durner
  25  */
  26
  27 #include "platform.h"
  28 #include "gnunet_container_lib.h"
  29
  30 /**
  31  * Element in our linked list.
  32  */
  33 struct GNUNET_CONTAINER_SList_Elem
  34 {
  35   /**
  36    * This is a linked list.
  37    */
  38   struct GNUNET_CONTAINER_SList_Elem *next;
  39
  40   /**
  41    * Application data stored at this element.
  42    */
  43   void *elem;
  44
  45   /**
  46    * Number of bytes stored in elem.
  47    */
  48   size_t len;
  49
  50   /**
  51    * Disposition of the element.
  52    */
  53   enum GNUNET_CONTAINER_SListDisposition disp;
  54 };
  55
  56
  57 /**
  58  * Handle to a singly linked list
  59  */
  60 struct GNUNET_CONTAINER_SList
  61 {
  62   /**
  63    * Head of the linked list.
  64    */
  65   struct GNUNET_CONTAINER_SList_Elem *head;
  66
  67   /**
  68    * Number of elements in the list.
  69    */
  70   unsigned int length;
  71 };
  72
  73
  74 /**
  75  * Handle to a singly linked list iterator
  76  */
  77 struct GNUNET_CONTAINER_SList_Iterator
  78 {
  79   /**
  80    * Linked list that we are iterating over.
  81    */
  82   struct GNUNET_CONTAINER_SList *list;
  83
  84   /**
  85    * Last element accessed.
  86    */
  87   struct GNUNET_CONTAINER_SList_Elem *last;
  88
  89   /**
  90    * Current list element.
  91    */
  92   struct GNUNET_CONTAINER_SList_Elem *elem;
  93 };
  94
  95
  96 /**
  97  * Create a new element that is to be inserted into the list
  98  * @internal
  99  * @param disp memory disposition
 100  * @param buf payload buffer
 101  * @param len length of the buffer
 102  * @return a new element
 103  */
 104 static struct GNUNET_CONTAINER_SList_Elem *
 105 create_elem (enum GNUNET_CONTAINER_SListDisposition disp,
 106              const void *buf, size_t len)
 107 {
 108   struct GNUNET_CONTAINER_SList_Elem *e;
 109
 110   if (disp == GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT)
 111     {
 112       e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem) + len);
 113       memcpy (&e[1], buf, len);
 114       e->elem = (void *) &e[1];
 115     }
 116   else
 117     {
 118       e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem));
 119       e->elem = (void *) buf;
 120     }
 121   e->disp = disp;
 122   e->len = len;
 123   return e;
 124 }
 125
 126
 127 /**
 128  * Add a new element to the list
 129  * @param l list
 130  * @param disp memory disposition
 131  * @param buf payload buffer
 132  * @param len length of the buffer
 133  */
 134 void
 135 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
 136                             enum GNUNET_CONTAINER_SListDisposition disp,
 137                             const void *buf, size_t len)
 138 {
 139   struct GNUNET_CONTAINER_SList_Elem *e;
 140
 141   e = create_elem (disp, buf, len);
 142   e->next = l->head;
 143   l->head = e;
 144   l->length++;
 145 }
 146
 147
 148 /**
 149  * Append a singly linked list to another
 150  * @param dst list to append to
 151  * @param src source
 152  */
 153 void
 154 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst, struct GNUNET_CONTAINER_SList *src)
 155 {
 156   struct GNUNET_CONTAINER_SList_Iterator *i;
 157
 158   for (i = GNUNET_CONTAINER_slist_begin (src); GNUNET_CONTAINER_slist_end (i) !=
 159       GNUNET_YES; GNUNET_CONTAINER_slist_next (i))
 160
 161     {
 162       GNUNET_CONTAINER_slist_add (dst,
 163           (i->elem->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC) ? GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC
 164               : GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT, i->elem->elem,
 165           i->elem->len);
 166     }
 167   GNUNET_CONTAINER_slist_iter_destroy (i);
 168 }
 169
 170
 171 /**
 172  * Create a new singly linked list
 173  * @return the new list
 174  */
 175 struct GNUNET_CONTAINER_SList *
 176 GNUNET_CONTAINER_slist_create ()
 177 {
 178   return GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList));
 179 }
 180
 181
 182 /**
 183  * Destroy a singly linked list
 184  * @param l the list to be destroyed
 185  */
 186 void
 187 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l)
 188 {
 189   GNUNET_CONTAINER_slist_clear (l);
 190   GNUNET_free (l);
 191 }
 192
 193
 194 /**
 195  * Return the beginning of a list
 196  * @param l list
 197  * @return iterator pointing to the beginning
 198  */
 199 struct GNUNET_CONTAINER_SList_Iterator *
 200 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l)
 201 {
 202   struct GNUNET_CONTAINER_SList_Iterator *ret;
 203
 204   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Iterator));
 205   ret->elem = l->head;
 206   ret->list = l;
 207   return ret;
 208 }
 209
 210
 211 /**
 212  * Clear a list
 213  * @param l list
 214  */
 215 void
 216 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l)
 217 {
 218   struct GNUNET_CONTAINER_SList_Elem *e;
 219   struct GNUNET_CONTAINER_SList_Elem *n;
 220
 221   e = l->head;
 222   while (e != NULL)
 223     {
 224       n = e->next;
 225       if (e->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
 226         GNUNET_free (e->elem);
 227       GNUNET_free (e);
 228       e = n;
 229     }
 230   l->head = NULL;
 231   l->length = 0;
 232 }
 233
 234
 235 /**
 236  * Check if a list contains a certain element
 237  *
 238  * @param l list
 239  * @param buf payload buffer to find
 240  * @param len length of the payload (number of bytes in buf)
 241  */
 242 int
 243 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
 244                                  const void *buf, size_t len)
 245 {
 246   struct GNUNET_CONTAINER_SList_Elem *e;
 247
 248   for (e = l->head; e != NULL; e = e->next)
 249     if ((e->len == len) && (memcmp (buf, e->elem, len) == 0))
 250       return GNUNET_YES;
 251   return GNUNET_NO;
 252 }
 253
 254
 255 /**
 256  * Count the elements of a list
 257  * @param l list
 258  * @return number of elements in the list
 259  */
 260 int
 261 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l)
 262 {
 263   return l->length;
 264 }
 265
 266
 267 /**
 268  * Remove an element from the list
 269  *
 270  * @param i iterator that points to the element to be removed
 271  */
 272 void
 273 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
 274 {
 275   struct GNUNET_CONTAINER_SList_Elem *next;
 276
 277   next = i->elem->next;
 278   if (i->last != NULL)
 279     i->last->next = next;
 280   else
 281     i->list->head = next;
 282   if (i->elem->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
 283     GNUNET_free (i->elem->elem);
 284   GNUNET_free (i->elem);
 285   i->list->length--;
 286   i->elem = next;
 287 }
 288
 289
 290 /**
 291  * Insert an element into a list at a specific position
 292  * @param before where to insert the new element
 293  * @param disp memory disposition
 294  * @param buf payload buffer
 295  * @param len length of the payload
 296  */
 297 void
 298 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
 299                                enum GNUNET_CONTAINER_SListDisposition disp,
 300                                const void *buf, size_t len)
 301 {
 302   struct GNUNET_CONTAINER_SList_Elem *e;
 303
 304   e = create_elem (disp, buf, len);
 305   e->next = before->elem;
 306   if (before->last != NULL)
 307     before->last->next = e;
 308   else
 309     before->list->head = e;
 310   before->list->length++;
 311 }
 312
 313
 314 /**
 315  * Advance an iterator to the next element
 316  * @param i iterator
 317  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
 318  */
 319 int
 320 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i)
 321 {
 322   i->last = i->elem;
 323   i->elem = i->elem->next;
 324
 325   return (i->elem != NULL) ? GNUNET_YES : GNUNET_NO;
 326 }
 327
 328
 329 /**
 330  * Check if an iterator points beyond the end of a list
 331  *
 332  * @param i iterator
 333  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
 334  *         points to a valid element
 335  */
 336 int
 337 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i)
 338 {
 339   return (i->elem == NULL) ? GNUNET_YES : GNUNET_NO;
 340 }
 341
 342
 343 /**
 344  * Retrieve the element at a specific position in a list
 345  * @param i iterator
 346  * @param len payload length
 347  * @return payload
 348  */
 349 const void *
 350 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
 351                             size_t * len)
 352 {
 353   if (len)
 354     *len = i->elem->len;
 355   return i->elem->elem;
 356 }
 357
 358 /**
 359  * Release an iterator
 360  * @param i iterator
 361  */
 362 void
 363 GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator
 364                                      *i)
 365 {
 366   GNUNET_free (i);
 367 }
 368
 369 /* end of container_slist.c */