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>
33 #include <pthread.h>
35 /*
36 * private data types
37 */
39 struct sdb_llist_elem;
40 typedef struct sdb_llist_elem sdb_llist_elem_t;
42 struct sdb_llist_elem {
43 sdb_object_t *obj;
45 sdb_llist_elem_t *next;
46 sdb_llist_elem_t *prev;
47 };
49 struct sdb_llist {
50 pthread_rwlock_t lock;
52 sdb_llist_elem_t *head;
53 sdb_llist_elem_t *tail;
55 size_t length;
56 };
58 struct sdb_llist_iter {
59 sdb_llist_t *list;
60 sdb_llist_elem_t *elem;
61 };
63 /*
64 * private helper functions
65 */
67 /* Insert a new element after 'elem'. If 'elem' is NULL, insert at the head of
68 * the list. */
69 static int
70 sdb_llist_insert_after(sdb_llist_t *list, sdb_llist_elem_t *elem,
71 sdb_object_t *obj)
72 {
73 sdb_llist_elem_t *new;
75 assert(list);
77 new = malloc(sizeof(*new));
78 if (! new)
79 return -1;
81 new->obj = obj;
82 if (elem)
83 new->next = elem->next;
84 else if (list->head)
85 new->next = list->head;
86 else
87 new->next = NULL;
88 new->prev = elem;
90 if (elem) {
91 if (elem->next)
92 elem->next->prev = new;
93 else
94 list->tail = new;
95 elem->next = new;
96 }
97 else {
98 /* new entry will be new head */
99 if (list->head)
100 list->head->prev = new;
102 list->head = new;
103 if (! list->tail)
104 list->tail = new;
105 }
107 assert(list->head && list->tail);
108 if (! list->length) {
109 assert(list->head == list->tail);
110 }
112 sdb_object_ref(obj);
113 ++list->length;
114 return 0;
115 } /* sdb_llist_insert_after */
117 static sdb_object_t *
118 sdb_llist_remove_elem(sdb_llist_t *list, sdb_llist_elem_t *elem)
119 {
120 sdb_object_t *obj;
122 assert(list && elem);
124 obj = elem->obj;
126 if (elem->prev)
127 elem->prev->next = elem->next;
128 else {
129 assert(elem == list->head);
130 list->head = elem->next;
131 }
133 if (elem->next)
134 elem->next->prev = elem->prev;
135 else {
136 assert(elem == list->tail);
137 list->tail = elem->prev;
138 }
140 elem->prev = elem->next = NULL;
141 free(elem);
143 --list->length;
144 return obj;
145 } /* sdb_llist_remove_elem */
147 /*
148 * public API
149 */
151 sdb_llist_t *
152 sdb_llist_create(void)
153 {
154 sdb_llist_t *list;
156 list = malloc(sizeof(*list));
157 if (! list)
158 return NULL;
160 pthread_rwlock_init(&list->lock, /* attr = */ NULL);
162 list->head = list->tail = NULL;
163 list->length = 0;
164 return list;
165 } /* sdb_llist_create */
167 sdb_llist_t *
168 sdb_llist_clone(sdb_llist_t *list)
169 {
170 sdb_llist_t *new;
171 sdb_llist_elem_t *elem;
173 if (! list)
174 return NULL;
176 new = sdb_llist_create();
177 if (! new)
178 return NULL;
180 if (! list->length) {
181 assert((! list->head) && (! list->tail));
182 return new;
183 }
185 for (elem = list->head; elem; elem = elem->next) {
186 if (sdb_llist_append(new, elem->obj)) {
187 sdb_llist_destroy(new);
188 return NULL;
189 }
190 }
191 return new;
192 } /* sdb_llist_clone */
194 void
195 sdb_llist_destroy(sdb_llist_t *list)
196 {
197 sdb_llist_elem_t *elem;
199 if (! list)
200 return;
202 pthread_rwlock_wrlock(&list->lock);
204 elem = list->head;
205 while (elem) {
206 sdb_llist_elem_t *tmp = elem->next;
208 sdb_object_deref(elem->obj);
209 free(elem);
211 elem = tmp;
212 }
214 list->head = list->tail = NULL;
215 list->length = 0;
217 pthread_rwlock_unlock(&list->lock);
218 pthread_rwlock_destroy(&list->lock);
219 free(list);
220 } /* sdb_llist_destroy */
222 int
223 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
224 {
225 int status;
227 if ((! list) || (! obj))
228 return -1;
230 pthread_rwlock_wrlock(&list->lock);
231 status = sdb_llist_insert_after(list, list->tail, obj);
232 pthread_rwlock_unlock(&list->lock);
233 return status;
234 } /* sdb_llist_append */
236 int
237 sdb_llist_insert(sdb_llist_t *list, sdb_object_t *obj, size_t index)
238 {
239 sdb_llist_elem_t *prev;
240 sdb_llist_elem_t *next;
242 int status;
244 size_t i;
246 if ((! list) || (! obj) || (index > list->length))
247 return -1;
249 pthread_rwlock_wrlock(&list->lock);
251 prev = NULL;
252 next = list->head;
254 for (i = 0; i < index; ++i) {
255 prev = next;
256 next = next->next;
257 }
258 status = sdb_llist_insert_after(list, prev, obj);
259 pthread_rwlock_unlock(&list->lock);
260 return status;
261 } /* sdb_llist_insert */
263 int
264 sdb_llist_insert_sorted(sdb_llist_t *list, sdb_object_t *obj,
265 int (*compare)(const sdb_object_t *, const sdb_object_t *))
266 {
267 sdb_llist_elem_t *prev;
268 sdb_llist_elem_t *next;
270 int status;
272 if ((! list) || (! obj) || (! compare))
273 return -1;
275 pthread_rwlock_wrlock(&list->lock);
277 prev = NULL;
278 next = list->head;
280 while (next) {
281 if (compare(obj, next->obj) < 0)
282 break;
284 prev = next;
285 next = next->next;
286 }
287 status = sdb_llist_insert_after(list, prev, obj);
288 pthread_rwlock_unlock(&list->lock);
289 return status;
290 } /* sdb_llist_insert_sorted */
292 sdb_object_t *
293 sdb_llist_search(sdb_llist_t *list, const sdb_object_t *key,
294 int (*compare)(const sdb_object_t *, const sdb_object_t *))
295 {
296 sdb_llist_elem_t *elem;
298 if ((! list) || (! compare))
299 return NULL;
301 pthread_rwlock_rdlock(&list->lock);
303 for (elem = list->head; elem; elem = elem->next)
304 if (! compare(elem->obj, key))
305 break;
307 pthread_rwlock_unlock(&list->lock);
309 if (elem)
310 return elem->obj;
311 return NULL;
312 } /* sdb_llist_search */
314 sdb_object_t *
315 sdb_llist_shift(sdb_llist_t *list)
316 {
317 sdb_object_t *obj;
319 if ((! list) || (! list->head))
320 return NULL;
322 pthread_rwlock_wrlock(&list->lock);
323 obj = sdb_llist_remove_elem(list, list->head);
324 pthread_rwlock_unlock(&list->lock);
325 return obj;
326 } /* sdb_llist_shift */
328 sdb_llist_iter_t *
329 sdb_llist_get_iter(sdb_llist_t *list)
330 {
331 sdb_llist_iter_t *iter;
333 if (! list)
334 return NULL;
336 iter = malloc(sizeof(*iter));
337 if (! iter)
338 return NULL;
340 pthread_rwlock_rdlock(&list->lock);
342 iter->list = list;
343 iter->elem = list->head;
345 /* XXX: keep lock until destroying the iterator? */
346 pthread_rwlock_unlock(&list->lock);
347 return iter;
348 } /* sdb_llist_get_iter */
350 void
351 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
352 {
353 if (! iter)
354 return;
356 iter->list = NULL;
357 iter->elem = NULL;
358 free(iter);
359 } /* sdb_llist_iter_destroy */
361 _Bool
362 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
363 {
364 if (! iter)
365 return 0;
366 return iter->elem != NULL;
367 } /* sdb_llist_iter_has_next */
369 sdb_object_t *
370 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
371 {
372 sdb_object_t *obj;
374 if ((! iter) || (! iter->elem))
375 return NULL;
377 pthread_rwlock_rdlock(&iter->list->lock);
379 obj = iter->elem->obj;
380 iter->elem = iter->elem->next;
382 pthread_rwlock_unlock(&iter->list->lock);
383 return obj;
384 } /* sdb_llist_iter_get_next */
386 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */