tinc-vpn.org Git - tinc/blob - lib/rbl.c

   1 /*
   2     rbl.c -- red-black tree + linked list convenience
   3     Copyright (C) 2000 Ivo Timmermans <itimmermans@bigfoot.com>,
   4                   2000 Guus Sliepen <guus@sliepen.warande.net>
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19
  20     $Id: rbl.c,v 1.1.2.8 2000/11/20 19:12:10 guus Exp $
  21 */
  22
  23 #include <stdlib.h>
  24 #include <xalloc.h>
  25
  26 #include "rbl.h"
  27
  28 /* Allocate a new rbl node */
  29 rbl_t *new_rbl()
  30 {
  31   return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
  32 }
  33
  34 /* Free a rbl node */
  35 void free_rbl(rbl_t *rbl)
  36 {
  37   free(rbl);
  38 }
  39
  40 /* Allocate a new rbltree header */
  41 rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
  42 {
  43   rbltree_t *tree;
  44
  45   tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
  46   if(tree)
  47     {
  48       tree->compare = compare;
  49       tree->delete = delete;
  50     }
  51
  52   return tree;
  53 }
  54
  55 /* Free a rbltree header */
  56 void free_rbltree(rbltree_t *tree)
  57 {
  58   free(tree);
  59 }
  60
  61 /* Search closest match in the tree */
  62 rbl_t *rbl_search_closest_rbl(rbltree_t *tree, void *data)
  63 {
  64   rbl_t *rbl, *next;
  65   int result;
  66
  67   next = rbl = tree->top;
  68
  69   while(next)
  70     {
  71       rbl = next;
  72
  73       result = tree->compare(data, rbl->data);
  74
  75       if(result < 0)
  76         next = rbl->left;
  77       else if(result > 0)
  78         next = rbl->right;
  79       else
  80         break;
  81     }
  82
  83   return rbl;
  84 }
  85
  86 void *rbl_search_closest(rbltree_t *tree, void *data)
  87 {
  88   return rbl_search_closest_rbl(tree, data)->data;
  89 }
  90
  91 /* Search exact match or return NULL pointer */
  92 rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
  93 {
  94   rbl_t *rbl, *next;
  95   int result;
  96
  97   next = rbl = tree->top;
  98
  99   while(next)
 100     {
 101       rbl = next;
 102
 103       result = tree->compare(data, rbl->data);
 104
 105       if(result < 0)
 106         next = rbl->left;
 107       else if(result > 0)
 108         next = rbl->right;
 109       else
 110         return rbl;
 111     }
 112
 113   return NULL;
 114 }
 115
 116 void *rbl_search(rbltree_t *tree, void *data)
 117 {
 118   rbl_t *rbl;
 119
 120   rbl = rbl_search_rbl(tree, data);
 121
 122   if(rbl)
 123     return rbl->data;
 124   else
 125     return NULL;
 126 }
 127
 128 /* Red-black tree operations taken from Introduction to Algorithms,
 129    Cormen, Leiserson & Rivest, chapter 14.
 130 */
 131
 132 void rbl_left_rotate(rbl_t *x)
 133 {
 134   rbl_t *y;
 135
 136   y = x->right;
 137   x->right = y->left;
 138
 139   if(y->left)
 140     y->left->parent = x;
 141
 142   y->parent = x->parent;
 143
 144   if(!x->parent)
 145     x->tree->top = y;
 146   else
 147     if(x == x->parent->left)
 148       x->parent->left = y;
 149     else
 150       x->parent->right = y;
 151
 152   y->left = x;
 153   x->parent = y;
 154 }
 155
 156 void rbl_right_rotate(rbl_t *y)
 157 {
 158   rbl_t *x;
 159
 160   x = y->left;
 161   y->left = x->right;
 162
 163   if(x->right)
 164     x->right->parent = y;
 165
 166   x->parent = y->parent;
 167
 168   if(!y->parent)
 169     y->tree->top = x;
 170   else
 171     if(y == y->parent->right)
 172       y->parent->right = x;
 173     else
 174       y->parent->left = x;
 175
 176   x->right = y;
 177   y->parent = x;
 178 }
 179
 180 /* Insert a node into the rbl tree */
 181 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
 182 {
 183   rbl_t *closest, *x, *y;
 184   int result;
 185
 186   rbl->tree = tree;
 187
 188   /* Binary tree and linked list insert */
 189
 190   if(tree->top)
 191     {
 192       closest = rbl_search_closest_rbl(tree, rbl->data);
 193       result = tree->compare(rbl->data, closest->data);
 194       if(result < 0)
 195         {
 196           closest->left = rbl;
 197
 198           rbl->prev = closest->prev;
 199           rbl->next = closest;
 200           closest->prev = rbl;
 201
 202           if(rbl->prev)
 203             rbl->prev->next = rbl;
 204           else
 205             tree->head = rbl;
 206         }
 207       else if(result > 0)
 208         {
 209           closest->right = rbl;
 210
 211           rbl->next = closest->next;
 212           rbl->prev = closest;
 213           closest->next = rbl;
 214
 215           if(rbl->next)
 216             rbl->next->prev = rbl;
 217           else
 218             tree->tail = rbl;
 219         }
 220       else
 221         return closest;         /* Ofcourse, we cannot add two identical things */
 222
 223       rbl->parent = closest;
 224     }
 225   else
 226     {
 227       tree->top = rbl;
 228       tree->head = rbl;
 229       tree->tail = rbl;
 230     }
 231
 232   /* Red-black part of insert */
 233
 234   x = rbl;
 235   x->color = RBL_RED;
 236
 237   while(x != tree->top && x->parent->color == RBL_RED)
 238     {
 239       if(x->parent == x->parent->parent->left)
 240         {
 241           y = x->parent->parent->right;
 242           if(y && y->color == RBL_RED)
 243             {
 244               x->parent->color = RBL_BLACK;
 245               y->color = RBL_BLACK;
 246               x->parent->parent->color = RBL_RED;
 247               x = x->parent->parent;
 248             }
 249           else
 250             {
 251               if(x == x->parent->right)
 252                 {
 253                   x = x->parent;
 254                   rbl_left_rotate(x);
 255                 }
 256               x->parent->color = RBL_BLACK;
 257               x->parent->parent->color = RBL_RED;
 258               rbl_right_rotate(x->parent->parent);
 259             }
 260         }
 261       else
 262         {
 263           y = x->parent->parent->left;
 264           if(y && y->color == RBL_RED)
 265             {
 266               x->parent->color = RBL_BLACK;
 267               y->color = RBL_BLACK;
 268               x->parent->parent->color = RBL_RED;
 269               x = x->parent->parent;
 270             }
 271           else
 272             {
 273               if(x == x->parent->left)
 274                 {
 275                   x = x->parent;
 276                   rbl_right_rotate(x);
 277                 }
 278               x->parent->color = RBL_BLACK;
 279               x->parent->parent->color = RBL_RED;
 280               rbl_left_rotate(x->parent->parent);
 281             }
 282         }
 283     }
 284
 285   tree->top->color = RBL_BLACK;
 286   return rbl;
 287 }
 288
 289 /* Create a new node and insert it into the tree */
 290 rbl_t *rbl_insert(rbltree_t *tree, void *data)
 291 {
 292   rbl_t *rbl;
 293
 294   rbl = new_rbl();
 295   rbl->data = data;
 296
 297   if(rbl_insert_rbl(tree, rbl) == rbl)
 298     return rbl;
 299   else
 300     {
 301       free_rbl(rbl);
 302       return NULL;
 303     }
 304 }
 305
 306 /* Restore red-black property after violation due to a deletion */
 307 void rbl_delete_fixup(rbl_t *x)
 308 {
 309   rbl_t *w;
 310
 311   while(x != x->tree->top && x->color == RBL_BLACK)
 312     {
 313       if(x == x->parent->left)
 314         {
 315           w = x->parent->right;
 316           if(w->color == RBL_RED)
 317             {
 318               w->color = RBL_BLACK;
 319               x->parent->color = RBL_RED;
 320               rbl_left_rotate(x->parent);
 321               w = x->parent->right;
 322             }
 323           if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
 324             {
 325               w->color = RBL_RED;
 326               x = x->parent;
 327             }
 328           else
 329             {
 330               if(w->right->color == RBL_BLACK)
 331                 {
 332                   w->left->color = RBL_BLACK;
 333                   w->color = RBL_RED;
 334                   rbl_right_rotate(w);
 335                   w = x->parent->right;
 336                 }
 337               w->color = x->parent->color;
 338               x->parent->color = RBL_BLACK;
 339               w->right->color = RBL_BLACK;
 340               rbl_left_rotate(x->parent);
 341               x = x->tree->top;
 342             }
 343         }
 344       else
 345         {
 346           w = x->parent->left;
 347           if(w->color == RBL_RED)
 348             {
 349               w->color = RBL_BLACK;
 350               x->parent->color = RBL_RED;
 351               rbl_right_rotate(x->parent);
 352               w = x->parent->left;
 353             }
 354           if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
 355             {
 356               w->color = RBL_RED;
 357               x = x->parent;
 358             }
 359           else
 360             {
 361               if(w->left->color == RBL_BLACK)
 362                 {
 363                   w->right->color = RBL_BLACK;
 364                   w->color = RBL_RED;
 365                   rbl_left_rotate(w);
 366                   w = x->parent->left;
 367                 }
 368               w->color = x->parent->color;
 369               x->parent->color = RBL_BLACK;
 370               w->left->color = RBL_BLACK;
 371               rbl_right_rotate(x->parent);
 372               x = x->tree->top;
 373             }
 374         }
 375     }
 376
 377   x->color = RBL_BLACK;
 378 }
 379
 380 /* Unlink node from the tree, but keep the node intact. */
 381 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
 382 {
 383   rbl_t *x, *y;
 384
 385   /* Binary tree delete */
 386
 387   if(rbl->left && rbl->right)
 388     y = rbl->next;
 389   else
 390     y = rbl;
 391
 392   if(y->left)
 393     x = y->left;
 394   else
 395     x = y->right;
 396
 397   if(x)
 398     x->parent = y->parent;
 399
 400   if(!y->parent)
 401     rbl->tree->top = x;
 402   else
 403     if(y == y->parent->left)
 404       y->parent->left = x;
 405     else
 406       y->parent->right = x;
 407
 408   if(y != rbl)
 409     {
 410       y->left = rbl->left;
 411       y->right = rbl->right;
 412       y->parent = rbl->parent;
 413       if(rbl == rbl->parent->left)
 414         rbl->parent->left = y;
 415       else
 416         rbl->parent->right = y;
 417     }
 418
 419   /* Linked list delete */
 420
 421   if(rbl->prev)
 422     rbl->prev->next = rbl->next;
 423   else
 424     rbl->tree->head = rbl->next;
 425
 426   if(rbl->next)
 427     rbl->next->prev = rbl->prev;
 428   else
 429     rbl->tree->tail = rbl->prev;
 430
 431   /* Red-black part of delete */
 432
 433   if(y->color == RBL_BLACK && x)
 434     rbl_delete_fixup(x);
 435
 436   return rbl;
 437 }
 438
 439 /* Search node in tree and unlink it */
 440 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
 441 {
 442   rbl_t *rbl;
 443
 444   rbl = rbl_search_rbl(tree, data);
 445
 446   if(rbl)
 447     return rbl_unlink_rbl(rbl);
 448   else
 449     return NULL;
 450 }
 451
 452 /* Unlink node and free it */
 453 void rbl_delete_rbl(rbl_t *rbl)
 454 {
 455   free_rbl(rbl_unlink_rbl(rbl));
 456 }
 457
 458 /* Search node in tree, unlink and free it */
 459 void rbl_delete(rbltree_t *tree, void *data)
 460 {
 461   free_rbl(rbl_unlink(tree, data));
 462 }
 463
 464 rbl_unlink_rbltree_branch(rbl_t *rbl)
 465 {
 466   if(rbl->left)
 467     rbl_unlink_rbltree_branch(rbl->left);
 468
 469   if(rbl->right)
 470     rbl_unlink_rbltree_branch(rbl->right);
 471
 472   if(rbl->parent)
 473     {
 474       if(rbl == rbl->parent->left)
 475         rbl->parent->left = NULL;
 476       else
 477         rbl->parent->right = NULL;
 478     }
 479 }
 480
 481 /* Optimized unlinking for a complete tree */
 482 void rbl_unlink_rbltree(rbltree_t *tree)
 483 {
 484   rbl_t *rbl, *next;
 485
 486   for(rbl = tree->head; rbl; rbl = next)
 487     {
 488       next = rbl->next;
 489       rbl->tree = NULL;
 490       rbl->parent = NULL;
 491       rbl->left = NULL;
 492       rbl->right = NULL;
 493       rbl->prev = NULL;
 494       rbl->next = NULL;
 495     }
 496
 497   tree->top = NULL;
 498   tree->head = NULL;
 499   tree->tail = NULL;
 500 }
 501
 502 /* Optimized deletion for a complete tree */
 503 void rbl_delete_rbltree(rbltree_t *tree)
 504 {
 505   rbl_t *rbl, *next;
 506
 507   for(rbl = tree->head; rbl; rbl = next)
 508     {
 509       next = rbl->next;
 510       tree->delete(rbl->data);
 511     }
 512
 513   tree->top = NULL;
 514   tree->head = NULL;
 515   tree->tail = NULL;
 516 }
 517
 518 /* Do action for each list entry (in order)
 519    Deletion of entry for which action is called is allowed.
 520  */
 521 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
 522 {
 523   rbl_t *rbl, *next;
 524
 525   for(rbl = tree->head; rbl; rbl = next)
 526     {
 527       next = rbl->next;
 528       action(rbl->data);
 529     }
 530 }
 531
 532 void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
 533 {
 534   rbl_t *rbl, *next;
 535
 536   for(rbl = tree->head; rbl; rbl = next)
 537     {
 538       next = rbl->next;
 539       action(rbl);
 540     }
 541 }