rbtree.c revision 269257
1254721Semaste/* 2254721Semaste * rbtree.c -- generic red black tree 3353358Sdim * 4353358Sdim * Copyright (c) 2001-2007, NLnet Labs. All rights reserved. 5353358Sdim * 6254721Semaste * This software is open source. 7254721Semaste * 8254721Semaste * Redistribution and use in source and binary forms, with or without 9254721Semaste * modification, are permitted provided that the following conditions 10254721Semaste * are met: 11254721Semaste * 12288943Sdim * Redistributions of source code must retain the above copyright notice, 13254721Semaste * this list of conditions and the following disclaimer. 14288943Sdim * 15309124Sdim * Redistributions in binary form must reproduce the above copyright notice, 16254721Semaste * this list of conditions and the following disclaimer in the documentation 17254721Semaste * and/or other materials provided with the distribution. 18254721Semaste * 19254721Semaste * Neither the name of the NLNET LABS nor the names of its contributors may 20288943Sdim * be used to endorse or promote products derived from this software without 21360784Sdim * specific prior written permission. 22258054Semaste * 23327952Sdim * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24321369Sdim * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25321369Sdim * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26341825Sdim * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27353358Sdim * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28314564Sdim * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29314564Sdim * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30341825Sdim * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31254721Semaste * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32254721Semaste * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33254721Semaste * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34353358Sdim * 35353358Sdim */ 36353358Sdim 37353358Sdim/** 38288943Sdim * \file 39314564Sdim * Implementation of a redblack tree. 40288943Sdim */ 41314564Sdim 42314564Sdim#include "config.h" 43314564Sdim#include "log.h" 44296417Sdim#include "fptr_wlist.h" 45314564Sdim#include "util/rbtree.h" 46288943Sdim 47314564Sdim/** Node colour black */ 48314564Sdim#define BLACK 0 49288943Sdim/** Node colour red */ 50314564Sdim#define RED 1 51314564Sdim 52314564Sdim/** the NULL node, global alloc */ 53288943Sdimrbnode_t rbtree_null_node = { 54314564Sdim RBTREE_NULL, /* Parent. */ 55322326Semaste RBTREE_NULL, /* Left. */ 56288943Sdim RBTREE_NULL, /* Right. */ 57353358Sdim NULL, /* Key. */ 58341825Sdim BLACK /* Color. */ 59314564Sdim}; 60353358Sdim 61314564Sdim/** rotate subtree left (to preserve redblack property) */ 62353358Sdimstatic void rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node); 63353358Sdim/** rotate subtree right (to preserve redblack property) */ 64353358Sdimstatic void rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node); 65353358Sdim/** Fixup node colours when insert happened */ 66353358Sdimstatic void rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node); 67353358Sdim/** Fixup node colours when delete happened */ 68314564Sdimstatic void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent); 69314564Sdim 70314564Sdim/* 71314564Sdim * Creates a new red black tree, intializes and returns a pointer to it. 72296417Sdim * 73314564Sdim * Return NULL on failure. 74314564Sdim * 75341825Sdim */ 76341825Sdimrbtree_t * 77314564Sdimrbtree_create (int (*cmpf)(const void *, const void *)) 78296417Sdim{ 79314564Sdim rbtree_t *rbtree; 80254721Semaste 81314564Sdim /* Allocate memory for it */ 82288943Sdim rbtree = (rbtree_t *) malloc(sizeof(rbtree_t)); 83314564Sdim if (!rbtree) { 84288943Sdim return NULL; 85314564Sdim } 86314564Sdim 87341825Sdim /* Initialize it */ 88341825Sdim rbtree_init(rbtree, cmpf); 89341825Sdim 90314564Sdim return rbtree; 91314564Sdim} 92341825Sdim 93341825Sdimvoid 94314564Sdimrbtree_init(rbtree_t *rbtree, int (*cmpf)(const void *, const void *)) 95254721Semaste{ 96314564Sdim /* Initialize it */ 97314564Sdim rbtree->root = RBTREE_NULL; 98254721Semaste rbtree->count = 0; 99314564Sdim rbtree->cmp = cmpf; 100254721Semaste} 101314564Sdim 102254721Semaste/* 103314564Sdim * Rotates the node to the left. 104353358Sdim * 105254721Semaste */ 106353358Sdimstatic void 107280031Sdimrbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node) 108314564Sdim{ 109321369Sdim rbnode_t *right = node->right; 110254721Semaste node->right = right->left; 111327952Sdim if (right->left != RBTREE_NULL) 112327952Sdim right->left->parent = node; 113327952Sdim 114327952Sdim right->parent = node->parent; 115254721Semaste 116314564Sdim if (node->parent != RBTREE_NULL) { 117314564Sdim if (node == node->parent->left) { 118341825Sdim node->parent->left = right; 119341825Sdim } else { 120314564Sdim node->parent->right = right; 121353358Sdim } 122314564Sdim } else { 123314564Sdim rbtree->root = right; 124314564Sdim } 125353358Sdim right->left = node; 126314564Sdim node->parent = right; 127314564Sdim} 128314564Sdim 129353358Sdim/* 130254721Semaste * Rotates the node to the right. 131341825Sdim * 132341825Sdim */ 133314564Sdimstatic void 134341825Sdimrbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node) 135341825Sdim{ 136341825Sdim rbnode_t *left = node->left; 137341825Sdim node->left = left->right; 138341825Sdim if (left->right != RBTREE_NULL) 139341825Sdim left->right->parent = node; 140341825Sdim 141341825Sdim left->parent = node->parent; 142314564Sdim 143353358Sdim if (node->parent != RBTREE_NULL) { 144314564Sdim if (node == node->parent->right) { 145314564Sdim node->parent->right = left; 146321369Sdim } else { 147321369Sdim node->parent->left = left; 148321369Sdim } 149254721Semaste } else { 150314564Sdim rbtree->root = left; 151314564Sdim } 152341825Sdim left->right = node; 153341825Sdim node->parent = left; 154341825Sdim} 155341825Sdim 156314564Sdimstatic void 157353358Sdimrbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node) 158314564Sdim{ 159314564Sdim rbnode_t *uncle; 160314564Sdim 161314564Sdim /* While not at the root and need fixing... */ 162314564Sdim while (node != rbtree->root && node->parent->color == RED) { 163314564Sdim /* If our parent is left child of our grandparent... */ 164314564Sdim if (node->parent == node->parent->parent->left) { 165314564Sdim uncle = node->parent->parent->right; 166314564Sdim 167314564Sdim /* If our uncle is red... */ 168314564Sdim if (uncle->color == RED) { 169314564Sdim /* Paint the parent and the uncle black... */ 170353358Sdim node->parent->color = BLACK; 171314564Sdim uncle->color = BLACK; 172314564Sdim 173314564Sdim /* And the grandparent red... */ 174314564Sdim node->parent->parent->color = RED; 175314564Sdim 176314564Sdim /* And continue fixing the grandparent */ 177314564Sdim node = node->parent->parent; 178314564Sdim } else { /* Our uncle is black... */ 179314564Sdim /* Are we the right child? */ 180314564Sdim if (node == node->parent->right) { 181314564Sdim node = node->parent; 182314564Sdim rbtree_rotate_left(rbtree, node); 183314564Sdim } 184314564Sdim /* Now we're the left child, repaint and rotate... */ 185314564Sdim node->parent->color = BLACK; 186314564Sdim node->parent->parent->color = RED; 187314564Sdim rbtree_rotate_right(rbtree, node->parent->parent); 188314564Sdim } 189353358Sdim } else { 190314564Sdim uncle = node->parent->parent->left; 191314564Sdim 192314564Sdim /* If our uncle is red... */ 193353358Sdim if (uncle->color == RED) { 194314564Sdim /* Paint the parent and the uncle black... */ 195321369Sdim node->parent->color = BLACK; 196321369Sdim uncle->color = BLACK; 197254721Semaste 198341825Sdim /* And the grandparent red... */ 199341825Sdim node->parent->parent->color = RED; 200314564Sdim 201314564Sdim /* And continue fixing the grandparent */ 202254721Semaste node = node->parent->parent; 203314564Sdim } else { /* Our uncle is black... */ 204314564Sdim /* Are we the right child? */ 205341825Sdim if (node == node->parent->left) { 206341825Sdim node = node->parent; 207341825Sdim rbtree_rotate_right(rbtree, node); 208341825Sdim } 209341825Sdim /* Now we're the right child, repaint and rotate... */ 210341825Sdim node->parent->color = BLACK; 211254721Semaste node->parent->parent->color = RED; 212341825Sdim rbtree_rotate_left(rbtree, node->parent->parent); 213254721Semaste } 214314564Sdim } 215254721Semaste } 216314564Sdim rbtree->root->color = BLACK; 217254721Semaste} 218314564Sdim 219314564Sdim 220254721Semaste/* 221314564Sdim * Inserts a node into a red black tree. 222254721Semaste * 223314564Sdim * Returns NULL on failure or the pointer to the newly added node 224288943Sdim * otherwise. 225314564Sdim */ 226254721Semasterbnode_t * 227314564Sdimrbtree_insert (rbtree_t *rbtree, rbnode_t *data) 228314564Sdim{ 229341825Sdim /* XXX Not necessary, but keeps compiler quiet... */ 230341825Sdim int r = 0; 231341825Sdim 232341825Sdim /* We start at the root of the tree */ 233314564Sdim rbnode_t *node = rbtree->root; 234254721Semaste rbnode_t *parent = RBTREE_NULL; 235314564Sdim 236314564Sdim fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp)); 237341825Sdim /* Lets find the new parent... */ 238341825Sdim while (node != RBTREE_NULL) { 239341825Sdim /* Compare two keys, do we have a duplicate? */ 240314564Sdim if ((r = rbtree->cmp(data->key, node->key)) == 0) { 241254721Semaste return NULL; 242314564Sdim } 243314564Sdim parent = node; 244314564Sdim 245314564Sdim if (r < 0) { 246254721Semaste node = node->left; 247314564Sdim } else { 248314564Sdim node = node->right; 249314564Sdim } 250314564Sdim } 251288943Sdim 252314564Sdim /* Initialize the new node */ 253314564Sdim data->parent = parent; 254314564Sdim data->left = data->right = RBTREE_NULL; 255314564Sdim data->color = RED; 256254721Semaste rbtree->count++; 257314564Sdim 258288943Sdim /* Insert it into the tree... */ 259314564Sdim if (parent != RBTREE_NULL) { 260254721Semaste if (r < 0) { 261353358Sdim parent->left = data; 262254721Semaste } else { 263314564Sdim parent->right = data; 264314564Sdim } 265341825Sdim } else { 266341825Sdim rbtree->root = data; 267314564Sdim } 268353358Sdim 269314564Sdim /* Fix up the red-black properties... */ 270314564Sdim rbtree_insert_fixup(rbtree, data); 271353358Sdim 272314564Sdim return data; 273314564Sdim} 274314564Sdim 275314564Sdim/* 276314564Sdim * Searches the red black tree, returns the data if key is found or NULL otherwise. 277314564Sdim * 278314564Sdim */ 279314564Sdimrbnode_t * 280353358Sdimrbtree_search (rbtree_t *rbtree, const void *key) 281314564Sdim{ 282314564Sdim rbnode_t *node; 283314564Sdim 284314564Sdim if (rbtree_find_less_equal(rbtree, key, &node)) { 285314564Sdim return node; 286314564Sdim } else { 287353358Sdim return NULL; 288314564Sdim } 289321369Sdim} 290321369Sdim 291254721Semaste/** helpers for delete: swap node colours */ 292314564Sdimstatic void swap_int8(uint8_t* x, uint8_t* y) 293314564Sdim{ 294341825Sdim uint8_t t = *x; *x = *y; *y = t; 295341825Sdim} 296314564Sdim 297314564Sdim/** helpers for delete: swap node pointers */ 298314564Sdimstatic void swap_np(rbnode_t** x, rbnode_t** y) 299254721Semaste{ 300321369Sdim rbnode_t* t = *x; *x = *y; *y = t; 301321369Sdim} 302321369Sdim 303321369Sdim/** Update parent pointers of child trees of 'parent' */ 304321369Sdimstatic void change_parent_ptr(rbtree_t* rbtree, rbnode_t* parent, rbnode_t* old, rbnode_t* new) 305288943Sdim{ 306314564Sdim if(parent == RBTREE_NULL) 307314564Sdim { 308254721Semaste log_assert(rbtree->root == old); 309321369Sdim if(rbtree->root == old) rbtree->root = new; 310254721Semaste return; 311321369Sdim } 312254721Semaste log_assert(parent->left == old || parent->right == old 313341825Sdim || parent->left == new || parent->right == new); 314341825Sdim if(parent->left == old) parent->left = new; 315314564Sdim if(parent->right == old) parent->right = new; 316353358Sdim} 317314564Sdim/** Update parent pointer of a node 'child' */ 318314564Sdimstatic void change_child_ptr(rbnode_t* child, rbnode_t* old, rbnode_t* new) 319353358Sdim{ 320314564Sdim if(child == RBTREE_NULL) return; 321314564Sdim log_assert(child->parent == old || child->parent == new); 322314564Sdim if(child->parent == old) child->parent = new; 323353358Sdim} 324314564Sdim 325314564Sdimrbnode_t* 326314564Sdimrbtree_delete(rbtree_t *rbtree, const void *key) 327314564Sdim{ 328296417Sdim rbnode_t *to_delete; 329314564Sdim rbnode_t *child; 330314564Sdim if((to_delete = rbtree_search(rbtree, key)) == 0) return 0; 331254721Semaste rbtree->count--; 332341825Sdim 333341825Sdim /* make sure we have at most one non-leaf child */ 334321369Sdim if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL) 335254721Semaste { 336341825Sdim /* swap with smallest from right subtree (or largest from left) */ 337341825Sdim rbnode_t *smright = to_delete->right; 338353358Sdim while(smright->left != RBTREE_NULL) 339353358Sdim smright = smright->left; 340353358Sdim /* swap the smright and to_delete elements in the tree, 341321369Sdim * but the rbnode_t is first part of user data struct 342254721Semaste * so cannot just swap the keys and data pointers. Instead 343314564Sdim * readjust the pointers left,right,parent */ 344321369Sdim 345254721Semaste /* swap colors - colors are tied to the position in the tree */ 346341825Sdim swap_int8(&to_delete->color, &smright->color); 347341825Sdim 348314564Sdim /* swap child pointers in parents of smright/to_delete */ 349314564Sdim change_parent_ptr(rbtree, to_delete->parent, to_delete, smright); 350314564Sdim if(to_delete->right != smright) 351254721Semaste change_parent_ptr(rbtree, smright->parent, smright, to_delete); 352341825Sdim 353341825Sdim /* swap parent pointers in children of smright/to_delete */ 354341825Sdim change_child_ptr(smright->left, smright, to_delete); 355341825Sdim change_child_ptr(smright->left, smright, to_delete); 356314564Sdim change_child_ptr(smright->right, smright, to_delete); 357254721Semaste change_child_ptr(smright->right, smright, to_delete); 358341825Sdim change_child_ptr(to_delete->left, to_delete, smright); 359341825Sdim if(to_delete->right != smright) 360341825Sdim change_child_ptr(to_delete->right, to_delete, smright); 361341825Sdim if(to_delete->right == smright) 362341825Sdim { 363314564Sdim /* set up so after swap they work */ 364314564Sdim to_delete->right = to_delete; 365314564Sdim smright->parent = smright; 366314564Sdim } 367321369Sdim 368254721Semaste /* swap pointers in to_delete/smright nodes */ 369314564Sdim swap_np(&to_delete->parent, &smright->parent); 370314564Sdim swap_np(&to_delete->left, &smright->left); 371314564Sdim swap_np(&to_delete->right, &smright->right); 372314564Sdim 373321369Sdim /* now delete to_delete (which is at the location where the smright previously was) */ 374296417Sdim } 375314564Sdim log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL); 376314564Sdim 377341825Sdim if(to_delete->left != RBTREE_NULL) child = to_delete->left; 378341825Sdim else child = to_delete->right; 379341825Sdim 380341825Sdim /* unlink to_delete from the tree, replace to_delete with child */ 381341825Sdim change_parent_ptr(rbtree, to_delete->parent, to_delete, child); 382314564Sdim change_child_ptr(child, to_delete, to_delete->parent); 383353358Sdim 384314564Sdim if(to_delete->color == RED) 385314564Sdim { 386314564Sdim /* if node is red then the child (black) can be swapped in */ 387314564Sdim } 388314564Sdim else if(child->color == RED) 389314564Sdim { 390314564Sdim /* change child to BLACK, removing a RED node is no problem */ 391314564Sdim if(child!=RBTREE_NULL) child->color = BLACK; 392314564Sdim } 393321369Sdim else rbtree_delete_fixup(rbtree, child, to_delete->parent); 394254721Semaste 395314564Sdim /* unlink completely */ 396314564Sdim to_delete->parent = RBTREE_NULL; 397341825Sdim to_delete->left = RBTREE_NULL; 398341825Sdim to_delete->right = RBTREE_NULL; 399341825Sdim to_delete->color = BLACK; 400341825Sdim return to_delete; 401341825Sdim} 402314564Sdim 403353358Sdimstatic void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent) 404314564Sdim{ 405314564Sdim rbnode_t* sibling; 406353358Sdim int go_up = 1; 407314564Sdim 408314564Sdim /* determine sibling to the node that is one-black short */ 409314564Sdim if(child_parent->right == child) sibling = child_parent->left; 410314564Sdim else sibling = child_parent->right; 411314564Sdim 412321369Sdim while(go_up) 413254721Semaste { 414341825Sdim if(child_parent == RBTREE_NULL) 415341825Sdim { 416314564Sdim /* removed parent==black from root, every path, so ok */ 417314564Sdim return; 418258884Semaste } 419314564Sdim 420288943Sdim if(sibling->color == RED) 421341825Sdim { /* rotate to get a black sibling */ 422341825Sdim child_parent->color = RED; 423341825Sdim sibling->color = BLACK; 424314564Sdim if(child_parent->right == child) 425288943Sdim rbtree_rotate_right(rbtree, child_parent); 426341825Sdim else rbtree_rotate_left(rbtree, child_parent); 427341825Sdim /* new sibling after rotation */ 428314564Sdim if(child_parent->right == child) sibling = child_parent->left; 429314564Sdim else sibling = child_parent->right; 430314564Sdim } 431314564Sdim 432288943Sdim if(child_parent->color == BLACK 433314564Sdim && sibling->color == BLACK 434258884Semaste && sibling->left->color == BLACK 435314564Sdim && sibling->right->color == BLACK) 436314564Sdim { /* fixup local with recolor of sibling */ 437314564Sdim if(sibling != RBTREE_NULL) 438258884Semaste sibling->color = RED; 439314564Sdim 440258054Semaste child = child_parent; 441314564Sdim child_parent = child_parent->parent; 442314564Sdim /* prepare to go up, new sibling */ 443314564Sdim if(child_parent->right == child) sibling = child_parent->left; 444314564Sdim else sibling = child_parent->right; 445258884Semaste } 446314564Sdim else go_up = 0; 447258884Semaste } 448314564Sdim 449314564Sdim if(child_parent->color == RED 450314564Sdim && sibling->color == BLACK 451314564Sdim && sibling->left->color == BLACK 452314564Sdim && sibling->right->color == BLACK) 453258884Semaste { 454341825Sdim /* move red to sibling to rebalance */ 455341825Sdim if(sibling != RBTREE_NULL) 456341825Sdim sibling->color = RED; 457327952Sdim child_parent->color = BLACK; 458327952Sdim return; 459314564Sdim } 460314564Sdim log_assert(sibling != RBTREE_NULL); 461258054Semaste 462314564Sdim /* get a new sibling, by rotating at sibling. See which child 463314564Sdim of sibling is red */ 464288943Sdim if(child_parent->right == child 465353358Sdim && sibling->color == BLACK 466288943Sdim && sibling->right->color == RED 467353358Sdim && sibling->left->color == BLACK) 468258054Semaste { 469353358Sdim sibling->color = RED; 470288943Sdim sibling->right->color = BLACK; 471353358Sdim rbtree_rotate_left(rbtree, sibling); 472288943Sdim /* new sibling after rotation */ 473341825Sdim if(child_parent->right == child) sibling = child_parent->left; 474341825Sdim else sibling = child_parent->right; 475314564Sdim } 476314564Sdim else if(child_parent->left == child 477258054Semaste && sibling->color == BLACK 478314564Sdim && sibling->left->color == RED 479314564Sdim && sibling->right->color == BLACK) 480314564Sdim { 481314564Sdim sibling->color = RED; 482314564Sdim sibling->left->color = BLACK; 483258054Semaste rbtree_rotate_right(rbtree, sibling); 484314564Sdim /* new sibling after rotation */ 485262528Semaste if(child_parent->right == child) sibling = child_parent->left; 486314564Sdim else sibling = child_parent->right; 487296417Sdim } 488314564Sdim 489341825Sdim /* now we have a black sibling with a red child. rotate and exchange colors. */ 490341825Sdim sibling->color = child_parent->color; 491296417Sdim child_parent->color = BLACK; 492314564Sdim if(child_parent->right == child) 493314564Sdim { 494314564Sdim log_assert(sibling->left->color == RED); 495314564Sdim sibling->left->color = BLACK; 496314564Sdim rbtree_rotate_right(rbtree, child_parent); 497296417Sdim } 498321369Sdim else 499296417Sdim { 500321369Sdim log_assert(sibling->right->color == RED); 501321369Sdim sibling->right->color = BLACK; 502296417Sdim rbtree_rotate_left(rbtree, child_parent); 503321369Sdim } 504321369Sdim} 505296417Sdim 506360784Sdimint 507360784Sdimrbtree_find_less_equal(rbtree_t *rbtree, const void *key, rbnode_t **result) 508360784Sdim{ 509314564Sdim int r; 510314564Sdim rbnode_t *node; 511258054Semaste 512321369Sdim log_assert(result); 513262528Semaste 514314564Sdim /* We start at root... */ 515314564Sdim node = rbtree->root; 516314564Sdim 517254721Semaste *result = NULL; 518314564Sdim fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp)); 519321369Sdim 520314564Sdim /* While there are children... */ 521314564Sdim while (node != RBTREE_NULL) { 522314564Sdim r = rbtree->cmp(key, node->key); 523314564Sdim if (r == 0) { 524314564Sdim /* Exact match */ 525254721Semaste *result = node; 526314564Sdim return 1; 527321369Sdim } 528314564Sdim if (r < 0) { 529353358Sdim node = node->left; 530314564Sdim } else { 531314564Sdim /* Temporary match */ 532314564Sdim *result = node; 533254721Semaste node = node->right; 534321369Sdim } 535309124Sdim } 536321369Sdim return 0; 537321369Sdim} 538254721Semaste 539321369Sdim/* 540314564Sdim * Finds the first element in the red black tree 541314564Sdim * 542254721Semaste */ 543314564Sdimrbnode_t * 544314564Sdimrbtree_first (rbtree_t *rbtree) 545341825Sdim{ 546341825Sdim rbnode_t *node; 547341825Sdim 548341825Sdim for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left); 549341825Sdim return node; 550314564Sdim} 551353358Sdim 552314564Sdimrbnode_t * 553314564Sdimrbtree_last (rbtree_t *rbtree) 554353358Sdim{ 555314564Sdim rbnode_t *node; 556314564Sdim 557314564Sdim for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right); 558314564Sdim return node; 559314564Sdim} 560314564Sdim 561314564Sdim/* 562314564Sdim * Returns the next node... 563353358Sdim * 564314564Sdim */ 565321369Sdimrbnode_t * 566254721Semasterbtree_next (rbnode_t *node) 567341825Sdim{ 568254721Semaste rbnode_t *parent; 569314564Sdim 570314564Sdim if (node->right != RBTREE_NULL) { 571321369Sdim /* One right, then keep on going left... */ 572314564Sdim for (node = node->right; node->left != RBTREE_NULL; node = node->left); 573322326Semaste } else { 574322326Semaste parent = node->parent; 575322326Semaste while (parent != RBTREE_NULL && node == parent->right) { 576322326Semaste node = parent; 577322326Semaste parent = parent->parent; 578314564Sdim } 579314564Sdim node = parent; 580314564Sdim } 581314564Sdim return node; 582314564Sdim} 583314564Sdim 584314564Sdimrbnode_t * 585314564Sdimrbtree_previous(rbnode_t *node) 586314564Sdim{ 587314564Sdim rbnode_t *parent; 588314564Sdim 589314564Sdim if (node->left != RBTREE_NULL) { 590314564Sdim /* One left, then keep on going right... */ 591314564Sdim for (node = node->left; node->right != RBTREE_NULL; node = node->right); 592314564Sdim } else { 593314564Sdim parent = node->parent; 594314564Sdim while (parent != RBTREE_NULL && node == parent->left) { 595314564Sdim node = parent; 596314564Sdim parent = parent->parent; 597314564Sdim } 598314564Sdim node = parent; 599314564Sdim } 600314564Sdim return node; 601314564Sdim} 602314564Sdim 603314564Sdim/** recursive descent traverse */ 604314564Sdimstatic void 605314564Sdimtraverse_post(void (*func)(rbnode_t*, void*), void* arg, rbnode_t* node) 606314564Sdim{ 607314564Sdim if(!node || node == RBTREE_NULL) 608314564Sdim return; 609314564Sdim /* recurse */ 610314564Sdim traverse_post(func, arg, node->left); 611314564Sdim traverse_post(func, arg, node->right); 612321369Sdim /* call user func */ 613314564Sdim (*func)(node, arg); 614314564Sdim} 615314564Sdim 616314564Sdimvoid 617314564Sdimtraverse_postorder(rbtree_t* tree, void (*func)(rbnode_t*, void*), void* arg) 618314564Sdim{ 619314564Sdim traverse_post(func, arg, tree->root); 620314564Sdim} 621341825Sdim