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.11 2000/11/22 19:14:08 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 void *rbl_search_closest(rbltree_t *tree, void *data)
  92 {
  93   rbl_t *rbl;
  94
  95   rbl = rbl_search_closest_rbl(tree, data);
  96
  97   if(rbl)
  98     return rbl->data;
  99   else
 100     return NULL;
 101 }
 102
 103 /* Search exact match or return NULL pointer */
 104 rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
 105 {
 106   rbl_t *rbl;
 107   int result;
 108
 109   rbl = tree->top;
 110
 111   while(rbl)
 112     {
 113       result = tree->compare(data, rbl->data);
 114
 115       if(result < 0)
 116         rbl = rbl->left;
 117       else if(result > 0)
 118         rbl = rbl->right;
 119       else
 120         return rbl;
 121     }
 122
 123   return NULL;
 124 }
 125
 126 void *rbl_search(rbltree_t *tree, void *data)
 127 {
 128   rbl_t *rbl;
 129
 130   rbl = rbl_search_rbl(tree, data);
 131
 132   if(rbl)
 133     return rbl->data;
 134   else
 135     return NULL;
 136 }
 137
 138 /* Red-black tree operations taken from Introduction to Algorithms,
 139    Cormen, Leiserson & Rivest, chapter 14.
 140 */
 141
 142 void rbl_left_rotate(rbl_t *x)
 143 {
 144   rbl_t *y;
 145
 146   y = x->right;
 147   x->right = y->left;
 148
 149   if(y->left)
 150     y->left->parent = x;
 151
 152   y->parent = x->parent;
 153
 154   if(!x->parent)
 155     x->tree->top = y;
 156   else
 157     if(x == x->parent->left)
 158       x->parent->left = y;
 159     else
 160       x->parent->right = y;
 161
 162   y->left = x;
 163   x->parent = y;
 164 }
 165
 166 void rbl_right_rotate(rbl_t *y)
 167 {
 168   rbl_t *x;
 169
 170   x = y->left;
 171   y->left = x->right;
 172
 173   if(x->right)
 174     x->right->parent = y;
 175
 176   x->parent = y->parent;
 177
 178   if(!y->parent)
 179     y->tree->top = x;
 180   else
 181     if(y == y->parent->right)
 182       y->parent->right = x;
 183     else
 184       y->parent->left = x;
 185
 186   x->right = y;
 187   y->parent = x;
 188 }
 189
 190 /* Insert a node into the rbl tree */
 191 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
 192 {
 193   rbl_t *closest, *x, *y;
 194   int result;
 195
 196   rbl->tree = tree;
 197
 198   /* Binary tree and linked list insert */
 199
 200   if(tree->top)
 201     {
 202       closest = rbl_search_closest_rbl(tree, rbl->data);
 203       result = tree->compare(rbl->data, closest->data);
 204       if(result < 0)
 205         {
 206           closest->left = rbl;
 207
 208           rbl->prev = closest->prev;
 209           rbl->next = closest;
 210           closest->prev = rbl;
 211
 212           if(rbl->prev)
 213             rbl->prev->next = rbl;
 214           else
 215             tree->head = rbl;
 216         }
 217       else if(result > 0)
 218         {
 219           closest->right = rbl;
 220
 221           rbl->next = closest->next;
 222           rbl->prev = closest;
 223           closest->next = rbl;
 224
 225           if(rbl->next)
 226             rbl->next->prev = rbl;
 227           else
 228             tree->tail = rbl;
 229         }
 230       else
 231         return closest;         /* Ofcourse, we cannot add two identical things */
 232
 233       rbl->parent = closest;
 234     }
 235   else
 236     {
 237       tree->top = rbl;
 238       tree->head = rbl;
 239       tree->tail = rbl;
 240     }
 241
 242   /* Red-black part of insert */
 243
 244   x = rbl;
 245   x->color = RBL_RED;
 246
 247   while(x != tree->top && x->parent->color == RBL_RED)
 248     {
 249       if(x->parent == x->parent->parent->left)
 250         {
 251           y = x->parent->parent->right;
 252           if(y && y->color == RBL_RED)
 253             {
 254               x->parent->color = RBL_BLACK;
 255               y->color = RBL_BLACK;
 256               x->parent->parent->color = RBL_RED;
 257               x = x->parent->parent;
 258             }
 259           else
 260             {
 261               if(x == x->parent->right)
 262                 {
 263                   x = x->parent;
 264                   rbl_left_rotate(x);
 265                 }
 266               x->parent->color = RBL_BLACK;
 267               x->parent->parent->color = RBL_RED;
 268               rbl_right_rotate(x->parent->parent);
 269             }
 270         }
 271       else
 272         {
 273           y = x->parent->parent->left;
 274           if(y && y->color == RBL_RED)
 275             {
 276               x->parent->color = RBL_BLACK;
 277               y->color = RBL_BLACK;
 278               x->parent->parent->color = RBL_RED;
 279               x = x->parent->parent;
 280             }
 281           else
 282             {
 283               if(x == x->parent->left)
 284                 {
 285                   x = x->parent;
 286                   rbl_right_rotate(x);
 287                 }
 288               x->parent->color = RBL_BLACK;
 289               x->parent->parent->color = RBL_RED;
 290               rbl_left_rotate(x->parent->parent);
 291             }
 292         }
 293     }
 294
 295   tree->top->color = RBL_BLACK;
 296   return rbl;
 297 }
 298
 299 /* Create a new node and insert it into the tree */
 300 rbl_t *rbl_insert(rbltree_t *tree, void *data)
 301 {
 302   rbl_t *rbl;
 303
 304   rbl = new_rbl();
 305   rbl->data = data;
 306
 307   if(rbl_insert_rbl(tree, rbl) == rbl)
 308     return rbl;
 309   else
 310     {
 311       free_rbl(rbl);
 312       return NULL;
 313     }
 314 }
 315
 316 /* Restore red-black property after violation due to a deletion */
 317 void rbl_delete_fixup(rbl_t *x)
 318 {
 319   rbl_t *w;
 320
 321   while(x != x->tree->top && x->color == RBL_BLACK)
 322     {
 323       if(x == x->parent->left)
 324         {
 325           w = x->parent->right;
 326           if(w->color == RBL_RED)
 327             {
 328               w->color = RBL_BLACK;
 329               x->parent->color = RBL_RED;
 330               rbl_left_rotate(x->parent);
 331               w = x->parent->right;
 332             }
 333           if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
 334             {
 335               w->color = RBL_RED;
 336               x = x->parent;
 337             }
 338           else
 339             {
 340               if(w->right->color == RBL_BLACK)
 341                 {
 342                   w->left->color = RBL_BLACK;
 343                   w->color = RBL_RED;
 344                   rbl_right_rotate(w);
 345                   w = x->parent->right;
 346                 }
 347               w->color = x->parent->color;
 348               x->parent->color = RBL_BLACK;
 349               w->right->color = RBL_BLACK;
 350               rbl_left_rotate(x->parent);
 351               x = x->tree->top;
 352             }
 353         }
 354       else
 355         {
 356           w = x->parent->left;
 357           if(w->color == RBL_RED)
 358             {
 359               w->color = RBL_BLACK;
 360               x->parent->color = RBL_RED;
 361               rbl_right_rotate(x->parent);
 362               w = x->parent->left;
 363             }
 364           if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
 365             {
 366               w->color = RBL_RED;
 367               x = x->parent;
 368             }
 369           else
 370             {
 371               if(w->left->color == RBL_BLACK)
 372                 {
 373                   w->right->color = RBL_BLACK;
 374                   w->color = RBL_RED;
 375                   rbl_left_rotate(w);
 376                   w = x->parent->left;
 377                 }
 378               w->color = x->parent->color;
 379               x->parent->color = RBL_BLACK;
 380               w->left->color = RBL_BLACK;
 381               rbl_right_rotate(x->parent);
 382               x = x->tree->top;
 383             }
 384         }
 385     }
 386
 387   x->color = RBL_BLACK;
 388 }
 389
 390 /* Unlink node from the tree, but keep the node intact. */
 391 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
 392 {
 393   rbl_t *x, *y;
 394
 395   /* Binary tree delete */
 396
 397   if(rbl->left && rbl->right)
 398     y = rbl->next;
 399   else
 400     y = rbl;
 401
 402   if(y->left)
 403     x = y->left;
 404   else
 405     x = y->right;
 406
 407   if(x)
 408     x->parent = y->parent;
 409
 410   if(!y->parent)
 411     rbl->tree->top = x;
 412   else
 413     if(y == y->parent->left)
 414       y->parent->left = x;
 415     else
 416       y->parent->right = x;
 417
 418   if(y != rbl)
 419     {
 420       y->left = rbl->left;
 421       y->right = rbl->right;
 422       y->parent = rbl->parent;
 423       if(rbl == rbl->parent->left)
 424         rbl->parent->left = y;
 425       else
 426         rbl->parent->right = y;
 427     }
 428
 429   /* Linked list delete */
 430
 431   if(rbl->prev)
 432     rbl->prev->next = rbl->next;
 433   else
 434     rbl->tree->head = rbl->next;
 435
 436   if(rbl->next)
 437     rbl->next->prev = rbl->prev;
 438   else
 439     rbl->tree->tail = rbl->prev;
 440
 441   /* Red-black part of delete */
 442
 443   if(y->color == RBL_BLACK && x)
 444     rbl_delete_fixup(x);
 445
 446   return rbl;
 447 }
 448
 449 /* Search node in tree and unlink it */
 450 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
 451 {
 452   rbl_t *rbl;
 453
 454   rbl = rbl_search_rbl(tree, data);
 455
 456   if(rbl)
 457     rbl_unlink_rbl(rbl);
 458
 459   return rbl;
 460 }
 461
 462 /* Unlink node and free it */
 463 void rbl_delete_rbl(rbl_t *rbl)
 464 {
 465   rbl_unlink_rbl(rbl);
 466   free_rbl(rbl);
 467 }
 468
 469 /* Search node in tree, unlink and free it */
 470 void rbl_delete(rbltree_t *tree, void *data)
 471 {
 472   rbl_t *rbl;
 473
 474   rbl = rbl_unlink(tree, data);
 475
 476   if(rbl)
 477     free_rbl(rbl);
 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       free_rbl(rbl);
 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 }