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 struct GNUNET_CONTAINER_SList_Elem
  31 {
  32   void *elem;
  33   size_t len;
  34   int disp;
  35   struct GNUNET_CONTAINER_SList_Elem *next;
  36 };
  37
  38 struct GNUNET_CONTAINER_SList
  39 {
  40   struct GNUNET_CONTAINER_SList_Elem head;
  41 };
  42
  43 struct GNUNET_CONTAINER_SList_Iterator
  44 {
  45   struct GNUNET_CONTAINER_SList_Elem *last;
  46   struct GNUNET_CONTAINER_SList_Elem *elem;
  47 };
  48
  49 /**
  50  * Create a new element that is to be inserted into the list
  51  * @internal
  52  * @param disp memory disposition
  53  * @param buf payload buffer
  54  * @param len length of the buffer
  55  * @return a new element
  56  */
  57 static struct GNUNET_CONTAINER_SList_Elem *
  58 create_elem (int disp, const void *buf, size_t len)
  59 {
  60   struct GNUNET_CONTAINER_SList_Elem *e;
  61
  62   e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem));
  63   e->disp = disp;
  64   if (disp == GNUNET_MEM_DISP_TRANSIENT)
  65     {
  66       e->elem = GNUNET_malloc (len);
  67       memcpy (e->elem, buf, len);
  68     }
  69   else
  70     e->elem = (void *) buf;
  71   e->len = len;
  72
  73   return e;
  74 }
  75
  76 /**
  77  * Add a new element to the list
  78  * @param l list
  79  * @param disp memory disposition
  80  * @param buf payload buffer
  81  * @param len length of the buffer
  82  */
  83 void
  84 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, int disp,
  85                             const void *buf, size_t len)
  86 {
  87   struct GNUNET_CONTAINER_SList_Elem *e;
  88
  89   e = create_elem (disp, buf, len);
  90   e->next = l->head.next;
  91   l->head.next = e;
  92 }
  93
  94 /**
  95  * Create a new singly linked list
  96  * @return the new list
  97  */
  98 struct GNUNET_CONTAINER_SList *
  99 GNUNET_CONTAINER_slist_create ()
 100 {
 101   struct GNUNET_CONTAINER_SList *ret;
 102
 103   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList));
 104   if (NULL == ret)
 105     return NULL;
 106
 107   memset (&ret->head, 0, sizeof (struct GNUNET_CONTAINER_SList));
 108
 109   return ret;
 110 }
 111
 112 /**
 113  * Destroy a singly linked list
 114  * @param l the list to be destroyed
 115  */
 116 void
 117 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l)
 118 {
 119   GNUNET_CONTAINER_slist_clear (l);
 120   GNUNET_free (l);
 121 }
 122
 123 /**
 124  * Return the beginning of a list
 125  * @param l list
 126  * @return iterator pointing to the beginning
 127  */
 128 const struct GNUNET_CONTAINER_SList_Iterator *
 129 GNUNET_CONTAINER_slist_begin (const struct GNUNET_CONTAINER_SList *l)
 130 {
 131   struct GNUNET_CONTAINER_SList_Iterator *ret;
 132
 133   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Iterator));
 134   ret->elem = l->head.next;
 135   ret->last = (struct GNUNET_CONTAINER_SList_Elem *) &l->head;
 136   return ret;
 137 }
 138
 139 /**
 140  * Clear a list
 141  * @param l list
 142  */
 143 void
 144 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l)
 145 {
 146   struct GNUNET_CONTAINER_SList_Elem *e, *n;
 147
 148   e = l->head.next;
 149   while (e != NULL)
 150     {
 151       if (e->disp != GNUNET_MEM_DISP_STATIC)
 152         GNUNET_free (e->elem);
 153       n = e->next;
 154       GNUNET_free (e);
 155       e = n;
 156     }
 157   l->head.next = NULL;
 158 }
 159
 160 /**
 161  * Check if a list contains a certain element
 162  * @param l list
 163  * @param buf payload buffer to find
 164  * @param lenght of the payload
 165  */
 166 int
 167 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
 168                                  const void *buf, size_t len)
 169 {
 170   struct GNUNET_CONTAINER_SList_Elem *e;
 171
 172   for (e = l->head.next; e != NULL; e = e->next)
 173     if (e->len == len && memcmp (buf, e->elem, len) == 0)
 174       return GNUNET_YES;
 175
 176   return GNUNET_NO;
 177 }
 178
 179 /**
 180  * Count the elements of a list
 181  * @param l list
 182  * @return number of elements in the list
 183  */
 184 int
 185 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l)
 186 {
 187   int n;
 188   struct GNUNET_CONTAINER_SList_Elem *e;
 189
 190   for (n = 0, e = l->head.next; e != NULL; e = e->next)
 191     n++;
 192
 193   return n;
 194 }
 195
 196 /**
 197  * Remove an element from the list
 198  * @param i iterator that points to the element to be removed
 199  */
 200 void
 201 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
 202 {
 203   struct GNUNET_CONTAINER_SList_Elem *next;
 204
 205   next = i->elem->next;
 206   i->last->next = next;
 207   if (i->elem->disp != GNUNET_MEM_DISP_STATIC)
 208     GNUNET_free (i->elem->elem);
 209   GNUNET_free (i->elem);
 210   i->elem = next;
 211 }
 212
 213 /**
 214  * Insert an element into a list at a specific position
 215  * @param before where to insert the new element
 216  * @param disp memory disposition
 217  * @param buf payload buffer
 218  * @param len length of the payload
 219  */
 220 void
 221 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
 222                                int disp, const void *buf, size_t len)
 223 {
 224   struct GNUNET_CONTAINER_SList_Elem *e;
 225
 226   e = create_elem (disp, buf, len);
 227   e->next = before->elem;
 228   before->last->next = e;
 229 }
 230
 231 /**
 232  * Advance an iterator to the next element
 233  * @param i iterator
 234  * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
 235  */
 236 int
 237 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i)
 238 {
 239   i->last = i->elem;
 240   i->elem = i->elem->next;
 241
 242   return i->elem != NULL;
 243 }
 244
 245 /**
 246  * Check if an iterator points beyond the end of a list
 247  * @param i iterator
 248  * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
 249  *         points to a valid element
 250  */
 251 int
 252 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i)
 253 {
 254   return i->elem == NULL;
 255 }
 256
 257 /**
 258  * Retrieve the element at a specific position in a list
 259  * @param i iterator
 260  * @param len payload length
 261  * @return payload
 262  */
 263 void *
 264 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
 265                             size_t * len)
 266 {
 267   if (len)
 268     *len = i->elem->len;
 269   return i->elem->elem;
 270 }