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 #if HAVE_CONFIG_H
  29 #       include "config.h"
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #include "utils/llist.h"
  33
  34 #include <assert.h>
  35 #include <stdlib.h>
  36 #include <strings.h>
  37
  38 #include <pthread.h>
  39
  40 /*
  41  * private data types
  42  */
  43
  44 struct sdb_llist_elem;
  45 typedef struct sdb_llist_elem sdb_llist_elem_t;
  46
  47 struct sdb_llist_elem {
  48         sdb_object_t *obj;
  49
  50         sdb_llist_elem_t *next;
  51         sdb_llist_elem_t *prev;
  52 };
  53
  54 struct sdb_llist {
  55         pthread_rwlock_t lock;
  56
  57         sdb_llist_elem_t *head;
  58         sdb_llist_elem_t *tail;
  59
  60         size_t length;
  61 };
  62
  63 struct sdb_llist_iter {
  64         sdb_llist_t *list;
  65         sdb_llist_elem_t *elem;
  66 };
  67
  68 /*
  69  * private helper functions
  70  */
  71
  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;
  79
  80         assert(list);
  81
  82         new = malloc(sizeof(*new));
  83         if (! new)
  84                 return -1;
  85
  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;
  94
  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;
 106
 107                 list->head = new;
 108                 if (! list->tail)
 109                         list->tail = new;
 110         }
 111
 112         assert(list->head && list->tail);
 113         if (! list->length) {
 114                 assert(list->head == list->tail);
 115         }
 116
 117         sdb_object_ref(obj);
 118         ++list->length;
 119         return 0;
 120 } /* sdb_llist_insert_after */
 121
 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;
 127
 128         assert(list && lookup);
 129
 130         for (elem = list->head; elem; elem = elem->next)
 131                 if (! lookup(elem->obj, user_data))
 132                         break;
 133         return elem;
 134 } /* llist_search */
 135
 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;
 140
 141         assert(list && elem);
 142
 143         obj = elem->obj;
 144
 145         if (elem->prev)
 146                 elem->prev->next = elem->next;
 147         else {
 148                 assert(elem == list->head);
 149                 list->head = elem->next;
 150         }
 151
 152         if (elem->next)
 153                 elem->next->prev = elem->prev;
 154         else {
 155                 assert(elem == list->tail);
 156                 list->tail = elem->prev;
 157         }
 158
 159         elem->prev = elem->next = NULL;
 160         free(elem);
 161
 162         --list->length;
 163         return obj;
 164 } /* sdb_llist_remove_elem */
 165
 166 /*
 167  * public API
 168  */
 169
 170 sdb_llist_t *
 171 sdb_llist_create(void)
 172 {
 173         sdb_llist_t *list;
 174
 175         list = malloc(sizeof(*list));
 176         if (! list)
 177                 return NULL;
 178
 179         pthread_rwlock_init(&list->lock, /* attr = */ NULL);
 180
 181         list->head = list->tail = NULL;
 182         list->length = 0;
 183         return list;
 184 } /* sdb_llist_create */
 185
 186 sdb_llist_t *
 187 sdb_llist_clone(sdb_llist_t *list)
 188 {
 189         sdb_llist_t *new;
 190         sdb_llist_elem_t *elem;
 191
 192         if (! list)
 193                 return NULL;
 194
 195         new = sdb_llist_create();
 196         if (! new)
 197                 return NULL;
 198
 199         if (! list->length) {
 200                 assert((! list->head) && (! list->tail));
 201                 return new;
 202         }
 203
 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 */
 212
 213 void
 214 sdb_llist_destroy(sdb_llist_t *list)
 215 {
 216         sdb_llist_elem_t *elem;
 217
 218         if (! list)
 219                 return;
 220
 221         pthread_rwlock_wrlock(&list->lock);
 222
 223         elem = list->head;
 224         while (elem) {
 225                 sdb_llist_elem_t *tmp = elem->next;
 226
 227                 sdb_object_deref(elem->obj);
 228                 free(elem);
 229
 230                 elem = tmp;
 231         }
 232
 233         list->head = list->tail = NULL;
 234         list->length = 0;
 235
 236         pthread_rwlock_unlock(&list->lock);
 237         pthread_rwlock_destroy(&list->lock);
 238         free(list);
 239 } /* sdb_llist_destroy */
 240
 241 int
 242 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
 243 {
 244         int status;
 245
 246         if ((! list) || (! obj))
 247                 return -1;
 248
 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 */
 254
 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;
 260
 261         int status;
 262
 263         size_t i;
 264
 265         if ((! list) || (! obj) || (idx > list->length))
 266                 return -1;
 267
 268         pthread_rwlock_wrlock(&list->lock);
 269
 270         prev = NULL;
 271         next = list->head;
 272
 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 */
 281
 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;
 288
 289         int status;
 290
 291         if ((! list) || (! obj) || (! compare))
 292                 return -1;
 293
 294         pthread_rwlock_wrlock(&list->lock);
 295
 296         prev = NULL;
 297         next = list->head;
 298
 299         while (next) {
 300                 if (compare(obj, next->obj) < 0)
 301                         break;
 302
 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 */
 310
 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;
 316
 317         if ((! list) || (i >= list->length))
 318                 return NULL;
 319
 320         for (elem = list->head, j = 0; j < i; elem = elem->next, ++j)
 321                 /* iterate */;
 322
 323         assert(elem);
 324         return elem->obj;
 325 } /* sdb_llist_get */
 326
 327 sdb_object_t *
 328 sdb_llist_search(sdb_llist_t *list,
 329                 sdb_llist_lookup_cb lookup, const void *user_data)
 330 {
 331         sdb_llist_elem_t *elem;
 332
 333         if ((! list) || (! lookup))
 334                 return NULL;
 335
 336         pthread_rwlock_rdlock(&list->lock);
 337         elem = llist_search(list, lookup, user_data);
 338         pthread_rwlock_unlock(&list->lock);
 339
 340         if (elem)
 341                 return elem->obj;
 342         return NULL;
 343 } /* sdb_llist_search */
 344
 345 sdb_object_t *
 346 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
 347 {
 348         sdb_llist_elem_t *elem;
 349
 350         if (! list)
 351                 return NULL;
 352
 353         pthread_rwlock_rdlock(&list->lock);
 354
 355         for (elem = list->head; elem; elem = elem->next)
 356                 if (! strcasecmp(elem->obj->name, key))
 357                         break;
 358
 359         pthread_rwlock_unlock(&list->lock);
 360
 361         if (elem)
 362                 return elem->obj;
 363         return NULL;
 364 } /* sdb_llist_search_by_name */
 365
 366 sdb_object_t *
 367 sdb_llist_remove(sdb_llist_t *list,
 368                 sdb_llist_lookup_cb lookup, const void *user_data)
 369 {
 370         sdb_llist_elem_t *elem;
 371         sdb_object_t *obj = NULL;
 372
 373         if ((! list) || (! lookup))
 374                 return NULL;
 375
 376         pthread_rwlock_wrlock(&list->lock);
 377         elem = llist_search(list, lookup, user_data);
 378         if (elem)
 379                 obj = sdb_llist_remove_elem(list, elem);
 380         pthread_rwlock_unlock(&list->lock);
 381
 382         return obj;
 383 } /* sdb_llist_remove */
 384
 385 sdb_object_t *
 386 sdb_llist_shift(sdb_llist_t *list)
 387 {
 388         sdb_object_t *obj;
 389
 390         if ((! list) || (! list->head))
 391                 return NULL;
 392
 393         pthread_rwlock_wrlock(&list->lock);
 394         obj = sdb_llist_remove_elem(list, list->head);
 395         pthread_rwlock_unlock(&list->lock);
 396         return obj;
 397 } /* sdb_llist_shift */
 398
 399 sdb_llist_iter_t *
 400 sdb_llist_get_iter(sdb_llist_t *list)
 401 {
 402         sdb_llist_iter_t *iter;
 403
 404         if (! list)
 405                 return NULL;
 406
 407         iter = malloc(sizeof(*iter));
 408         if (! iter)
 409                 return NULL;
 410
 411         pthread_rwlock_rdlock(&list->lock);
 412
 413         iter->list = list;
 414         iter->elem = list->head;
 415
 416         /* XXX: keep lock until destroying the iterator? */
 417         pthread_rwlock_unlock(&list->lock);
 418         return iter;
 419 } /* sdb_llist_get_iter */
 420
 421 void
 422 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
 423 {
 424         if (! iter)
 425                 return;
 426
 427         iter->list = NULL;
 428         iter->elem = NULL;
 429         free(iter);
 430 } /* sdb_llist_iter_destroy */
 431
 432 _Bool
 433 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
 434 {
 435         if (! iter)
 436                 return 0;
 437         return iter->elem != NULL;
 438 } /* sdb_llist_iter_has_next */
 439
 440 sdb_object_t *
 441 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
 442 {
 443         sdb_object_t *obj;
 444
 445         if ((! iter) || (! iter->elem))
 446                 return NULL;
 447
 448         pthread_rwlock_rdlock(&iter->list->lock);
 449
 450         /* XXX: increment ref-cnt for this object?
 451          *      also: when letting an element take ownership of next and prev
 452          *      elements, this might be a fairly cheap way to implement a weak
 453          *      type of snapshotting */
 454
 455         obj = iter->elem->obj;
 456         iter->elem = iter->elem->next;
 457
 458         pthread_rwlock_unlock(&iter->list->lock);
 459         return obj;
 460 } /* sdb_llist_iter_get_next */
 461
 462 int
 463 sdb_llist_iter_remove_current(sdb_llist_iter_t *iter)
 464 {
 465         sdb_llist_elem_t *elem;
 466
 467         if ((! iter) || (! iter->list))
 468                 return -1;
 469
 470         pthread_rwlock_wrlock(&iter->list->lock);
 471
 472         if (! iter->elem) /* reached end of list */
 473                 elem = iter->list->tail;
 474         else
 475                 elem = iter->elem->prev;
 476         if (elem)
 477                 sdb_llist_remove_elem(iter->list, elem);
 478
 479         pthread_rwlock_unlock(&iter->list->lock);
 480
 481         if (! elem)
 482                 return -1;
 483         return 0;
 484 } /* sdb_llist_iter_remove */
 485
 486 size_t
 487 sdb_llist_len(sdb_llist_t *list)
 488 {
 489         if (! list)
 490                 return 0;
 491         return list->length;
 492 } /* sdb_llist_len */
 493
 494 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 495