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_llist_elem_t *
119 llist_search(sdb_llist_t *list,
120 sdb_llist_lookup_cb lookup, const void *user_data)
121 {
122 sdb_llist_elem_t *elem;
124 assert(list && lookup);
126 for (elem = list->head; elem; elem = elem->next)
127 if (! lookup(elem->obj, user_data))
128 break;
129 return elem;
130 } /* llist_search */
132 static sdb_object_t *
133 sdb_llist_remove_elem(sdb_llist_t *list, sdb_llist_elem_t *elem)
134 {
135 sdb_object_t *obj;
137 assert(list && elem);
139 obj = elem->obj;
141 if (elem->prev)
142 elem->prev->next = elem->next;
143 else {
144 assert(elem == list->head);
145 list->head = elem->next;
146 }
148 if (elem->next)
149 elem->next->prev = elem->prev;
150 else {
151 assert(elem == list->tail);
152 list->tail = elem->prev;
153 }
155 elem->prev = elem->next = NULL;
156 free(elem);
158 --list->length;
159 return obj;
160 } /* sdb_llist_remove_elem */
162 /*
163 * public API
164 */
166 sdb_llist_t *
167 sdb_llist_create(void)
168 {
169 sdb_llist_t *list;
171 list = malloc(sizeof(*list));
172 if (! list)
173 return NULL;
175 pthread_rwlock_init(&list->lock, /* attr = */ NULL);
177 list->head = list->tail = NULL;
178 list->length = 0;
179 return list;
180 } /* sdb_llist_create */
182 sdb_llist_t *
183 sdb_llist_clone(sdb_llist_t *list)
184 {
185 sdb_llist_t *new;
186 sdb_llist_elem_t *elem;
188 if (! list)
189 return NULL;
191 new = sdb_llist_create();
192 if (! new)
193 return NULL;
195 if (! list->length) {
196 assert((! list->head) && (! list->tail));
197 return new;
198 }
200 for (elem = list->head; elem; elem = elem->next) {
201 if (sdb_llist_append(new, elem->obj)) {
202 sdb_llist_destroy(new);
203 return NULL;
204 }
205 }
206 return new;
207 } /* sdb_llist_clone */
209 void
210 sdb_llist_destroy(sdb_llist_t *list)
211 {
212 sdb_llist_elem_t *elem;
214 if (! list)
215 return;
217 pthread_rwlock_wrlock(&list->lock);
219 elem = list->head;
220 while (elem) {
221 sdb_llist_elem_t *tmp = elem->next;
223 sdb_object_deref(elem->obj);
224 free(elem);
226 elem = tmp;
227 }
229 list->head = list->tail = NULL;
230 list->length = 0;
232 pthread_rwlock_unlock(&list->lock);
233 pthread_rwlock_destroy(&list->lock);
234 free(list);
235 } /* sdb_llist_destroy */
237 int
238 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
239 {
240 int status;
242 if ((! list) || (! obj))
243 return -1;
245 pthread_rwlock_wrlock(&list->lock);
246 status = sdb_llist_insert_after(list, list->tail, obj);
247 pthread_rwlock_unlock(&list->lock);
248 return status;
249 } /* sdb_llist_append */
251 int
252 sdb_llist_insert(sdb_llist_t *list, sdb_object_t *obj, size_t idx)
253 {
254 sdb_llist_elem_t *prev;
255 sdb_llist_elem_t *next;
257 int status;
259 size_t i;
261 if ((! list) || (! obj) || (idx > list->length))
262 return -1;
264 pthread_rwlock_wrlock(&list->lock);
266 prev = NULL;
267 next = list->head;
269 for (i = 0; i < idx; ++i) {
270 prev = next;
271 next = next->next;
272 }
273 status = sdb_llist_insert_after(list, prev, obj);
274 pthread_rwlock_unlock(&list->lock);
275 return status;
276 } /* sdb_llist_insert */
278 int
279 sdb_llist_insert_sorted(sdb_llist_t *list,
280 sdb_object_t *obj, sdb_llist_cmp_cb compare)
281 {
282 sdb_llist_elem_t *prev;
283 sdb_llist_elem_t *next;
285 int status;
287 if ((! list) || (! obj) || (! compare))
288 return -1;
290 pthread_rwlock_wrlock(&list->lock);
292 prev = NULL;
293 next = list->head;
295 while (next) {
296 if (compare(obj, next->obj) < 0)
297 break;
299 prev = next;
300 next = next->next;
301 }
302 status = sdb_llist_insert_after(list, prev, obj);
303 pthread_rwlock_unlock(&list->lock);
304 return status;
305 } /* sdb_llist_insert_sorted */
307 sdb_object_t *
308 sdb_llist_get(sdb_llist_t *list, size_t i)
309 {
310 sdb_llist_elem_t *elem;
311 size_t j;
313 if ((! list) || (i >= list->length))
314 return NULL;
316 for (elem = list->head, j = 0; j < i; elem = elem->next, ++j)
317 /* iterate */;
319 assert(elem);
320 return elem->obj;
321 } /* sdb_llist_get */
323 sdb_object_t *
324 sdb_llist_search(sdb_llist_t *list,
325 sdb_llist_lookup_cb lookup, const void *user_data)
326 {
327 sdb_llist_elem_t *elem;
329 if ((! list) || (! lookup))
330 return NULL;
332 pthread_rwlock_rdlock(&list->lock);
333 elem = llist_search(list, lookup, user_data);
334 pthread_rwlock_unlock(&list->lock);
336 if (elem)
337 return elem->obj;
338 return NULL;
339 } /* sdb_llist_search */
341 sdb_object_t *
342 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
343 {
344 sdb_llist_elem_t *elem;
346 if (! list)
347 return NULL;
349 pthread_rwlock_rdlock(&list->lock);
351 for (elem = list->head; elem; elem = elem->next)
352 if (! strcasecmp(elem->obj->name, key))
353 break;
355 pthread_rwlock_unlock(&list->lock);
357 if (elem)
358 return elem->obj;
359 return NULL;
360 } /* sdb_llist_search_by_name */
362 sdb_object_t *
363 sdb_llist_remove(sdb_llist_t *list,
364 sdb_llist_lookup_cb lookup, const void *user_data)
365 {
366 sdb_llist_elem_t *elem;
367 sdb_object_t *obj = NULL;
369 if ((! list) || (! lookup))
370 return NULL;
372 pthread_rwlock_wrlock(&list->lock);
373 elem = llist_search(list, lookup, user_data);
374 if (elem)
375 obj = sdb_llist_remove_elem(list, elem);
376 pthread_rwlock_unlock(&list->lock);
378 return obj;
379 } /* sdb_llist_remove */
381 sdb_object_t *
382 sdb_llist_shift(sdb_llist_t *list)
383 {
384 sdb_object_t *obj;
386 if ((! list) || (! list->head))
387 return NULL;
389 pthread_rwlock_wrlock(&list->lock);
390 obj = sdb_llist_remove_elem(list, list->head);
391 pthread_rwlock_unlock(&list->lock);
392 return obj;
393 } /* sdb_llist_shift */
395 sdb_llist_iter_t *
396 sdb_llist_get_iter(sdb_llist_t *list)
397 {
398 sdb_llist_iter_t *iter;
400 if (! list)
401 return NULL;
403 iter = malloc(sizeof(*iter));
404 if (! iter)
405 return NULL;
407 pthread_rwlock_rdlock(&list->lock);
409 iter->list = list;
410 iter->elem = list->head;
412 /* XXX: keep lock until destroying the iterator? */
413 pthread_rwlock_unlock(&list->lock);
414 return iter;
415 } /* sdb_llist_get_iter */
417 void
418 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
419 {
420 if (! iter)
421 return;
423 iter->list = NULL;
424 iter->elem = NULL;
425 free(iter);
426 } /* sdb_llist_iter_destroy */
428 _Bool
429 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
430 {
431 if (! iter)
432 return 0;
433 return iter->elem != NULL;
434 } /* sdb_llist_iter_has_next */
436 sdb_object_t *
437 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
438 {
439 sdb_object_t *obj;
441 if ((! iter) || (! iter->elem))
442 return NULL;
444 pthread_rwlock_rdlock(&iter->list->lock);
446 /* XXX: increment ref-cnt for this object?
447 * also: when letting an element take ownership of next and prev
448 * elements, this might be a fairly cheap way to implement a weak
449 * type of snapshotting */
451 obj = iter->elem->obj;
452 iter->elem = iter->elem->next;
454 pthread_rwlock_unlock(&iter->list->lock);
455 return obj;
456 } /* sdb_llist_iter_get_next */
458 int
459 sdb_llist_iter_remove_current(sdb_llist_iter_t *iter)
460 {
461 sdb_llist_elem_t *elem;
463 if ((! iter) || (! iter->list))
464 return -1;
466 pthread_rwlock_wrlock(&iter->list->lock);
468 if (! iter->elem) /* reached end of list */
469 elem = iter->list->tail;
470 else
471 elem = iter->elem->prev;
472 if (elem)
473 sdb_llist_remove_elem(iter->list, elem);
475 pthread_rwlock_unlock(&iter->list->lock);
477 if (! elem)
478 return -1;
479 return 0;
480 } /* sdb_llist_iter_remove */
482 size_t
483 sdb_llist_len(sdb_llist_t *list)
484 {
485 if (! list)
486 return 0;
487 return list->length;
488 } /* sdb_llist_len */
490 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */