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 static void
  73 llist_clear(sdb_llist_t *list)
  74 {
  75         sdb_llist_elem_t *elem;
  76
  77         assert(list);
  78         elem = list->head;
  79         while (elem) {
  80                 sdb_llist_elem_t *tmp = elem->next;
  81
  82                 sdb_object_deref(elem->obj);
  83                 free(elem);
  84
  85                 elem = tmp;
  86         }
  87
  88         list->head = list->tail = NULL;
  89         list->length = 0;
  90 } /* llist_clear */
  91
  92 /* Insert a new element after 'elem'. If 'elem' is NULL, insert at the head of
  93  * the list. */
  94 static int
  95 llist_insert_after(sdb_llist_t *list, sdb_llist_elem_t *elem,
  96                 sdb_object_t *obj)
  97 {
  98         sdb_llist_elem_t *new;
  99
 100         assert(list);
 101
 102         new = malloc(sizeof(*new));
 103         if (! new)
 104                 return -1;
 105
 106         new->obj  = obj;
 107         if (elem)
 108                 new->next = elem->next;
 109         else if (list->head)
 110                 new->next = list->head;
 111         else
 112                 new->next = NULL;
 113         new->prev = elem;
 114
 115         if (elem) {
 116                 if (elem->next)
 117                         elem->next->prev = new;
 118                 else
 119                         list->tail = new;
 120                 elem->next = new;
 121         }
 122         else {
 123                 /* new entry will be new head */
 124                 if (list->head)
 125                         list->head->prev = new;
 126
 127                 list->head = new;
 128                 if (! list->tail)
 129                         list->tail = new;
 130         }
 131
 132         assert(list->head && list->tail);
 133         if (! list->length) {
 134                 assert(list->head == list->tail);
 135         }
 136
 137         sdb_object_ref(obj);
 138         ++list->length;
 139         return 0;
 140 } /* llist_insert_after */
 141
 142 static sdb_llist_elem_t *
 143 llist_search(sdb_llist_t *list,
 144                 sdb_object_lookup_cb lookup, const void *user_data)
 145 {
 146         sdb_llist_elem_t *elem;
 147
 148         assert(list && lookup);
 149
 150         for (elem = list->head; elem; elem = elem->next)
 151                 if (! lookup(elem->obj, user_data))
 152                         break;
 153         return elem;
 154 } /* llist_search */
 155
 156 static sdb_object_t *
 157 llist_remove_elem(sdb_llist_t *list, sdb_llist_elem_t *elem)
 158 {
 159         sdb_object_t *obj;
 160
 161         assert(list && elem);
 162
 163         obj = elem->obj;
 164
 165         if (elem->prev)
 166                 elem->prev->next = elem->next;
 167         else {
 168                 assert(elem == list->head);
 169                 list->head = elem->next;
 170         }
 171
 172         if (elem->next)
 173                 elem->next->prev = elem->prev;
 174         else {
 175                 assert(elem == list->tail);
 176                 list->tail = elem->prev;
 177         }
 178
 179         elem->prev = elem->next = NULL;
 180         free(elem);
 181
 182         --list->length;
 183         return obj;
 184 } /* llist_remove_elem */
 185
 186 /*
 187  * public API
 188  */
 189
 190 sdb_llist_t *
 191 sdb_llist_create(void)
 192 {
 193         sdb_llist_t *list;
 194
 195         list = malloc(sizeof(*list));
 196         if (! list)
 197                 return NULL;
 198
 199         pthread_rwlock_init(&list->lock, /* attr = */ NULL);
 200
 201         list->head = list->tail = NULL;
 202         list->length = 0;
 203         return list;
 204 } /* sdb_llist_create */
 205
 206 sdb_llist_t *
 207 sdb_llist_clone(sdb_llist_t *list)
 208 {
 209         sdb_llist_t *new;
 210         sdb_llist_elem_t *elem;
 211
 212         if (! list)
 213                 return NULL;
 214
 215         new = sdb_llist_create();
 216         if (! new)
 217                 return NULL;
 218
 219         if (! list->length) {
 220                 assert((! list->head) && (! list->tail));
 221                 return new;
 222         }
 223
 224         for (elem = list->head; elem; elem = elem->next) {
 225                 if (sdb_llist_append(new, elem->obj)) {
 226                         sdb_llist_destroy(new);
 227                         return NULL;
 228                 }
 229         }
 230         return new;
 231 } /* sdb_llist_clone */
 232
 233 void
 234 sdb_llist_destroy(sdb_llist_t *list)
 235 {
 236         if (! list)
 237                 return;
 238
 239         pthread_rwlock_wrlock(&list->lock);
 240         llist_clear(list);
 241         pthread_rwlock_unlock(&list->lock);
 242         pthread_rwlock_destroy(&list->lock);
 243         free(list);
 244 } /* sdb_llist_destroy */
 245
 246 void
 247 sdb_llist_clear(sdb_llist_t *list)
 248 {
 249         if (! list)
 250                 return;
 251
 252         pthread_rwlock_wrlock(&list->lock);
 253         llist_clear(list);
 254         pthread_rwlock_unlock(&list->lock);
 255 } /* sdb_llist_clear */
 256
 257 int
 258 sdb_llist_append(sdb_llist_t *list, sdb_object_t *obj)
 259 {
 260         int status;
 261
 262         if ((! list) || (! obj))
 263                 return -1;
 264
 265         pthread_rwlock_wrlock(&list->lock);
 266         status = llist_insert_after(list, list->tail, obj);
 267         pthread_rwlock_unlock(&list->lock);
 268         return status;
 269 } /* sdb_llist_append */
 270
 271 int
 272 sdb_llist_insert(sdb_llist_t *list, sdb_object_t *obj, size_t idx)
 273 {
 274         sdb_llist_elem_t *prev;
 275         sdb_llist_elem_t *next;
 276
 277         int status;
 278
 279         size_t i;
 280
 281         if ((! list) || (! obj) || (idx > list->length))
 282                 return -1;
 283
 284         pthread_rwlock_wrlock(&list->lock);
 285
 286         prev = NULL;
 287         next = list->head;
 288
 289         for (i = 0; i < idx; ++i) {
 290                 prev = next;
 291                 next = next->next;
 292         }
 293         status = llist_insert_after(list, prev, obj);
 294         pthread_rwlock_unlock(&list->lock);
 295         return status;
 296 } /* sdb_llist_insert */
 297
 298 int
 299 sdb_llist_insert_sorted(sdb_llist_t *list,
 300                 sdb_object_t *obj, sdb_object_cmp_cb compare)
 301 {
 302         sdb_llist_elem_t *prev;
 303         sdb_llist_elem_t *next;
 304
 305         int status;
 306
 307         if ((! list) || (! obj) || (! compare))
 308                 return -1;
 309
 310         pthread_rwlock_wrlock(&list->lock);
 311
 312         prev = NULL;
 313         next = list->head;
 314
 315         while (next) {
 316                 if (compare(obj, next->obj) < 0)
 317                         break;
 318
 319                 prev = next;
 320                 next = next->next;
 321         }
 322         status = llist_insert_after(list, prev, obj);
 323         pthread_rwlock_unlock(&list->lock);
 324         return status;
 325 } /* sdb_llist_insert_sorted */
 326
 327 sdb_object_t *
 328 sdb_llist_get(sdb_llist_t *list, size_t i)
 329 {
 330         sdb_llist_elem_t *elem;
 331         size_t j;
 332
 333         if ((! list) || (i >= list->length))
 334                 return NULL;
 335
 336         for (elem = list->head, j = 0; j < i; elem = elem->next, ++j)
 337                 /* iterate */;
 338
 339         assert(elem);
 340         sdb_object_ref(elem->obj);
 341         return elem->obj;
 342 } /* sdb_llist_get */
 343
 344 sdb_object_t *
 345 sdb_llist_search(sdb_llist_t *list,
 346                 sdb_object_lookup_cb lookup, const void *user_data)
 347 {
 348         sdb_llist_elem_t *elem;
 349
 350         if ((! list) || (! lookup))
 351                 return NULL;
 352
 353         pthread_rwlock_rdlock(&list->lock);
 354         elem = llist_search(list, lookup, user_data);
 355         pthread_rwlock_unlock(&list->lock);
 356
 357         if (elem)
 358                 return elem->obj;
 359         return NULL;
 360 } /* sdb_llist_search */
 361
 362 sdb_object_t *
 363 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
 364 {
 365         sdb_llist_elem_t *elem;
 366
 367         if (! list)
 368                 return NULL;
 369
 370         pthread_rwlock_rdlock(&list->lock);
 371
 372         for (elem = list->head; elem; elem = elem->next)
 373                 if (! strcasecmp(elem->obj->name, key))
 374                         break;
 375
 376         pthread_rwlock_unlock(&list->lock);
 377
 378         if (elem)
 379                 return elem->obj;
 380         return NULL;
 381 } /* sdb_llist_search_by_name */
 382
 383 sdb_object_t *
 384 sdb_llist_remove(sdb_llist_t *list,
 385                 sdb_object_lookup_cb lookup, const void *user_data)
 386 {
 387         sdb_llist_elem_t *elem;
 388         sdb_object_t *obj = NULL;
 389
 390         if ((! list) || (! lookup))
 391                 return NULL;
 392
 393         pthread_rwlock_wrlock(&list->lock);
 394         elem = llist_search(list, lookup, user_data);
 395         if (elem)
 396                 obj = llist_remove_elem(list, elem);
 397         pthread_rwlock_unlock(&list->lock);
 398
 399         return obj;
 400 } /* sdb_llist_remove */
 401
 402 sdb_object_t *
 403 sdb_llist_remove_by_name(sdb_llist_t *list, const char *key)
 404 {
 405         sdb_llist_elem_t *elem;
 406         sdb_object_t *obj = NULL;
 407
 408         if (! list)
 409                 return NULL;
 410
 411         pthread_rwlock_rdlock(&list->lock);
 412
 413         for (elem = list->head; elem; elem = elem->next)
 414                 if ((key == elem->obj->name)
 415                                 || (! strcasecmp(elem->obj->name, key)))
 416                         break;
 417
 418         if (elem)
 419                 obj = llist_remove_elem(list, elem);
 420         pthread_rwlock_unlock(&list->lock);
 421
 422         return obj;
 423 } /* sdb_llist_remove_by_name */
 424
 425 sdb_object_t *
 426 sdb_llist_shift(sdb_llist_t *list)
 427 {
 428         sdb_object_t *obj;
 429
 430         if ((! list) || (! list->head))
 431                 return NULL;
 432
 433         pthread_rwlock_wrlock(&list->lock);
 434         obj = llist_remove_elem(list, list->head);
 435         pthread_rwlock_unlock(&list->lock);
 436         return obj;
 437 } /* sdb_llist_shift */
 438
 439 sdb_llist_iter_t *
 440 sdb_llist_get_iter(sdb_llist_t *list)
 441 {
 442         sdb_llist_iter_t *iter;
 443
 444         if (! list)
 445                 return NULL;
 446
 447         iter = malloc(sizeof(*iter));
 448         if (! iter)
 449                 return NULL;
 450
 451         pthread_rwlock_rdlock(&list->lock);
 452
 453         iter->list = list;
 454         iter->elem = list->head;
 455
 456         /* XXX: keep lock until destroying the iterator? */
 457         pthread_rwlock_unlock(&list->lock);
 458         return iter;
 459 } /* sdb_llist_get_iter */
 460
 461 void
 462 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
 463 {
 464         if (! iter)
 465                 return;
 466
 467         iter->list = NULL;
 468         iter->elem = NULL;
 469         free(iter);
 470 } /* sdb_llist_iter_destroy */
 471
 472 bool
 473 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
 474 {
 475         if (! iter)
 476                 return 0;
 477         return iter->elem != NULL;
 478 } /* sdb_llist_iter_has_next */
 479
 480 sdb_object_t *
 481 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
 482 {
 483         sdb_object_t *obj;
 484
 485         if ((! iter) || (! iter->elem))
 486                 return NULL;
 487
 488         pthread_rwlock_rdlock(&iter->list->lock);
 489
 490         /* XXX: increment ref-cnt for this object?
 491          *      also: when letting an element take ownership of next and prev
 492          *      elements, this might be a fairly cheap way to implement a weak
 493          *      type of snapshotting */
 494
 495         obj = iter->elem->obj;
 496         iter->elem = iter->elem->next;
 497
 498         pthread_rwlock_unlock(&iter->list->lock);
 499         return obj;
 500 } /* sdb_llist_iter_get_next */
 501
 502 int
 503 sdb_llist_iter_remove_current(sdb_llist_iter_t *iter)
 504 {
 505         sdb_llist_elem_t *elem;
 506
 507         if ((! iter) || (! iter->list))
 508                 return -1;
 509
 510         pthread_rwlock_wrlock(&iter->list->lock);
 511
 512         if (! iter->elem) /* reached end of list */
 513                 elem = iter->list->tail;
 514         else
 515                 elem = iter->elem->prev;
 516         if (elem)
 517                 llist_remove_elem(iter->list, elem);
 518
 519         pthread_rwlock_unlock(&iter->list->lock);
 520
 521         if (! elem)
 522                 return -1;
 523         return 0;
 524 } /* sdb_llist_iter_remove */
 525
 526 size_t
 527 sdb_llist_len(sdb_llist_t *list)
 528 {
 529         if (! list)
 530                 return 0;
 531         return list->length;
 532 } /* sdb_llist_len */
 533
 534 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 535