069c14eee204c6f6570286dc0d9a46532a5f747b
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 /* Insert a new element after 'elem'. If 'elem' is NULL, insert at the head of
73 * the list. */
74 static int
75 sdb_llist_insert_after(sdb_llist_t *list, sdb_llist_elem_t *elem,
76 sdb_object_t *obj)
77 {
78 sdb_llist_elem_t *new;
80 assert(list);
82 new = malloc(sizeof(*new));
83 if (! new)
84 return -1;
86 new->obj = obj;
87 if (elem)
88 new->next = elem->next;
89 else if (list->head)
90 new->next = list->head;
91 else
92 new->next = NULL;
93 new->prev = elem;
95 if (elem) {
96 if (elem->next)
97 elem->next->prev = new;
98 else
99 list->tail = new;
100 elem->next = new;
101 }
102 else {
103 /* new entry will be new head */
104 if (list->head)
105 list->head->prev = new;
107 list->head = new;
108 if (! list->tail)
109 list->tail = new;
110 }
112 assert(list->head && list->tail);
113 if (! list->length) {
114 assert(list->head == list->tail);
115 }
117 sdb_object_ref(obj);
118 ++list->length;
119 return 0;
120 } /* sdb_llist_insert_after */
122 static sdb_llist_elem_t *
123 llist_search(sdb_llist_t *list,
124 sdb_llist_lookup_cb lookup, const void *user_data)
125 {
126 sdb_llist_elem_t *elem;
128 assert(list && lookup);
130 for (elem = list->head; elem; elem = elem->next)
131 if (! lookup(elem->obj, user_data))
132 break;
133 return elem;
134 } /* llist_search */
136 static sdb_object_t *
137 sdb_llist_remove_elem(sdb_llist_t *list, sdb_llist_elem_t *elem)
138 {
139 sdb_object_t *obj;
141 assert(list && elem);
143 obj = elem->obj;
145 if (elem->prev)
146 elem->prev->next = elem->next;
147 else {
148 assert(elem == list->head);
149 list->head = elem->next;
150 }
152 if (elem->next)
153 elem->next->prev = elem->prev;
154 else {
155 assert(elem == list->tail);
156 list->tail = elem->prev;
157 }
159 elem->prev = elem->next = NULL;
160 free(elem);
162 --list->length;
163 return obj;
164 } /* sdb_llist_remove_elem */
166 /*
167 * public API
168 */
170 sdb_llist_t *
171 sdb_llist_create(void)
172 {
173 sdb_llist_t *list;
175 list = malloc(sizeof(*list));
176 if (! list)
177 return NULL;
179 pthread_rwlock_init(&list->lock, /* attr = */ NULL);
181 list->head = list->tail = NULL;
182 list->length = 0;
183 return list;
184 } /* sdb_llist_create */
186 sdb_llist_t *
187 sdb_llist_clone(sdb_llist_t *list)
188 {
189 sdb_llist_t *new;
190 sdb_llist_elem_t *elem;
192 if (! list)
193 return NULL;
195 new = sdb_llist_create();
196 if (! new)
197 return NULL;
199 if (! list->length) {
200 assert((! list->head) && (! list->tail));
201 return new;
202 }
204 for (elem = list->head; elem; elem = elem->next) {
205 if (sdb_llist_append(new, elem->obj)) {
206 sdb_llist_destroy(new);
207 return NULL;
208 }
209 }
210 return new;
211 } /* sdb_llist_clone */
213 void
214 sdb_llist_destroy(sdb_llist_t *list)
215 {
216 sdb_llist_elem_t *elem;
218 if (! list)
219 return;
221 pthread_rwlock_wrlock(&list->lock);
223 elem = list->head;
224 while (elem) {
225 sdb_llist_elem_t *tmp = elem->next;
227 sdb_object_deref(elem->obj);
228 free(elem);
230 elem = tmp;
231 }
233 list->head = list->tail = NULL;
234 list->length = 0;
236 pthread_rwlock_unlock(&list->lock);
237 pthread_rwlock_destroy(&list->lock);
238 free(list);
239 } /* sdb_llist_destroy */
241 int
242 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
243 {
244 int status;
246 if ((! list) || (! obj))
247 return -1;
249 pthread_rwlock_wrlock(&list->lock);
250 status = sdb_llist_insert_after(list, list->tail, obj);
251 pthread_rwlock_unlock(&list->lock);
252 return status;
253 } /* sdb_llist_append */
255 int
256 sdb_llist_insert(sdb_llist_t *list, sdb_object_t *obj, size_t idx)
257 {
258 sdb_llist_elem_t *prev;
259 sdb_llist_elem_t *next;
261 int status;
263 size_t i;
265 if ((! list) || (! obj) || (idx > list->length))
266 return -1;
268 pthread_rwlock_wrlock(&list->lock);
270 prev = NULL;
271 next = list->head;
273 for (i = 0; i < idx; ++i) {
274 prev = next;
275 next = next->next;
276 }
277 status = sdb_llist_insert_after(list, prev, obj);
278 pthread_rwlock_unlock(&list->lock);
279 return status;
280 } /* sdb_llist_insert */
282 int
283 sdb_llist_insert_sorted(sdb_llist_t *list,
284 sdb_object_t *obj, sdb_llist_cmp_cb compare)
285 {
286 sdb_llist_elem_t *prev;
287 sdb_llist_elem_t *next;
289 int status;
291 if ((! list) || (! obj) || (! compare))
292 return -1;
294 pthread_rwlock_wrlock(&list->lock);
296 prev = NULL;
297 next = list->head;
299 while (next) {
300 if (compare(obj, next->obj) < 0)
301 break;
303 prev = next;
304 next = next->next;
305 }
306 status = sdb_llist_insert_after(list, prev, obj);
307 pthread_rwlock_unlock(&list->lock);
308 return status;
309 } /* sdb_llist_insert_sorted */
311 sdb_object_t *
312 sdb_llist_get(sdb_llist_t *list, size_t i)
313 {
314 sdb_llist_elem_t *elem;
315 size_t j;
317 if ((! list) || (i >= list->length))
318 return NULL;
320 for (elem = list->head, j = 0; j < i; elem = elem->next, ++j)
321 /* iterate */;
323 assert(elem);
324 sdb_object_ref(elem->obj);
325 return elem->obj;
326 } /* sdb_llist_get */
328 sdb_object_t *
329 sdb_llist_search(sdb_llist_t *list,
330 sdb_llist_lookup_cb lookup, const void *user_data)
331 {
332 sdb_llist_elem_t *elem;
334 if ((! list) || (! lookup))
335 return NULL;
337 pthread_rwlock_rdlock(&list->lock);
338 elem = llist_search(list, lookup, user_data);
339 pthread_rwlock_unlock(&list->lock);
341 if (elem)
342 return elem->obj;
343 return NULL;
344 } /* sdb_llist_search */
346 sdb_object_t *
347 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
348 {
349 sdb_llist_elem_t *elem;
351 if (! list)
352 return NULL;
354 pthread_rwlock_rdlock(&list->lock);
356 for (elem = list->head; elem; elem = elem->next)
357 if (! strcasecmp(elem->obj->name, key))
358 break;
360 pthread_rwlock_unlock(&list->lock);
362 if (elem)
363 return elem->obj;
364 return NULL;
365 } /* sdb_llist_search_by_name */
367 sdb_object_t *
368 sdb_llist_remove(sdb_llist_t *list,
369 sdb_llist_lookup_cb lookup, const void *user_data)
370 {
371 sdb_llist_elem_t *elem;
372 sdb_object_t *obj = NULL;
374 if ((! list) || (! lookup))
375 return NULL;
377 pthread_rwlock_wrlock(&list->lock);
378 elem = llist_search(list, lookup, user_data);
379 if (elem)
380 obj = sdb_llist_remove_elem(list, elem);
381 pthread_rwlock_unlock(&list->lock);
383 return obj;
384 } /* sdb_llist_remove */
386 sdb_object_t *
387 sdb_llist_remove_by_name(sdb_llist_t *list, const char *key)
388 {
389 sdb_llist_elem_t *elem;
390 sdb_object_t *obj = NULL;
392 if (! list)
393 return NULL;
395 pthread_rwlock_rdlock(&list->lock);
397 for (elem = list->head; elem; elem = elem->next)
398 if ((key == elem->obj->name)
399 || (! strcasecmp(elem->obj->name, key)))
400 break;
402 if (elem)
403 obj = sdb_llist_remove_elem(list, elem);
404 pthread_rwlock_unlock(&list->lock);
406 return obj;
407 } /* sdb_llist_remove_by_name */
409 sdb_object_t *
410 sdb_llist_shift(sdb_llist_t *list)
411 {
412 sdb_object_t *obj;
414 if ((! list) || (! list->head))
415 return NULL;
417 pthread_rwlock_wrlock(&list->lock);
418 obj = sdb_llist_remove_elem(list, list->head);
419 pthread_rwlock_unlock(&list->lock);
420 return obj;
421 } /* sdb_llist_shift */
423 sdb_llist_iter_t *
424 sdb_llist_get_iter(sdb_llist_t *list)
425 {
426 sdb_llist_iter_t *iter;
428 if (! list)
429 return NULL;
431 iter = malloc(sizeof(*iter));
432 if (! iter)
433 return NULL;
435 pthread_rwlock_rdlock(&list->lock);
437 iter->list = list;
438 iter->elem = list->head;
440 /* XXX: keep lock until destroying the iterator? */
441 pthread_rwlock_unlock(&list->lock);
442 return iter;
443 } /* sdb_llist_get_iter */
445 void
446 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
447 {
448 if (! iter)
449 return;
451 iter->list = NULL;
452 iter->elem = NULL;
453 free(iter);
454 } /* sdb_llist_iter_destroy */
456 _Bool
457 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
458 {
459 if (! iter)
460 return 0;
461 return iter->elem != NULL;
462 } /* sdb_llist_iter_has_next */
464 sdb_object_t *
465 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
466 {
467 sdb_object_t *obj;
469 if ((! iter) || (! iter->elem))
470 return NULL;
472 pthread_rwlock_rdlock(&iter->list->lock);
474 /* XXX: increment ref-cnt for this object?
475 * also: when letting an element take ownership of next and prev
476 * elements, this might be a fairly cheap way to implement a weak
477 * type of snapshotting */
479 obj = iter->elem->obj;
480 iter->elem = iter->elem->next;
482 pthread_rwlock_unlock(&iter->list->lock);
483 return obj;
484 } /* sdb_llist_iter_get_next */
486 int
487 sdb_llist_iter_remove_current(sdb_llist_iter_t *iter)
488 {
489 sdb_llist_elem_t *elem;
491 if ((! iter) || (! iter->list))
492 return -1;
494 pthread_rwlock_wrlock(&iter->list->lock);
496 if (! iter->elem) /* reached end of list */
497 elem = iter->list->tail;
498 else
499 elem = iter->elem->prev;
500 if (elem)
501 sdb_llist_remove_elem(iter->list, elem);
503 pthread_rwlock_unlock(&iter->list->lock);
505 if (! elem)
506 return -1;
507 return 0;
508 } /* sdb_llist_iter_remove */
510 size_t
511 sdb_llist_len(sdb_llist_t *list)
512 {
513 if (! list)
514 return 0;
515 return list->length;
516 } /* sdb_llist_len */
518 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */