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 #include <strings.h>
  33
  34 #include <pthread.h>
  35
  36 /*
  37  * private data types
  38  */
  39
  40 struct sdb_llist_elem;
  41 typedef struct sdb_llist_elem sdb_llist_elem_t;
  42
  43 struct sdb_llist_elem {
  44         sdb_object_t *obj;
  45
  46         sdb_llist_elem_t *next;
  47         sdb_llist_elem_t *prev;
  48 };
  49
  50 struct sdb_llist {
  51         pthread_rwlock_t lock;
  52
  53         sdb_llist_elem_t *head;
  54         sdb_llist_elem_t *tail;
  55
  56         size_t length;
  57 };
  58
  59 struct sdb_llist_iter {
  60         sdb_llist_t *list;
  61         sdb_llist_elem_t *elem;
  62 };
  63
  64 /*
  65  * private helper functions
  66  */
  67
  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;
  75
  76         assert(list);
  77
  78         new = malloc(sizeof(*new));
  79         if (! new)
  80                 return -1;
  81
  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;
  90
  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;
 102
 103                 list->head = new;
 104                 if (! list->tail)
 105                         list->tail = new;
 106         }
 107
 108         assert(list->head && list->tail);
 109         if (! list->length) {
 110                 assert(list->head == list->tail);
 111         }
 112
 113         sdb_object_ref(obj);
 114         ++list->length;
 115         return 0;
 116 } /* sdb_llist_insert_after */
 117
 118 static sdb_object_t *
 119 sdb_llist_remove_elem(sdb_llist_t *list, sdb_llist_elem_t *elem)
 120 {
 121         sdb_object_t *obj;
 122
 123         assert(list && elem);
 124
 125         obj = elem->obj;
 126
 127         if (elem->prev)
 128                 elem->prev->next = elem->next;
 129         else {
 130                 assert(elem == list->head);
 131                 list->head = elem->next;
 132         }
 133
 134         if (elem->next)
 135                 elem->next->prev = elem->prev;
 136         else {
 137                 assert(elem == list->tail);
 138                 list->tail = elem->prev;
 139         }
 140
 141         elem->prev = elem->next = NULL;
 142         free(elem);
 143
 144         --list->length;
 145         return obj;
 146 } /* sdb_llist_remove_elem */
 147
 148 /*
 149  * public API
 150  */
 151
 152 sdb_llist_t *
 153 sdb_llist_create(void)
 154 {
 155         sdb_llist_t *list;
 156
 157         list = malloc(sizeof(*list));
 158         if (! list)
 159                 return NULL;
 160
 161         pthread_rwlock_init(&list->lock, /* attr = */ NULL);
 162
 163         list->head = list->tail = NULL;
 164         list->length = 0;
 165         return list;
 166 } /* sdb_llist_create */
 167
 168 sdb_llist_t *
 169 sdb_llist_clone(sdb_llist_t *list)
 170 {
 171         sdb_llist_t *new;
 172         sdb_llist_elem_t *elem;
 173
 174         if (! list)
 175                 return NULL;
 176
 177         new = sdb_llist_create();
 178         if (! new)
 179                 return NULL;
 180
 181         if (! list->length) {
 182                 assert((! list->head) && (! list->tail));
 183                 return new;
 184         }
 185
 186         for (elem = list->head; elem; elem = elem->next) {
 187                 if (sdb_llist_append(new, elem->obj)) {
 188                         sdb_llist_destroy(new);
 189                         return NULL;
 190                 }
 191         }
 192         return new;
 193 } /* sdb_llist_clone */
 194
 195 void
 196 sdb_llist_destroy(sdb_llist_t *list)
 197 {
 198         sdb_llist_elem_t *elem;
 199
 200         if (! list)
 201                 return;
 202
 203         pthread_rwlock_wrlock(&list->lock);
 204
 205         elem = list->head;
 206         while (elem) {
 207                 sdb_llist_elem_t *tmp = elem->next;
 208
 209                 sdb_object_deref(elem->obj);
 210                 free(elem);
 211
 212                 elem = tmp;
 213         }
 214
 215         list->head = list->tail = NULL;
 216         list->length = 0;
 217
 218         pthread_rwlock_unlock(&list->lock);
 219         pthread_rwlock_destroy(&list->lock);
 220         free(list);
 221 } /* sdb_llist_destroy */
 222
 223 int
 224 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
 225 {
 226         int status;
 227
 228         if ((! list) || (! obj))
 229                 return -1;
 230
 231         pthread_rwlock_wrlock(&list->lock);
 232         status = sdb_llist_insert_after(list, list->tail, obj);
 233         pthread_rwlock_unlock(&list->lock);
 234         return status;
 235 } /* sdb_llist_append */
 236
 237 int
 238 sdb_llist_insert(sdb_llist_t *list, sdb_object_t *obj, size_t idx)
 239 {
 240         sdb_llist_elem_t *prev;
 241         sdb_llist_elem_t *next;
 242
 243         int status;
 244
 245         size_t i;
 246
 247         if ((! list) || (! obj) || (idx > list->length))
 248                 return -1;
 249
 250         pthread_rwlock_wrlock(&list->lock);
 251
 252         prev = NULL;
 253         next = list->head;
 254
 255         for (i = 0; i < idx; ++i) {
 256                 prev = next;
 257                 next = next->next;
 258         }
 259         status = sdb_llist_insert_after(list, prev, obj);
 260         pthread_rwlock_unlock(&list->lock);
 261         return status;
 262 } /* sdb_llist_insert */
 263
 264 int
 265 sdb_llist_insert_sorted(sdb_llist_t *list,
 266                 sdb_object_t *obj, sdb_llist_cmp_cb compare)
 267 {
 268         sdb_llist_elem_t *prev;
 269         sdb_llist_elem_t *next;
 270
 271         int status;
 272
 273         if ((! list) || (! obj) || (! compare))
 274                 return -1;
 275
 276         pthread_rwlock_wrlock(&list->lock);
 277
 278         prev = NULL;
 279         next = list->head;
 280
 281         while (next) {
 282                 if (compare(obj, next->obj) < 0)
 283                         break;
 284
 285                 prev = next;
 286                 next = next->next;
 287         }
 288         status = sdb_llist_insert_after(list, prev, obj);
 289         pthread_rwlock_unlock(&list->lock);
 290         return status;
 291 } /* sdb_llist_insert_sorted */
 292
 293 sdb_object_t *
 294 sdb_llist_search(sdb_llist_t *list,
 295                 const sdb_object_t *key, sdb_llist_cmp_cb compare)
 296 {
 297         sdb_llist_elem_t *elem;
 298
 299         if ((! list) || (! compare))
 300                 return NULL;
 301
 302         pthread_rwlock_rdlock(&list->lock);
 303
 304         for (elem = list->head; elem; elem = elem->next)
 305                 if (! compare(elem->obj, key))
 306                         break;
 307
 308         pthread_rwlock_unlock(&list->lock);
 309
 310         if (elem)
 311                 return elem->obj;
 312         return NULL;
 313 } /* sdb_llist_search */
 314
 315 sdb_object_t *
 316 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
 317 {
 318         sdb_llist_elem_t *elem;
 319
 320         if (! list)
 321                 return NULL;
 322
 323         pthread_rwlock_rdlock(&list->lock);
 324
 325         for (elem = list->head; elem; elem = elem->next)
 326                 if (! strcasecmp(elem->obj->name, key))
 327                         break;
 328
 329         pthread_rwlock_unlock(&list->lock);
 330
 331         if (elem)
 332                 return elem->obj;
 333         return NULL;
 334 } /* sdb_llist_search_by_name */
 335
 336 sdb_object_t *
 337 sdb_llist_shift(sdb_llist_t *list)
 338 {
 339         sdb_object_t *obj;
 340
 341         if ((! list) || (! list->head))
 342                 return NULL;
 343
 344         pthread_rwlock_wrlock(&list->lock);
 345         obj = sdb_llist_remove_elem(list, list->head);
 346         pthread_rwlock_unlock(&list->lock);
 347         return obj;
 348 } /* sdb_llist_shift */
 349
 350 sdb_llist_iter_t *
 351 sdb_llist_get_iter(sdb_llist_t *list)
 352 {
 353         sdb_llist_iter_t *iter;
 354
 355         if (! list)
 356                 return NULL;
 357
 358         iter = malloc(sizeof(*iter));
 359         if (! iter)
 360                 return NULL;
 361
 362         pthread_rwlock_rdlock(&list->lock);
 363
 364         iter->list = list;
 365         iter->elem = list->head;
 366
 367         /* XXX: keep lock until destroying the iterator? */
 368         pthread_rwlock_unlock(&list->lock);
 369         return iter;
 370 } /* sdb_llist_get_iter */
 371
 372 void
 373 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
 374 {
 375         if (! iter)
 376                 return;
 377
 378         iter->list = NULL;
 379         iter->elem = NULL;
 380         free(iter);
 381 } /* sdb_llist_iter_destroy */
 382
 383 _Bool
 384 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
 385 {
 386         if (! iter)
 387                 return 0;
 388         return iter->elem != NULL;
 389 } /* sdb_llist_iter_has_next */
 390
 391 sdb_object_t *
 392 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
 393 {
 394         sdb_object_t *obj;
 395
 396         if ((! iter) || (! iter->elem))
 397                 return NULL;
 398
 399         pthread_rwlock_rdlock(&iter->list->lock);
 400
 401         obj = iter->elem->obj;
 402         iter->elem = iter->elem->next;
 403
 404         pthread_rwlock_unlock(&iter->list->lock);
 405         return obj;
 406 } /* sdb_llist_iter_get_next */
 407
 408 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 409