src/utils/llist.c

   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  */
  27
  28 #include "utils/llist.h"
  29
  30 #include <assert.h>
  31 #include <stdlib.h>
  32
  33 #include <pthread.h>
  34
  35 /*
  36  * private data types
  37  */
  38
  39 struct sdb_llist_elem;
  40 typedef struct sdb_llist_elem sdb_llist_elem_t;
  41
  42 struct sdb_llist_elem {
  43         sdb_object_t *obj;
  44
  45         sdb_llist_elem_t *next;
  46         sdb_llist_elem_t *prev;
  47 };
  48
  49 struct sdb_llist {
  50         pthread_rwlock_t lock;
  51
  52         sdb_llist_elem_t *head;
  53         sdb_llist_elem_t *tail;
  54
  55         size_t length;
  56 };
  57
  58 struct sdb_llist_iter {
  59         sdb_llist_t *list;
  60         sdb_llist_elem_t *elem;
  61 };
  62
  63 /*
  64  * private helper functions
  65  */
  66
  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;
  74
  75         assert(list);
  76
  77         new = malloc(sizeof(*new));
  78         if (! new)
  79                 return -1;
  80
  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;
  89
  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;
 101
 102                 list->head = new;
 103                 if (! list->tail)
 104                         list->tail = new;
 105         }
 106
 107         assert(list->head && list->tail);
 108         if (! list->length) {
 109                 assert(list->head == list->tail);
 110         }
 111
 112         sdb_object_ref(obj);
 113         ++list->length;
 114         return 0;
 115 } /* sdb_llist_insert_after */
 116
 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;
 121
 122         assert(list && elem);
 123
 124         obj = elem->obj;
 125
 126         if (elem->prev)
 127                 elem->prev->next = elem->next;
 128         else {
 129                 assert(elem == list->head);
 130                 list->head = elem->next;
 131         }
 132
 133         if (elem->next)
 134                 elem->next->prev = elem->prev;
 135         else {
 136                 assert(elem == list->tail);
 137                 list->tail = elem->prev;
 138         }
 139
 140         elem->prev = elem->next = NULL;
 141         free(elem);
 142
 143         --list->length;
 144         return obj;
 145 } /* sdb_llist_remove_elem */
 146
 147 /*
 148  * public API
 149  */
 150
 151 sdb_llist_t *
 152 sdb_llist_create(void)
 153 {
 154         sdb_llist_t *list;
 155
 156         list = malloc(sizeof(*list));
 157         if (! list)
 158                 return NULL;
 159
 160         pthread_rwlock_init(&list->lock, /* attr = */ NULL);
 161
 162         list->head = list->tail = NULL;
 163         list->length = 0;
 164         return list;
 165 } /* sdb_llist_create */
 166
 167 sdb_llist_t *
 168 sdb_llist_clone(sdb_llist_t *list)
 169 {
 170         sdb_llist_t *clone;
 171         sdb_llist_elem_t *elem;
 172
 173         if (! list)
 174                 return NULL;
 175
 176         clone = sdb_llist_create();
 177         if (! clone)
 178                 return NULL;
 179
 180         if (! list->length) {
 181                 assert((! list->head) && (! list->tail));
 182                 return clone;
 183         }
 184
 185         for (elem = list->head; elem; elem = elem->next) {
 186                 if (sdb_llist_append(clone, elem->obj)) {
 187                         sdb_llist_destroy(clone);
 188                         return NULL;
 189                 }
 190         }
 191         return clone;
 192 } /* sdb_llist_clone */
 193
 194 void
 195 sdb_llist_destroy(sdb_llist_t *list)
 196 {
 197         sdb_llist_elem_t *elem;
 198
 199         if (! list)
 200                 return;
 201
 202         pthread_rwlock_wrlock(&list->lock);
 203
 204         elem = list->head;
 205         while (elem) {
 206                 sdb_llist_elem_t *tmp = elem->next;
 207
 208                 sdb_object_deref(elem->obj);
 209                 free(elem);
 210
 211                 elem = tmp;
 212         }
 213
 214         list->head = list->tail = NULL;
 215         list->length = 0;
 216
 217         pthread_rwlock_unlock(&list->lock);
 218         pthread_rwlock_destroy(&list->lock);
 219         free(list);
 220 } /* sdb_llist_destroy */
 221
 222 int
 223 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
 224 {
 225         int status;
 226
 227         if ((! list) || (! obj))
 228                 return -1;
 229
 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 */
 235
 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;
 241
 242         int status;
 243
 244         size_t i;
 245
 246         if ((! list) || (! obj) || (index > list->length))
 247                 return -1;
 248
 249         pthread_rwlock_wrlock(&list->lock);
 250
 251         prev = NULL;
 252         next = list->head;
 253
 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 */
 262
 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;
 269
 270         int status;
 271
 272         if ((! list) || (! obj) || (! compare))
 273                 return -1;
 274
 275         pthread_rwlock_wrlock(&list->lock);
 276
 277         prev = NULL;
 278         next = list->head;
 279
 280         while (next) {
 281                 if (compare(obj, next->obj) < 0)
 282                         break;
 283
 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 */
 291
 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;
 297
 298         if ((! list) || (! compare))
 299                 return NULL;
 300
 301         pthread_rwlock_rdlock(&list->lock);
 302
 303         for (elem = list->head; elem; elem = elem->next)
 304                 if (! compare(elem->obj, key))
 305                         break;
 306
 307         pthread_rwlock_unlock(&list->lock);
 308
 309         if (elem)
 310                 return elem->obj;
 311         return NULL;
 312 } /* sdb_llist_search */
 313
 314 sdb_object_t *
 315 sdb_llist_shift(sdb_llist_t *list)
 316 {
 317         sdb_object_t *obj;
 318
 319         if ((! list) || (! list->head))
 320                 return NULL;
 321
 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 */
 327
 328 sdb_llist_iter_t *
 329 sdb_llist_get_iter(sdb_llist_t *list)
 330 {
 331         sdb_llist_iter_t *iter;
 332
 333         if (! list)
 334                 return NULL;
 335
 336         iter = malloc(sizeof(*iter));
 337         if (! iter)
 338                 return NULL;
 339
 340         pthread_rwlock_rdlock(&list->lock);
 341
 342         iter->list = list;
 343         iter->elem = list->head;
 344
 345         /* XXX: keep lock until destroying the iterator? */
 346         pthread_rwlock_unlock(&list->lock);
 347         return iter;
 348 } /* sdb_llist_get_iter */
 349
 350 void
 351 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
 352 {
 353         if (! iter)
 354                 return;
 355
 356         iter->list = NULL;
 357         iter->elem = NULL;
 358         free(iter);
 359 } /* sdb_llist_iter_destroy */
 360
 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 */
 368
 369 sdb_object_t *
 370 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
 371 {
 372         sdb_object_t *obj;
 373
 374         if ((! iter) || (! iter->elem))
 375                 return NULL;
 376
 377         pthread_rwlock_rdlock(&iter->list->lock);
 378
 379         obj = iter->elem->obj;
 380         iter->elem = iter->elem->next;
 381
 382         pthread_rwlock_unlock(&iter->list->lock);
 383         return obj;
 384 } /* sdb_llist_iter_get_next */
 385
 386 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 387