diff options
Diffstat (limited to 'gnulib/lib/gl_anyavltree_list2.h')
| m--------- | gnulib | 0 | ||||
| -rw-r--r-- | gnulib/lib/gl_anyavltree_list2.h | 809 |
2 files changed, 809 insertions, 0 deletions
diff --git a/gnulib b/gnulib deleted file mode 160000 -Subproject 443bc5ffcf7429e557f4a371b0661abe98ddbc1 diff --git a/gnulib/lib/gl_anyavltree_list2.h b/gnulib/lib/gl_anyavltree_list2.h new file mode 100644 index 0000000..41cca3c --- /dev/null +++ b/gnulib/lib/gl_anyavltree_list2.h @@ -0,0 +1,809 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006-2007, 2009-2011 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 <http://www.gnu.org/licenses/>. */ + +/* Common code of gl_avltree_list.c and gl_avltreehash_list.c. */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Create a subtree for count >= 1 elements. + Its height is h where 2^(h-1) <= count <= 2^h - 1. + Return NULL upon out-of-memory. */ +static gl_list_node_t +create_subtree_with_contents (size_t count, const void **contents) +{ + size_t half1 = (count - 1) / 2; + size_t half2 = count / 2; + /* Note: half1 + half2 = count - 1. */ + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (node == NULL) + return NULL; + + if (half1 > 0) + { + node->left = create_subtree_with_contents (half1, contents); + if (node->left == NULL) + goto fail1; + node->left->parent = node; + } + else + node->left = NULL; + + node->value = contents[half1]; + + if (half2 > 0) + { + node->right = create_subtree_with_contents (half2, contents + half1 + 1); + if (node->right == NULL) + goto fail2; + node->right->parent = node; + } + else + node->right = NULL; + + /* balance is 0, except when count is a power of two and > 1. + Reason: half1 <= half2 <= half1 + 1, and the two branches can have + different heights only if half1 = 2^h - 1 and half2 = 2^h; in this + case, count = half1 + half2 + 1 = 2^(h+1). */ + node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0); + + node->branch_size = count; + + return node; + + fail2: + if (node->left != NULL) + free_subtree (node->left); + fail1: + free (node); + return NULL; +} + +static gl_list_t +gl_tree_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + { + size_t estimate = xsum (count, count / 2); /* 1.5 * count */ + if (estimate < 10) + estimate = 10; + list->table_size = next_prime (estimate); + if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t)))) + goto fail1; + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail1; + } +#endif + if (count > 0) + { + list->root = create_subtree_with_contents (count, contents); + if (list->root == NULL) + goto fail2; + list->root->parent = NULL; + +#if WITH_HASHTABLE + /* Now that the tree is built, node_position() works. Now we can + add the nodes to the hash table. */ + if (add_nodes_to_buckets (list) < 0) + goto fail3; +#endif + } + else + list->root = NULL; + + return list; + +#if WITH_HASHTABLE + fail3: + free_subtree (list->root); +#endif + fail2: +#if WITH_HASHTABLE + free (list->table); + fail1: +#endif + free (list); + return NULL; +} + +/* 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_list_t list, + gl_list_node_t node, int height_diff, gl_list_node_t parent) +{ + for (;;) + { + gl_list_node_t child; + int previous_balance; + int balance_diff; + gl_list_node_t nodeleft; + gl_list_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_list_node_t *nodep; + + if (node->parent == NULL) + /* node == list->root */ + nodep = &list->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_list_node_t nodeleftleft = nodeleft->left; + gl_list_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; + + node->branch_size = + (nodeleftright != NULL ? nodeleftright->branch_size : 0) + + 1 + (noderight != NULL ? noderight->branch_size : 0); + nodeleft->branch_size = + nodeleftleft->branch_size + 1 + node->branch_size; + + *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_list_node_t L = nodeleft->right = nodeleftright->left; + gl_list_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; + + nodeleft->branch_size = + (nodeleft->left != NULL ? nodeleft->left->branch_size : 0) + + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0); + node->branch_size = + (node->left != NULL ? node->left->branch_size : 0) + + 1 + (node->right != NULL ? node->right->branch_size : 0); + nodeleftright->branch_size = + nodeleft->branch_size + 1 + node->branch_size; + + *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_list_node_t noderightleft = noderight->left; + gl_list_node_t noderightright = noderight->right; + 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; + + node->branch_size = + (nodeleft != NULL ? nodeleft->branch_size : 0) + + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0); + noderight->branch_size = + node->branch_size + 1 + noderightright->branch_size; + + *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_list_node_t L = node->right = noderightleft->left; + gl_list_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; + + node->branch_size = + (node->left != NULL ? node->left->branch_size : 0) + + 1 + (node->right != NULL ? node->right->branch_size : 0); + noderight->branch_size = + (noderight->left != NULL ? noderight->left->branch_size : 0) + + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0); + noderightleft->branch_size = + node->branch_size + 1 + noderight->branch_size; + + *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 void +gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node) +{ + gl_list_node_t parent = node->parent; + + if (node->left == NULL) + { + /* Replace node with node->right. */ + gl_list_node_t child = node->right; + + if (child != NULL) + child->parent = parent; + if (parent == NULL) + list->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = parent; p != NULL; p = p->parent) + p->branch_size--; + } + + rebalance (list, 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_list_node_t child = node->left; + + child->parent = parent; + if (parent == NULL) + list->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = parent; p != NULL; p = p->parent) + p->branch_size--; + } + + rebalance (list, child, -1, parent); + } + } + else + { + /* Replace node with the rightmost element of the node->left subtree. */ + gl_list_node_t subst; + gl_list_node_t subst_parent; + gl_list_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; + } + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = subst_parent; p != NULL; p = p->parent) + p->branch_size--; + } + + /* 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->branch_size = node->branch_size; + subst->parent = parent; + if (parent == NULL) + list->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 (list, child, -1, subst_parent != node ? subst_parent : subst); + } +} + +static gl_list_node_t +gl_tree_nx_add_first (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->balance = 0; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (list->root == NULL) + { + list->root = new_node; + new_node->parent = NULL; + } + else + { + gl_list_node_t node; + + for (node = list->root; node->left != NULL; ) + node = node->left; + + node->left = new_node; + new_node->parent = node; + node->balance--; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Rebalance. */ + if (node->right == NULL && node->parent != NULL) + rebalance (list, node, 1, node->parent); + } + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_nx_add_last (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->balance = 0; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (list->root == NULL) + { + list->root = new_node; + new_node->parent = NULL; + } + else + { + gl_list_node_t node; + + for (node = list->root; node->right != NULL; ) + node = node->right; + + node->right = new_node; + new_node->parent = node; + node->balance++; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Rebalance. */ + if (node->left == NULL && node->parent != NULL) + rebalance (list, node, 1, node->parent); + } + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node; + bool height_inc; + + new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->balance = 0; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* 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; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Rebalance. */ + if (height_inc && node->parent != NULL) + rebalance (list, node, 1, node->parent); + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node; + bool height_inc; + + new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->balance = 0; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* 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; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Rebalance. */ + if (height_inc && node->parent != NULL) + rebalance (list, node, 1, node->parent); + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} |