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_search(sdb_llist_t *list,
 309                 sdb_llist_lookup_cb lookup, const void *user_data)
 310 {
 311         sdb_llist_elem_t *elem;
 312
 313         if ((! list) || (! lookup))
 314                 return NULL;
 315
 316         pthread_rwlock_rdlock(&list->lock);
 317         elem = llist_search(list, lookup, user_data);
 318         pthread_rwlock_unlock(&list->lock);
 319
 320         if (elem)
 321                 return elem->obj;
 322         return NULL;
 323 } /* sdb_llist_search */
 324
 325 sdb_object_t *
 326 sdb_llist_search_by_name(sdb_llist_t *list, const char *key)
 327 {
 328         sdb_llist_elem_t *elem;
 329
 330         if (! list)
 331                 return NULL;
 332
 333         pthread_rwlock_rdlock(&list->lock);
 334
 335         for (elem = list->head; elem; elem = elem->next)
 336                 if (! strcasecmp(elem->obj->name, key))
 337                         break;
 338
 339         pthread_rwlock_unlock(&list->lock);
 340
 341         if (elem)
 342                 return elem->obj;
 343         return NULL;
 344 } /* sdb_llist_search_by_name */
 345
 346 sdb_object_t *
 347 sdb_llist_remove(sdb_llist_t *list,
 348                 sdb_llist_lookup_cb lookup, const void *user_data)
 349 {
 350         sdb_llist_elem_t *elem;
 351         sdb_object_t *obj = NULL;
 352
 353         if ((! list) || (! lookup))
 354                 return NULL;
 355
 356         pthread_rwlock_wrlock(&list->lock);
 357         elem = llist_search(list, lookup, user_data);
 358         if (elem)
 359                 obj = sdb_llist_remove_elem(list, elem);
 360         pthread_rwlock_unlock(&list->lock);
 361
 362         return obj;
 363 } /* sdb_llist_remove */
 364
 365 sdb_object_t *
 366 sdb_llist_shift(sdb_llist_t *list)
 367 {
 368         sdb_object_t *obj;
 369
 370         if ((! list) || (! list->head))
 371                 return NULL;
 372
 373         pthread_rwlock_wrlock(&list->lock);
 374         obj = sdb_llist_remove_elem(list, list->head);
 375         pthread_rwlock_unlock(&list->lock);
 376         return obj;
 377 } /* sdb_llist_shift */
 378
 379 sdb_llist_iter_t *
 380 sdb_llist_get_iter(sdb_llist_t *list)
 381 {
 382         sdb_llist_iter_t *iter;
 383
 384         if (! list)
 385                 return NULL;
 386
 387         iter = malloc(sizeof(*iter));
 388         if (! iter)
 389                 return NULL;
 390
 391         pthread_rwlock_rdlock(&list->lock);
 392
 393         iter->list = list;
 394         iter->elem = list->head;
 395
 396         /* XXX: keep lock until destroying the iterator? */
 397         pthread_rwlock_unlock(&list->lock);
 398         return iter;
 399 } /* sdb_llist_get_iter */
 400
 401 void
 402 sdb_llist_iter_destroy(sdb_llist_iter_t *iter)
 403 {
 404         if (! iter)
 405                 return;
 406
 407         iter->list = NULL;
 408         iter->elem = NULL;
 409         free(iter);
 410 } /* sdb_llist_iter_destroy */
 411
 412 _Bool
 413 sdb_llist_iter_has_next(sdb_llist_iter_t *iter)
 414 {
 415         if (! iter)
 416                 return 0;
 417         return iter->elem != NULL;
 418 } /* sdb_llist_iter_has_next */
 419
 420 sdb_object_t *
 421 sdb_llist_iter_get_next(sdb_llist_iter_t *iter)
 422 {
 423         sdb_object_t *obj;
 424
 425         if ((! iter) || (! iter->elem))
 426                 return NULL;
 427
 428         pthread_rwlock_rdlock(&iter->list->lock);
 429
 430         obj = iter->elem->obj;
 431         iter->elem = iter->elem->next;
 432
 433         pthread_rwlock_unlock(&iter->list->lock);
 434         return obj;
 435 } /* sdb_llist_iter_get_next */
 436
 437 int
 438 sdb_llist_iter_remove_current(sdb_llist_iter_t *iter)
 439 {
 440         sdb_llist_elem_t *elem;
 441
 442         if ((! iter) || (! iter->list))
 443                 return -1;
 444
 445         pthread_rwlock_wrlock(&iter->list->lock);
 446
 447         if (! iter->elem) /* reached end of list */
 448                 elem = iter->list->tail;
 449         else
 450                 elem = iter->elem->prev;
 451         if (elem)
 452                 sdb_llist_remove_elem(iter->list, elem);
 453
 454         pthread_rwlock_unlock(&iter->list->lock);
 455
 456         if (! elem)
 457                 return -1;
 458         return 0;
 459 } /* sdb_llist_iter_remove */
 460
 461 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 462