diff options
author | Christian Grothoff <christian@grothoff.org> | 2009-10-03 18:23:39 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2009-10-03 18:23:39 +0000 |
commit | 9a496f231cdaeb77da9b6f0ac8f77bac20fbd19c (patch) | |
tree | d5b3eda56638508b6bfdc00864df4bc43f07c282 /src/util/container_slist.c | |
parent | 71050ec2a7ea81ac57bc4fba010ae2baf027b8c6 (diff) | |
download | gnunet-9a496f231cdaeb77da9b6f0ac8f77bac20fbd19c.tar.gz gnunet-9a496f231cdaeb77da9b6f0ac8f77bac20fbd19c.zip |
fixing slist api and implementation
Diffstat (limited to 'src/util/container_slist.c')
-rw-r--r-- | src/util/container_slist.c | 105 |
1 files changed, 59 insertions, 46 deletions
diff --git a/src/util/container_slist.c b/src/util/container_slist.c index c279bb2ea..874068bdb 100644 --- a/src/util/container_slist.c +++ b/src/util/container_slist.c | |||
@@ -29,19 +29,21 @@ | |||
29 | 29 | ||
30 | struct GNUNET_CONTAINER_SList_Elem | 30 | struct GNUNET_CONTAINER_SList_Elem |
31 | { | 31 | { |
32 | void *elem; | 32 | struct GNUNET_CONTAINER_SList_Elem *next; |
33 | const void *elem; | ||
33 | size_t len; | 34 | size_t len; |
34 | int disp; | 35 | int disp; |
35 | struct GNUNET_CONTAINER_SList_Elem *next; | ||
36 | }; | 36 | }; |
37 | 37 | ||
38 | struct GNUNET_CONTAINER_SList | 38 | struct GNUNET_CONTAINER_SList |
39 | { | 39 | { |
40 | struct GNUNET_CONTAINER_SList_Elem head; | 40 | struct GNUNET_CONTAINER_SList_Elem *head; |
41 | unsigned int length; | ||
41 | }; | 42 | }; |
42 | 43 | ||
43 | struct GNUNET_CONTAINER_SList_Iterator | 44 | struct GNUNET_CONTAINER_SList_Iterator |
44 | { | 45 | { |
46 | struct GNUNET_CONTAINER_SList *list; | ||
45 | struct GNUNET_CONTAINER_SList_Elem *last; | 47 | struct GNUNET_CONTAINER_SList_Elem *last; |
46 | struct GNUNET_CONTAINER_SList_Elem *elem; | 48 | struct GNUNET_CONTAINER_SList_Elem *elem; |
47 | }; | 49 | }; |
@@ -59,20 +61,23 @@ create_elem (int disp, const void *buf, size_t len) | |||
59 | { | 61 | { |
60 | struct GNUNET_CONTAINER_SList_Elem *e; | 62 | struct GNUNET_CONTAINER_SList_Elem *e; |
61 | 63 | ||
62 | e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem)); | ||
63 | e->disp = disp; | ||
64 | if (disp == GNUNET_MEM_DISP_TRANSIENT) | 64 | if (disp == GNUNET_MEM_DISP_TRANSIENT) |
65 | { | 65 | { |
66 | e->elem = GNUNET_malloc (len); | 66 | e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem) + len); |
67 | memcpy (e->elem, buf, len); | 67 | memcpy (&e[1], buf, len); |
68 | e->elem = (const void*) &e[1]; | ||
68 | } | 69 | } |
69 | else | 70 | else |
70 | e->elem = (void *) buf; | 71 | { |
72 | e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem)); | ||
73 | e->elem = buf; | ||
74 | } | ||
75 | e->disp = disp; | ||
71 | e->len = len; | 76 | e->len = len; |
72 | |||
73 | return e; | 77 | return e; |
74 | } | 78 | } |
75 | 79 | ||
80 | |||
76 | /** | 81 | /** |
77 | * Add a new element to the list | 82 | * Add a new element to the list |
78 | * @param l list | 83 | * @param l list |
@@ -87,10 +92,12 @@ GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, int disp, | |||
87 | struct GNUNET_CONTAINER_SList_Elem *e; | 92 | struct GNUNET_CONTAINER_SList_Elem *e; |
88 | 93 | ||
89 | e = create_elem (disp, buf, len); | 94 | e = create_elem (disp, buf, len); |
90 | e->next = l->head.next; | 95 | e->next = l->head; |
91 | l->head.next = e; | 96 | l->head = e; |
97 | l->length++; | ||
92 | } | 98 | } |
93 | 99 | ||
100 | |||
94 | /** | 101 | /** |
95 | * Create a new singly linked list | 102 | * Create a new singly linked list |
96 | * @return the new list | 103 | * @return the new list |
@@ -98,15 +105,7 @@ GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, int disp, | |||
98 | struct GNUNET_CONTAINER_SList * | 105 | struct GNUNET_CONTAINER_SList * |
99 | GNUNET_CONTAINER_slist_create () | 106 | GNUNET_CONTAINER_slist_create () |
100 | { | 107 | { |
101 | struct GNUNET_CONTAINER_SList *ret; | 108 | return GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList)); |
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 | } | 109 | } |
111 | 110 | ||
112 | /** | 111 | /** |
@@ -120,22 +119,24 @@ GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l) | |||
120 | GNUNET_free (l); | 119 | GNUNET_free (l); |
121 | } | 120 | } |
122 | 121 | ||
122 | |||
123 | /** | 123 | /** |
124 | * Return the beginning of a list | 124 | * Return the beginning of a list |
125 | * @param l list | 125 | * @param l list |
126 | * @return iterator pointing to the beginning | 126 | * @return iterator pointing to the beginning |
127 | */ | 127 | */ |
128 | const struct GNUNET_CONTAINER_SList_Iterator * | 128 | struct GNUNET_CONTAINER_SList_Iterator * |
129 | GNUNET_CONTAINER_slist_begin (const struct GNUNET_CONTAINER_SList *l) | 129 | GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l) |
130 | { | 130 | { |
131 | struct GNUNET_CONTAINER_SList_Iterator *ret; | 131 | struct GNUNET_CONTAINER_SList_Iterator *ret; |
132 | 132 | ||
133 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Iterator)); | 133 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Iterator)); |
134 | ret->elem = l->head.next; | 134 | ret->elem = l->head; |
135 | ret->last = (struct GNUNET_CONTAINER_SList_Elem *) &l->head; | 135 | ret->list = l; |
136 | return ret; | 136 | return ret; |
137 | } | 137 | } |
138 | 138 | ||
139 | |||
139 | /** | 140 | /** |
140 | * Clear a list | 141 | * Clear a list |
141 | * @param l list | 142 | * @param l list |
@@ -143,22 +144,24 @@ GNUNET_CONTAINER_slist_begin (const struct GNUNET_CONTAINER_SList *l) | |||
143 | void | 144 | void |
144 | GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l) | 145 | GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l) |
145 | { | 146 | { |
146 | struct GNUNET_CONTAINER_SList_Elem *e, *n; | 147 | struct GNUNET_CONTAINER_SList_Elem *e; |
148 | struct GNUNET_CONTAINER_SList_Elem *n; | ||
147 | 149 | ||
148 | e = l->head.next; | 150 | e = l->head; |
149 | while (e != NULL) | 151 | while (e != NULL) |
150 | { | 152 | { |
151 | if (e->disp != GNUNET_MEM_DISP_STATIC) | ||
152 | GNUNET_free (e->elem); | ||
153 | n = e->next; | 153 | n = e->next; |
154 | GNUNET_free (e); | 154 | GNUNET_free (e); |
155 | e = n; | 155 | e = n; |
156 | } | 156 | } |
157 | l->head.next = NULL; | 157 | l->head = NULL; |
158 | l->length = 0; | ||
158 | } | 159 | } |
159 | 160 | ||
161 | |||
160 | /** | 162 | /** |
161 | * Check if a list contains a certain element | 163 | * Check if a list contains a certain element |
164 | * | ||
162 | * @param l list | 165 | * @param l list |
163 | * @param buf payload buffer to find | 166 | * @param buf payload buffer to find |
164 | * @param lenght of the payload | 167 | * @param lenght of the payload |
@@ -169,13 +172,14 @@ GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l, | |||
169 | { | 172 | { |
170 | struct GNUNET_CONTAINER_SList_Elem *e; | 173 | struct GNUNET_CONTAINER_SList_Elem *e; |
171 | 174 | ||
172 | for (e = l->head.next; e != NULL; e = e->next) | 175 | for (e = l->head; e != NULL; e = e->next) |
173 | if (e->len == len && memcmp (buf, e->elem, len) == 0) | 176 | if ( (e->len == len) && |
177 | (memcmp (buf, e->elem, len) == 0) ) | ||
174 | return GNUNET_YES; | 178 | return GNUNET_YES; |
175 | |||
176 | return GNUNET_NO; | 179 | return GNUNET_NO; |
177 | } | 180 | } |
178 | 181 | ||
182 | |||
179 | /** | 183 | /** |
180 | * Count the elements of a list | 184 | * Count the elements of a list |
181 | * @param l list | 185 | * @param l list |
@@ -184,17 +188,13 @@ GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l, | |||
184 | int | 188 | int |
185 | GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l) | 189 | GNUNET_CONTAINER_slist_count (const struct GNUNET_CONTAINER_SList *l) |
186 | { | 190 | { |
187 | int n; | 191 | return l->length; |
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 | } | 192 | } |
195 | 193 | ||
194 | |||
196 | /** | 195 | /** |
197 | * Remove an element from the list | 196 | * Remove an element from the list |
197 | * | ||
198 | * @param i iterator that points to the element to be removed | 198 | * @param i iterator that points to the element to be removed |
199 | */ | 199 | */ |
200 | void | 200 | void |
@@ -203,13 +203,16 @@ GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i) | |||
203 | struct GNUNET_CONTAINER_SList_Elem *next; | 203 | struct GNUNET_CONTAINER_SList_Elem *next; |
204 | 204 | ||
205 | next = i->elem->next; | 205 | next = i->elem->next; |
206 | i->last->next = next; | 206 | if (i->last != NULL) |
207 | if (i->elem->disp != GNUNET_MEM_DISP_STATIC) | 207 | i->last->next = next; |
208 | GNUNET_free (i->elem->elem); | 208 | else |
209 | i->list->head = next; | ||
209 | GNUNET_free (i->elem); | 210 | GNUNET_free (i->elem); |
211 | i->list->length--; | ||
210 | i->elem = next; | 212 | i->elem = next; |
211 | } | 213 | } |
212 | 214 | ||
215 | |||
213 | /** | 216 | /** |
214 | * Insert an element into a list at a specific position | 217 | * Insert an element into a list at a specific position |
215 | * @param before where to insert the new element | 218 | * @param before where to insert the new element |
@@ -225,9 +228,14 @@ GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before, | |||
225 | 228 | ||
226 | e = create_elem (disp, buf, len); | 229 | e = create_elem (disp, buf, len); |
227 | e->next = before->elem; | 230 | e->next = before->elem; |
228 | before->last->next = e; | 231 | if (before->last != NULL) |
232 | before->last->next = e; | ||
233 | else | ||
234 | before->list->head = e; | ||
235 | before->list->length++; | ||
229 | } | 236 | } |
230 | 237 | ||
238 | |||
231 | /** | 239 | /** |
232 | * Advance an iterator to the next element | 240 | * Advance an iterator to the next element |
233 | * @param i iterator | 241 | * @param i iterator |
@@ -239,11 +247,13 @@ GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i) | |||
239 | i->last = i->elem; | 247 | i->last = i->elem; |
240 | i->elem = i->elem->next; | 248 | i->elem = i->elem->next; |
241 | 249 | ||
242 | return i->elem != NULL; | 250 | return (i->elem != NULL) ? GNUNET_YES : GNUNET_NO; |
243 | } | 251 | } |
244 | 252 | ||
253 | |||
245 | /** | 254 | /** |
246 | * Check if an iterator points beyond the end of a list | 255 | * Check if an iterator points beyond the end of a list |
256 | * | ||
247 | * @param i iterator | 257 | * @param i iterator |
248 | * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator | 258 | * @return GNUNET_YES if the end has been reached, GNUNET_NO if the iterator |
249 | * points to a valid element | 259 | * points to a valid element |
@@ -251,16 +261,17 @@ GNUNET_CONTAINER_slist_next (struct GNUNET_CONTAINER_SList_Iterator *i) | |||
251 | int | 261 | int |
252 | GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i) | 262 | GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i) |
253 | { | 263 | { |
254 | return i->elem == NULL; | 264 | return (i->elem == NULL) ? GNUNET_YES : GNUNET_NO; |
255 | } | 265 | } |
256 | 266 | ||
267 | |||
257 | /** | 268 | /** |
258 | * Retrieve the element at a specific position in a list | 269 | * Retrieve the element at a specific position in a list |
259 | * @param i iterator | 270 | * @param i iterator |
260 | * @param len payload length | 271 | * @param len payload length |
261 | * @return payload | 272 | * @return payload |
262 | */ | 273 | */ |
263 | void * | 274 | const void * |
264 | GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i, | 275 | GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i, |
265 | size_t * len) | 276 | size_t * len) |
266 | { | 277 | { |
@@ -268,3 +279,5 @@ GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i, | |||
268 | *len = i->elem->len; | 279 | *len = i->elem->len; |
269 | return i->elem->elem; | 280 | return i->elem->elem; |
270 | } | 281 | } |
282 | |||
283 | /* end of container_slist.c */ | ||