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,
 107              size_t len)
 108 {
 109   struct GNUNET_CONTAINER_SList_Elem *e;
 110
 111   if (disp == GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT)
 112     {
 113       e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem) + len);
 114       memcpy (&e[1], buf, len);
 115       e->elem = (void*) &e[1];
 116     }
 117   else
 118     {
 119       e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem));
 120       e->elem = (void*) buf;
 121     }
 122   e->disp = disp;
 123   e->len = len;
 124   return e;
 125 }
 126
 127
 128 /**
 129  * Add a new element to the list
 130  * @param l list
 131  * @param disp memory disposition
 132  * @param buf payload buffer
 133  * @param len length of the buffer
 134  */
 135 void
 136 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
 137                             enum GNUNET_CONTAINER_SListDisposition disp,
 138                             const void *buf, size_t len)
 139 {
 140   struct GNUNET_CONTAINER_SList_Elem *e;
 141
 142   e = create_elem (disp, buf, len);
 143   e->next = l->head;
 144   l->head = e;
 145   l->length++;
 146 }
 147
 148
 149 /**
 150  * Create a new singly linked list
 151  * @return the new list
 152  */
 153 struct GNUNET_CONTAINER_SList *
 154 GNUNET_CONTAINER_slist_create ()
 155 {
 156   return GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList));
 157 }
 158
 159
 160 /**
 161  * Destroy a singly linked list
 162  * @param l the list to be destroyed
 163  */
 164 void
 165 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l)
 166 {
 167   GNUNET_CONTAINER_slist_clear (l);
 168   GNUNET_free (l);
 169 }
 170
 171
 172 /**
 173  * Return the beginning of a list
 174  * @param l list
 175  * @return iterator pointing to the beginning
 176  */
 177 struct GNUNET_CONTAINER_SList_Iterator *
 178 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l)
 179 {
 180   struct GNUNET_CONTAINER_SList_Iterator *ret;
 181
 182   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Iterator));
 183   ret->elem = l->head;
 184   ret->list = l;
 185   return ret;
 186 }
 187
 188
 189 /**
 190  * Clear a list
 191  * @param l list
 192  */
 193 void
 194 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l)
 195 {
 196   struct GNUNET_CONTAINER_SList_Elem *e;
 197   struct GNUNET_CONTAINER_SList_Elem *n;
 198
 199   e = l->head;
 200   while (e != NULL)
 201     {
 202       n = e->next;
 203       if (e->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
 204         GNUNET_free (e->elem);
 205       GNUNET_free (e);
 206       e = n;
 207     }
 208   l->head = NULL;
 209   l->length = 0;
 210 }
 211
 212
 213 /**
 214  * Check if a list contains a certain element
 215  *
 216  * @param l list
 217  * @param buf payload buffer to find
 218  * @param len length of the payload (number of bytes in buf)
 219  */
 220 int
 221 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
 222                                  const void *buf, size_t len)
 223 {
 224   struct GNUNET_CONTAINER_SList_Elem *e;
 225
 226   for (e = l->head; e != NULL; e = e->next)
 227     if ( (e->len == len) &&
 228          (memcmp (buf, e->elem, len) == 0) )
 229       return GNUNET_YES;
 230   return GNUNET_NO;
 231 }
 232
 233
 234 /**
 235  * Count the elements of a list
 236  * @param l list
 237  * @return number of elements in the list
 238  */
 239 int
 240 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l)
 241 {
 242   return l->length;
 243 }
 244
 245
 246 /**
 247  * Remove an element from the list
 248  *
 249  * @param i iterator that points to the element to be removed
 250  */
 251 void
 252 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
 253 {
 254   struct GNUNET_CONTAINER_SList_Elem *next;
 255
 256   next = i->elem->next;
 257   if (i->last != NULL)
 258     i->last->next = next;
 259   else
 260     i->list->head = next;
 261   if (i->elem->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
 262     GNUNET_free (i->elem->elem);
 263   GNUNET_free (i->elem);
 264   i->list->length--;
 265   i->elem = next;
 266 }
 267
 268
 269 /**
 270  * Insert an element into a list at a specific position
 271  * @param before where to insert the new element
 272  * @param disp memory disposition
 273  * @param buf payload buffer
 274  * @param len length of the payload
 275  */
 276 void
 277 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
 278                                enum GNUNET_CONTAINER_SListDisposition disp,
 279                                const void *buf, size_t len)
 280 {
 281   struct GNUNET_CONTAINER_SList_Elem *e;
 282
 283   e = create_elem (disp, buf, len);
 284   e->next = before->elem;
 285   if (before->last != NULL)
 286     before->last->next = e;
 287   else
 288     before->list->head = e;
 289   before->list->length++;
 290 }
 291
 292
 293 /**
 294  * Advance an iterator to the next element
 295  * @param i iterator
 296  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
 297  */
 298 int
 299 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i)
 300 {
 301   i->last = i->elem;
 302   i->elem = i->elem->next;
 303
 304   return (i->elem != NULL) ? GNUNET_YES : GNUNET_NO;
 305 }
 306
 307
 308 /**
 309  * Check if an iterator points beyond the end of a list
 310  *
 311  * @param i iterator
 312  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
 313  *         points to a valid element
 314  */
 315 int
 316 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i)
 317 {
 318   return (i->elem == NULL) ? GNUNET_YES : GNUNET_NO;
 319 }
 320
 321
 322 /**
 323  * Retrieve the element at a specific position in a list
 324  * @param i iterator
 325  * @param len payload length
 326  * @return payload
 327  */
 328 const void *
 329 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
 330                             size_t * len)
 331 {
 332   if (len)
 333     *len = i->elem->len;
 334   return i->elem->elem;
 335 }
 336
 337 /* end of container_slist.c */