src/utils_avltree.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3
   4 #include "utils_avltree.h"
   5
   6 #define BALANCE(n) ((((n)->right == NULL) ? 0 : (n)->right->height) \
   7                                  - (((n)->left == NULL) ? 0 : (n)->left->height))
   8
   9 /*
  10  * private data types
  11  */
  12 struct avl_node_s
  13 {
  14         void *key;
  15         void *value;
  16
  17         int height;
  18         struct avl_node_s *left;
  19         struct avl_node_s *right;
  20         struct avl_node_s *parent;
  21 };
  22 typedef struct avl_node_s avl_node_t;
  23
  24 struct avl_tree_s
  25 {
  26         avl_node_t *root;
  27         int (*compare) (const void *, const void *);
  28 };
  29
  30 struct avl_iterator_s
  31 {
  32         avl_tree_t *tree;
  33         avl_node_t *node;
  34 };
  35
  36 /*
  37  * private functions
  38  */
  39 static void free_node (avl_node_t *n)
  40 {
  41         if (n == NULL)
  42                 return;
  43
  44         if (n->left != NULL)
  45                 free_node (n->left);
  46         if (n->right != NULL)
  47                 free_node (n->right);
  48
  49         free (n);
  50 }
  51
  52 static avl_node_t *search (avl_tree_t *t, void *key)
  53 {
  54         avl_node_t *n;
  55         int cmp;
  56
  57         n = t->root;
  58         while (n != NULL)
  59         {
  60                 cmp = t->compare (key, n->key);
  61                 if (cmp == 0)
  62                         return (n);
  63                 else if (cmp < 0)
  64                         n = n->left;
  65                 else
  66                         n = n->right;
  67         }
  68
  69         return (NULL);
  70 }
  71
  72 static void rebalance (avl_tree_t *t, avl_node_t *n)
  73 {
  74         int height_left;
  75         int height_right;
  76         int height_new;
  77         int cmp;
  78
  79         while (n != NULL)
  80         {
  81                 height_left = (n->left == NULL) ? 0 : n->left->height;
  82                 height_right = (n->right == NULL) ? 0 : n->right->height;
  83
  84                 height_new = 1 + ((height_left > height_right) ? height_left : height_right);
  85
  86                 if (height_new == n->height)
  87                         break;
  88
  89                 n->height = height_new;
  90
  91                 cmp = height_right - height_left;
  92                 if (cmp < -1)
  93                 {
  94                         avl_node_t *l;
  95                         avl_node_t *lr;
  96
  97                         l = n->left;
  98                         lr = l->right;
  99
 100                         l->right = n;
 101                         l->parent = n->parent;
 102                         n->parent = l;
 103                         n->left = lr;
 104
 105                         if (lr != NULL)
 106                                 lr->parent = n;
 107
 108                         if (l->parent == NULL)
 109                         {
 110                                 assert (t->root == n);
 111                                 t->root = l;
 112                         }
 113                         else
 114                         {
 115                                 assert ((l->parent->left == n) || (l->parent->right == n));
 116                                 if (l->parent->left == n)
 117                                         l->parent->left = l;
 118                                 else
 119                                         l->parent->right = l;
 120                         }
 121                 }
 122                 else if (cmp > 1)
 123                 {
 124                         avl_node_t *r;
 125                         avl_node_t *rl;
 126
 127                         r = n->right;
 128                         rl = r->left;
 129
 130                         r->left = n;
 131                         r->parent = n->parent;
 132                         n->parent = r;
 133                         n->right = rl;
 134
 135                         if (rl != NULL)
 136                                 rl->parent = n;
 137
 138                         if (r->parent == NULL)
 139                         {
 140                                 assert (t->root == n);
 141                                 t->root = r;
 142                         }
 143                         else
 144                         {
 145                                 assert ((r->parent->left == n) || (r->parent->right == n));
 146                                 if (r->parent->left == n)
 147                                         r->parent->left = r;
 148                                 else
 149                                         r->parent->right = r;
 150                         }
 151                 }
 152                 else
 153                 {
 154                         n = n->parent;
 155                 }
 156
 157                 assert ((n == NULL) || (n->parent == NULL)
 158                                 || (n->parent->left == n)
 159                                 || (n->parent->right == n));
 160         } /* while (n != NULL) */
 161 } /* void rebalance */
 162
 163 static avl_iterator_t *avl_create_iterator (avl_tree_t *t, avl_node_t *n)
 164 {
 165         avl_iterator_t *iter;
 166
 167         iter = (avl_iterator_t *) malloc (sizeof (avl_iterator_t));
 168         if (iter == NULL)
 169                 return (NULL);
 170
 171         iter->tree = t;
 172         iter->node = n;
 173
 174         return (iter);
 175 }
 176
 177 void *avl_node_next (avl_tree_t *t, avl_node_t *n)
 178 {
 179         avl_node_t *r; /* return node */
 180
 181         if (n == NULL)
 182         {
 183                 return (NULL);
 184         }
 185         else if (n->right == NULL)
 186         {
 187
 188                 r = n->parent;
 189                 while (r != NULL)
 190                 {
 191                         /* stop if a bigger node is found */
 192                         if (t->compare (n, r) < 0) /* n < r */
 193                                 break;
 194                         r = r->parent;
 195                 }
 196         }
 197         else
 198         {
 199                 r = n->right;
 200                 while (r->left != NULL)
 201                         r = r->left;
 202         }
 203
 204         return (r);
 205 }
 206
 207 void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 208 {
 209         avl_node_t *r; /* return node */
 210
 211         if (n == NULL)
 212         {
 213                 return (NULL);
 214         }
 215         else if (n->left == NULL)
 216         {
 217
 218                 r = n->parent;
 219                 while (r != NULL)
 220                 {
 221                         /* stop if a smaller node is found */
 222                         if (t->compare (n, r) > 0) /* n > r */
 223                                 break;
 224                         r = r->parent;
 225                 }
 226         }
 227         else
 228         {
 229                 r = n->left;
 230                 while (r->right != NULL)
 231                         r = r->right;
 232         }
 233
 234         return (r);
 235 }
 236
 237 static void *_remove (avl_tree_t *t, avl_node_t *n)
 238 {
 239         void *ret;
 240
 241         assert ((t != NULL) && (n != NULL));
 242
 243         ret = n->value;
 244
 245         if ((n->left == NULL) && (n->right == NULL))
 246         {
 247                 /* Deleting a leave is easy */
 248                 if (n->parent == NULL)
 249                 {
 250                         assert (t->root == n);
 251                         t->root = NULL;
 252                 }
 253                 else
 254                 {
 255                         assert ((n->parent->left == n)
 256                                         || (n->parent->right == n));
 257                         if (n->parent->left == n)
 258                                 n->parent->left = NULL;
 259                         else
 260                                 n->parent->right = NULL;
 261
 262                         rebalance (t, n->parent);
 263                 }
 264
 265                 free_node (n);
 266         }
 267         else
 268         {
 269                 avl_node_t *r; /* replacement node */
 270                 if (BALANCE (n) < 0)
 271                 {
 272                         assert (n->left != NULL);
 273                         r = avl_node_prev (t, n);
 274                 }
 275                 else
 276                 {
 277                         assert (n->right != NULL);
 278                         r = avl_node_next (t, n);
 279                 }
 280                 n->key   = r->key;
 281                 n->value = r->value;
 282
 283                 _remove (t, r);
 284         }
 285
 286         return (ret);
 287 } /* void *_remove */
 288
 289 /*
 290  * public functions
 291  */
 292 avl_tree_t *avl_create (int (*compare) (const void *, const void *))
 293 {
 294         avl_tree_t *t;
 295
 296         if ((t = (avl_tree_t *) malloc (sizeof (avl_tree_t))) == NULL)
 297                 return (NULL);
 298
 299         t->root = NULL;
 300         t->compare = compare;
 301
 302         return (t);
 303 }
 304
 305 void avl_destroy (avl_tree_t *t)
 306 {
 307         free_node (t->root);
 308         free (t);
 309 }
 310
 311 int avl_insert (avl_tree_t *t, void *key, void *value)
 312 {
 313         avl_node_t *new;
 314         avl_node_t *nptr;
 315         int cmp;
 316
 317         if ((new = (avl_node_t *) malloc (sizeof (avl_node_t))) == NULL)
 318                 return (-1);
 319
 320         new->key = key;
 321         new->value = value;
 322         new->height = 1;
 323         new->left = NULL;
 324         new->right = NULL;
 325
 326         if (t->root == NULL)
 327         {
 328                 new->parent = NULL;
 329                 t->root = new;
 330                 return (0);
 331         }
 332
 333         nptr = t->root;
 334         while (42)
 335         {
 336                 cmp = t->compare (nptr->key, new->key);
 337                 if (cmp == 0)
 338                 {
 339                         free_node (new);
 340                         return (-1);
 341                 }
 342                 else if (cmp < 0)
 343                 {
 344                         /* nptr < new */
 345                         if (nptr->right == NULL)
 346                         {
 347                                 nptr->right = new;
 348                                 new->parent = nptr;
 349                                 nptr = NULL;
 350                                 break;
 351                         }
 352                         else
 353                         {
 354                                 nptr = nptr->right;
 355                         }
 356                 }
 357                 else /* if (cmp > 0) */
 358                 {
 359                         /* nptr > new */
 360                         if (nptr->left == NULL)
 361                         {
 362                                 nptr->left = new;
 363                                 new->parent = nptr;
 364                                 nptr = NULL;
 365                                 break;
 366                         }
 367                         else
 368                         {
 369                                 nptr = nptr->left;
 370                         }
 371                 }
 372         } /* while (42) */
 373
 374         assert ((new->parent != NULL)
 375                         && ((new->parent->left == new)
 376                                 || (new->parent->right == new)));
 377
 378         return (0);
 379 } /* int avl_insert */
 380
 381 void *avl_remove (avl_tree_t *t, void *key)
 382 {
 383         avl_node_t *n;
 384
 385         assert (t != NULL);
 386
 387         n = search (t, key);
 388         if (n == NULL)
 389                 return (NULL);
 390
 391         return (_remove (t, n));
 392 } /* void *avl_remove */
 393
 394 void *avl_get (avl_tree_t *t, void *key)
 395 {
 396         avl_node_t *n;
 397
 398         n = search (t, key);
 399         if (n == NULL)
 400                 return (NULL);
 401
 402         return (n->value);
 403 }
 404
 405 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
 406 {
 407         avl_node_t *n;
 408
 409         if (t == NULL)
 410                 return (NULL);
 411
 412         for (n = t->root; n != NULL; n = n->left)
 413                 if (n->left == NULL)
 414                         break;
 415
 416         return (avl_create_iterator (t, n));
 417 } /* avl_iterator_t *avl_get_iterator */
 418
 419 void *avl_iterator_next (avl_iterator_t *iter)
 420 {
 421         avl_node_t *n;
 422
 423         if ((iter == NULL) || (iter->node == NULL))
 424                 return (NULL);
 425
 426         n = avl_node_next (iter->tree, iter->node);
 427
 428         if (n == NULL)
 429                 return (NULL);
 430
 431         iter->node = n;
 432         return (n);
 433
 434 }
 435
 436 void *avl_iterator_prev (avl_iterator_t *iter)
 437 {
 438         avl_node_t *n;
 439
 440         if ((iter == NULL) || (iter->node == NULL))
 441                 return (NULL);
 442
 443         n = avl_node_prev (iter->tree, iter->node);
 444
 445         if (n == NULL)
 446                 return (NULL);
 447
 448         iter->node = n;
 449         return (n);
 450
 451 }
 452
 453 void avl_iterator_destroy (avl_iterator_t *iter)
 454 {
 455         free (iter);
 456 }