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.2 2000/11/18 18:14:57 guus Exp $
  21 */
  22
  23
  24 /* Allocate a new rbl node */
  25 rbl_t *new_rbl()
  26 {
  27   return (rbl_t *)xmalloc_and_zero(sizeof(*rbl));
  28 }
  29
  30 /* Free a rbl node */
  31 void free_rbl(rbl_t *rbl)
  32 {
  33   free(rbl);
  34 }
  35
  36 /* Allocate a new rbltree header */
  37 rbltree_t *new_rbltree(rbl_compare_t *compare, rbl_delete_t *delete)
  38 {
  39   rbltree_t *tree;
  40
  41   tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
  42   if(tree)
  43     {
  44       tree->compare = compare;
  45       tree->delete = delete;
  46     }
  47
  48   return tree;
  49 }
  50
  51 /* Free a rbltree header */
  52 void free_rbltree(rbltree_t *tree)
  53 {
  54   free(tree);
  55 }
  56
  57 /* Search closest match in the tree */
  58 rbl_t rbl_search_closest(rbltree_t *tree, void *data)
  59 {
  60   rbl_t *rbl, *next;
  61   int result;
  62
  63   next = rbl = tree->head;
  64
  65   while(next)
  66     {
  67       rbl = next;
  68
  69       result = tree->compare(rbl->data, data);
  70
  71       if(result < 0)
  72         next = rbl->left;
  73       else if(result > 0)
  74         next = rbl->right;
  75       else
  76         break;
  77     }
  78
  79   return rbl;
  80 }
  81
  82 /* Search exact match or return NULL pointer */
  83 rbl_t rbl_search(rbltree_t *tree, void *data)
  84 {
  85   rbl_t *rbl, *next;
  86   int result;
  87
  88   next = rbl = tree->head;
  89
  90   while(next)
  91     {
  92       rbl = next;
  93
  94       result = tree->compare(rbl->data, data);
  95
  96       if(result < 0)
  97         next = rbl->left;
  98       else if(result > 0)
  99         next = rbl->right;
 100       else
 101         return rbl;
 102     }
 103
 104   return NULL;
 105 }
 106
 107 /* Red-black tree operations taken from Introduction to Algorithms,
 108    Cormen, Leiserson & Rivest, chapter 14.
 109 */
 110
 111 void rbl_left_rotate(rbl_t *x)
 112 {
 113   rbl_t *y;
 114
 115   y = x->right;
 116   x->right = y->left;
 117
 118   if(y->left)
 119     y->left->parent = x;
 120
 121   y->parent = x->parent;
 122
 123   if(!x->parent)
 124     x->tree->head = y;
 125   else
 126     if(x == x->parent->left)
 127       x->parent->left = y;
 128     else
 129       x->parent->right = y;
 130
 131   y->left = x;
 132   x->parent = y;
 133 }
 134
 135 void rbl_right_rotate(rbl_t *y)
 136 {
 137   rbl_t *x;
 138
 139   x = y->left;
 140   y->left = x->right;
 141
 142   if(x->right)
 143     x->right->parent = y;
 144
 145   x->parent = y->parent;
 146
 147   if(!y->parent)
 148     y->tree->head = x;
 149   else
 150     if(y == y->parent->right)
 151       y->parent->right = x;
 152     else
 153       y->parent->left = x;
 154
 155   x->right = y;
 156   y->parent = x;
 157 }
 158
 159 /* Insert a node into the rbl tree */
 160 rbl_t rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
 161 {
 162    rbl_t *closest, y;
 163    int result;
 164
 165   /* Binary tree and linked list insert */
 166
 167   if(tree->head)
 168     {
 169       closest = rbl_search_closest(tree, rbl->data);
 170       result = tree->compare(rbl->data, data);
 171       if(result < 0)
 172         {
 173           closest->left = rbl;
 174           rbl->prev = closest->prev;
 175           rbl->next = closest;
 176           closest->prev = rbl;
 177           rbl->prev->next = rbl;
 178         }
 179       else if(result > 0)
 180         {
 181           closest->right = rbl;
 182           rbl->next = closest->right;
 183           rbl->prev = closest;
 184           closest->next = rbl;
 185           rbl->next->prev = rbl;
 186         }
 187       else
 188         return closest;         /* Ofcourse, we cannot add two identical things */
 189     }
 190   else
 191     tree->head = rbl;
 192
 193   /* Red-black part of insert */
 194
 195   rbl->color = RBL_RED;
 196
 197   while(rbl->parent && rbl->parent->color == RBL_RED)
 198     {
 199       if(rbl->parent == rbl->parent->parent->left)
 200         {
 201           y = rbl->parent->parent->right;
 202           if(y->color == RBL_RED)
 203             {
 204               rbl->parent->color = RBL_BLACK;
 205               y->color = RBL_BLACK;
 206               rbl->parent->parent->color = RBL_RED;
 207               rbl = rbl->parent->parent;
 208             }
 209           else
 210             {
 211               if(rbl == rbl->parent->right)
 212                 {
 213                   rbl = rbl->parent;
 214                   rbl_left_rotate(rbl);
 215                 }
 216               rbl->parent->color = RBL_BLACK;
 217               rbl->parent->parent->color = RBL_RED;
 218               rbl_right_rotate(rbl->parent->parent);
 219             }
 220         }
 221       else
 222         {
 223           y = rbl->parent->parent->left;
 224           if(y->color == RBL_RED)
 225             {
 226               rbl->parent->color = RBL_BLACK;
 227               y->color = RBL_BLACK;
 228               rbl->parent->parent->color = RBL_RED;
 229               rbl = rbl->parent->parent;
 230             }
 231           else
 232             {
 233               if(rbl == rbl->parent->left)
 234                 {
 235                   rbl = rbl->parent;
 236                   rbl_right_rotate(rbl);
 237                 }
 238               rbl->parent->color = RBL_BLACK;
 239               rbl->parent->parent->color = RBL_RED;
 240               rbl_left_rotate(rbl->parent->parent);
 241             }
 242         }
 243     }
 244
 245   tree->head->color = RBL_BLACK;
 246
 247   return rbl;
 248 }
 249
 250 /* Create a new node and insert it into the tree */
 251 rbl_t rbl_insert(rbltree_t *tree, void *data)
 252 {
 253   rbl_t *rbl;
 254
 255   rbl = new_rbl();
 256   rbl->data = data;
 257
 258   return rbl_insert_rbl(tree, rbl);
 259 }
 260
 261 /* Unlink node from the tree, but keep the node intact */
 262 rbl_t rbl_unlink_rbl(rbl_t *rbl)
 263 {
 264 }
 265
 266 /* Search node in tree and unlink it */
 267 rbl_t rbl_unlink(rbltree_t *tree, void *data)
 268 {
 269   rbl_t *rbl;
 270
 271   rbl = rbl_search(tree, data);
 272
 273   if(rbl)
 274     return rbl_unlink_rbl(rbl);
 275   else
 276     return NULL;
 277 }
 278
 279 /* Unlink node and free it */
 280 void rbl_delete_rbl(rbl_t *rbl)
 281 {
 282   free_rbl(rbl_unlink_rbl(rbl));
 283 }
 284
 285 /* Search node in tree, unlink and free it */
 286 void rbl_delete(rbltree_t *tree, void *data)
 287 {
 288   free_rbl(rbl_unlink(tree, data));
 289 }