Mercurial > gnulib
changeset 40007:31ddfa01e256
rbtree-omap: New module.
* lib/gl_rbtree_omap.h: New file.
* lib/gl_rbtree_omap.c: New file.
* lib/gl_rbtree_ordered.h: Code moved to here from lib/gl_rbtree_oset.c.
Parameterize.
* lib/gl_rbtree_oset.c: Include gl_rbtree_ordered.h.
* modules/rbtree-omap: New file.
* modules/rbtree-oset (Files): Add lib/gl_rbtree_ordered.h.
(Makefile.am): Add gl_rbtree_ordered.h to lib_SOURCES.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Tue, 11 Dec 2018 20:56:27 +0100 |
| parents | 0caeb347e88e |
| children | eb287ca6dd6c |
| files | ChangeLog lib/gl_rbtree_omap.c lib/gl_rbtree_omap.h lib/gl_rbtree_ordered.h lib/gl_rbtree_oset.c modules/rbtree-omap modules/rbtree-oset |
| diffstat | 7 files changed, 939 insertions(+), 759 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog Tue Dec 11 20:56:25 2018 +0100 +++ b/ChangeLog Tue Dec 11 20:56:27 2018 +0100 @@ -1,5 +1,15 @@ 2018-12-11 Bruno Haible <bruno@clisp.org> + rbtree-omap: New module. + * lib/gl_rbtree_omap.h: New file. + * lib/gl_rbtree_omap.c: New file. + * lib/gl_rbtree_ordered.h: Code moved to here from lib/gl_rbtree_oset.c. + Parameterize. + * lib/gl_rbtree_oset.c: Include gl_rbtree_ordered.h. + * modules/rbtree-omap: New file. + * modules/rbtree-oset (Files): Add lib/gl_rbtree_ordered.h. + (Makefile.am): Add gl_rbtree_ordered.h to lib_SOURCES. + avltree-omap: New module. * lib/gl_avltree_omap.h: New file. * lib/gl_avltree_omap.c: New file.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_rbtree_omap.c Tue Dec 11 20:56:27 2018 +0100 @@ -0,0 +1,75 @@ +/* Ordered map data type implemented by a binary tree. + Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + 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 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 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_rbtree_omap.h" + +#include <stdlib.h> + +/* -------------------------- gl_omap_t Data Type -------------------------- */ + +/* Parameterization of gl_rbtree_ordered.h. */ +#define CONTAINER_T gl_omap_t +#define CONTAINER_IMPL gl_omap_impl +#define CONTAINER_IMPL_BASE gl_omap_impl_base +#define NODE_IMPL gl_omap_node_impl +#define NODE_T gl_omap_node_t +#define NODE_PAYLOAD_FIELDS \ + const void *key; \ + const void *value; +#define NODE_PAYLOAD_PARAMS \ + const void *key, const void *value +#define NODE_PAYLOAD_ASSIGN(node) \ + node->key = key; \ + node->value = value; +#define NODE_PAYLOAD_DISPOSE \ + if (container->base.vdispose_fn != NULL) \ + container->base.vdispose_fn (node->value); \ + if (container->base.kdispose_fn != NULL) \ + container->base.kdispose_fn (node->key); + +#include "gl_rbtree_ordered.h" + +/* Generic binary tree code. */ +#include "gl_anytree_omap.h" + +/* For debugging. */ +void +gl_rbtree_omap_check_invariants (gl_omap_t map) +{ + size_t counter = 0; + if (map->root != NULL) + check_invariants (map->root, NULL, &counter); + if (!(map->count == counter)) + abort (); +} + +const struct gl_omap_implementation gl_rbtree_omap_implementation = + { + gl_tree_nx_create_empty, + gl_tree_size, + gl_tree_search, + gl_tree_search_atleast, + gl_tree_nx_getput, + gl_tree_getremove, + gl_tree_omap_free, + gl_tree_iterator, + gl_tree_iterator_next, + gl_tree_iterator_free + };
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_rbtree_omap.h Tue Dec 11 20:56:27 2018 +0100 @@ -0,0 +1,34 @@ +/* Ordered map data type implemented by a binary tree. + Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + 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 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 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_RBTREE_OMAP_H +#define _GL_RBTREE_OMAP_H + +#include "gl_omap.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_omap_implementation gl_rbtree_omap_implementation; +#define GL_RBTREE_OMAP &gl_rbtree_omap_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_RBTREE_OMAP_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_rbtree_ordered.h Tue Dec 11 20:56:27 2018 +0100 @@ -0,0 +1,778 @@ +/* Ordered {set,map} data type implemented by a binary tree. + Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + 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 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 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + 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, see <https://www.gnu.org/licenses/>. */ + +/* A red-black tree is a binary tree where every node is colored black or + red such that + 1. The root is black. + 2. No red node has a red parent. + Or equivalently: No red node has a red child. + 3. All paths from the root down to any NULL endpoint contain the same + number of black nodes. + 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 + alternately black-red-black-red-...-black-red.) The height of the tree + therefore is >= bh, <= 2*bh. + */ + +/* Color of a node. */ +typedef enum color { BLACK, RED } color_t; + +/* Tree node implementation, valid for this file only. */ +struct NODE_IMPL +{ + struct NODE_IMPL *left; /* left branch, or NULL */ + struct NODE_IMPL *right; /* right branch, or NULL */ + /* Parent pointer, or NULL. The parent pointer is not needed for most + operations. It is needed so that a NODE_T can be returned without + memory allocation, on which the functions <container>_remove_node, + <container>_add_before, <container>_add_after can be implemented. */ + struct NODE_IMPL *parent; + color_t color; /* node's color */ + NODE_PAYLOAD_FIELDS +}; +typedef struct NODE_IMPL * NODE_T; + +/* Concrete CONTAINER_IMPL type, valid for this file only. */ +struct CONTAINER_IMPL +{ + struct CONTAINER_IMPL_BASE base; + struct NODE_IMPL *root; /* root node or NULL */ + size_t count; /* number of nodes */ +}; + +/* A red-black tree of height h has a black-height bh >= ceil(h/2) and + therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree + of height h >= 117 would have at least 2^59 - 1 elements, and because even + on 64-bit machines, + sizeof (NODE_IMPL) * (2^59 - 1) > 2^64 + this would exceed the address space of the machine. */ +#define MAXHEIGHT 116 + +/* Rotate left a subtree. + + 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 NODE_T +rotate_left (NODE_T b_node, NODE_T d_node) +{ + NODE_T c_node = d_node->left; + + b_node->right = c_node; + d_node->left = b_node; + + d_node->parent = b_node->parent; + b_node->parent = d_node; + if (c_node != NULL) + c_node->parent = b_node; + + return d_node; +} + +/* Rotate right a subtree. + + 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 NODE_T +rotate_right (NODE_T b_node, NODE_T d_node) +{ + NODE_T c_node = b_node->right; + + d_node->left = c_node; + b_node->right = d_node; + + b_node->parent = d_node->parent; + d_node->parent = b_node; + if (c_node != NULL) + c_node->parent = d_node; + + return b_node; +} + +/* Ensure the tree is balanced, after an insertion operation. + Also assigns node->color. + parent is the given node's parent, known to be non-NULL. */ +static void +rebalance_after_add (CONTAINER_T container, NODE_T node, NODE_T parent) +{ + for (;;) + { + /* At this point, parent = node->parent != NULL. + Think of node->color being RED (although node->color is not yet + assigned.) */ + NODE_T grandparent; + NODE_T uncle; + + if (parent->color == BLACK) + { + /* 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. */ + + if (grandparent->left == parent) + uncle = grandparent->right; + else if (grandparent->right == parent) + uncle = grandparent->left; + else + 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; + } + 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. */ + NODE_T *grandparentp; + + if (grandparent->parent == NULL) + grandparentp = &container->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; + } + } +} + +/* Ensure the tree is balanced, after a deletion operation. + CHILD was a grandchild of PARENT and is now its child. Between them, + a black node was removed. CHILD is also black, or NULL. + (CHILD can also be NULL. But PARENT is non-NULL.) */ +static void +rebalance_after_remove (CONTAINER_T container, NODE_T child, NODE_T parent) +{ + 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. */ + NODE_T *parentp; + + if (parent->parent == NULL) + parentp = &container->root; + else if (parent->parent->left == parent) + parentp = &parent->parent->left; + else if (parent->parent->right == parent) + parentp = &parent->parent->right; + else + abort (); + + if (parent->left == child) + { + 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) + { + 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 (); + + /* 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; + } +#endif + + if (parent == NULL) + return; + } +} + +static NODE_T +gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS) +{ + /* Create new node. */ + NODE_T new_node = + (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + NODE_PAYLOAD_ASSIGN(new_node) + + /* Add it to the tree. */ + if (container->root == NULL) + { + new_node->color = BLACK; + container->root = new_node; + new_node->parent = NULL; + } + else + { + NODE_T node; + + for (node = container->root; node->left != NULL; ) + node = node->left; + + node->left = new_node; + new_node->parent = node; + + /* Color and rebalance. */ + rebalance_after_add (container, new_node, node); + } + + container->count++; + return new_node; +} + +static NODE_T +gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) +{ + /* Create new node. */ + NODE_T new_node = + (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + NODE_PAYLOAD_ASSIGN(new_node) + + /* Add it to the tree. */ + if (node->left == NULL) + node->left = new_node; + else + { + for (node = node->left; node->right != NULL; ) + node = node->right; + node->right = new_node; + } + new_node->parent = node; + + /* Color and rebalance. */ + rebalance_after_add (container, new_node, node); + + container->count++; + return new_node; +} + +static NODE_T +gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS) +{ + /* Create new node. */ + NODE_T new_node = + (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + NODE_PAYLOAD_ASSIGN(new_node) + + /* Add it to the tree. */ + if (node->right == NULL) + node->right = new_node; + else + { + for (node = node->right; node->left != NULL; ) + node = node->left; + node->left = new_node; + } + new_node->parent = node; + + /* Color and rebalance. */ + rebalance_after_add (container, new_node, node); + + container->count++; + return new_node; +} + +static bool +gl_tree_remove_node (CONTAINER_T container, NODE_T node) +{ + NODE_T parent = node->parent; + + if (node->left == NULL) + { + /* Replace node with node->right. */ + 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; + } + if (parent == NULL) + container->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 (container, 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. */ + /* Replace node with node->left. */ + 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. */ + child->color = BLACK; + if (parent == NULL) + container->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + } + } + else + { + /* Replace node with the rightmost element of the node->left subtree. */ + NODE_T subst; + NODE_T subst_parent; + NODE_T child; + color_t removed_color; + + for (subst = node->left; subst->right != NULL; ) + subst = subst->right; + + subst_parent = subst->parent; + + child = subst->left; + + 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. */ + if (subst_parent != node) + { + 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.) */ + if (subst_parent != node) + { + 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) + container->root = subst; + else if (parent->left == node) + parent->left = subst; + else /* parent->right == node */ + 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 (container, child, + subst_parent != node ? subst_parent : subst); + } + } + + container->count--; + NODE_PAYLOAD_DISPOSE + free (node); + return true; +} + +/* For debugging. */ +static unsigned int +check_invariants (NODE_T node, NODE_T parent, size_t *counterp) +{ + unsigned int left_blackheight = + (node->left != NULL ? check_invariants (node->left, node, counterp) : 0); + unsigned int right_blackheight = + (node->right != NULL ? check_invariants (node->right, node, counterp) : 0); + + if (!(node->parent == parent)) + abort (); + if (!(node->color == BLACK || node->color == RED)) + abort (); + if (parent == NULL && !(node->color == BLACK)) + abort (); + if (!(left_blackheight == right_blackheight)) + abort (); + + (*counterp)++; + + return left_blackheight + (node->color == BLACK ? 1 : 0); +}
--- a/lib/gl_rbtree_oset.c Tue Dec 11 20:56:25 2018 +0100 +++ b/lib/gl_rbtree_oset.c Tue Dec 11 20:56:27 2018 +0100 @@ -22,773 +22,30 @@ #include <stdlib.h> -/* A red-black tree is a binary tree where every node is colored black or - red such that - 1. The root is black. - 2. No red node has a red parent. - Or equivalently: No red node has a red child. - 3. All paths from the root down to any NULL endpoint contain the same - number of black nodes. - 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 - alternately black-red-black-red-...-black-red.) The height of the tree - therefore is >= bh, <= 2*bh. - */ - /* -------------------------- gl_oset_t Data Type -------------------------- */ -/* Color of a node. */ -typedef enum color { BLACK, RED } color_t; - -/* Tree node implementation, valid for this file only. */ -struct gl_oset_node_impl -{ - struct gl_oset_node_impl *left; /* left branch, or NULL */ - struct gl_oset_node_impl *right; /* right branch, or NULL */ - /* Parent pointer, or NULL. The parent pointer is not needed for most - operations. It is needed so that a gl_oset_node_t can be returned - without memory allocation, on which the functions gl_oset_remove_node, - gl_oset_add_before, gl_oset_add_after can be implemented. */ - struct gl_oset_node_impl *parent; - color_t color; /* node's color */ +/* Parameterization of gl_rbtree_ordered.h. */ +#define CONTAINER_T gl_oset_t +#define CONTAINER_IMPL gl_oset_impl +#define CONTAINER_IMPL_BASE gl_oset_impl_base +#define NODE_IMPL gl_oset_node_impl +#define NODE_T gl_oset_node_t +#define NODE_PAYLOAD_FIELDS \ const void *value; -}; -typedef struct gl_oset_node_impl * gl_oset_node_t; - -/* Concrete gl_oset_impl type, valid for this file only. */ -struct gl_oset_impl -{ - struct gl_oset_impl_base base; - struct gl_oset_node_impl *root; /* root node or NULL */ - size_t count; /* number of nodes */ -}; - -/* A red-black tree of height h has a black-height bh >= ceil(h/2) and - therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree - of height h >= 117 would have at least 2^59 - 1 elements, and because even - on 64-bit machines, - sizeof (gl_oset_node_impl) * (2^59 - 1) > 2^64 - this would exceed the address space of the machine. */ -#define MAXHEIGHT 116 - -/* Rotate left a subtree. - - 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 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; - - b_node->right = c_node; - d_node->left = b_node; - - d_node->parent = b_node->parent; - b_node->parent = d_node; - if (c_node != NULL) - c_node->parent = b_node; - - return d_node; -} - -/* Rotate right a subtree. - - 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 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; - - d_node->left = c_node; - b_node->right = d_node; - - b_node->parent = d_node->parent; - d_node->parent = b_node; - if (c_node != NULL) - c_node->parent = d_node; - - return b_node; -} - -/* Ensure the tree is balanced, after an insertion operation. - Also assigns node->color. - parent is the given node's parent, known to be non-NULL. */ -static void -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.) */ - 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; - } - - grandparent = parent->parent; - /* Since parent is RED, we know that - grandparent is != NULL and colored BLACK. */ - - if (grandparent->left == parent) - uncle = grandparent->right; - else if (grandparent->right == parent) - uncle = grandparent->left; - else - 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; - } - 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; - } - - /* 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; - } - } -} - -/* Ensure the tree is balanced, after a deletion operation. - CHILD was a grandchild of PARENT and is now its child. Between them, - a black node was removed. CHILD is also black, or NULL. - (CHILD can also be NULL. But PARENT is non-NULL.) */ -static void -rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t parent) -{ - 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. */ - gl_oset_node_t *parentp; - - if (parent->parent == NULL) - parentp = &set->root; - else if (parent->parent->left == parent) - parentp = &parent->parent->left; - else if (parent->parent->right == parent) - parentp = &parent->parent->right; - else - 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; - } - } - } - else if (parent->right == child) - { - gl_oset_node_t sibling = parent->left; - /* sibling's black-height is >= 1. In particular, - sibling != NULL. +#define NODE_PAYLOAD_PARAMS \ + const void *elt +#define NODE_PAYLOAD_ASSIGN(node) \ + node->value = elt; +#define NODE_PAYLOAD_DISPOSE \ + if (container->base.dispose_fn != NULL) \ + container->base.dispose_fn (node->value); - 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 (); - - /* 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; - } -#endif - - if (parent == NULL) - return; - } -} - -static gl_oset_node_t -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 *) malloc (sizeof (struct gl_oset_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->value = elt; - - /* Add it to the tree. */ - if (set->root == NULL) - { - new_node->color = BLACK; - set->root = new_node; - new_node->parent = NULL; - } - else - { - gl_oset_node_t node; - - for (node = set->root; node->left != NULL; ) - node = node->left; - - node->left = new_node; - new_node->parent = node; - - /* Color and rebalance. */ - rebalance_after_add (set, new_node, node); - } - - set->count++; - return new_node; -} - -static gl_oset_node_t -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 *) malloc (sizeof (struct gl_oset_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->value = elt; - - /* Add it to the tree. */ - if (node->left == NULL) - node->left = new_node; - else - { - for (node = node->left; node->right != NULL; ) - node = node->right; - node->right = new_node; - } - new_node->parent = node; - - /* Color and rebalance. */ - rebalance_after_add (set, new_node, node); - - set->count++; - return new_node; -} - -static gl_oset_node_t -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 *) malloc (sizeof (struct gl_oset_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->value = elt; - - /* Add it to the tree. */ - if (node->right == NULL) - node->right = new_node; - else - { - for (node = node->right; node->left != NULL; ) - node = node->left; - node->left = new_node; - } - new_node->parent = node; - - /* Color and rebalance. */ - rebalance_after_add (set, new_node, node); - - set->count++; - return new_node; -} - -static bool -gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) -{ - gl_oset_node_t parent = node->parent; - - if (node->left == NULL) - { - /* Replace node with node->right. */ - 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; - } - if (parent == NULL) - 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); - } - } - 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. */ - /* 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. */ - child->color = BLACK; - if (parent == NULL) - set->root = child; - else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - } - } - else - { - /* Replace node with the rightmost element of the node->left subtree. */ - gl_oset_node_t subst; - gl_oset_node_t subst_parent; - gl_oset_node_t child; - color_t removed_color; - - for (subst = node->left; subst->right != NULL; ) - subst = subst->right; - - subst_parent = subst->parent; - - child = subst->left; - - 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. */ - if (subst_parent != node) - { - 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.) */ - if (subst_parent != node) - { - 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; - else if (parent->left == node) - parent->left = subst; - else /* parent->right == node */ - 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); - } - } - - set->count--; - if (set->base.dispose_fn != NULL) - set->base.dispose_fn (node->value); - free (node); - return true; -} +#include "gl_rbtree_ordered.h" /* Generic binary tree code. */ #include "gl_anytree_oset.h" /* For debugging. */ -static unsigned int -check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp) -{ - unsigned int left_blackheight = - (node->left != NULL ? check_invariants (node->left, node, counterp) : 0); - unsigned int right_blackheight = - (node->right != NULL ? check_invariants (node->right, node, counterp) : 0); - - if (!(node->parent == parent)) - abort (); - if (!(node->color == BLACK || node->color == RED)) - abort (); - if (parent == NULL && !(node->color == BLACK)) - abort (); - if (!(left_blackheight == right_blackheight)) - abort (); - - (*counterp)++; - - return left_blackheight + (node->color == BLACK ? 1 : 0); -} void gl_rbtree_oset_check_invariants (gl_oset_t set) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/modules/rbtree-omap Tue Dec 11 20:56:27 2018 +0100 @@ -0,0 +1,25 @@ +Description: +Ordered map data type implemented by a binary tree. + +Files: +lib/gl_rbtree_omap.h +lib/gl_rbtree_omap.c +lib/gl_rbtree_ordered.h +lib/gl_anytree_omap.h + +Depends-on: +omap + +configure.ac: + +Makefile.am: +lib_SOURCES += gl_rbtree_omap.h gl_rbtree_omap.c gl_rbtree_ordered.h gl_anytree_omap.h + +Include: +"gl_rbtree_omap.h" + +License: +GPL + +Maintainer: +all
--- a/modules/rbtree-oset Tue Dec 11 20:56:25 2018 +0100 +++ b/modules/rbtree-oset Tue Dec 11 20:56:27 2018 +0100 @@ -4,6 +4,7 @@ Files: lib/gl_rbtree_oset.h lib/gl_rbtree_oset.c +lib/gl_rbtree_ordered.h lib/gl_anytree_oset.h Depends-on: @@ -12,7 +13,7 @@ configure.ac: Makefile.am: -lib_SOURCES += gl_rbtree_oset.h gl_rbtree_oset.c gl_anytree_oset.h +lib_SOURCES += gl_rbtree_oset.h gl_rbtree_oset.c gl_rbtree_ordered.h gl_anytree_oset.h Include: "gl_rbtree_oset.h"