2 This file is part of GNUnet.
3 (C) 2009 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file util/container_slist.c
23 * @brief Implementation of a singly-linked list
28 #include "gnunet_container_lib.h"
30 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
33 * Element in our linked list.
35 struct GNUNET_CONTAINER_SList_Elem
38 * This is a linked list.
40 struct GNUNET_CONTAINER_SList_Elem *next;
43 * Application data stored at this element.
48 * Number of bytes stored in elem.
53 * Disposition of the element.
55 enum GNUNET_CONTAINER_SListDisposition disp;
60 * Handle to a singly linked list
62 struct GNUNET_CONTAINER_SList
65 * Head of the linked list.
67 struct GNUNET_CONTAINER_SList_Elem *head;
70 * Tail of the linked list.
72 struct GNUNET_CONTAINER_SList_Elem *tail;
75 * Number of elements in the list.
83 * Create a new element that is to be inserted into the list
85 * @param disp memory disposition
86 * @param buf payload buffer
87 * @param len length of the buffer
88 * @return a new element
90 static struct GNUNET_CONTAINER_SList_Elem *
91 create_elem (enum GNUNET_CONTAINER_SListDisposition disp, const void *buf,
94 struct GNUNET_CONTAINER_SList_Elem *e;
96 if (disp == GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT)
98 e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem) + len);
99 memcpy (&e[1], buf, len);
100 e->elem = (void *) &e[1];
104 e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem));
105 e->elem = (void *) buf;
114 * Add a new element to the list
116 * @param disp memory disposition
117 * @param buf payload buffer
118 * @param len length of the buffer
121 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
122 enum GNUNET_CONTAINER_SListDisposition disp,
123 const void *buf, size_t len)
125 struct GNUNET_CONTAINER_SList_Elem *e;
127 e = create_elem (disp, buf, len);
136 * Add a new element to the end of the list
138 * @param disp memory disposition
139 * @param buf payload buffer
140 * @param len length of the buffer
143 GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
144 enum GNUNET_CONTAINER_SListDisposition disp,
145 const void *buf, size_t len)
147 struct GNUNET_CONTAINER_SList_Elem *e;
149 e = create_elem (disp, buf, len);
160 * Append a singly linked list to another
161 * @param dst list to append to
165 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst,
166 struct GNUNET_CONTAINER_SList *src)
168 struct GNUNET_CONTAINER_SList_Iterator i;
170 for (i = GNUNET_CONTAINER_slist_begin (src);
171 GNUNET_CONTAINER_slist_end (&i) != GNUNET_YES;
172 GNUNET_CONTAINER_slist_next (&i))
175 GNUNET_CONTAINER_slist_add (dst,
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);
182 GNUNET_CONTAINER_slist_iter_destroy (&i);
187 * Create a new singly linked list
188 * @return the new list
190 struct GNUNET_CONTAINER_SList *
191 GNUNET_CONTAINER_slist_create ()
193 return GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList));
198 * Destroy a singly linked list
199 * @param l the list to be destroyed
202 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l)
204 GNUNET_CONTAINER_slist_clear (l);
210 * Return the beginning of a list
212 * @return iterator pointing to the beginning
214 struct GNUNET_CONTAINER_SList_Iterator
215 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l)
217 struct GNUNET_CONTAINER_SList_Iterator ret;
219 memset (&ret, 0, sizeof (ret));
231 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l)
233 struct GNUNET_CONTAINER_SList_Elem *e;
234 struct GNUNET_CONTAINER_SList_Elem *n;
240 if (e->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
241 GNUNET_free (e->elem);
252 * Check if a list contains a certain element
254 * @param buf payload buffer to find
255 * @param len length of the payload (number of bytes in buf)
257 * @return GNUNET_YES if found, GNUNET_NO otherwise
260 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
261 const void *buf, size_t len)
263 struct GNUNET_CONTAINER_SList_Elem *e;
265 for (e = l->head; e != NULL; e = e->next)
266 if ((e->len == len) && (memcmp (buf, e->elem, len) == 0))
271 typedef int (*Comparator)(const void *, size_t, const void *, size_t);
274 * Check if a list contains a certain element
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
281 * @return NULL if the 'buf' could not be found, pointer to the
282 * list element, if found
285 GNUNET_CONTAINER_slist_contains2 (const struct GNUNET_CONTAINER_SList *l,
286 const void *buf, size_t len,
289 struct GNUNET_CONTAINER_SList_Elem *e;
291 for (e = l->head; e != NULL; e = e->next)
292 if ((e->len == len) && (*compare)(buf, len, e->elem, e->len) == 0)
299 * Count the elements of a list
301 * @return number of elements in the list
304 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l)
311 * Remove an element from the list
313 * @param i iterator that points to the element to be removed
316 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
318 struct GNUNET_CONTAINER_SList_Elem *next;
320 next = i->elem->next;
322 i->last->next = next;
324 i->list->head = next;
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);
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
343 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
344 enum GNUNET_CONTAINER_SListDisposition disp,
345 const void *buf, size_t len)
347 struct GNUNET_CONTAINER_SList_Elem *e;
349 e = create_elem (disp, buf, len);
350 e->next = before->elem;
351 if (before->last != NULL)
352 before->last->next = e;
354 before->list->head = e;
356 before->list->tail = e;
357 before->list->length++;
362 * Advance an iterator to the next element
364 * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
367 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i)
370 i->elem = i->elem->next;
372 return (i->elem != NULL) ? GNUNET_YES : GNUNET_NO;
377 * Check if an iterator points beyond the end of a list
380 * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
381 * points to a valid element
384 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i)
386 return (i->elem == NULL) ? GNUNET_YES : GNUNET_NO;
391 * Retrieve the element at a specific position in a list
393 * @param len payload length
397 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
402 return i->elem->elem;
406 * Release an iterator
410 GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i)
414 /* end of container_slist.c */