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