X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_rbtree_oset.c;h=9393d12026ee5a5dc3cc35d3680ca6fe720bf975;hb=4779b635ef35c7b0bc4044fcb5bc746d06f158c4;hp=78636d615616e62836dc3b82cd86c9a8a761d552;hpb=5c90f29795d4e8d9a66268d5dc61d02b82cf7db8;p=gnulib.git diff --git a/lib/gl_rbtree_oset.c b/lib/gl_rbtree_oset.c index 78636d615..9393d1202 100644 --- a/lib/gl_rbtree_oset.c +++ b/lib/gl_rbtree_oset.c @@ -1,11 +1,11 @@ /* Ordered set data type implemented by a binary tree. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2007, 2009-2013 Free Software Foundation, Inc. Written by Bruno Haible , 2006. - This program is free software; you can redistribute it and/or modify + This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -13,8 +13,7 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software Foundation, - Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + along with this program. If not, see . */ #include @@ -23,8 +22,6 @@ #include -#include "xalloc.h" - /* A red-black tree is a binary tree where every node is colored black or red such that 1. The root is black. @@ -35,7 +32,7 @@ Let's call this the "black-height" bh of the tree. It follows that every such path contains exactly bh black and between 0 and bh red nodes. (The extreme cases are a path containing only black nodes, and a path colored - alternatingly black-red-black-red-...-black-red.) The height of the tree + alternately black-red-black-red-...-black-red.) The height of the tree therefore is >= bh, <= 2*bh. */ @@ -77,15 +74,15 @@ struct gl_oset_impl /* Rotate left a subtree. - B D - / \ / \ - A D --> B E - / \ / \ - C E A C + B D + / \ / \ + A D --> B E + / \ / \ + C E A C Change the tree structure, update the branch sizes. The caller must update the colors and register D as child of its parent. */ -static inline gl_oset_node_t +static gl_oset_node_t rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node) { gl_oset_node_t c_node = d_node->left; @@ -103,15 +100,15 @@ rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node) /* Rotate right a subtree. - D B - / \ / \ - B E --> A D - / \ / \ - A C C E + D B + / \ / \ + B E --> A D + / \ / \ + A C C E Change the tree structure, update the branch sizes. The caller must update the colors and register B as child of its parent. */ -static inline gl_oset_node_t +static gl_oset_node_t rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node) { gl_oset_node_t c_node = b_node->right; @@ -136,118 +133,118 @@ rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent) for (;;) { /* At this point, parent = node->parent != NULL. - Think of node->color being RED (although node->color is not yet - assigned.) */ + Think of node->color being RED (although node->color is not yet + assigned.) */ gl_oset_node_t grandparent; gl_oset_node_t uncle; if (parent->color == BLACK) - { - /* A RED color for node is acceptable. */ - node->color = RED; - return; - } + { + /* A RED color for node is acceptable. */ + node->color = RED; + return; + } grandparent = parent->parent; /* Since parent is RED, we know that - grandparent is != NULL and colored BLACK. */ + grandparent is != NULL and colored BLACK. */ if (grandparent->left == parent) - uncle = grandparent->right; + uncle = grandparent->right; else if (grandparent->right == parent) - uncle = grandparent->left; + uncle = grandparent->left; else - abort (); + abort (); if (uncle != NULL && uncle->color == RED) - { - /* Change grandparent from BLACK to RED, and - change parent and uncle from RED to BLACK. - This makes it acceptable for node to be RED. */ - node->color = RED; - parent->color = uncle->color = BLACK; - node = grandparent; - } + { + /* Change grandparent from BLACK to RED, and + change parent and uncle from RED to BLACK. + This makes it acceptable for node to be RED. */ + node->color = RED; + parent->color = uncle->color = BLACK; + node = grandparent; + } else - { - /* grandparent and uncle are BLACK. parent is RED. node wants - to be RED too. - In this case, recoloring is not sufficient. Need to perform - one or two rotations. */ - gl_oset_node_t *grandparentp; - - if (grandparent->parent == NULL) - grandparentp = &set->root; - else if (grandparent->parent->left == grandparent) - grandparentp = &grandparent->parent->left; - else if (grandparent->parent->right == grandparent) - grandparentp = &grandparent->parent->right; - else - abort (); - - if (grandparent->left == parent) - { - if (parent->right == node) - { - /* Rotation between node and parent. */ - grandparent->left = rotate_left (parent, node); - node = parent; - parent = grandparent->left; - } - /* grandparent and uncle are BLACK. parent and node want to be - RED. parent = grandparent->left. node = parent->left. - - grandparent parent - bh+1 bh+1 - / \ / \ - parent uncle --> node grandparent - bh bh bh bh - / \ / \ - node C C uncle - bh bh bh bh - */ - *grandparentp = rotate_right (parent, grandparent); - parent->color = BLACK; - node->color = grandparent->color = RED; - } - else /* grandparent->right == parent */ - { - if (parent->left == node) - { - /* Rotation between node and parent. */ - grandparent->right = rotate_right (node, parent); - node = parent; - parent = grandparent->right; - } - /* grandparent and uncle are BLACK. parent and node want to be - RED. parent = grandparent->right. node = parent->right. - - grandparent parent - bh+1 bh+1 - / \ / \ - uncle parent --> grandparent node - bh bh bh bh - / \ / \ - C node uncle C - bh bh bh bh - */ - *grandparentp = rotate_left (grandparent, parent); - parent->color = BLACK; - node->color = grandparent->color = RED; - } - return; - } + { + /* grandparent and uncle are BLACK. parent is RED. node wants + to be RED too. + In this case, recoloring is not sufficient. Need to perform + one or two rotations. */ + gl_oset_node_t *grandparentp; + + if (grandparent->parent == NULL) + grandparentp = &set->root; + else if (grandparent->parent->left == grandparent) + grandparentp = &grandparent->parent->left; + else if (grandparent->parent->right == grandparent) + grandparentp = &grandparent->parent->right; + else + abort (); + + if (grandparent->left == parent) + { + if (parent->right == node) + { + /* Rotation between node and parent. */ + grandparent->left = rotate_left (parent, node); + node = parent; + parent = grandparent->left; + } + /* grandparent and uncle are BLACK. parent and node want to be + RED. parent = grandparent->left. node = parent->left. + + grandparent parent + bh+1 bh+1 + / \ / \ + parent uncle --> node grandparent + bh bh bh bh + / \ / \ + node C C uncle + bh bh bh bh + */ + *grandparentp = rotate_right (parent, grandparent); + parent->color = BLACK; + node->color = grandparent->color = RED; + } + else /* grandparent->right == parent */ + { + if (parent->left == node) + { + /* Rotation between node and parent. */ + grandparent->right = rotate_right (node, parent); + node = parent; + parent = grandparent->right; + } + /* grandparent and uncle are BLACK. parent and node want to be + RED. parent = grandparent->right. node = parent->right. + + grandparent parent + bh+1 bh+1 + / \ / \ + uncle parent --> grandparent node + bh bh bh bh + / \ / \ + C node uncle C + bh bh bh bh + */ + *grandparentp = rotate_left (grandparent, parent); + parent->color = BLACK; + node->color = grandparent->color = RED; + } + return; + } /* Start again with a new (node, parent) pair. */ parent = node->parent; if (parent == NULL) - { - /* Change node's color from RED to BLACK. This increases the - tree's black-height. */ - node->color = BLACK; - return; - } + { + /* Change node's color from RED to BLACK. This increases the + tree's black-height. */ + node->color = BLACK; + return; + } } } @@ -261,289 +258,292 @@ rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t pare for (;;) { /* At this point, we reduced the black-height of the CHILD subtree by 1. - To make up, either look for a possibility to turn a RED to a BLACK - node, or try to reduce the black-height tree of CHILD's sibling - subtree as well. */ + To make up, either look for a possibility to turn a RED to a BLACK + node, or try to reduce the black-height tree of CHILD's sibling + subtree as well. */ gl_oset_node_t *parentp; if (parent->parent == NULL) - parentp = &set->root; + parentp = &set->root; else if (parent->parent->left == parent) - parentp = &parent->parent->left; + parentp = &parent->parent->left; else if (parent->parent->right == parent) - parentp = &parent->parent->right; + parentp = &parent->parent->right; else - abort (); + abort (); if (parent->left == child) - { - gl_oset_node_t sibling = parent->right; - /* sibling's black-height is >= 1. In particular, - sibling != NULL. - - parent - / \ - child sibling - bh bh+1 - */ - - if (sibling->color == RED) - { - /* sibling is RED, hence parent is BLACK and sibling's children - are non-NULL and BLACK. - - parent sibling - bh+2 bh+2 - / \ / \ - child sibling --> parent SR - bh bh+1 bh+1 bh+1 - / \ / \ - SL SR child SL - bh+1 bh+1 bh bh+1 - */ - *parentp = rotate_left (parent, sibling); - parent->color = RED; - sibling->color = BLACK; - - /* Concentrate on the subtree of parent. The new sibling is - one of the old sibling's children, and known to be BLACK. */ - parentp = &sibling->left; - sibling = parent->right; - } - /* Now we know that sibling is BLACK. - - parent - / \ - child sibling - bh bh+1 - */ - if (sibling->right != NULL && sibling->right->color == RED) - { - /* - parent sibling - bh+1|bh+2 bh+1|bh+2 - / \ / \ - child sibling --> parent SR - bh bh+1 bh+1 bh+1 - / \ / \ - SL SR child SL - bh bh bh bh - */ - *parentp = rotate_left (parent, sibling); - sibling->color = parent->color; - parent->color = BLACK; - sibling->right->color = BLACK; - return; - } - else if (sibling->left != NULL && sibling->left->color == RED) - { - /* - parent parent - bh+1|bh+2 bh+1|bh+2 - / \ / \ - child sibling --> child SL - bh bh+1 bh bh+1 - / \ / \ - SL SR SLL sibling - bh bh bh bh - / \ / \ - SLL SLR SLR SR - bh bh bh bh - - where SLL, SLR, SR are all black. - */ - parent->right = rotate_right (sibling->left, sibling); - /* Change sibling from BLACK to RED and SL from RED to BLACK. */ - sibling->color = RED; - sibling = parent->right; - sibling->color = BLACK; - - /* Now do as in the previous case. */ - *parentp = rotate_left (parent, sibling); - sibling->color = parent->color; - parent->color = BLACK; - sibling->right->color = BLACK; - return; - } - else - { - if (parent->color == BLACK) - { - /* Change sibling from BLACK to RED. Then the entire - subtree at parent has decreased its black-height. - parent parent - bh+2 bh+1 - / \ / \ - child sibling --> child sibling - bh bh+1 bh bh - */ - sibling->color = RED; - - child = parent; - } - else - { - /* Change parent from RED to BLACK, but compensate by - changing sibling from BLACK to RED. - parent parent - bh+1 bh+1 - / \ / \ - child sibling --> child sibling - bh bh+1 bh bh - */ - parent->color = BLACK; - sibling->color = RED; - return; - } - } - } + { + gl_oset_node_t sibling = parent->right; + /* sibling's black-height is >= 1. In particular, + sibling != NULL. + + parent + / \ + child sibling + bh bh+1 + */ + + if (sibling->color == RED) + { + /* sibling is RED, hence parent is BLACK and sibling's children + are non-NULL and BLACK. + + parent sibling + bh+2 bh+2 + / \ / \ + child sibling --> parent SR + bh bh+1 bh+1 bh+1 + / \ / \ + SL SR child SL + bh+1 bh+1 bh bh+1 + */ + *parentp = rotate_left (parent, sibling); + parent->color = RED; + sibling->color = BLACK; + + /* Concentrate on the subtree of parent. The new sibling is + one of the old sibling's children, and known to be BLACK. */ + parentp = &sibling->left; + sibling = parent->right; + } + /* Now we know that sibling is BLACK. + + parent + / \ + child sibling + bh bh+1 + */ + if (sibling->right != NULL && sibling->right->color == RED) + { + /* + parent sibling + bh+1|bh+2 bh+1|bh+2 + / \ / \ + child sibling --> parent SR + bh bh+1 bh+1 bh+1 + / \ / \ + SL SR child SL + bh bh bh bh + */ + *parentp = rotate_left (parent, sibling); + sibling->color = parent->color; + parent->color = BLACK; + sibling->right->color = BLACK; + return; + } + else if (sibling->left != NULL && sibling->left->color == RED) + { + /* + parent parent + bh+1|bh+2 bh+1|bh+2 + / \ / \ + child sibling --> child SL + bh bh+1 bh bh+1 + / \ / \ + SL SR SLL sibling + bh bh bh bh + / \ / \ + SLL SLR SLR SR + bh bh bh bh + + where SLL, SLR, SR are all black. + */ + parent->right = rotate_right (sibling->left, sibling); + /* Change sibling from BLACK to RED and SL from RED to BLACK. */ + sibling->color = RED; + sibling = parent->right; + sibling->color = BLACK; + + /* Now do as in the previous case. */ + *parentp = rotate_left (parent, sibling); + sibling->color = parent->color; + parent->color = BLACK; + sibling->right->color = BLACK; + return; + } + else + { + if (parent->color == BLACK) + { + /* Change sibling from BLACK to RED. Then the entire + subtree at parent has decreased its black-height. + parent parent + bh+2 bh+1 + / \ / \ + child sibling --> child sibling + bh bh+1 bh bh + */ + sibling->color = RED; + + child = parent; + } + else + { + /* Change parent from RED to BLACK, but compensate by + changing sibling from BLACK to RED. + parent parent + bh+1 bh+1 + / \ / \ + child sibling --> child sibling + bh bh+1 bh bh + */ + parent->color = BLACK; + sibling->color = RED; + return; + } + } + } else if (parent->right == child) - { - gl_oset_node_t sibling = parent->left; - /* sibling's black-height is >= 1. In particular, - sibling != NULL. - - parent - / \ - sibling child - bh+1 bh - */ - - if (sibling->color == RED) - { - /* sibling is RED, hence parent is BLACK and sibling's children - are non-NULL and BLACK. - - parent sibling - bh+2 bh+2 - / \ / \ - sibling child --> SR parent - bh+1 ch bh+1 bh+1 - / \ / \ - SL SR SL child - bh+1 bh+1 bh+1 bh - */ - *parentp = rotate_right (sibling, parent); - parent->color = RED; - sibling->color = BLACK; - - /* Concentrate on the subtree of parent. The new sibling is - one of the old sibling's children, and known to be BLACK. */ - parentp = &sibling->right; - sibling = parent->left; - } - /* Now we know that sibling is BLACK. - - parent - / \ - sibling child - bh+1 bh - */ - if (sibling->left != NULL && sibling->left->color == RED) - { - /* - parent sibling - bh+1|bh+2 bh+1|bh+2 - / \ / \ - sibling child --> SL parent - bh+1 bh bh+1 bh+1 - / \ / \ - SL SR SR child - bh bh bh bh - */ - *parentp = rotate_right (sibling, parent); - sibling->color = parent->color; - parent->color = BLACK; - sibling->left->color = BLACK; - return; - } - else if (sibling->right != NULL && sibling->right->color == RED) - { - /* - parent parent - bh+1|bh+2 bh+1|bh+2 - / \ / \ - sibling child --> SR child - bh+1 bh bh+1 bh - / \ / \ - SL SR sibling SRR - bh bh bh bh - / \ / \ - SRL SRR SL SRL - bh bh bh bh - - where SL, SRL, SRR are all black. - */ - parent->left = rotate_left (sibling, sibling->right); - /* Change sibling from BLACK to RED and SL from RED to BLACK. */ - sibling->color = RED; - sibling = parent->left; - sibling->color = BLACK; - - /* Now do as in the previous case. */ - *parentp = rotate_right (sibling, parent); - sibling->color = parent->color; - parent->color = BLACK; - sibling->left->color = BLACK; - return; - } - else - { - if (parent->color == BLACK) - { - /* Change sibling from BLACK to RED. Then the entire - subtree at parent has decreased its black-height. - parent parent - bh+2 bh+1 - / \ / \ - sibling child --> sibling child - bh+1 bh bh bh - */ - sibling->color = RED; - - child = parent; - } - else - { - /* Change parent from RED to BLACK, but compensate by - changing sibling from BLACK to RED. - parent parent - bh+1 bh+1 - / \ / \ - sibling child --> sibling child - bh+1 bh bh bh - */ - parent->color = BLACK; - sibling->color = RED; - return; - } - } - } + { + gl_oset_node_t sibling = parent->left; + /* sibling's black-height is >= 1. In particular, + sibling != NULL. + + parent + / \ + sibling child + bh+1 bh + */ + + if (sibling->color == RED) + { + /* sibling is RED, hence parent is BLACK and sibling's children + are non-NULL and BLACK. + + parent sibling + bh+2 bh+2 + / \ / \ + sibling child --> SR parent + bh+1 ch bh+1 bh+1 + / \ / \ + SL SR SL child + bh+1 bh+1 bh+1 bh + */ + *parentp = rotate_right (sibling, parent); + parent->color = RED; + sibling->color = BLACK; + + /* Concentrate on the subtree of parent. The new sibling is + one of the old sibling's children, and known to be BLACK. */ + parentp = &sibling->right; + sibling = parent->left; + } + /* Now we know that sibling is BLACK. + + parent + / \ + sibling child + bh+1 bh + */ + if (sibling->left != NULL && sibling->left->color == RED) + { + /* + parent sibling + bh+1|bh+2 bh+1|bh+2 + / \ / \ + sibling child --> SL parent + bh+1 bh bh+1 bh+1 + / \ / \ + SL SR SR child + bh bh bh bh + */ + *parentp = rotate_right (sibling, parent); + sibling->color = parent->color; + parent->color = BLACK; + sibling->left->color = BLACK; + return; + } + else if (sibling->right != NULL && sibling->right->color == RED) + { + /* + parent parent + bh+1|bh+2 bh+1|bh+2 + / \ / \ + sibling child --> SR child + bh+1 bh bh+1 bh + / \ / \ + SL SR sibling SRR + bh bh bh bh + / \ / \ + SRL SRR SL SRL + bh bh bh bh + + where SL, SRL, SRR are all black. + */ + parent->left = rotate_left (sibling, sibling->right); + /* Change sibling from BLACK to RED and SL from RED to BLACK. */ + sibling->color = RED; + sibling = parent->left; + sibling->color = BLACK; + + /* Now do as in the previous case. */ + *parentp = rotate_right (sibling, parent); + sibling->color = parent->color; + parent->color = BLACK; + sibling->left->color = BLACK; + return; + } + else + { + if (parent->color == BLACK) + { + /* Change sibling from BLACK to RED. Then the entire + subtree at parent has decreased its black-height. + parent parent + bh+2 bh+1 + / \ / \ + sibling child --> sibling child + bh+1 bh bh bh + */ + sibling->color = RED; + + child = parent; + } + else + { + /* Change parent from RED to BLACK, but compensate by + changing sibling from BLACK to RED. + parent parent + bh+1 bh+1 + / \ / \ + sibling child --> sibling child + bh+1 bh bh bh + */ + parent->color = BLACK; + sibling->color = RED; + return; + } + } + } else - abort (); + abort (); /* Start again with a new (child, parent) pair. */ parent = child->parent; #if 0 /* Already handled. */ if (child != NULL && child->color == RED) - { - child->color = BLACK; - return; - } + { + child->color = BLACK; + return; + } #endif if (parent == NULL) - return; + return; } } static gl_oset_node_t -gl_tree_add_first (gl_oset_t set, const void *elt) +gl_tree_nx_add_first (gl_oset_t set, const void *elt) { /* Create new node. */ gl_oset_node_t new_node = - (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl)); + (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); + + if (new_node == NULL) + return NULL; new_node->left = NULL; new_node->right = NULL; @@ -561,7 +561,7 @@ gl_tree_add_first (gl_oset_t set, const void *elt) gl_oset_node_t node; for (node = set->root; node->left != NULL; ) - node = node->left; + node = node->left; node->left = new_node; new_node->parent = node; @@ -575,11 +575,14 @@ gl_tree_add_first (gl_oset_t set, const void *elt) } static gl_oset_node_t -gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt) +gl_tree_nx_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt) { /* Create new node. */ gl_oset_node_t new_node = - (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl)); + (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); + + if (new_node == NULL) + return NULL; new_node->left = NULL; new_node->right = NULL; @@ -591,7 +594,7 @@ gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt) else { for (node = node->left; node->right != NULL; ) - node = node->right; + node = node->right; node->right = new_node; } new_node->parent = node; @@ -604,11 +607,14 @@ gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt) } static gl_oset_node_t -gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt) +gl_tree_nx_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt) { /* Create new node. */ gl_oset_node_t new_node = - (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl)); + (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); + + if (new_node == NULL) + return NULL; new_node->left = NULL; new_node->right = NULL; @@ -620,7 +626,7 @@ gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt) else { for (node = node->right; node->left != NULL; ) - node = node->left; + node = node->left; node->left = new_node; } new_node->parent = node; @@ -643,45 +649,45 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) gl_oset_node_t child = node->right; if (child != NULL) - { - child->parent = parent; - /* Since node->left == NULL, child must be RED and of height 1, - hence node must have been BLACK. Recolor the child. */ - child->color = BLACK; - } + { + child->parent = parent; + /* Since node->left == NULL, child must be RED and of height 1, + hence node must have been BLACK. Recolor the child. */ + child->color = BLACK; + } if (parent == NULL) - set->root = child; + set->root = child; else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - - if (child == NULL && node->color == BLACK) - rebalance_after_remove (set, child, parent); - } + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + if (child == NULL && node->color == BLACK) + rebalance_after_remove (set, child, parent); + } } else if (node->right == NULL) { /* It is not absolutely necessary to treat this case. But the more - general case below is more complicated, hence slower. */ + general case below is more complicated, hence slower. */ /* Replace node with node->left. */ gl_oset_node_t child = node->left; child->parent = parent; /* Since node->right == NULL, child must be RED and of height 1, - hence node must have been BLACK. Recolor the child. */ + hence node must have been BLACK. Recolor the child. */ child->color = BLACK; if (parent == NULL) - set->root = child; + set->root = child; else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - } + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + } } else { @@ -692,7 +698,7 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) color_t removed_color; for (subst = node->left; subst->right != NULL; ) - subst = subst->right; + subst = subst->right; subst_parent = subst->parent; @@ -701,57 +707,59 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) removed_color = subst->color; /* The case subst_parent == node is special: If we do nothing special, - we get confusion about node->left, subst->left and child->parent. - subst_parent == node - <==> The 'for' loop above terminated immediately. - <==> subst == subst_parent->left - [otherwise subst == subst_parent->right] - In this case, we would need to first set - child->parent = node; node->left = child; - and later - when we copy subst into node's position - again - child->parent = subst; subst->left = child; - Altogether a no-op. */ + we get confusion about node->left, subst->left and child->parent. + subst_parent == node + <==> The 'for' loop above terminated immediately. + <==> subst == subst_parent->left + [otherwise subst == subst_parent->right] + In this case, we would need to first set + child->parent = node; node->left = child; + and later - when we copy subst into node's position - again + child->parent = subst; subst->left = child; + Altogether a no-op. */ if (subst_parent != node) - { - if (child != NULL) - child->parent = subst_parent; - subst_parent->right = child; - } + { + if (child != NULL) + child->parent = subst_parent; + subst_parent->right = child; + } /* Copy subst into node's position. - (This is safer than to copy subst's value into node, keep node in - place, and free subst.) */ + (This is safer than to copy subst's value into node, keep node in + place, and free subst.) */ if (subst_parent != node) - { - subst->left = node->left; - subst->left->parent = subst; - } + { + subst->left = node->left; + subst->left->parent = subst; + } subst->right = node->right; subst->right->parent = subst; subst->color = node->color; subst->parent = parent; if (parent == NULL) - set->root = subst; + set->root = subst; else if (parent->left == node) - parent->left = subst; + parent->left = subst; else /* parent->right == node */ - parent->right = subst; + parent->right = subst; if (removed_color == BLACK) - { - if (child != NULL && child->color == RED) - /* Recolor the child. */ - child->color = BLACK; - else - /* Rebalancing starts at child's parent, that is subst_parent - - except when subst_parent == node. In this case, we need to use - its replacement, subst. */ - rebalance_after_remove (set, child, - subst_parent != node ? subst_parent : subst); - } + { + if (child != NULL && child->color == RED) + /* Recolor the child. */ + child->color = BLACK; + else + /* Rebalancing starts at child's parent, that is subst_parent - + except when subst_parent == node. In this case, we need to use + its replacement, subst. */ + rebalance_after_remove (set, child, + subst_parent != node ? subst_parent : subst); + } } set->count--; + if (set->base.dispose_fn != NULL) + set->base.dispose_fn (node->value); free (node); return true; } @@ -793,11 +801,11 @@ gl_rbtree_oset_check_invariants (gl_oset_t set) const struct gl_oset_implementation gl_rbtree_oset_implementation = { - gl_tree_create_empty, + gl_tree_nx_create_empty, gl_tree_size, gl_tree_search, gl_tree_search_atleast, - gl_tree_add, + gl_tree_nx_add, gl_tree_remove, gl_tree_oset_free, gl_tree_iterator,