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