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 2, 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"
31 * Element in our linked list.
33 struct GNUNET_CONTAINER_SList_Elem
36 * This is a linked list.
38 struct GNUNET_CONTAINER_SList_Elem *next;
41 * Application data stored at this element.
46 * Number of bytes stored in elem.
51 * Disposition of the element.
53 enum GNUNET_CONTAINER_SListDisposition disp;
58 * Handle to a singly linked list
60 struct GNUNET_CONTAINER_SList
63 * Head of the linked list.
65 struct GNUNET_CONTAINER_SList_Elem *head;
68 * Tail of the linked list.
70 struct GNUNET_CONTAINER_SList_Elem *tail;
73 * Number of elements in the list.
80 * Handle to a singly linked list iterator
82 struct GNUNET_CONTAINER_SList_Iterator
85 * Linked list that we are iterating over.
87 struct GNUNET_CONTAINER_SList *list;
90 * Last element accessed.
92 struct GNUNET_CONTAINER_SList_Elem *last;
95 * Current list element.
97 struct GNUNET_CONTAINER_SList_Elem *elem;
102 * Create a new element that is to be inserted into the list
104 * @param disp memory disposition
105 * @param buf payload buffer
106 * @param len length of the buffer
107 * @return a new element
109 static struct GNUNET_CONTAINER_SList_Elem *
110 create_elem (enum GNUNET_CONTAINER_SListDisposition disp,
111 const void *buf, size_t len)
113 struct GNUNET_CONTAINER_SList_Elem *e;
115 if (disp == GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT)
117 e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem) + len);
118 memcpy (&e[1], buf, len);
119 e->elem = (void *) &e[1];
123 e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem));
124 e->elem = (void *) buf;
133 * Add a new element to the list
135 * @param disp memory disposition
136 * @param buf payload buffer
137 * @param len length of the buffer
140 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
141 enum GNUNET_CONTAINER_SListDisposition disp,
142 const void *buf, size_t len)
144 struct GNUNET_CONTAINER_SList_Elem *e;
146 e = create_elem (disp, buf, len);
149 if (l->tail == NULL) l->tail = e;
154 * Add a new element to the end of the list
156 * @param disp memory disposition
157 * @param buf payload buffer
158 * @param len length of the buffer
161 GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
162 enum GNUNET_CONTAINER_SListDisposition disp,
163 const void *buf, size_t len)
165 struct GNUNET_CONTAINER_SList_Elem *e;
167 e = create_elem (disp, buf, len);
178 * Append a singly linked list to another
179 * @param dst list to append to
183 GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst, struct GNUNET_CONTAINER_SList *src)
185 struct GNUNET_CONTAINER_SList_Iterator *i;
187 for (i = GNUNET_CONTAINER_slist_begin (src); GNUNET_CONTAINER_slist_end (i) !=
188 GNUNET_YES; GNUNET_CONTAINER_slist_next (i))
191 GNUNET_CONTAINER_slist_add (dst,
192 (i->elem->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC) ? GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC
193 : GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT, i->elem->elem,
196 GNUNET_CONTAINER_slist_iter_destroy (i);
201 * Create a new singly linked list
202 * @return the new list
204 struct GNUNET_CONTAINER_SList *
205 GNUNET_CONTAINER_slist_create ()
207 return GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList));
212 * Destroy a singly linked list
213 * @param l the list to be destroyed
216 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l)
218 GNUNET_CONTAINER_slist_clear (l);
224 * Return the beginning of a list
226 * @return iterator pointing to the beginning
228 struct GNUNET_CONTAINER_SList_Iterator *
229 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l)
231 struct GNUNET_CONTAINER_SList_Iterator *ret;
233 ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Iterator));
245 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l)
247 struct GNUNET_CONTAINER_SList_Elem *e;
248 struct GNUNET_CONTAINER_SList_Elem *n;
254 if (e->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
255 GNUNET_free (e->elem);
266 * Check if a list contains a certain element
269 * @param buf payload buffer to find
270 * @param len length of the payload (number of bytes in buf)
273 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
274 const void *buf, size_t len)
276 struct GNUNET_CONTAINER_SList_Elem *e;
278 for (e = l->head; e != NULL; e = e->next)
279 if ((e->len == len) && (memcmp (buf, e->elem, len) == 0))
286 * Count the elements of a list
288 * @return number of elements in the list
291 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l)
298 * Remove an element from the list
300 * @param i iterator that points to the element to be removed
303 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
305 struct GNUNET_CONTAINER_SList_Elem *next;
307 next = i->elem->next;
309 i->last->next = next;
311 i->list->head = next;
313 i->list->tail = i->last;
314 if (i->elem->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
315 GNUNET_free (i->elem->elem);
316 GNUNET_free (i->elem);
323 * Insert an element into a list at a specific position
324 * @param before where to insert the new element
325 * @param disp memory disposition
326 * @param buf payload buffer
327 * @param len length of the payload
330 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
331 enum GNUNET_CONTAINER_SListDisposition disp,
332 const void *buf, size_t len)
334 struct GNUNET_CONTAINER_SList_Elem *e;
336 e = create_elem (disp, buf, len);
337 e->next = before->elem;
338 if (before->last != NULL)
339 before->last->next = e;
341 before->list->head = e;
343 before->list->tail = e;
344 before->list->length++;
349 * Advance an iterator to the next element
351 * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
354 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i)
357 i->elem = i->elem->next;
359 return (i->elem != NULL) ? GNUNET_YES : GNUNET_NO;
364 * Check if an iterator points beyond the end of a list
367 * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
368 * points to a valid element
371 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i)
373 return (i->elem == NULL) ? GNUNET_YES : GNUNET_NO;
378 * Retrieve the element at a specific position in a list
380 * @param len payload length
384 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
389 return i->elem->elem;
393 * Release an iterator
397 GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator
403 /* end of container_slist.c */