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