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