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 node_t *
 138 node_smallest(sdb_avltree_t *tree)
 139 {
 140         node_t *n;
 141
 142         if (! tree)
 143                 return NULL;
 144
 145         n = tree->root;
 146         while (n && n->left)
 147                 n = n->left;
 148         return n;
 149 } /* node_smallest */
 150
 151 static void
 152 tree_clear(sdb_avltree_t *tree)
 153 {
 154         node_t *n;
 155
 156         n = node_smallest(tree);
 157         while (n) {
 158                 node_t *tmp = node_next(n);
 159
 160                 node_destroy(n);
 161                 n = tmp;
 162         }
 163
 164         tree->root = NULL;
 165         tree->size = 0;
 166 } /* tree_clear */
 167
 168 /* Switch node 'n' with its right child, making 'n'
 169  * the new left child of that node. */
 170 static void
 171 rotate_left(sdb_avltree_t *tree, node_t *n)
 172 {
 173         node_t *n2 = n->right;
 174         node_t *c = n2->left;
 175
 176         n2->parent = n->parent;
 177         if (! n2->parent)
 178                 tree->root = n2;
 179         else if (n2->parent->left == n)
 180                 n2->parent->left = n2;
 181         else
 182                 n2->parent->right = n2;
 183
 184         n2->left = n;
 185         n->parent = n2;
 186
 187         n->right = c;
 188         if (c)
 189                 c->parent = n;
 190
 191         n->height = CALC_HEIGHT(n);
 192         n2->height = CALC_HEIGHT(n2);
 193 } /* rotate_left */
 194
 195 /* Switch node 'n' with its left child, making 'n'
 196  * the new right child of that node. */
 197 static void
 198 rotate_right(sdb_avltree_t *tree, node_t *n)
 199 {
 200         node_t *n2 = n->left;
 201         node_t *c = n2->right;
 202
 203         n2->parent = n->parent;
 204         if (! n2->parent)
 205                 tree->root = n2;
 206         else if (n2->parent->left == n)
 207                 n2->parent->left = n2;
 208         else
 209                 n2->parent->right = n2;
 210
 211         n2->right = n;
 212         n->parent = n2;
 213
 214         n->left = c;
 215         if (c)
 216                 c->parent = n;
 217
 218         n->height = CALC_HEIGHT(n);
 219         n2->height = CALC_HEIGHT(n2);
 220 } /* rotate_right */
 221
 222 /* Rebalance a tree starting at node 'n' towards the root;
 223  * also, update the node heights all the way up to the root. */
 224 static void
 225 rebalance(sdb_avltree_t *tree, node_t *n)
 226 {
 227         for ( ; n; n = n->parent) {
 228                 int bf = BALANCE(n);
 229
 230                 if (bf == 0)
 231                         return;
 232
 233                 if ((-1 <= bf) && (bf <= 1)) {
 234                         n->height = CALC_HEIGHT(n);
 235                         continue;
 236                 }
 237
 238                 assert((-2 <= bf) && (bf <= 2));
 239
 240                 if (bf == 2) {
 241                         if (BALANCE(n->left) == -1)
 242                                 rotate_left(tree, n->left);
 243                         rotate_right(tree, n);
 244                 }
 245                 else {
 246                         if (BALANCE(n->right) == 1)
 247                                 rotate_right(tree, n->right);
 248                         rotate_left(tree, n);
 249                 }
 250
 251                 /* n was moved downwards; get back to the previous level */
 252                 n = n->parent;
 253         }
 254 } /* rebalance */
 255
 256 /*
 257  * public API
 258  */
 259
 260 sdb_avltree_t *
 261 sdb_avltree_create(sdb_object_cmp_cb cmp)
 262 {
 263         sdb_avltree_t *tree;
 264
 265         tree = malloc(sizeof(*tree));
 266         if (! tree)
 267                 return NULL;
 268
 269         if (! cmp)
 270                 cmp = sdb_object_cmp_by_name;
 271
 272         pthread_rwlock_init(&tree->lock, /* attr = */ NULL);
 273         tree->cmp = cmp;
 274
 275         tree->root = NULL;
 276         tree->size = 0;
 277         return tree;
 278 } /* sdb_avltree_create */
 279
 280 void
 281 sdb_avltree_destroy(sdb_avltree_t *tree)
 282 {
 283         if (! tree)
 284                 return;
 285
 286         pthread_rwlock_wrlock(&tree->lock);
 287         tree_clear(tree);
 288         pthread_rwlock_unlock(&tree->lock);
 289         pthread_rwlock_destroy(&tree->lock);
 290         free(tree);
 291 } /* sdb_avltree_destroy */
 292
 293 void
 294 sdb_avltree_clear(sdb_avltree_t *tree)
 295 {
 296         if (! tree)
 297                 return;
 298
 299         pthread_rwlock_wrlock(&tree->lock);
 300         tree_clear(tree);
 301         pthread_rwlock_unlock(&tree->lock);
 302 } /* sdb_avltree_clear */
 303
 304 int
 305 sdb_avltree_insert(sdb_avltree_t *tree, sdb_object_t *obj)
 306 {
 307         node_t *parent;
 308         node_t *n;
 309
 310         int diff = -1;
 311
 312         if (! tree)
 313                 return -1;
 314
 315         n = node_create(obj);
 316         if (! n)
 317                 return -1;
 318
 319         pthread_rwlock_wrlock(&tree->lock);
 320
 321         if (! tree->root) {
 322                 tree->root = n;
 323                 tree->size = 1;
 324                 pthread_rwlock_unlock(&tree->lock);
 325                 return 0;
 326         }
 327
 328         parent = tree->root;
 329         while (42) {
 330                 assert(parent);
 331
 332                 diff = tree->cmp(obj, parent->obj);
 333                 if (! diff) {
 334                         node_destroy(n);
 335                         pthread_rwlock_unlock(&tree->lock);
 336                         return -1;
 337                 }
 338
 339                 if (diff < 0) {
 340                         if (! parent->left) {
 341                                 parent->left = n;
 342                                 break;
 343                         }
 344                         parent = parent->left;
 345                 }
 346                 else {
 347                         if (! parent->right) {
 348                                 parent->right = n;
 349                                 break;
 350                         }
 351                         parent = parent->right;
 352                 }
 353         }
 354
 355         n->parent = parent;
 356         ++tree->size;
 357
 358         rebalance(tree, parent);
 359         pthread_rwlock_unlock(&tree->lock);
 360         return 0;
 361 } /* sdb_avltree_insert */
 362
 363 sdb_avltree_iter_t *
 364 sdb_avltree_get_iter(sdb_avltree_t *tree)
 365 {
 366         sdb_avltree_iter_t *iter;
 367
 368         if (! tree)
 369                 return NULL;
 370
 371         iter = malloc(sizeof(*iter));
 372         if (! iter)
 373                 return NULL;
 374
 375         pthread_rwlock_rdlock(&tree->lock);
 376
 377         iter->tree = tree;
 378         iter->node = node_smallest(tree);
 379
 380         pthread_rwlock_unlock(&tree->lock);
 381         return iter;
 382 } /* sdb_avltree_get_iter */
 383
 384 void
 385 sdb_avltree_iter_destroy(sdb_avltree_iter_t *iter)
 386 {
 387         if (! iter)
 388                 return;
 389
 390         iter->tree = NULL;
 391         iter->node = NULL;
 392         free(iter);
 393 } /* sdb_avltree_iter_destroy */
 394
 395 _Bool
 396 sdb_avltree_iter_has_next(sdb_avltree_iter_t *iter)
 397 {
 398         if (! iter)
 399                 return 0;
 400
 401         return iter->node != NULL;
 402 } /* sdb_avltree_iter_has_next */
 403
 404 sdb_object_t *
 405 sdb_avltree_iter_get_next(sdb_avltree_iter_t *iter)
 406 {
 407         node_t *n;
 408
 409         if (! iter)
 410                 return NULL;
 411
 412         n = iter->node;
 413         iter->node = node_next(iter->node);
 414         return n ? n->obj : NULL;
 415 } /* sdb_avltree_iter_get_next */
 416
 417 size_t
 418 sdb_avltree_size(sdb_avltree_t *tree)
 419 {
 420         return tree ? tree->size : 0;
 421 } /* sdb_avltree_size */
 422
 423 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 424