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 "sysdb.h"
  33 #include "utils/avltree.h"
  34
  35 #include <assert.h>
  36
  37 #include <stdlib.h>
  38 #include <pthread.h>
  39
  40 /*
  41  * private data types
  42  */
  43
  44 struct node;
  45 typedef struct node node_t;
  46
  47 struct node {
  48         sdb_object_t *obj;
  49
  50         node_t *parent;
  51         node_t *left;
  52         node_t *right;
  53
  54         size_t height;
  55 };
  56
  57 #define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
  58 #define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
  59                         NODE_HEIGHT((n)->left)) + 1)
  60
  61 #define BALANCE(n) \
  62         ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0)
  63
  64 struct sdb_avltree {
  65         pthread_rwlock_t lock;
  66
  67         sdb_object_cmp_cb cmp;
  68
  69         node_t *root;
  70         size_t size;
  71 };
  72
  73 struct sdb_avltree_iter {
  74         sdb_avltree_t *tree;
  75         node_t *node;
  76 };
  77
  78 /*
  79  * private helper functions
  80  */
  81
  82 static void
  83 node_destroy(node_t *n)
  84 {
  85         sdb_object_deref(n->obj);
  86         n->obj = NULL;
  87         n->parent = n->left = n->right = NULL;
  88         free(n);
  89 } /* node_destroy */
  90
  91 static node_t *
  92 node_create(sdb_object_t *obj)
  93 {
  94         node_t *n = malloc(sizeof(*n));
  95         if (! n)
  96                 return NULL;
  97
  98         sdb_object_ref(obj);
  99         n->obj = obj;
 100         n->parent = n->left = n->right = NULL;
 101         n->height = 1;
 102         return n;
 103 } /* node_create */
 104
 105 static node_t *
 106 node_next(node_t *n)
 107 {
 108         node_t *next;
 109
 110         if (! n)
 111                 return NULL;
 112
 113         /* descend into the right tree */
 114         if (n->right) {
 115                 next = n->right;
 116                 while (next->left)
 117                         next = next->left;
 118                 return next;
 119         }
 120
 121         /* visit the parent if we're in its left tree */
 122         if (n->parent && (n->parent->left == n))
 123                 return n->parent;
 124
 125         /* find the parent of the sibling sub-tree on the right */
 126         next = n->parent;
 127         next = NULL;
 128         while (n->parent && (n->parent->right == n)) {
 129                 n = n->parent;
 130                 next = n;
 131         }
 132         if (next)
 133                 next = next->parent;
 134         return next;
 135 } /* node_next */
 136
 137 static void
 138 tree_clear(sdb_avltree_t *tree)
 139 {
 140         node_t *n;
 141
 142         n = tree->root;
 143         while (n) {
 144                 node_t *tmp = node_next(n);
 145
 146                 node_destroy(n);
 147                 n = tmp;
 148         }
 149
 150         tree->root = NULL;
 151         tree->size = 0;
 152 } /* tree_clear */
 153
 154 /* Switch node 'n' with its right child, making 'n'
 155  * the new left child of that node. */
 156 static void
 157 rotate_left(sdb_avltree_t *tree, node_t *n)
 158 {
 159         node_t *n2 = n->right;
 160         node_t *c = n2->left;
 161
 162         n2->parent = n->parent;
 163         if (! n2->parent)
 164                 tree->root = n2;
 165         else if (n2->parent->left == n)
 166                 n2->parent->left = n2;
 167         else
 168                 n2->parent->right = n2;
 169
 170         n2->left = n;
 171         n->parent = n2;
 172
 173         n->right = c;
 174         if (c)
 175                 c->parent = n;
 176
 177         n->height = CALC_HEIGHT(n);
 178         n2->height = CALC_HEIGHT(n2);
 179 } /* rotate_left */
 180
 181 /* Switch node 'n' with its left child, making 'n'
 182  * the new right child of that node. */
 183 static void
 184 rotate_right(sdb_avltree_t *tree, node_t *n)
 185 {
 186         node_t *n2 = n->left;
 187         node_t *c = n2->right;
 188
 189         n2->parent = n->parent;
 190         if (! n2->parent)
 191                 tree->root = n2;
 192         else if (n2->parent->left == n)
 193                 n2->parent->left = n2;
 194         else
 195                 n2->parent->right = n2;
 196
 197         n2->right = n;
 198         n->parent = n2;
 199
 200         n->left = c;
 201         if (c)
 202                 c->parent = n;
 203
 204         n->height = CALC_HEIGHT(n);
 205         n2->height = CALC_HEIGHT(n2);
 206 } /* rotate_right */
 207
 208 /* Rebalance a tree starting at node 'n' towards the root;
 209  * also, update the node heights all the way up to the root. */
 210 static void
 211 rebalance(sdb_avltree_t *tree, node_t *n)
 212 {
 213         for ( ; n; n = n->parent) {
 214                 int bf = BALANCE(n);
 215
 216                 if (bf == 0)
 217                         return;
 218
 219                 if ((-1 <= bf) && (bf <= 1)) {
 220                         n->height = CALC_HEIGHT(n);
 221                         continue;
 222                 }
 223
 224                 assert((-2 <= bf) && (bf <= 2));
 225
 226                 if (bf == 2) {
 227                         if (BALANCE(n->left) == -1)
 228                                 rotate_left(tree, n->left);
 229                         rotate_right(tree, n);
 230                 }
 231                 else {
 232                         if (BALANCE(n->right) == 1)
 233                                 rotate_right(tree, n->right);
 234                         rotate_left(tree, n);
 235                 }
 236
 237                 /* n was moved downwards; get back to the previous level */
 238                 n = n->parent;
 239         }
 240 } /* rebalance */
 241
 242 /*
 243  * public API
 244  */
 245
 246 sdb_avltree_t *
 247 sdb_avltree_create(sdb_object_cmp_cb cmp)
 248 {
 249         sdb_avltree_t *tree;
 250
 251         tree = malloc(sizeof(*tree));
 252         if (! tree)
 253                 return NULL;
 254
 255         if (! cmp)
 256                 cmp = sdb_object_cmp_by_name;
 257
 258         pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
 259         tree->cmp = cmp;
 260
 261         tree->root = NULL;
 262         tree->size = 0;
 263         return tree;
 264 } /* sdb_avltree_create */
 265
 266 void
 267 sdb_avltree_destroy(sdb_avltree_t *tree)
 268 {
 269         if (! tree)
 270                 return;
 271
 272         pthread_rwlock_wrlock(&tree->lock);
 273         tree_clear(tree);
 274         pthread_rwlock_unlock(&tree->lock);
 275         pthread_rwlock_destroy(&tree->lock);
 276         free(tree);
 277 } /* sdb_avltree_destroy */
 278
 279 void
 280 sdb_avltree_clear(sdb_avltree_t *tree)
 281 {
 282         if (! tree)
 283                 return;
 284
 285         pthread_rwlock_wrlock(&tree->lock);
 286         tree_clear(tree);
 287         pthread_rwlock_unlock(&tree->lock);
 288 } /* sdb_avltree_clear */
 289
 290 int
 291 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
 292 {
 293         node_t *parent;
 294         node_t *n;
 295
 296         int diff = -1;
 297
 298         if (! tree)
 299                 return -1;
 300
 301         n = node_create(obj);
 302         if (! n)
 303                 return -1;
 304
 305         if (! tree->root) {
 306                 tree->root = n;
 307                 tree->size = 1;
 308                 return 0;
 309         }
 310
 311         parent = tree->root;
 312         while (42) {
 313                 assert(parent);
 314
 315                 diff = tree->cmp(obj, parent->obj);
 316                 if (! diff) {
 317                         node_destroy(n);
 318                         return -1;
 319                 }
 320
 321                 if (diff < 0) {
 322                         if (! parent->left) {
 323                                 parent->left = n;
 324                                 break;
 325                         }
 326                         parent = parent->left;
 327                 }
 328                 else {
 329                         if (! parent->right) {
 330                                 parent->right = n;
 331                                 break;
 332                         }
 333                         parent = parent->right;
 334                 }
 335         }
 336
 337         n->parent = parent;
 338         ++tree->size;
 339
 340         rebalance(tree, parent);
 341         return 0;
 342 } /* sdb_avltree_insert */
 343
 344 sdb_avltree_iter_t *
 345 sdb_avltree_get_iter(sdb_avltree_t *tree)
 346 {
 347         sdb_avltree_iter_t *iter;
 348
 349         if (! tree)
 350                 return NULL;
 351
 352         iter = malloc(sizeof(*iter));
 353         if (! iter)
 354                 return NULL;
 355
 356         pthread_rwlock_rdlock(&tree->lock);
 357
 358         iter->tree = tree;
 359         iter->node = tree->root->left;
 360         while (iter->node && iter->node->left)
 361                 iter->node = iter->node->left;
 362
 363         pthread_rwlock_unlock(&tree->lock);
 364         return iter;
 365 } /* sdb_avltree_get_iter */
 366
 367 void
 368 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
 369 {
 370         if (! iter)
 371                 return;
 372
 373         iter->tree = NULL;
 374         iter->node = NULL;
 375         free(iter);
 376 } /* sdb_avltree_iter_destroy */
 377
 378 _Bool
 379 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
 380 {
 381         if (! iter)
 382                 return 0;
 383
 384         return iter->node != NULL;
 385 } /* sdb_avltree_iter_has_next */
 386
 387 sdb_object_t *
 388 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
 389 {
 390         node_t *n;
 391
 392         if (! iter)
 393                 return NULL;
 394
 395         n = iter->node;
 396         iter->node = node_next(iter->node);
 397         return n ? n->obj : NULL;
 398 } /* sdb_avltree_iter_get_next */
 399
 400 size_t
 401 sdb_avltree_size(sdb_avltree_t *tree)
 402 {
 403         return tree ? tree->size : 0;
 404 } /* sdb_avltree_size */
 405
 406 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 407