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