diff options
author | Bruno Haible <bruno@clisp.org> | 2018-12-11 20:56:25 +0100 |
---|---|---|
committer | Bruno Haible <bruno@clisp.org> | 2018-12-11 20:56:25 +0100 |
commit | eaf9a78f20bdb8e805ae7501bba020272b1f91cf (patch) | |
tree | fa5eebbed9b64de48cecc455166125617dc8d94a /lib/gl_avltree_oset.c | |
parent | 83ac717e2c236cb1734b8f9eeab6d70b5fb7e6dd (diff) | |
download | gnulib-eaf9a78f20bdb8e805ae7501bba020272b1f91cf.tar.gz |
avltree-omap: New module.
* lib/gl_avltree_omap.h: New file.
* lib/gl_avltree_omap.c: New file.
* lib/gl_avltree_ordered.h: Code moved to here from
lib/gl_avltree_oset.c. Parameterize.
* lib/gl_avltree_oset.c: Include gl_avltree_ordered.h.
* lib/gl_anytree_omap.h: New file.
* modules/avltree-omap: New file.
* modules/avltree-oset (Files): Add lib/gl_avltree_ordered.h.
(Makefile.am): Add gl_avltree_ordered.h to lib_SOURCES.
Diffstat (limited to 'lib/gl_avltree_oset.c')
-rw-r--r-- | lib/gl_avltree_oset.c | 542 |
1 files changed, 15 insertions, 527 deletions
diff --git a/lib/gl_avltree_oset.c b/lib/gl_avltree_oset.c index ead337c0e1..4bda91eaae 100644 --- a/lib/gl_avltree_oset.c +++ b/lib/gl_avltree_oset.c @@ -22,542 +22,30 @@ #include <stdlib.h> -/* An AVL tree is a binary tree where - 1. The height of each node is calculated as - heightof(node) = 1 + max (heightof(node.left), heightof(node.right)). - 2. The heights of the subtrees of each node differ by at most 1: - | heightof(right) - heightof(left) | <= 1. - 3. The index of the elements in the node.left subtree are smaller than - the index of node. - The index of the elements in the node.right subtree are larger than - the index of node. - */ - /* -------------------------- gl_oset_t Data Type -------------------------- */ -/* 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; - int balance; /* heightof(right) - heightof(left), - always = -1 or 0 or 1 */ +/* Parameterization of gl_avltree_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 */ -}; - -/* An AVL tree of height h has at least F_(h+2) - 1 [Fibonacci number] and at - most 2^h - 1 elements. So, h <= 84 (because a tree of height h >= 85 would - have at least F_87 - 1 elements, and because even on 64-bit machines, - sizeof (gl_oset_node_impl) * (F_87 - 1) > 2^64 - this would exceed the address space of the machine. */ -#define MAXHEIGHT 83 - -/* Ensure the tree is balanced, after an insertion or deletion operation. - The height of NODE is incremented by HEIGHT_DIFF (1 or -1). - PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.) - Rotation operations are performed starting at PARENT (not NODE itself!). */ -static void -rebalance (gl_oset_t set, - gl_oset_node_t node, int height_diff, gl_oset_node_t parent) -{ - for (;;) - { - gl_oset_node_t child; - int previous_balance; - int balance_diff; - gl_oset_node_t nodeleft; - gl_oset_node_t noderight; - - child = node; - node = parent; - - previous_balance = node->balance; - - /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right - branch's height has increased by 1 or the left branch's height has - decreased by 1, -1 if the right branch's height has decreased by 1 or - the left branch's height has increased by 1, 0 if no height change. */ - if (node->left != NULL || node->right != NULL) - balance_diff = (child == node->right ? height_diff : -height_diff); - else - /* Special case where above formula doesn't work, because the caller - didn't tell whether node's left or right branch shrunk from height 1 - to NULL. */ - balance_diff = - previous_balance; - - node->balance += balance_diff; - if (balance_diff == previous_balance) - { - /* node->balance is outside the range [-1,1]. Must rotate. */ - gl_oset_node_t *nodep; - - if (node->parent == NULL) - /* node == set->root */ - nodep = &set->root; - else if (node->parent->left == node) - nodep = &node->parent->left; - else if (node->parent->right == node) - nodep = &node->parent->right; - else - abort (); - - nodeleft = node->left; - noderight = node->right; - - if (balance_diff < 0) - { - /* node->balance = -2. The subtree is heavier on the left side. - Rotate from left to right: - - * - / \ - h+2 h - */ - gl_oset_node_t nodeleftright = nodeleft->right; - if (nodeleft->balance <= 0) - { - /* - * h+2|h+3 - / \ / \ - h+2 h --> / h+1|h+2 - / \ | / \ - h+1 h|h+1 h+1 h|h+1 h - */ - node->left = nodeleftright; - nodeleft->right = node; - - nodeleft->parent = node->parent; - node->parent = nodeleft; - if (nodeleftright != NULL) - nodeleftright->parent = node; - - nodeleft->balance += 1; - node->balance = - nodeleft->balance; - - *nodep = nodeleft; - height_diff = (height_diff < 0 - ? /* noderight's height had been decremented from - h+1 to h. The subtree's height changes from - h+3 to h+2|h+3. */ - nodeleft->balance - 1 - : /* nodeleft's height had been incremented from - h+1 to h+2. The subtree's height changes from - h+2 to h+2|h+3. */ - nodeleft->balance); - } - else - { - /* - * h+2 - / \ / \ - h+2 h --> h+1 h+1 - / \ / \ / \ - h h+1 h L R h - / \ - L R - - */ - gl_oset_node_t L = nodeleft->right = nodeleftright->left; - gl_oset_node_t R = node->left = nodeleftright->right; - nodeleftright->left = nodeleft; - nodeleftright->right = node; - - nodeleftright->parent = node->parent; - if (L != NULL) - L->parent = nodeleft; - if (R != NULL) - R->parent = node; - nodeleft->parent = nodeleftright; - node->parent = nodeleftright; - - nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0); - node->balance = (nodeleftright->balance < 0 ? 1 : 0); - nodeleftright->balance = 0; +#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); - *nodep = nodeleftright; - height_diff = (height_diff < 0 - ? /* noderight's height had been decremented from - h+1 to h. The subtree's height changes from - h+3 to h+2. */ - -1 - : /* nodeleft's height had been incremented from - h+1 to h+2. The subtree's height changes from - h+2 to h+2. */ - 0); - } - } - else - { - /* node->balance = 2. The subtree is heavier on the right side. - Rotate from right to left: - - * - / \ - h h+2 - */ - gl_oset_node_t noderightleft = noderight->left; - if (noderight->balance >= 0) - { - /* - * h+2|h+3 - / \ / \ - h h+2 --> h+1|h+2 \ - / \ / \ | - h|h+1 h+1 h h|h+1 h+1 - */ - node->right = noderightleft; - noderight->left = node; - - noderight->parent = node->parent; - node->parent = noderight; - if (noderightleft != NULL) - noderightleft->parent = node; - - noderight->balance -= 1; - node->balance = - noderight->balance; - - *nodep = noderight; - height_diff = (height_diff < 0 - ? /* nodeleft's height had been decremented from - h+1 to h. The subtree's height changes from - h+3 to h+2|h+3. */ - - noderight->balance - 1 - : /* noderight's height had been incremented from - h+1 to h+2. The subtree's height changes from - h+2 to h+2|h+3. */ - - noderight->balance); - } - else - { - /* - * h+2 - / \ / \ - h h+2 --> h+1 h+1 - / \ / \ / \ - h+1 h h L R h - / \ - L R - - */ - gl_oset_node_t L = node->right = noderightleft->left; - gl_oset_node_t R = noderight->left = noderightleft->right; - noderightleft->left = node; - noderightleft->right = noderight; - - noderightleft->parent = node->parent; - if (L != NULL) - L->parent = node; - if (R != NULL) - R->parent = noderight; - node->parent = noderightleft; - noderight->parent = noderightleft; - - node->balance = (noderightleft->balance > 0 ? -1 : 0); - noderight->balance = (noderightleft->balance < 0 ? 1 : 0); - noderightleft->balance = 0; - - *nodep = noderightleft; - height_diff = (height_diff < 0 - ? /* nodeleft's height had been decremented from - h+1 to h. The subtree's height changes from - h+3 to h+2. */ - -1 - : /* noderight's height had been incremented from - h+1 to h+2. The subtree's height changes from - h+2 to h+2. */ - 0); - } - } - node = *nodep; - } - else - { - /* No rotation needed. Only propagation of the height change to the - next higher level. */ - if (height_diff < 0) - height_diff = (previous_balance == 0 ? 0 : -1); - else - height_diff = (node->balance == 0 ? 0 : 1); - } - - if (height_diff == 0) - break; - - parent = node->parent; - if (parent == NULL) - break; - } -} - -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->balance = 0; - new_node->value = elt; - - /* Add it to the tree. */ - if (set->root == NULL) - { - 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; - node->balance--; - - /* Rebalance. */ - if (node->right == NULL && node->parent != NULL) - rebalance (set, node, 1, node->parent); - } - - 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)); - bool height_inc; - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->balance = 0; - new_node->value = elt; - - /* Add it to the tree. */ - if (node->left == NULL) - { - node->left = new_node; - node->balance--; - height_inc = (node->right == NULL); - } - else - { - for (node = node->left; node->right != NULL; ) - node = node->right; - node->right = new_node; - node->balance++; - height_inc = (node->left == NULL); - } - new_node->parent = node; - - /* Rebalance. */ - if (height_inc && node->parent != NULL) - rebalance (set, node, 1, node->parent); - - 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)); - bool height_inc; - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->balance = 0; - new_node->value = elt; - - /* Add it to the tree. */ - if (node->right == NULL) - { - node->right = new_node; - node->balance++; - height_inc = (node->left == NULL); - } - else - { - for (node = node->right; node->left != NULL; ) - node = node->left; - node->left = new_node; - node->balance--; - height_inc = (node->right == NULL); - } - new_node->parent = node; - - /* Rebalance. */ - if (height_inc && node->parent != NULL) - rebalance (set, node, 1, node->parent); - - 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; - if (parent == NULL) - set->root = child; - else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - - rebalance (set, child, -1, 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; - if (parent == NULL) - set->root = child; - else - { - if (parent->left == node) - parent->left = child; - else /* parent->right == node */ - parent->right = child; - - rebalance (set, child, -1, parent); - } - } - 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; - - for (subst = node->left; subst->right != NULL; ) - subst = subst->right; - - subst_parent = subst->parent; - - child = subst->left; - - /* 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->balance = node->balance; - subst->parent = parent; - if (parent == NULL) - set->root = subst; - else if (parent->left == node) - parent->left = subst; - else /* parent->right == node */ - parent->right = subst; - - /* 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 (set, child, -1, 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_avltree_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_height = - (node->left != NULL ? check_invariants (node->left, node, counterp) : 0); - unsigned int right_height = - (node->right != NULL ? check_invariants (node->right, node, counterp) : 0); - int balance = (int)right_height - (int)left_height; - - if (!(node->parent == parent)) - abort (); - if (!(balance >= -1 && balance <= 1)) - abort (); - if (!(node->balance == balance)) - abort (); - - (*counterp)++; - - return 1 + (left_height > right_height ? left_height : right_height); -} void gl_avltree_oset_check_invariants (gl_oset_t set) { |