Mercurial > gnulib
changeset 40006:0caeb347e88e
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.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Tue, 11 Dec 2018 20:56:25 +0100 |
| parents | db8e2e244697 |
| children | 31ddfa01e256 |
| files | ChangeLog lib/gl_anytree_omap.h lib/gl_avltree_omap.c lib/gl_avltree_omap.h lib/gl_avltree_ordered.h lib/gl_avltree_oset.c modules/avltree-omap modules/avltree-oset |
| diffstat | 8 files changed, 1014 insertions(+), 528 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog Tue Dec 11 20:56:22 2018 +0100 +++ b/ChangeLog Tue Dec 11 20:56:25 2018 +0100 @@ -1,5 +1,16 @@ 2018-12-11 Bruno Haible <bruno@clisp.org> + 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. + array-omap: New module. * lib/gl_array_omap.h: New file. * lib/gl_array_omap.c: New file.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_anytree_omap.h Tue Dec 11 20:56:25 2018 +0100 @@ -0,0 +1,305 @@ +/* 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/>. */ + +/* Common code of gl_avltree_omap.c and gl_rbtree_omap.c. */ + +/* An item on the stack used for iterating across the elements. */ +typedef struct +{ + gl_omap_node_t node; + bool rightp; +} iterstack_item_t; + +/* A stack used for iterating across the elements. */ +typedef iterstack_item_t iterstack_t[MAXHEIGHT]; + +static gl_omap_t +gl_tree_nx_create_empty (gl_omap_implementation_t implementation, + gl_mapkey_compar_fn compar_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn) +{ + struct gl_omap_impl *map = + (struct gl_omap_impl *) malloc (sizeof (struct gl_omap_impl)); + + if (map == NULL) + return NULL; + + map->base.vtable = implementation; + map->base.compar_fn = compar_fn; + map->base.kdispose_fn = kdispose_fn; + map->base.vdispose_fn = vdispose_fn; + map->root = NULL; + map->count = 0; + + return map; +} + +static size_t +gl_tree_size (gl_omap_t map) +{ + return map->count; +} + +static bool +gl_tree_search (gl_omap_t map, const void *key, const void **valuep) +{ + gl_mapkey_compar_fn compar = map->base.compar_fn; + gl_omap_node_t node; + + for (node = map->root; node != NULL; ) + { + int cmp = (compar != NULL + ? compar (node->key, key) + : (node->key > key ? 1 : + node->key < key ? -1 : 0)); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have a key equal to KEY. */ + *valuep = node->value; + return true; + } + } + return false; +} + +static bool +gl_tree_search_atleast (gl_omap_t map, + gl_mapkey_threshold_fn threshold_fn, + const void *threshold, + const void **keyp, const void **valuep) +{ + gl_omap_node_t node; + + for (node = map->root; node != NULL; ) + { + if (! threshold_fn (node->key, threshold)) + node = node->right; + else + { + /* We have a key >= THRESHOLD. But we need the leftmost such + element. */ + gl_omap_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + if (! threshold_fn (node->key, threshold)) + node = node->right; + else + { + found = node; + node = node->left; + } + } + *keyp = found->key; + *valuep = found->value; + return true; + } + } + return false; +} + +static int +gl_tree_nx_getput (gl_omap_t map, const void *key, const void *value, + const void **oldvaluep) +{ + gl_mapkey_compar_fn compar; + gl_omap_node_t node = map->root; + + if (node == NULL) + { + if (gl_tree_nx_add_first (map, key, value) == NULL) + return -1; + return true; + } + + compar = map->base.compar_fn; + + for (;;) + { + int cmp = (compar != NULL + ? compar (node->key, key) + : (node->key > key ? 1 : + node->key < key ? -1 : 0)); + + if (cmp < 0) + { + if (node->right == NULL) + { + if (gl_tree_nx_add_after (map, node, key, value) == NULL) + return -1; + return true; + } + node = node->right; + } + else if (cmp > 0) + { + if (node->left == NULL) + { + if (gl_tree_nx_add_before (map, node, key, value) == NULL) + return -1; + return true; + } + node = node->left; + } + else /* cmp == 0 */ + { + *oldvaluep = node->value; + node->value = value; + return false; + } + } +} + +static bool +gl_tree_getremove (gl_omap_t map, const void *key, const void **oldvaluep) +{ + gl_mapkey_compar_fn compar = map->base.compar_fn; + gl_omap_node_t node; + + for (node = map->root; node != NULL; ) + { + int cmp = (compar != NULL + ? compar (node->key, key) + : (node->key > key ? 1 : + node->key < key ? -1 : 0)); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have a key equal to KEY. */ + *oldvaluep = node->value; + gl_tree_remove_node (map, node); + return true; + } + } + return false; +} + +static void +gl_tree_omap_free (gl_omap_t map) +{ + /* Iterate across all elements in post-order. */ + gl_omap_node_t node = map->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = false; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + goto done_iterate; + stack_ptr--; + node = stack_ptr->node; + if (!stack_ptr->rightp) + break; + /* Free the current node. */ + if (map->base.vdispose_fn != NULL) + map->base.vdispose_fn (node->value); + if (map->base.kdispose_fn != NULL) + map->base.kdispose_fn (node->key); + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + done_iterate: + free (map); +} + +/* --------------------- gl_omap_iterator_t Data Type --------------------- */ + +static gl_omap_iterator_t +gl_tree_iterator (gl_omap_t map) +{ + gl_omap_iterator_t result; + gl_omap_node_t node; + + result.vtable = map->base.vtable; + result.map = map; + /* Start node is the leftmost node. */ + node = map->root; + if (node != NULL) + while (node->left != NULL) + node = node->left; + result.p = node; + /* End point is past the rightmost node. */ + result.q = NULL; +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static bool +gl_tree_iterator_next (gl_omap_iterator_t *iterator, + const void **keyp, const void **valuep) +{ + if (iterator->p != iterator->q) + { + gl_omap_node_t node = (gl_omap_node_t) iterator->p; + *keyp = node->key; + *valuep = node->value; + /* Advance to the next node. */ + if (node->right != NULL) + { + node = node->right; + while (node->left != NULL) + node = node->left; + } + else + { + while (node->parent != NULL && node->parent->right == node) + node = node->parent; + node = node->parent; + } + iterator->p = node; + return true; + } + else + return false; +} + +static void +gl_tree_iterator_free (gl_omap_iterator_t *iterator) +{ +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_avltree_omap.c Tue Dec 11 20:56:25 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_avltree_omap.h" + +#include <stdlib.h> + +/* -------------------------- gl_omap_t Data Type -------------------------- */ + +/* Parameterization of gl_avltree_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_avltree_ordered.h" + +/* Generic binary tree code. */ +#include "gl_anytree_omap.h" + +/* For debugging. */ +void +gl_avltree_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_avltree_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_avltree_omap.h Tue Dec 11 20:56:25 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_AVLTREE_OMAP_H +#define _GL_AVLTREE_OMAP_H + +#include "gl_omap.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_omap_implementation gl_avltree_omap_implementation; +#define GL_AVLTREE_OMAP &gl_avltree_omap_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_AVLTREE_OMAP_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_avltree_ordered.h Tue Dec 11 20:56:25 2018 +0100 @@ -0,0 +1,547 @@ +/* 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/>. */ + +/* 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. + */ + +/* 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; + int balance; /* heightof(right) - heightof(left), + always = -1 or 0 or 1 */ + 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 */ +}; + +/* 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 (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 (CONTAINER_T container, + NODE_T node, int height_diff, NODE_T parent) +{ + for (;;) + { + NODE_T child; + int previous_balance; + int balance_diff; + NODE_T nodeleft; + 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. */ + NODE_T *nodep; + + if (node->parent == NULL) + /* node == container->root */ + nodep = &container->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 + */ + 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 + + */ + NODE_T L = nodeleft->right = nodeleftright->left; + 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; + + *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 + */ + 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 + + */ + NODE_T L = node->right = noderightleft->left; + 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 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; + new_node->balance = 0; + NODE_PAYLOAD_ASSIGN(new_node) + + /* Add it to the tree. */ + if (container->root == NULL) + { + 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; + node->balance--; + + /* Rebalance. */ + if (node->right == NULL && node->parent != NULL) + rebalance (container, node, 1, node->parent); + } + + 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)); + bool height_inc; + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->balance = 0; + NODE_PAYLOAD_ASSIGN(new_node) + + /* 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 (container, node, 1, node->parent); + + 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)); + bool height_inc; + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->balance = 0; + NODE_PAYLOAD_ASSIGN(new_node) + + /* 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 (container, node, 1, node->parent); + + 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; + if (parent == NULL) + container->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + rebalance (container, 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. */ + NODE_T child = node->left; + + child->parent = parent; + if (parent == NULL) + container->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + rebalance (container, child, -1, parent); + } + } + else + { + /* Replace node with the rightmost element of the node->left subtree. */ + NODE_T subst; + NODE_T subst_parent; + 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) + container->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 (container, child, -1, 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_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); +}
--- a/lib/gl_avltree_oset.c Tue Dec 11 20:56:22 2018 +0100 +++ b/lib/gl_avltree_oset.c Tue Dec 11 20:56:25 2018 +0100 @@ -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; - - *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; +#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 = 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) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/modules/avltree-omap Tue Dec 11 20:56:25 2018 +0100 @@ -0,0 +1,25 @@ +Description: +Ordered map data type implemented by a binary tree. + +Files: +lib/gl_avltree_omap.h +lib/gl_avltree_omap.c +lib/gl_avltree_ordered.h +lib/gl_anytree_omap.h + +Depends-on: +omap + +configure.ac: + +Makefile.am: +lib_SOURCES += gl_avltree_omap.h gl_avltree_omap.c gl_avltree_ordered.h gl_anytree_omap.h + +Include: +"gl_avltree_omap.h" + +License: +GPL + +Maintainer: +all
--- a/modules/avltree-oset Tue Dec 11 20:56:22 2018 +0100 +++ b/modules/avltree-oset Tue Dec 11 20:56:25 2018 +0100 @@ -4,6 +4,7 @@ Files: lib/gl_avltree_oset.h lib/gl_avltree_oset.c +lib/gl_avltree_ordered.h lib/gl_anytree_oset.h Depends-on: @@ -12,7 +13,7 @@ configure.ac: Makefile.am: -lib_SOURCES += gl_avltree_oset.h gl_avltree_oset.c gl_anytree_oset.h +lib_SOURCES += gl_avltree_oset.h gl_avltree_oset.c gl_avltree_ordered.h gl_anytree_oset.h Include: "gl_avltree_oset.h"