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 3, 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 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
  31
  32 /**
  33  * Element in our linked list.
  34  */
  35 struct GNUNET_CONTAINER_SList_Elem
  36 {
  37   /**
  38    * This is a linked list.
  39    */
  40   struct GNUNET_CONTAINER_SList_Elem *next;
  41
  42   /**
  43    * Application data stored at this element.
  44    */
  45   void *elem;
  46
  47   /**
  48    * Number of bytes stored in elem.
  49    */
  50   size_t len;
  51
  52   /**
  53    * Disposition of the element.
  54    */
  55   enum GNUNET_CONTAINER_SListDisposition disp;
  56 };
  57
  58
  59 /**
  60  * Handle to a singly linked list
  61  */
  62 struct GNUNET_CONTAINER_SList
  63 {
  64   /**
  65    * Head of the linked list.
  66    */
  67   struct GNUNET_CONTAINER_SList_Elem *head;
  68
  69   /**
  70    * Tail of the linked list.
  71    */
  72   struct GNUNET_CONTAINER_SList_Elem *tail;
  73
  74   /**
  75    * Number of elements in the list.
  76    */
  77   unsigned int length;
  78 };
  79
  80
  81
  82 /**
  83  * Create a new element that is to be inserted into the list
  84  * @internal
  85  * @param disp memory disposition
  86  * @param buf payload buffer
  87  * @param len length of the buffer
  88  * @return a new element
  89  */
  90 static struct GNUNET_CONTAINER_SList_Elem *
  91 create_elem (enum GNUNET_CONTAINER_SListDisposition disp, const void *buf,
  92              size_t len)
  93 {
  94   struct GNUNET_CONTAINER_SList_Elem *e;
  95
  96   if (disp == GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT)
  97   {
  98     e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem) + len);
  99     memcpy (&e[1], buf, len);
 100     e->elem = (void *) &e[1];
 101   }
 102   else
 103   {
 104     e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem));
 105     e->elem = (void *) buf;
 106   }
 107   e->disp = disp;
 108   e->len = len;
 109   return e;
 110 }
 111
 112
 113 /**
 114  * Add a new element to the list
 115  * @param l list
 116  * @param disp memory disposition
 117  * @param buf payload buffer
 118  * @param len length of the buffer
 119  */
 120 void
 121 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
 122                             enum GNUNET_CONTAINER_SListDisposition disp,
 123                             const void *buf, size_t len)
 124 {
 125   struct GNUNET_CONTAINER_SList_Elem *e;
 126
 127   e = create_elem (disp, buf, len);
 128   e->next = l->head;
 129   l->head = e;
 130   if (l->tail == NULL)
 131     l->tail = e;
 132   l->length++;
 133 }
 134
 135 /**
 136  * Add a new element to the end of the list
 137  * @param l list
 138  * @param disp memory disposition
 139  * @param buf payload buffer
 140  * @param len length of the buffer
 141  */
 142 void
 143 GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
 144                                 enum GNUNET_CONTAINER_SListDisposition disp,
 145                                 const void *buf, size_t len)
 146 {
 147   struct GNUNET_CONTAINER_SList_Elem *e;
 148
 149   e = create_elem (disp, buf, len);
 150   if (l->tail != NULL)
 151     l->tail->next = e;
 152   if (l->head == NULL)
 153     l->head = e;
 154   l->tail = e;
 155   l->length++;
 156 }
 157
 158
 159 /**
 160  * Append a singly linked list to another
 161  * @param dst list to append to
 162  * @param src source
 163  */
 164 void
 165 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst,
 166                                struct GNUNET_CONTAINER_SList *src)
 167 {
 168   struct GNUNET_CONTAINER_SList_Iterator i;
 169
 170   for (i = GNUNET_CONTAINER_slist_begin (src);
 171        GNUNET_CONTAINER_slist_end (&i) != GNUNET_YES;
 172        GNUNET_CONTAINER_slist_next (&i))
 173
 174   {
 175     GNUNET_CONTAINER_slist_add (dst,
 176                                 (i.elem->disp ==
 177                                  GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC) ?
 178                                 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC :
 179                                 GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT,
 180                                 i.elem->elem, i.elem->len);
 181   }
 182   GNUNET_CONTAINER_slist_iter_destroy (&i);
 183 }
 184
 185
 186 /**
 187  * Create a new singly linked list
 188  * @return the new list
 189  */
 190 struct GNUNET_CONTAINER_SList *
 191 GNUNET_CONTAINER_slist_create ()
 192 {
 193   return GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList));
 194 }
 195
 196
 197 /**
 198  * Destroy a singly linked list
 199  * @param l the list to be destroyed
 200  */
 201 void
 202 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l)
 203 {
 204   GNUNET_CONTAINER_slist_clear (l);
 205   GNUNET_free (l);
 206 }
 207
 208
 209 /**
 210  * Return the beginning of a list
 211  * @param l list
 212  * @return iterator pointing to the beginning
 213  */
 214 struct GNUNET_CONTAINER_SList_Iterator
 215 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l)
 216 {
 217   struct GNUNET_CONTAINER_SList_Iterator ret;
 218
 219   memset (&ret, 0, sizeof (ret));
 220   ret.elem = l->head;
 221   ret.list = l;
 222   return ret;
 223 }
 224
 225
 226 /**
 227  * Clear a list
 228  * @param l list
 229  */
 230 void
 231 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l)
 232 {
 233   struct GNUNET_CONTAINER_SList_Elem *e;
 234   struct GNUNET_CONTAINER_SList_Elem *n;
 235
 236   e = l->head;
 237   while (e != NULL)
 238   {
 239     n = e->next;
 240     if (e->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
 241       GNUNET_free (e->elem);
 242     GNUNET_free (e);
 243     e = n;
 244   }
 245   l->head = NULL;
 246   l->tail = NULL;
 247   l->length = 0;
 248 }
 249
 250
 251 /**
 252  * Check if a list contains a certain element
 253  * @param l list
 254  * @param buf payload buffer to find
 255  * @param len length of the payload (number of bytes in buf)
 256  *
 257  * @return GNUNET_YES if found, GNUNET_NO otherwise
 258  */
 259 int
 260 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
 261                                  const void *buf, size_t len)
 262 {
 263   struct GNUNET_CONTAINER_SList_Elem *e;
 264
 265   for (e = l->head; e != NULL; e = e->next)
 266     if ((e->len == len) && (memcmp (buf, e->elem, len) == 0))
 267       return GNUNET_YES;
 268   return GNUNET_NO;
 269 }
 270
 271 typedef int (*Comparator)(const void *,  size_t, const void *,  size_t);
 272
 273 /**
 274  * Check if a list contains a certain element
 275  *
 276  * @param l list
 277  * @param buf payload buffer to find
 278  * @param len length of the payload (number of bytes in buf)
 279  * @param compare comparison function, should return 0 if compared elements match
 280  *
 281  * @return NULL if the 'buf' could not be found, pointer to the
 282  *         list element, if found
 283  */
 284 void *
 285 GNUNET_CONTAINER_slist_contains2 (const struct GNUNET_CONTAINER_SList *l,
 286                                   const void *buf, size_t len,
 287                                   Comparator compare)
 288 {
 289   struct GNUNET_CONTAINER_SList_Elem *e;
 290
 291   for (e = l->head; e != NULL; e = e->next)
 292     if ((e->len == len) && (*compare)(buf, len, e->elem, e->len) == 0)
 293       return e->elem;
 294   return NULL;
 295 }
 296
 297
 298 /**
 299  * Count the elements of a list
 300  * @param l list
 301  * @return number of elements in the list
 302  */
 303 int
 304 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l)
 305 {
 306   return l->length;
 307 }
 308
 309
 310 /**
 311  * Remove an element from the list
 312  *
 313  * @param i iterator that points to the element to be removed
 314  */
 315 void
 316 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
 317 {
 318   struct GNUNET_CONTAINER_SList_Elem *next;
 319
 320   next = i->elem->next;
 321   if (i->last != NULL)
 322     i->last->next = next;
 323   else
 324     i->list->head = next;
 325   if (next == NULL)
 326     i->list->tail = i->last;
 327   if (i->elem->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
 328     GNUNET_free (i->elem->elem);
 329   GNUNET_free (i->elem);
 330   i->list->length--;
 331   i->elem = next;
 332 }
 333
 334
 335 /**
 336  * Insert an element into a list at a specific position
 337  * @param before where to insert the new element
 338  * @param disp memory disposition
 339  * @param buf payload buffer
 340  * @param len length of the payload
 341  */
 342 void
 343 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
 344                                enum GNUNET_CONTAINER_SListDisposition disp,
 345                                const void *buf, size_t len)
 346 {
 347   struct GNUNET_CONTAINER_SList_Elem *e;
 348
 349   e = create_elem (disp, buf, len);
 350   e->next = before->elem;
 351   if (before->last != NULL)
 352     before->last->next = e;
 353   else
 354     before->list->head = e;
 355   if (e->next == NULL)
 356     before->list->tail = e;
 357   before->list->length++;
 358 }
 359
 360
 361 /**
 362  * Advance an iterator to the next element
 363  * @param i iterator
 364  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
 365  */
 366 int
 367 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i)
 368 {
 369   i->last = i->elem;
 370   i->elem = i->elem->next;
 371
 372   return (i->elem != NULL) ? GNUNET_YES : GNUNET_NO;
 373 }
 374
 375
 376 /**
 377  * Check if an iterator points beyond the end of a list
 378  *
 379  * @param i iterator
 380  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
 381  *         points to a valid element
 382  */
 383 int
 384 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i)
 385 {
 386   return (i->elem == NULL) ? GNUNET_YES : GNUNET_NO;
 387 }
 388
 389
 390 /**
 391  * Retrieve the element at a specific position in a list
 392  * @param i iterator
 393  * @param len payload length
 394  * @return payload
 395  */
 396 void *
 397 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
 398                             size_t * len)
 399 {
 400   if (len)
 401     *len = i->elem->len;
 402   return i->elem->elem;
 403 }
 404
 405 /**
 406  * Release an iterator
 407  * @param i iterator
 408  */
 409 void
 410 GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i)
 411 {
 412 }
 413
 414 /* end of container_slist.c */