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