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         sdb_object_ref(elem->obj);
 325         return elem->obj;
 326 } /* sdb_llist_get */
 327
 328 sdb_object_t *
 329 sdb_llist_search(sdb_llist_t *list,
 330                 sdb_llist_lookup_cb lookup, const void *user_data)
 331 {
 332         sdb_llist_elem_t *elem;
 333
 334         if ((! list) || (! lookup))
 335                 return NULL;
 336
 337         pthread_rwlock_rdlock(&list->lock);
 338         elem = llist_search(list, lookup, user_data);
 339         pthread_rwlock_unlock(&list->lock);
 340
 341         if (elem)
 342                 return elem->obj;
 343         return NULL;
 344 } /* sdb_llist_search */
 345
 346 sdb_object_t *
 347 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
 348 {
 349         sdb_llist_elem_t *elem;
 350
 351         if (! list)
 352                 return NULL;
 353
 354         pthread_rwlock_rdlock(&list->lock);
 355
 356         for (elem = list->head; elem; elem = elem->next)
 357                 if (! strcasecmp(elem->obj->name, key))
 358                         break;
 359
 360         pthread_rwlock_unlock(&list->lock);
 361
 362         if (elem)
 363                 return elem->obj;
 364         return NULL;
 365 } /* sdb_llist_search_by_name */
 366
 367 sdb_object_t *
 368 sdb_llist_remove(sdb_llist_t *list,
 369                 sdb_llist_lookup_cb lookup, const void *user_data)
 370 {
 371         sdb_llist_elem_t *elem;
 372         sdb_object_t *obj = NULL;
 373
 374         if ((! list) || (! lookup))
 375                 return NULL;
 376
 377         pthread_rwlock_wrlock(&list->lock);
 378         elem = llist_search(list, lookup, user_data);
 379         if (elem)
 380                 obj = sdb_llist_remove_elem(list, elem);
 381         pthread_rwlock_unlock(&list->lock);
 382
 383         return obj;
 384 } /* sdb_llist_remove */
 385
 386 sdb_object_t *
 387 sdb_llist_remove_by_name(sdb_llist_t *list, const char *key)
 388 {
 389         sdb_llist_elem_t *elem;
 390         sdb_object_t *obj = NULL;
 391
 392         if (! list)
 393                 return NULL;
 394
 395         pthread_rwlock_rdlock(&list->lock);
 396
 397         for (elem = list->head; elem; elem = elem->next)
 398                 if ((key == elem->obj->name)
 399                                 || (! strcasecmp(elem->obj->name, key)))
 400                         break;
 401
 402         if (elem)
 403                 obj = sdb_llist_remove_elem(list, elem);
 404         pthread_rwlock_unlock(&list->lock);
 405
 406         return obj;
 407 } /* sdb_llist_remove_by_name */
 408
 409 sdb_object_t *
 410 sdb_llist_shift(sdb_llist_t *list)
 411 {
 412         sdb_object_t *obj;
 413
 414         if ((! list) || (! list->head))
 415                 return NULL;
 416
 417         pthread_rwlock_wrlock(&list->lock);
 418         obj = sdb_llist_remove_elem(list, list->head);
 419         pthread_rwlock_unlock(&list->lock);
 420         return obj;
 421 } /* sdb_llist_shift */
 422
 423 sdb_llist_iter_t *
 424 sdb_llist_get_iter(sdb_llist_t *list)
 425 {
 426         sdb_llist_iter_t *iter;
 427
 428         if (! list)
 429                 return NULL;
 430
 431         iter = malloc(sizeof(*iter));
 432         if (! iter)
 433                 return NULL;
 434
 435         pthread_rwlock_rdlock(&list->lock);
 436
 437         iter->list = list;
 438         iter->elem = list->head;
 439
 440         /* XXX: keep lock until destroying the iterator? */
 441         pthread_rwlock_unlock(&list->lock);
 442         return iter;
 443 } /* sdb_llist_get_iter */
 444
 445 void
 446 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
 447 {
 448         if (! iter)
 449                 return;
 450
 451         iter->list = NULL;
 452         iter->elem = NULL;
 453         free(iter);
 454 } /* sdb_llist_iter_destroy */
 455
 456 _Bool
 457 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
 458 {
 459         if (! iter)
 460                 return 0;
 461         return iter->elem != NULL;
 462 } /* sdb_llist_iter_has_next */
 463
 464 sdb_object_t *
 465 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
 466 {
 467         sdb_object_t *obj;
 468
 469         if ((! iter) || (! iter->elem))
 470                 return NULL;
 471
 472         pthread_rwlock_rdlock(&iter->list->lock);
 473
 474         /* XXX: increment ref-cnt for this object?
 475          *      also: when letting an element take ownership of next and prev
 476          *      elements, this might be a fairly cheap way to implement a weak
 477          *      type of snapshotting */
 478
 479         obj = iter->elem->obj;
 480         iter->elem = iter->elem->next;
 481
 482         pthread_rwlock_unlock(&iter->list->lock);
 483         return obj;
 484 } /* sdb_llist_iter_get_next */
 485
 486 int
 487 sdb_llist_iter_remove_current(sdb_llist_iter_t *iter)
 488 {
 489         sdb_llist_elem_t *elem;
 490
 491         if ((! iter) || (! iter->list))
 492                 return -1;
 493
 494         pthread_rwlock_wrlock(&iter->list->lock);
 495
 496         if (! iter->elem) /* reached end of list */
 497                 elem = iter->list->tail;
 498         else
 499                 elem = iter->elem->prev;
 500         if (elem)
 501                 sdb_llist_remove_elem(iter->list, elem);
 502
 503         pthread_rwlock_unlock(&iter->list->lock);
 504
 505         if (! elem)
 506                 return -1;
 507         return 0;
 508 } /* sdb_llist_iter_remove */
 509
 510 size_t
 511 sdb_llist_len(sdb_llist_t *list)
 512 {
 513         if (! list)
 514                 return 0;
 515         return list->length;
 516 } /* sdb_llist_len */
 517
 518 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 519