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 #if HAVE_CONFIG_H
29 # include "config.h"
30 #endif /* HAVE_CONFIG_H */
32 #include "utils/llist.h"
34 #include <assert.h>
35 #include <stdlib.h>
36 #include <strings.h>
38 #include <pthread.h>
40 /*
41 * private data types
42 */
44 struct sdb_llist_elem;
45 typedef struct sdb_llist_elem sdb_llist_elem_t;
47 struct sdb_llist_elem {
48 sdb_object_t *obj;
50 sdb_llist_elem_t *next;
51 sdb_llist_elem_t *prev;
52 };
54 struct sdb_llist {
55 pthread_rwlock_t lock;
57 sdb_llist_elem_t *head;
58 sdb_llist_elem_t *tail;
60 size_t length;
61 };
63 struct sdb_llist_iter {
64 sdb_llist_t *list;
65 sdb_llist_elem_t *elem;
66 };
68 /*
69 * private helper functions
70 */
72 static void
73 llist_clear(sdb_llist_t *list)
74 {
75 sdb_llist_elem_t *elem;
77 assert(list);
78 elem = list->head;
79 while (elem) {
80 sdb_llist_elem_t *tmp = elem->next;
82 sdb_object_deref(elem->obj);
83 free(elem);
85 elem = tmp;
86 }
88 list->head = list->tail = NULL;
89 list->length = 0;
90 } /* llist_clear */
92 /* Insert a new element after 'elem'. If 'elem' is NULL, insert at the head of
93 * the list. */
94 static int
95 llist_insert_after(sdb_llist_t *list, sdb_llist_elem_t *elem,
96 sdb_object_t *obj)
97 {
98 sdb_llist_elem_t *new;
100 assert(list);
102 new = malloc(sizeof(*new));
103 if (! new)
104 return -1;
106 new->obj = obj;
107 if (elem)
108 new->next = elem->next;
109 else if (list->head)
110 new->next = list->head;
111 else
112 new->next = NULL;
113 new->prev = elem;
115 if (elem) {
116 if (elem->next)
117 elem->next->prev = new;
118 else
119 list->tail = new;
120 elem->next = new;
121 }
122 else {
123 /* new entry will be new head */
124 if (list->head)
125 list->head->prev = new;
127 list->head = new;
128 if (! list->tail)
129 list->tail = new;
130 }
132 assert(list->head && list->tail);
133 if (! list->length) {
134 assert(list->head == list->tail);
135 }
137 sdb_object_ref(obj);
138 ++list->length;
139 return 0;
140 } /* llist_insert_after */
142 static sdb_llist_elem_t *
143 llist_search(sdb_llist_t *list,
144 sdb_llist_lookup_cb lookup, const void *user_data)
145 {
146 sdb_llist_elem_t *elem;
148 assert(list && lookup);
150 for (elem = list->head; elem; elem = elem->next)
151 if (! lookup(elem->obj, user_data))
152 break;
153 return elem;
154 } /* llist_search */
156 static sdb_object_t *
157 llist_remove_elem(sdb_llist_t *list, sdb_llist_elem_t *elem)
158 {
159 sdb_object_t *obj;
161 assert(list && elem);
163 obj = elem->obj;
165 if (elem->prev)
166 elem->prev->next = elem->next;
167 else {
168 assert(elem == list->head);
169 list->head = elem->next;
170 }
172 if (elem->next)
173 elem->next->prev = elem->prev;
174 else {
175 assert(elem == list->tail);
176 list->tail = elem->prev;
177 }
179 elem->prev = elem->next = NULL;
180 free(elem);
182 --list->length;
183 return obj;
184 } /* llist_remove_elem */
186 /*
187 * public API
188 */
190 sdb_llist_t *
191 sdb_llist_create(void)
192 {
193 sdb_llist_t *list;
195 list = malloc(sizeof(*list));
196 if (! list)
197 return NULL;
199 pthread_rwlock_init(&list->lock, /* attr = */ NULL);
201 list->head = list->tail = NULL;
202 list->length = 0;
203 return list;
204 } /* sdb_llist_create */
206 sdb_llist_t *
207 sdb_llist_clone(sdb_llist_t *list)
208 {
209 sdb_llist_t *new;
210 sdb_llist_elem_t *elem;
212 if (! list)
213 return NULL;
215 new = sdb_llist_create();
216 if (! new)
217 return NULL;
219 if (! list->length) {
220 assert((! list->head) && (! list->tail));
221 return new;
222 }
224 for (elem = list->head; elem; elem = elem->next) {
225 if (sdb_llist_append(new, elem->obj)) {
226 sdb_llist_destroy(new);
227 return NULL;
228 }
229 }
230 return new;
231 } /* sdb_llist_clone */
233 void
234 sdb_llist_destroy(sdb_llist_t *list)
235 {
236 if (! list)
237 return;
239 pthread_rwlock_wrlock(&list->lock);
240 llist_clear(list);
241 pthread_rwlock_unlock(&list->lock);
242 pthread_rwlock_destroy(&list->lock);
243 free(list);
244 } /* sdb_llist_destroy */
246 void
247 sdb_llist_clear(sdb_llist_t *list)
248 {
249 if (! list)
250 return;
252 pthread_rwlock_wrlock(&list->lock);
253 llist_clear(list);
254 pthread_rwlock_unlock(&list->lock);
255 } /* sdb_llist_clear */
257 int
258 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
259 {
260 int status;
262 if ((! list) || (! obj))
263 return -1;
265 pthread_rwlock_wrlock(&list->lock);
266 status = llist_insert_after(list, list->tail, obj);
267 pthread_rwlock_unlock(&list->lock);
268 return status;
269 } /* sdb_llist_append */
271 int
272 sdb_llist_insert(sdb_llist_t *list, sdb_object_t *obj, size_t idx)
273 {
274 sdb_llist_elem_t *prev;
275 sdb_llist_elem_t *next;
277 int status;
279 size_t i;
281 if ((! list) || (! obj) || (idx > list->length))
282 return -1;
284 pthread_rwlock_wrlock(&list->lock);
286 prev = NULL;
287 next = list->head;
289 for (i = 0; i < idx; ++i) {
290 prev = next;
291 next = next->next;
292 }
293 status = llist_insert_after(list, prev, obj);
294 pthread_rwlock_unlock(&list->lock);
295 return status;
296 } /* sdb_llist_insert */
298 int
299 sdb_llist_insert_sorted(sdb_llist_t *list,
300 sdb_object_t *obj, sdb_llist_cmp_cb compare)
301 {
302 sdb_llist_elem_t *prev;
303 sdb_llist_elem_t *next;
305 int status;
307 if ((! list) || (! obj) || (! compare))
308 return -1;
310 pthread_rwlock_wrlock(&list->lock);
312 prev = NULL;
313 next = list->head;
315 while (next) {
316 if (compare(obj, next->obj) < 0)
317 break;
319 prev = next;
320 next = next->next;
321 }
322 status = llist_insert_after(list, prev, obj);
323 pthread_rwlock_unlock(&list->lock);
324 return status;
325 } /* sdb_llist_insert_sorted */
327 sdb_object_t *
328 sdb_llist_get(sdb_llist_t *list, size_t i)
329 {
330 sdb_llist_elem_t *elem;
331 size_t j;
333 if ((! list) || (i >= list->length))
334 return NULL;
336 for (elem = list->head, j = 0; j < i; elem = elem->next, ++j)
337 /* iterate */;
339 assert(elem);
340 sdb_object_ref(elem->obj);
341 return elem->obj;
342 } /* sdb_llist_get */
344 sdb_object_t *
345 sdb_llist_search(sdb_llist_t *list,
346 sdb_llist_lookup_cb lookup, const void *user_data)
347 {
348 sdb_llist_elem_t *elem;
350 if ((! list) || (! lookup))
351 return NULL;
353 pthread_rwlock_rdlock(&list->lock);
354 elem = llist_search(list, lookup, user_data);
355 pthread_rwlock_unlock(&list->lock);
357 if (elem)
358 return elem->obj;
359 return NULL;
360 } /* sdb_llist_search */
362 sdb_object_t *
363 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
364 {
365 sdb_llist_elem_t *elem;
367 if (! list)
368 return NULL;
370 pthread_rwlock_rdlock(&list->lock);
372 for (elem = list->head; elem; elem = elem->next)
373 if (! strcasecmp(elem->obj->name, key))
374 break;
376 pthread_rwlock_unlock(&list->lock);
378 if (elem)
379 return elem->obj;
380 return NULL;
381 } /* sdb_llist_search_by_name */
383 sdb_object_t *
384 sdb_llist_remove(sdb_llist_t *list,
385 sdb_llist_lookup_cb lookup, const void *user_data)
386 {
387 sdb_llist_elem_t *elem;
388 sdb_object_t *obj = NULL;
390 if ((! list) || (! lookup))
391 return NULL;
393 pthread_rwlock_wrlock(&list->lock);
394 elem = llist_search(list, lookup, user_data);
395 if (elem)
396 obj = llist_remove_elem(list, elem);
397 pthread_rwlock_unlock(&list->lock);
399 return obj;
400 } /* sdb_llist_remove */
402 sdb_object_t *
403 sdb_llist_remove_by_name(sdb_llist_t *list, const char *key)
404 {
405 sdb_llist_elem_t *elem;
406 sdb_object_t *obj = NULL;
408 if (! list)
409 return NULL;
411 pthread_rwlock_rdlock(&list->lock);
413 for (elem = list->head; elem; elem = elem->next)
414 if ((key == elem->obj->name)
415 || (! strcasecmp(elem->obj->name, key)))
416 break;
418 if (elem)
419 obj = llist_remove_elem(list, elem);
420 pthread_rwlock_unlock(&list->lock);
422 return obj;
423 } /* sdb_llist_remove_by_name */
425 sdb_object_t *
426 sdb_llist_shift(sdb_llist_t *list)
427 {
428 sdb_object_t *obj;
430 if ((! list) || (! list->head))
431 return NULL;
433 pthread_rwlock_wrlock(&list->lock);
434 obj = llist_remove_elem(list, list->head);
435 pthread_rwlock_unlock(&list->lock);
436 return obj;
437 } /* sdb_llist_shift */
439 sdb_llist_iter_t *
440 sdb_llist_get_iter(sdb_llist_t *list)
441 {
442 sdb_llist_iter_t *iter;
444 if (! list)
445 return NULL;
447 iter = malloc(sizeof(*iter));
448 if (! iter)
449 return NULL;
451 pthread_rwlock_rdlock(&list->lock);
453 iter->list = list;
454 iter->elem = list->head;
456 /* XXX: keep lock until destroying the iterator? */
457 pthread_rwlock_unlock(&list->lock);
458 return iter;
459 } /* sdb_llist_get_iter */
461 void
462 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
463 {
464 if (! iter)
465 return;
467 iter->list = NULL;
468 iter->elem = NULL;
469 free(iter);
470 } /* sdb_llist_iter_destroy */
472 _Bool
473 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
474 {
475 if (! iter)
476 return 0;
477 return iter->elem != NULL;
478 } /* sdb_llist_iter_has_next */
480 sdb_object_t *
481 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
482 {
483 sdb_object_t *obj;
485 if ((! iter) || (! iter->elem))
486 return NULL;
488 pthread_rwlock_rdlock(&iter->list->lock);
490 /* XXX: increment ref-cnt for this object?
491 * also: when letting an element take ownership of next and prev
492 * elements, this might be a fairly cheap way to implement a weak
493 * type of snapshotting */
495 obj = iter->elem->obj;
496 iter->elem = iter->elem->next;
498 pthread_rwlock_unlock(&iter->list->lock);
499 return obj;
500 } /* sdb_llist_iter_get_next */
502 int
503 sdb_llist_iter_remove_current(sdb_llist_iter_t *iter)
504 {
505 sdb_llist_elem_t *elem;
507 if ((! iter) || (! iter->list))
508 return -1;
510 pthread_rwlock_wrlock(&iter->list->lock);
512 if (! iter->elem) /* reached end of list */
513 elem = iter->list->tail;
514 else
515 elem = iter->elem->prev;
516 if (elem)
517 llist_remove_elem(iter->list, elem);
519 pthread_rwlock_unlock(&iter->list->lock);
521 if (! elem)
522 return -1;
523 return 0;
524 } /* sdb_llist_iter_remove */
526 size_t
527 sdb_llist_len(sdb_llist_t *list)
528 {
529 if (! list)
530 return 0;
531 return list->length;
532 } /* sdb_llist_len */
534 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */