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