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"
30 struct GNUNET_CONTAINER_SList_Elem
35 struct GNUNET_CONTAINER_SList_Elem *next;
38 struct GNUNET_CONTAINER_SList
40 struct GNUNET_CONTAINER_SList_Elem head;
43 struct GNUNET_CONTAINER_SList_Iterator
45 struct GNUNET_CONTAINER_SList_Elem *last;
46 struct GNUNET_CONTAINER_SList_Elem *elem;
50 * Create a new element that is to be inserted into the list
52 * @param disp memory disposition
53 * @param buf payload buffer
54 * @param len length of the buffer
55 * @return a new element
57 static struct GNUNET_CONTAINER_SList_Elem *
58 create_elem (int disp, const void *buf, size_t len)
60 struct GNUNET_CONTAINER_SList_Elem *e;
62 e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem));
64 if (disp == GNUNET_MEM_DISP_TRANSIENT)
66 e->elem = GNUNET_malloc (len);
67 memcpy (e->elem, buf, len);
70 e->elem = (void *) buf;
77 * Add a new element to the list
79 * @param disp memory disposition
80 * @param buf payload buffer
81 * @param len length of the buffer
84 GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, int disp,
85 const void *buf, size_t len)
87 struct GNUNET_CONTAINER_SList_Elem *e;
89 e = create_elem (disp, buf, len);
90 e->next = l->head.next;
95 * Create a new singly linked list
96 * @return the new list
98 struct GNUNET_CONTAINER_SList *
99 GNUNET_CONTAINER_slist_create ()
101 struct GNUNET_CONTAINER_SList *ret;
103 ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList));
107 memset (&ret->head, 0, sizeof (struct GNUNET_CONTAINER_SList));
113 * Destroy a singly linked list
114 * @param l the list to be destroyed
117 GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l)
119 GNUNET_CONTAINER_slist_clear (l);
124 * Return the beginning of a list
126 * @return iterator pointing to the beginning
128 const struct GNUNET_CONTAINER_SList_Iterator *
129 GNUNET_CONTAINER_slist_begin (const struct GNUNET_CONTAINER_SList *l)
131 struct GNUNET_CONTAINER_SList_Iterator *ret;
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;
144 GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l)
146 struct GNUNET_CONTAINER_SList_Elem *e, *n;
151 if (e->disp != GNUNET_MEM_DISP_STATIC)
152 GNUNET_free (e->elem);
161 * Check if a list contains a certain element
163 * @param buf payload buffer to find
164 * @param lenght of the payload
167 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
168 const void *buf, size_t len)
170 struct GNUNET_CONTAINER_SList_Elem *e;
172 for (e = l->head.next; e != NULL; e = e->next)
173 if (e->len == len && memcmp (buf, e->elem, len) == 0)
180 * Count the elements of a list
182 * @return number of elements in the list
185 GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l)
188 struct GNUNET_CONTAINER_SList_Elem *e;
190 for (n = 0, e = l->head.next; e != NULL; e = e->next)
197 * Remove an element from the list
198 * @param i iterator that points to the element to be removed
201 GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
203 struct GNUNET_CONTAINER_SList_Elem *next;
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);
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
221 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
222 int disp, const void *buf, size_t len)
224 struct GNUNET_CONTAINER_SList_Elem *e;
226 e = create_elem (disp, buf, len);
227 e->next = before->elem;
228 before->last->next = e;
232 * Advance an iterator to the next element
234 * @return GNUNET_YES on success, GNUNET_NO if the end has been reached
237 GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i)
240 i->elem = i->elem->next;
242 return i->elem != NULL;
246 * Check if an iterator points beyond the end of a list
248 * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator
249 * points to a valid element
252 GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i)
254 return i->elem == NULL;
258 * Retrieve the element at a specific position in a list
260 * @param len payload length
264 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
269 return i->elem->elem;