src/utils/avltree.c

   1 /*
   2  * SysDB - src/utils/avltree.c
   3  * Copyright (C) 2014 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/avltree.h"
  33
  34 #include <assert.h>
  35
  36 #include <stdlib.h>
  37 #include <pthread.h>
  38
  39 /*
  40  * private data types
  41  */
  42
  43 struct node;
  44 typedef struct node node_t;
  45
  46 struct node {
  47         sdb_object_t *obj;
  48
  49         node_t *parent;
  50         node_t *left;
  51         node_t *right;
  52 };
  53
  54 struct sdb_avltree {
  55         pthread_rwlock_t lock;
  56
  57         sdb_object_cmp_cb cmp;
  58
  59         node_t *root;
  60         size_t size;
  61 };
  62
  63 struct sdb_avltree_iter {
  64         sdb_avltree_t *tree;
  65         node_t *node;
  66 };
  67
  68 /*
  69  * private helper functions
  70  */
  71
  72 static void
  73 node_destroy(node_t *n)
  74 {
  75         sdb_object_deref(n->obj);
  76         n->obj = NULL;
  77         n->parent = n->left = n->right = NULL;
  78         free(n);
  79 } /* node_destroy */
  80
  81 static node_t *
  82 node_create(sdb_object_t *obj)
  83 {
  84         node_t *n = malloc(sizeof(*n));
  85         if (! n)
  86                 return NULL;
  87
  88         sdb_object_ref(obj);
  89         n->obj = obj;
  90         n->parent = n->left = n->right = NULL;
  91         return n;
  92 } /* node_create */
  93
  94 static node_t *
  95 node_next(node_t *n)
  96 {
  97         node_t *next;
  98
  99         if (! n)
 100                 return NULL;
 101
 102         /* descend into the right tree */
 103         if (n->right) {
 104                 next = n->right;
 105                 while (next->left)
 106                         next = next->left;
 107                 return next;
 108         }
 109
 110         /* visit the parent if we're in its left tree */
 111         if (n->parent && (n->parent->left == n))
 112                 return n->parent;
 113
 114         /* find the parent of the sibling sub-tree on the right */
 115         next = n->parent;
 116         next = NULL;
 117         while (n->parent && (n->parent->right == n)) {
 118                 n = n->parent;
 119                 next = n;
 120         }
 121         if (next)
 122                 next = next->parent;
 123         return next;
 124 } /* node_next */
 125
 126 static void
 127 tree_clear(sdb_avltree_t *tree)
 128 {
 129         node_t *n;
 130
 131         n = tree->root;
 132         while (n) {
 133                 node_t *tmp = node_next(n);
 134
 135                 node_destroy(n);
 136                 n = tmp;
 137         }
 138
 139         tree->root = NULL;
 140         tree->size = 0;
 141 } /* tree_clear */
 142
 143 /*
 144  * public API
 145  */
 146
 147 sdb_avltree_t *
 148 sdb_avltree_create(sdb_object_cmp_cb cmp)
 149 {
 150         sdb_avltree_t *tree;
 151
 152         tree = malloc(sizeof(*tree));
 153         if (! tree)
 154                 return NULL;
 155
 156         if (! cmp)
 157                 cmp = sdb_object_cmp_by_name;
 158
 159         pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
 160         tree->cmp = cmp;
 161
 162         tree->root = NULL;
 163         tree->size = 0;
 164         return tree;
 165 } /* sdb_avltree_create */
 166
 167 void
 168 sdb_avltree_destroy(sdb_avltree_t *tree)
 169 {
 170         if (! tree)
 171                 return;
 172
 173         pthread_rwlock_wrlock(&tree->lock);
 174         tree_clear(tree);
 175         pthread_rwlock_unlock(&tree->lock);
 176         pthread_rwlock_destroy(&tree->lock);
 177         free(tree);
 178 } /* sdb_avltree_destroy */
 179
 180 void
 181 sdb_avltree_clear(sdb_avltree_t *tree)
 182 {
 183         if (! tree)
 184                 return;
 185
 186         pthread_rwlock_wrlock(&tree->lock);
 187         tree_clear(tree);
 188         pthread_rwlock_unlock(&tree->lock);
 189 } /* sdb_avltree_clear */
 190
 191 int
 192 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
 193 {
 194         node_t *parent;
 195         node_t *n;
 196
 197         int diff = -1;
 198
 199         if (! tree)
 200                 return -1;
 201
 202         n = node_create(obj);
 203         if (! n)
 204                 return -1;
 205
 206         if (! tree->root) {
 207                 tree->root = n;
 208                 tree->size = 1;
 209                 return 0;
 210         }
 211
 212         parent = tree->root;
 213         while (42) {
 214                 assert(parent);
 215
 216                 diff = tree->cmp(obj, parent->obj);
 217                 if (! diff) {
 218                         node_destroy(n);
 219                         return -1;
 220                 }
 221
 222                 if (diff < 0) {
 223                         if (! parent->left) {
 224                                 parent->left = n;
 225                                 break;
 226                         }
 227                         parent = parent->left;
 228                 }
 229                 else {
 230                         if (! parent->right) {
 231                                 parent->right = n;
 232                                 break;
 233                         }
 234                         parent = parent->right;
 235                 }
 236         }
 237
 238         n->parent = parent;
 239         ++tree->size;
 240
 241         /* XXX: rebalance */
 242         return 0;
 243 } /* sdb_avltree_insert */
 244
 245 sdb_avltree_iter_t *
 246 sdb_avltree_get_iter(sdb_avltree_t *tree)
 247 {
 248         sdb_avltree_iter_t *iter;
 249
 250         if (! tree)
 251                 return NULL;
 252
 253         iter = malloc(sizeof(*iter));
 254         if (! iter)
 255                 return NULL;
 256
 257         pthread_rwlock_rdlock(&tree->lock);
 258
 259         iter->tree = tree;
 260         iter->node = tree->root->left;
 261         while (iter->node && iter->node->left)
 262                 iter->node = iter->node->left;
 263
 264         pthread_rwlock_unlock(&tree->lock);
 265         return iter;
 266 } /* sdb_avltree_get_iter */
 267
 268 void
 269 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
 270 {
 271         if (! iter)
 272                 return;
 273
 274         iter->tree = NULL;
 275         iter->node = NULL;
 276         free(iter);
 277 } /* sdb_avltree_iter_destroy */
 278
 279 _Bool
 280 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
 281 {
 282         if (! iter)
 283                 return 0;
 284
 285         return iter->node != NULL;
 286 } /* sdb_avltree_iter_has_next */
 287
 288 sdb_object_t *
 289 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
 290 {
 291         node_t *n;
 292
 293         if (! iter)
 294                 return NULL;
 295
 296         n = iter->node;
 297         iter->node = node_next(iter->node);
 298         return n ? n->obj : NULL;
 299 } /* sdb_avltree_iter_get_next */
 300
 301 size_t
 302 sdb_avltree_size(sdb_avltree_t *tree)
 303 {
 304         return tree ? tree->size : 0;
 305 } /* sdb_avltree_size */
 306
 307 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 308