b606324e56f96b5510a48f10f7a27d4a30db57a0
1 /*
2 * SysDB - src/utils/llist.c
3 * Copyright (C) 2012 Sebastian 'tokkee' Harl <sh@tokkee.org>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
17 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
19 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
22 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
23 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
24 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
25 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
28 #include "utils/llist.h"
30 #include <assert.h>
31 #include <stdlib.h>
32 #include <strings.h>
34 #include <pthread.h>
36 /*
37 * private data types
38 */
40 struct sdb_llist_elem;
41 typedef struct sdb_llist_elem sdb_llist_elem_t;
43 struct sdb_llist_elem {
44 sdb_object_t *obj;
46 sdb_llist_elem_t *next;
47 sdb_llist_elem_t *prev;
48 };
50 struct sdb_llist {
51 pthread_rwlock_t lock;
53 sdb_llist_elem_t *head;
54 sdb_llist_elem_t *tail;
56 size_t length;
57 };
59 struct sdb_llist_iter {
60 sdb_llist_t *list;
61 sdb_llist_elem_t *elem;
62 };
64 /*
65 * private helper functions
66 */
68 /* Insert a new element after 'elem'. If 'elem' is NULL, insert at the head of
69 * the list. */
70 static int
71 sdb_llist_insert_after(sdb_llist_t *list, sdb_llist_elem_t *elem,
72 sdb_object_t *obj)
73 {
74 sdb_llist_elem_t *new;
76 assert(list);
78 new = malloc(sizeof(*new));
79 if (! new)
80 return -1;
82 new->obj = obj;
83 if (elem)
84 new->next = elem->next;
85 else if (list->head)
86 new->next = list->head;
87 else
88 new->next = NULL;
89 new->prev = elem;
91 if (elem) {
92 if (elem->next)
93 elem->next->prev = new;
94 else
95 list->tail = new;
96 elem->next = new;
97 }
98 else {
99 /* new entry will be new head */
100 if (list->head)
101 list->head->prev = new;
103 list->head = new;
104 if (! list->tail)
105 list->tail = new;
106 }
108 assert(list->head && list->tail);
109 if (! list->length) {
110 assert(list->head == list->tail);
111 }
113 sdb_object_ref(obj);
114 ++list->length;
115 return 0;
116 } /* sdb_llist_insert_after */
118 static sdb_object_t *
119 sdb_llist_remove_elem(sdb_llist_t *list, sdb_llist_elem_t *elem)
120 {
121 sdb_object_t *obj;
123 assert(list && elem);
125 obj = elem->obj;
127 if (elem->prev)
128 elem->prev->next = elem->next;
129 else {
130 assert(elem == list->head);
131 list->head = elem->next;
132 }
134 if (elem->next)
135 elem->next->prev = elem->prev;
136 else {
137 assert(elem == list->tail);
138 list->tail = elem->prev;
139 }
141 elem->prev = elem->next = NULL;
142 free(elem);
144 --list->length;
145 return obj;
146 } /* sdb_llist_remove_elem */
148 /*
149 * public API
150 */
152 sdb_llist_t *
153 sdb_llist_create(void)
154 {
155 sdb_llist_t *list;
157 list = malloc(sizeof(*list));
158 if (! list)
159 return NULL;
161 pthread_rwlock_init(&list->lock, /* attr = */ NULL);
163 list->head = list->tail = NULL;
164 list->length = 0;
165 return list;
166 } /* sdb_llist_create */
168 sdb_llist_t *
169 sdb_llist_clone(sdb_llist_t *list)
170 {
171 sdb_llist_t *new;
172 sdb_llist_elem_t *elem;
174 if (! list)
175 return NULL;
177 new = sdb_llist_create();
178 if (! new)
179 return NULL;
181 if (! list->length) {
182 assert((! list->head) && (! list->tail));
183 return new;
184 }
186 for (elem = list->head; elem; elem = elem->next) {
187 if (sdb_llist_append(new, elem->obj)) {
188 sdb_llist_destroy(new);
189 return NULL;
190 }
191 }
192 return new;
193 } /* sdb_llist_clone */
195 void
196 sdb_llist_destroy(sdb_llist_t *list)
197 {
198 sdb_llist_elem_t *elem;
200 if (! list)
201 return;
203 pthread_rwlock_wrlock(&list->lock);
205 elem = list->head;
206 while (elem) {
207 sdb_llist_elem_t *tmp = elem->next;
209 sdb_object_deref(elem->obj);
210 free(elem);
212 elem = tmp;
213 }
215 list->head = list->tail = NULL;
216 list->length = 0;
218 pthread_rwlock_unlock(&list->lock);
219 pthread_rwlock_destroy(&list->lock);
220 free(list);
221 } /* sdb_llist_destroy */
223 int
224 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
225 {
226 int status;
228 if ((! list) || (! obj))
229 return -1;
231 pthread_rwlock_wrlock(&list->lock);
232 status = sdb_llist_insert_after(list, list->tail, obj);
233 pthread_rwlock_unlock(&list->lock);
234 return status;
235 } /* sdb_llist_append */
237 int
238 sdb_llist_insert(sdb_llist_t *list, sdb_object_t *obj, size_t idx)
239 {
240 sdb_llist_elem_t *prev;
241 sdb_llist_elem_t *next;
243 int status;
245 size_t i;
247 if ((! list) || (! obj) || (idx > list->length))
248 return -1;
250 pthread_rwlock_wrlock(&list->lock);
252 prev = NULL;
253 next = list->head;
255 for (i = 0; i < idx; ++i) {
256 prev = next;
257 next = next->next;
258 }
259 status = sdb_llist_insert_after(list, prev, obj);
260 pthread_rwlock_unlock(&list->lock);
261 return status;
262 } /* sdb_llist_insert */
264 int
265 sdb_llist_insert_sorted(sdb_llist_t *list, sdb_object_t *obj,
266 int (*compare)(const sdb_object_t *, const sdb_object_t *))
267 {
268 sdb_llist_elem_t *prev;
269 sdb_llist_elem_t *next;
271 int status;
273 if ((! list) || (! obj) || (! compare))
274 return -1;
276 pthread_rwlock_wrlock(&list->lock);
278 prev = NULL;
279 next = list->head;
281 while (next) {
282 if (compare(obj, next->obj) < 0)
283 break;
285 prev = next;
286 next = next->next;
287 }
288 status = sdb_llist_insert_after(list, prev, obj);
289 pthread_rwlock_unlock(&list->lock);
290 return status;
291 } /* sdb_llist_insert_sorted */
293 sdb_object_t *
294 sdb_llist_search(sdb_llist_t *list, const sdb_object_t *key,
295 int (*compare)(const sdb_object_t *, const sdb_object_t *))
296 {
297 sdb_llist_elem_t *elem;
299 if ((! list) || (! compare))
300 return NULL;
302 pthread_rwlock_rdlock(&list->lock);
304 for (elem = list->head; elem; elem = elem->next)
305 if (! compare(elem->obj, key))
306 break;
308 pthread_rwlock_unlock(&list->lock);
310 if (elem)
311 return elem->obj;
312 return NULL;
313 } /* sdb_llist_search */
315 sdb_object_t *
316 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
317 {
318 sdb_llist_elem_t *elem;
320 if (! list)
321 return NULL;
323 pthread_rwlock_rdlock(&list->lock);
325 for (elem = list->head; elem; elem = elem->next)
326 if (! strcasecmp(elem->obj->name, key))
327 break;
329 pthread_rwlock_unlock(&list->lock);
331 if (elem)
332 return elem->obj;
333 return NULL;
334 } /* sdb_llist_search_by_name */
336 sdb_object_t *
337 sdb_llist_shift(sdb_llist_t *list)
338 {
339 sdb_object_t *obj;
341 if ((! list) || (! list->head))
342 return NULL;
344 pthread_rwlock_wrlock(&list->lock);
345 obj = sdb_llist_remove_elem(list, list->head);
346 pthread_rwlock_unlock(&list->lock);
347 return obj;
348 } /* sdb_llist_shift */
350 sdb_llist_iter_t *
351 sdb_llist_get_iter(sdb_llist_t *list)
352 {
353 sdb_llist_iter_t *iter;
355 if (! list)
356 return NULL;
358 iter = malloc(sizeof(*iter));
359 if (! iter)
360 return NULL;
362 pthread_rwlock_rdlock(&list->lock);
364 iter->list = list;
365 iter->elem = list->head;
367 /* XXX: keep lock until destroying the iterator? */
368 pthread_rwlock_unlock(&list->lock);
369 return iter;
370 } /* sdb_llist_get_iter */
372 void
373 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
374 {
375 if (! iter)
376 return;
378 iter->list = NULL;
379 iter->elem = NULL;
380 free(iter);
381 } /* sdb_llist_iter_destroy */
383 _Bool
384 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
385 {
386 if (! iter)
387 return 0;
388 return iter->elem != NULL;
389 } /* sdb_llist_iter_has_next */
391 sdb_object_t *
392 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
393 {
394 sdb_object_t *obj;
396 if ((! iter) || (! iter->elem))
397 return NULL;
399 pthread_rwlock_rdlock(&iter->list->lock);
401 obj = iter->elem->obj;
402 iter->elem = iter->elem->next;
404 pthread_rwlock_unlock(&iter->list->lock);
405 return obj;
406 } /* sdb_llist_iter_get_next */
408 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */