Mercurial > hg > octave-kai > gnulib-hg
changeset 6973:de9a21fc207a
Common code several concrete list implementations.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Mon, 17 Jul 2006 11:27:18 +0000 |
| parents | 1708033b9e1f |
| children | c7d0a3879b08 |
| files | lib/gl_anyavltree_list1.h lib/gl_anyavltree_list2.h lib/gl_anyhash_list1.h lib/gl_anyhash_list2.h lib/gl_anylinked_list1.h lib/gl_anylinked_list2.h lib/gl_anyrbtree_list1.h lib/gl_anyrbtree_list2.h lib/gl_anytree_list1.h lib/gl_anytree_list2.h lib/gl_anytreehash_list1.h lib/gl_anytreehash_list2.h |
| diffstat | 12 files changed, 3937 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/lib/gl_anyavltree_list1.h @@ -0,0 +1,71 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_avltree_list.c and gl_avltreehash_list.c. */ + +/* 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_list_t Data Type -------------------------- */ + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ +#if WITH_HASHTABLE + struct gl_hash_entry h; /* hash table entry fields; must be first */ +#endif + struct gl_list_node_impl *left; /* left branch, or NULL */ + struct gl_list_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_list_node_t can be returned + without memory allocation, on which the functions gl_list_remove_node, + gl_list_add_before, gl_list_add_after can be implemented. */ + struct gl_list_node_impl *parent; + int balance; /* heightof(right) - heightof(left), + always = -1 or 0 or 1 */ + size_t branch_size; /* number of nodes in this branch, + = branchsize(left)+branchsize(right)+1 */ + const void *value; +}; + +/* Concrete gl_list_impl type, valid for this file only. */ +struct gl_list_impl +{ + struct gl_list_impl_base base; +#if WITH_HASHTABLE + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; +#endif + struct gl_list_node_impl *root; /* root node or NULL */ +}; + +/* An AVL tree of height h has at least F_(h+2) [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 elements, and because even on 64-bit machines, + sizeof (gl_list_node_impl) * F_87 > 2^64 + this would exceed the address space of the machine. */ +#define MAXHEIGHT 83
new file mode 100644 --- /dev/null +++ b/lib/gl_anyavltree_list2.h @@ -0,0 +1,750 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* 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. */ +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 *) xmalloc (sizeof (struct gl_list_node_impl)); + + if (half1 > 0) + { + node->left = create_subtree_with_contents (half1, contents); + 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); + 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; +} + +static gl_list_t +gl_tree_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_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); + list->table = + (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t)); + } +#endif + if (count > 0) + { + list->root = create_subtree_with_contents (count, contents); + 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. */ + add_nodes_to_buckets (list); +#endif + } + else + list->root = NULL; + + return list; +} + +/* 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 gl_list_node_t +gl_tree_add_first (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + 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(). */ + add_to_bucket (list, new_node); + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_add_last (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + 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(). */ + add_to_bucket (list, new_node); + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + bool height_inc; + + 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(). */ + add_to_bucket (list, new_node); + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + bool height_inc; + + 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(). */ + add_to_bucket (list, new_node); + hash_resize_after_add (list); +#endif + + return new_node; +} + +static bool +gl_tree_remove_node (gl_list_t list, gl_list_node_t node) +{ + gl_list_node_t parent; + +#if WITH_HASHTABLE + /* Remove node from the hash table. + Note that this is only possible _before_ the node is removed from the + tree structure, because remove_from_bucket() uses node_position(). */ + remove_from_bucket (list, node); +#endif + + 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); + } + + free (node); + return true; +}
new file mode 100644 --- /dev/null +++ b/lib/gl_anyhash_list1.h @@ -0,0 +1,28 @@ +/* Sequential list data type implemented by a hash table with another list. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of + gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c. */ + +/* Hash table entry. */ +struct gl_hash_entry +{ + struct gl_hash_entry *hash_next; /* chain of entries in same bucket */ + size_t hashcode; /* cache of values' common hash code */ +}; +typedef struct gl_hash_entry * gl_hash_entry_t;
new file mode 100644 --- /dev/null +++ b/lib/gl_anyhash_list2.h @@ -0,0 +1,128 @@ +/* Sequential list data type implemented by a hash table with another list. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of + gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c. */ + +/* Array of primes, approximately in steps of factor 1.2. + This table was computed by executing the Common Lisp expression + (dotimes (i 244) (format t "nextprime(~D)~%" (ceiling (expt 1.2d0 i)))) + and feeding the result to PARI/gp. */ +static const size_t primes[] = + { + 11, 13, 17, 19, 23, 29, 37, 41, 47, 59, 67, 83, 97, 127, 139, 167, 199, + 239, 293, 347, 419, 499, 593, 709, 853, 1021, 1229, 1471, 1777, 2129, 2543, + 3049, 3659, 4391, 5273, 6323, 7589, 9103, 10937, 13109, 15727, 18899, + 22651, 27179, 32609, 39133, 46957, 56359, 67619, 81157, 97369, 116849, + 140221, 168253, 201907, 242309, 290761, 348889, 418667, 502409, 602887, + 723467, 868151, 1041779, 1250141, 1500181, 1800191, 2160233, 2592277, + 3110741, 3732887, 4479463, 5375371, 6450413, 7740517, 9288589, 11146307, + 13375573, 16050689, 19260817, 23112977, 27735583, 33282701, 39939233, + 47927081, 57512503, 69014987, 82818011, 99381577, 119257891, 143109469, + 171731387, 206077643, 247293161, 296751781, 356102141, 427322587, + 512787097, 615344489, 738413383, 886096061, 1063315271, 1275978331, + 1531174013, 1837408799, 2204890543UL, 2645868653UL, 3175042391UL, + 3810050851UL, +#if SIZE_MAX > 4294967295UL + 4572061027UL, 5486473229UL, 6583767889UL, 7900521449UL, 9480625733UL, + 11376750877UL, 13652101063UL, 16382521261UL, 19659025513UL, 23590830631UL, + 28308996763UL, 33970796089UL, 40764955463UL, 48917946377UL, 58701535657UL, + 70441842749UL, 84530211301UL, 101436253561UL, 121723504277UL, + 146068205131UL, 175281846149UL, 210338215379UL, 252405858521UL, + 302887030151UL, 363464436191UL, 436157323417UL, 523388788231UL, + 628066545713UL, 753679854847UL, 904415825857UL, 1085298991109UL, + 1302358789181UL, 1562830547009UL, 1875396656429UL, 2250475987709UL, + 2700571185239UL, 3240685422287UL, 3888822506759UL, 4666587008147UL, + 5599904409713UL, 6719885291641UL, 8063862349969UL, 9676634819959UL, + 11611961783951UL, 13934354140769UL, 16721224968907UL, 20065469962669UL, + 24078563955191UL, 28894276746229UL, 34673132095507UL, 41607758514593UL, + 49929310217531UL, 59915172260971UL, 71898206713183UL, 86277848055823UL, + 103533417666967UL, 124240101200359UL, 149088121440451UL, 178905745728529UL, + 214686894874223UL, 257624273849081UL, 309149128618903UL, 370978954342639UL, + 445174745211143UL, 534209694253381UL, 641051633104063UL, 769261959724877UL, + 923114351670013UL, 1107737222003791UL, 1329284666404567UL, + 1595141599685509UL, 1914169919622551UL, 2297003903547091UL, + 2756404684256459UL, 3307685621107757UL, 3969222745329323UL, + 4763067294395177UL, 5715680753274209UL, 6858816903929113UL, + 8230580284714831UL, 9876696341657791UL, 11852035609989371UL, + 14222442731987227UL, 17066931278384657UL, 20480317534061597UL, + 24576381040873903UL, 29491657249048679UL, 35389988698858471UL, + 42467986438630267UL, 50961583726356109UL, 61153900471627387UL, + 73384680565952851UL, 88061616679143347UL, 105673940014972061UL, + 126808728017966413UL, 152170473621559703UL, 182604568345871671UL, + 219125482015045997UL, 262950578418055169UL, 315540694101666193UL, + 378648832921999397UL, 454378599506399233UL, 545254319407679131UL, + 654305183289214771UL, 785166219947057701UL, 942199463936469157UL, + 1130639356723763129UL, 1356767228068515623UL, 1628120673682218619UL, + 1953744808418662409UL, 2344493770102394881UL, 2813392524122873857UL, + 3376071028947448339UL, 4051285234736937517UL, 4861542281684325481UL, + 5833850738021191727UL, 7000620885625427969UL, 8400745062750513217UL, + 10080894075300616261UL, 12097072890360739951UL, 14516487468432885797UL, + 17419784962119465179UL, +#endif + SIZE_MAX /* sentinel, to ensure the search terminates */ + }; + +/* Return a suitable prime >= ESTIMATE. */ +static size_t +next_prime (size_t estimate) +{ + size_t i; + + for (i = 0; i < sizeof (primes) / sizeof (primes[0]); i++) + if (primes[i] >= estimate) + return primes[i]; + return SIZE_MAX; /* not a prime, but better than nothing */ +} + +/* Resize the hash table with a new estimated size. */ +static void +hash_resize (gl_list_t list, size_t estimate) +{ + size_t new_size = next_prime (estimate); + + if (new_size > list->table_size) + { + gl_hash_entry_t *old_table = list->table; + /* Allocate the new table. */ + gl_hash_entry_t *new_table = + (gl_hash_entry_t *) xzalloc (new_size * sizeof (gl_hash_entry_t)); + size_t i; + + /* Iterate through the entries of the old table. */ + for (i = list->table_size; i > 0; ) + { + gl_hash_entry_t node = old_table[--i]; + + while (node != NULL) + { + gl_hash_entry_t next = node->hash_next; + /* Add the entry to the new table. */ + size_t index = node->hashcode % new_size; + node->hash_next = new_table[index]; + new_table[index] = node; + + node = next; + } + } + + list->table = new_table; + list->table_size = new_size; + free (old_table); + } +}
new file mode 100644 --- /dev/null +++ b/lib/gl_anylinked_list1.h @@ -0,0 +1,49 @@ +/* Sequential list data type implemented by a linked list. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_linked_list.c and gl_linkedhash_list.c. */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ +#if WITH_HASHTABLE + struct gl_hash_entry h; /* hash table entry fields; must be first */ +#endif + struct gl_list_node_impl *next; + struct gl_list_node_impl *prev; + const void *value; +}; + +/* Concrete gl_list_impl type, valid for this file only. */ +struct gl_list_impl +{ + struct gl_list_impl_base base; +#if WITH_HASHTABLE + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; +#endif + /* A circular list anchored at root. + The first node is = root.next, the last node is = root.prev. + The root's value is unused. */ + struct gl_list_node_impl root; + /* Number of list nodes, excluding the root. */ + size_t count; +};
new file mode 100644 --- /dev/null +++ b/lib/gl_anylinked_list2.h @@ -0,0 +1,843 @@ +/* Sequential list data type implemented by a linked list. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_linked_list.c and gl_linkedhash_list.c. */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +static gl_list_t +gl_linked_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + bool allow_duplicates) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + list->table_size = 11; + list->table = + (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t)); +#endif + list->root.next = &list->root; + list->root.prev = &list->root; + list->count = 0; + + return list; +} + +static gl_list_t +gl_linked_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + gl_list_node_t tail; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_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); + list->table = + (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t)); + } +#endif + list->count = count; + tail = &list->root; + for (; count > 0; contents++, count--) + { + gl_list_node_t node = + (struct gl_list_node_impl *) + xmalloc (sizeof (struct gl_list_node_impl)); + + node->value = *contents; +#if WITH_HASHTABLE + node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (node->value) + : (size_t)(uintptr_t) node->value); + + /* Add node to the hash table. */ + add_to_bucket (list, node); +#endif + + /* Add node to the list. */ + node->prev = tail; + tail->next = node; + tail = node; + } + tail->next = &list->root; + list->root.prev = tail; + + return list; +} + +static size_t +gl_linked_size (gl_list_t list) +{ + return list->count; +} + +static const void * +gl_linked_node_value (gl_list_t list, gl_list_node_t node) +{ + return node->value; +} + +static gl_list_node_t +gl_linked_next_node (gl_list_t list, gl_list_node_t node) +{ + return (node->next != &list->root ? node->next : NULL); +} + +static gl_list_node_t +gl_linked_previous_node (gl_list_t list, gl_list_node_t node) +{ + return (node->prev != &list->root ? node->prev : NULL); +} + +static const void * +gl_linked_get_at (gl_list_t list, size_t position) +{ + size_t count = list->count; + gl_list_node_t node; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + /* Here we know count > 0. */ + if (position <= ((count - 1) / 2)) + { + node = list->root.next; + for (; position > 0; position--) + node = node->next; + } + else + { + position = count - 1 - position; + node = list->root.prev; + for (; position > 0; position--) + node = node->prev; + } + return node->value; +} + +static gl_list_node_t +gl_linked_set_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = list->count; + gl_list_node_t node; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + /* Here we know count > 0. */ + if (position <= ((count - 1) / 2)) + { + node = list->root.next; + for (; position > 0; position--) + node = node->next; + } + else + { + position = count - 1 - position; + node = list->root.prev; + for (; position > 0; position--) + node = node->prev; + } +#if WITH_HASHTABLE + if (elt != node->value) + { + size_t new_hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + + if (new_hashcode != node->h.hashcode) + { + remove_from_bucket (list, node); + node->value = elt; + node->h.hashcode = new_hashcode; + add_to_bucket (list, node); + } + else + node->value = elt; + } +#else + node->value = elt; +#endif + return node; +} + +static gl_list_node_t +gl_linked_search (gl_list_t list, const void *elt) +{ +#if WITH_HASHTABLE + size_t hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t index = hashcode % list->table_size; + gl_listelement_equals_fn equals = list->base.equals_fn; + + if (!list->base.allow_duplicates) + { + /* Look for the first match in the hash bucket. */ + gl_list_node_t node; + + for (node = (gl_list_node_t) list->table[index]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + return node; + return NULL; + } + else + { + /* Look whether there is more than one match in the hash bucket. */ + bool multiple_matches = false; + gl_list_node_t first_match = NULL; + gl_list_node_t node; + + for (node = (gl_list_node_t) list->table[index]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + { + if (first_match == NULL) + first_match = node; + else + { + multiple_matches = true; + break; + } + } + if (!multiple_matches) + return first_match; + else + { + /* We need the match with the smallest index. But we don't have + a fast mapping node -> index. So we have to walk the list. */ + for (node = list->root.next; node != &list->root; node = node->next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + return node; + /* We know there are at least two matches. */ + abort (); + } + } +#else + gl_listelement_equals_fn equals = list->base.equals_fn; + gl_list_node_t node; + + if (equals != NULL) + { + for (node = list->root.next; node != &list->root; node = node->next) + if (equals (elt, node->value)) + return node; + } + else + { + for (node = list->root.next; node != &list->root; node = node->next) + if (elt == node->value) + return node; + } + return NULL; +#endif +} + +static size_t +gl_linked_indexof (gl_list_t list, const void *elt) +{ +#if WITH_HASHTABLE + /* Here the hash table doesn't help much. It only allows us to minimize + the number of equals() calls, by looking up first the node and then + its index. */ + size_t hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t index = hashcode % list->table_size; + gl_listelement_equals_fn equals = list->base.equals_fn; + gl_list_node_t node; + + /* First step: Look up the node. */ + if (!list->base.allow_duplicates) + { + /* Look for the first match in the hash bucket. */ + for (node = (gl_list_node_t) list->table[index]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + break; + } + else + { + /* Look whether there is more than one match in the hash bucket. */ + bool multiple_matches = false; + gl_list_node_t first_match = NULL; + + for (node = (gl_list_node_t) list->table[index]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + { + if (first_match == NULL) + first_match = node; + else + { + multiple_matches = true; + break; + } + } + if (multiple_matches) + { + /* We need the match with the smallest index. But we don't have + a fast mapping node -> index. So we have to walk the list. */ + size_t index; + + for (node = list->root.next, index = 0; + node != &list->root; + node = node->next, index++) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + return index; + /* We know there are at least two matches. */ + abort (); + } + node = first_match; + } + + /* Second step: Look up the index of the node. */ + if (node == NULL) + return (size_t)(-1); + else + { + size_t index = 0; + + for (; node->prev != &list->root; node = node->prev) + index++; + + return index; + } +#else + gl_listelement_equals_fn equals = list->base.equals_fn; + gl_list_node_t node; + + if (equals != NULL) + { + size_t index; + for (node = list->root.next, index = 0; + node != &list->root; + node = node->next, index++) + if (equals (elt, node->value)) + return index; + } + else + { + size_t index; + for (node = list->root.next, index = 0; + node != &list->root; + node = node->next, index++) + if (elt == node->value) + return index; + } + return (size_t)(-1); +#endif +} + +static gl_list_node_t +gl_linked_add_first (gl_list_t list, const void *elt) +{ + gl_list_node_t node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + node->value = elt; +#if WITH_HASHTABLE + node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (node->value) + : (size_t)(uintptr_t) node->value); + + /* Add node to the hash table. */ + add_to_bucket (list, node); +#endif + + /* Add node to the list. */ + node->prev = &list->root; + node->next = list->root.next; + node->next->prev = node; + list->root.next = node; + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return node; +} + +static gl_list_node_t +gl_linked_add_last (gl_list_t list, const void *elt) +{ + gl_list_node_t node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + node->value = elt; +#if WITH_HASHTABLE + node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (node->value) + : (size_t)(uintptr_t) node->value); + + /* Add node to the hash table. */ + add_to_bucket (list, node); +#endif + + /* Add node to the list. */ + node->next = &list->root; + node->prev = list->root.prev; + node->prev->next = node; + list->root.prev = node; + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return node; +} + +static gl_list_node_t +gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + 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); + + /* Add new_node to the hash table. */ + add_to_bucket (list, new_node); +#endif + + /* Add new_node to the list. */ + new_node->next = node; + new_node->prev = node->prev; + new_node->prev->next = new_node; + node->prev = new_node; + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + 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); + + /* Add new_node to the hash table. */ + add_to_bucket (list, new_node); +#endif + + /* Add new_node to the list. */ + new_node->prev = node; + new_node->next = node->next; + new_node->next->prev = new_node; + node->next = new_node; + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_linked_add_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = list->count; + gl_list_node_t new_node; + + if (!(position <= count)) + /* Invalid argument. */ + abort (); + + new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + 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); + + /* Add new_node to the hash table. */ + add_to_bucket (list, new_node); +#endif + + /* Add new_node to the list. */ + if (position <= (count / 2)) + { + gl_list_node_t node; + + node = &list->root; + for (; position > 0; position--) + node = node->next; + new_node->prev = node; + new_node->next = node->next; + new_node->next->prev = new_node; + node->next = new_node; + } + else + { + gl_list_node_t node; + + position = count - position; + node = &list->root; + for (; position > 0; position--) + node = node->prev; + new_node->next = node; + new_node->prev = node->prev; + new_node->prev->next = new_node; + node->prev = new_node; + } + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return new_node; +} + +static bool +gl_linked_remove_node (gl_list_t list, gl_list_node_t node) +{ + gl_list_node_t prev; + gl_list_node_t next; + +#if WITH_HASHTABLE + /* Remove node from the hash table. */ + remove_from_bucket (list, node); +#endif + + /* Remove node from the list. */ + prev = node->prev; + next = node->next; + + prev->next = next; + next->prev = prev; + list->count--; + + free (node); + return true; +} + +static bool +gl_linked_remove_at (gl_list_t list, size_t position) +{ + size_t count = list->count; + gl_list_node_t removed_node; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + /* Here we know count > 0. */ + if (position <= ((count - 1) / 2)) + { + gl_list_node_t node; + gl_list_node_t after_removed; + + node = &list->root; + for (; position > 0; position--) + node = node->next; + removed_node = node->next; + after_removed = node->next->next; + node->next = after_removed; + after_removed->prev = node; + } + else + { + gl_list_node_t node; + gl_list_node_t before_removed; + + position = count - 1 - position; + node = &list->root; + for (; position > 0; position--) + node = node->prev; + removed_node = node->prev; + before_removed = node->prev->prev; + node->prev = before_removed; + before_removed->next = node; + } +#if WITH_HASHTABLE + remove_from_bucket (list, removed_node); +#endif + list->count--; + + free (removed_node); + return true; +} + +static bool +gl_linked_remove (gl_list_t list, const void *elt) +{ + gl_list_node_t node = gl_linked_search (list, elt); + + if (node != NULL) + return gl_linked_remove_node (list, node); + else + return false; +} + +static void +gl_linked_list_free (gl_list_t list) +{ + gl_list_node_t node; + + for (node = list->root.next; node != &list->root; ) + { + gl_list_node_t next = node->next; + free (node); + node = next; + } +#if WITH_HASHTABLE + free (list->table); +#endif + free (list); +} + +/* --------------------- gl_list_iterator_t Data Type --------------------- */ + +static gl_list_iterator_t +gl_linked_iterator (gl_list_t list) +{ + gl_list_iterator_t result; + + result.vtable = list->base.vtable; + result.list = list; + result.p = list->root.next; + result.q = &list->root; + + return result; +} + +static gl_list_iterator_t +gl_linked_iterator_from_to (gl_list_t list, + size_t start_index, size_t end_index) +{ + gl_list_iterator_t result; + size_t n1, n2, n3; + + if (!(start_index <= end_index && end_index <= list->count)) + /* Invalid arguments. */ + abort (); + result.vtable = list->base.vtable; + result.list = list; + n1 = start_index; + n2 = end_index - start_index; + n3 = list->count - end_index; + /* Find the maximum among n1, n2, n3, so as to reduce the number of + loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */ + if (n1 > n2 && n1 > n3) + { + /* n1 is the maximum, use n2 and n3. */ + gl_list_node_t node; + size_t i; + + node = &list->root; + for (i = n3; i > 0; i--) + node = node->prev; + result.q = node; + for (i = n2; i > 0; i--) + node = node->prev; + result.p = node; + } + else if (n2 > n3) + { + /* n2 is the maximum, use n1 and n3. */ + gl_list_node_t node; + size_t i; + + node = list->root.next; + for (i = n1; i > 0; i--) + node = node->next; + result.p = node; + + node = &list->root; + for (i = n3; i > 0; i--) + node = node->prev; + result.q = node; + } + else + { + /* n3 is the maximum, use n1 and n2. */ + gl_list_node_t node; + size_t i; + + node = list->root.next; + for (i = n1; i > 0; i--) + node = node->next; + result.p = node; + for (i = n2; i > 0; i--) + node = node->next; + result.q = node; + } + + return result; +} + +static bool +gl_linked_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep) +{ + if (iterator->p != iterator->q) + { + gl_list_node_t node = (gl_list_node_t) iterator->p; + *eltp = node->value; + if (nodep != NULL) + *nodep = node; + iterator->p = node->next; + return true; + } + else + return false; +} + +static void +gl_linked_iterator_free (gl_list_iterator_t *iterator) +{ +} + +/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ + +static gl_list_node_t +gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root.next; node != &list->root; node = node->next) + { + int cmp = compar (node->value, elt); + + if (cmp > 0) + break; + if (cmp == 0) + return node; + } + return NULL; +} + +static size_t +gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + size_t index; + + for (node = list->root.next, index = 0; + node != &list->root; + node = node->next, index++) + { + int cmp = compar (node->value, elt); + + if (cmp > 0) + break; + if (cmp == 0) + return index; + } + return (size_t)(-1); +} + +static gl_list_node_t +gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root.next; node != &list->root; node = node->next) + if (compar (node->value, elt) >= 0) + return gl_linked_add_before (list, node, elt); + return gl_linked_add_last (list, elt); +} + +static bool +gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root.next; node != &list->root; node = node->next) + { + int cmp = compar (node->value, elt); + + if (cmp > 0) + break; + if (cmp == 0) + return gl_linked_remove_node (list, node); + } + return false; +}
new file mode 100644 --- /dev/null +++ b/lib/gl_anyrbtree_list1.h @@ -0,0 +1,77 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ + +/* 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 + alternatingly black-red-black-red-...-black-red.) The height of the tree + therefore is >= bh, <= 2*bh. + */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Color of a node. */ +typedef enum color { BLACK, RED } color_t; + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ +#if WITH_HASHTABLE + struct gl_hash_entry h; /* hash table entry fields; must be first */ +#endif + struct gl_list_node_impl *left; /* left branch, or NULL */ + struct gl_list_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_list_node_t can be returned + without memory allocation, on which the functions gl_list_remove_node, + gl_list_add_before, gl_list_add_after can be implemented. */ + struct gl_list_node_impl *parent; + color_t color; /* node's color */ + size_t branch_size; /* number of nodes in this branch, + = branchsize(left)+branchsize(right)+1 */ + const void *value; +}; + +/* Concrete gl_list_impl type, valid for this file only. */ +struct gl_list_impl +{ + struct gl_list_impl_base base; +#if WITH_HASHTABLE + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; +#endif + struct gl_list_node_impl *root; /* root node or NULL */ +}; + +/* 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_list_node_impl) * (2^59 - 1) > 2^64 + this would exceed the address space of the machine. */ +#define MAXHEIGHT 116
new file mode 100644 --- /dev/null +++ b/lib/gl_anyrbtree_list2.h @@ -0,0 +1,971 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Create a subtree for count >= 1 elements. + Its black-height bh is passed as argument, with + 2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1. + Its height is h where 2^(h-1) <= count <= 2^h - 1. */ +static gl_list_node_t +create_subtree_with_contents (unsigned int bh, + 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 *) xmalloc (sizeof (struct gl_list_node_impl)); + + if (half1 > 0) + { + /* half1 > 0 implies count > 1, implies bh >= 1, implies + 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */ + node->left = + create_subtree_with_contents (bh - 1, half1, contents); + node->left->parent = node; + } + else + node->left = NULL; + + node->value = contents[half1]; + + if (half2 > 0) + { + /* half2 > 0 implies count > 1, implies bh >= 1, implies + 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */ + node->right = + create_subtree_with_contents (bh - 1, half2, contents + half1 + 1); + node->right->parent = node; + } + else + node->right = NULL; + + node->color = (bh == 0 ? RED : BLACK); + + node->branch_size = count; + + return node; +} + +static gl_list_t +gl_tree_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_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); + list->table = + (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t)); + } +#endif + if (count > 0) + { + /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose + upper bh levels are black, and only the partially present lowest + level is red. */ + unsigned int bh; + { + size_t n; + for (n = count + 1, bh = 0; n > 1; n = n >> 1) + bh++; + } + + list->root = create_subtree_with_contents (bh, count, contents); + 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. */ + add_nodes_to_buckets (list); +#endif + } + else + list->root = NULL; + + return list; +} + +/* 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 inline gl_list_node_t +rotate_left (gl_list_node_t b_node, gl_list_node_t d_node) +{ + gl_list_node_t a_node = b_node->left; + gl_list_node_t c_node = d_node->left; + gl_list_node_t e_node = d_node->right; + + 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; + + b_node->branch_size = + (a_node != NULL ? a_node->branch_size : 0) + + 1 + (c_node != NULL ? c_node->branch_size : 0); + d_node->branch_size = + b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0); + + 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 inline gl_list_node_t +rotate_right (gl_list_node_t b_node, gl_list_node_t d_node) +{ + gl_list_node_t a_node = b_node->left; + gl_list_node_t c_node = b_node->right; + gl_list_node_t e_node = d_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; + + d_node->branch_size = + (c_node != NULL ? c_node->branch_size : 0) + + 1 + (e_node != NULL ? e_node->branch_size : 0); + b_node->branch_size = + (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size; + + 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_list_t list, gl_list_node_t node, gl_list_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_list_node_t grandparent; + gl_list_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_list_node_t *grandparentp; + + if (grandparent->parent == NULL) + grandparentp = &list->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_list_t list, gl_list_node_t child, gl_list_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_list_node_t *parentp; + + if (parent->parent == NULL) + parentp = &list->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_list_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_list_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 gl_list_node_t +gl_tree_add_first (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + new_node->left = NULL; + new_node->right = NULL; + 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) + { + new_node->color = BLACK; + 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; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + } + +#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(). */ + add_to_bucket (list, new_node); + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_add_last (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + new_node->left = NULL; + new_node->right = NULL; + 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) + { + new_node->color = BLACK; + 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; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + } + +#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(). */ + add_to_bucket (list, new_node); + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + new_node->left = NULL; + new_node->right = NULL; + 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; + else + { + for (node = node->left; node->right != NULL; ) + node = node->right; + node->right = new_node; + } + 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++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + +#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(). */ + add_to_bucket (list, new_node); + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl)); + + new_node->left = NULL; + new_node->right = NULL; + 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; + else + { + for (node = node->right; node->left != NULL; ) + node = node->left; + node->left = new_node; + } + 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++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + +#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(). */ + add_to_bucket (list, new_node); + hash_resize_after_add (list); +#endif + + return new_node; +} + +static bool +gl_tree_remove_node (gl_list_t list, gl_list_node_t node) +{ + gl_list_node_t parent; + +#if WITH_HASHTABLE + /* Remove node from the hash table. + Note that this is only possible _before_ the node is removed from the + tree structure, because remove_from_bucket() uses node_position(). */ + remove_from_bucket (list, node); +#endif + + 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; + /* 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) + 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--; + } + + if (child == NULL && node->color == BLACK) + rebalance_after_remove (list, 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_list_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) + 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--; + } + } + } + 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; + 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; + } + + /* 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->color = node->color; + 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; + + 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 (list, child, + subst_parent != node ? subst_parent : subst); + } + } + + free (node); + return true; +}
new file mode 100644 --- /dev/null +++ b/lib/gl_anytree_list1.h @@ -0,0 +1,30 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_avltree_list.c, gl_rbtree_list.c, + gl_avltreehash_list.c, gl_rbtreehash_list.c. */ + +/* An item on the stack used for iterating across the elements. */ +typedef struct +{ + gl_list_node_t node; + bool rightp; +} iterstack_item_t; + +/* A stack used for iterating across the elements. */ +typedef iterstack_item_t iterstack_t[MAXHEIGHT];
new file mode 100644 --- /dev/null +++ b/lib/gl_anytree_list2.h @@ -0,0 +1,547 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_avltree_list.c, gl_rbtree_list.c, + gl_avltreehash_list.c, gl_rbtreehash_list.c. */ + +static gl_list_t +gl_tree_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + bool allow_duplicates) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + list->table_size = 11; + list->table = + (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t)); +#endif + list->root = NULL; + + return list; +} + +static size_t +gl_tree_size (gl_list_t list) +{ + return (list->root != NULL ? list->root->branch_size : 0); +} + +static const void * +gl_tree_node_value (gl_list_t list, gl_list_node_t node) +{ + return node->value; +} + +static gl_list_node_t +gl_tree_next_node (gl_list_t list, gl_list_node_t 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; + } + return node; +} + +static gl_list_node_t +gl_tree_previous_node (gl_list_t list, gl_list_node_t node) +{ + if (node->left != NULL) + { + node = node->left; + while (node->right != NULL) + node = node->right; + } + else + { + while (node->parent != NULL && node->parent->left == node) + node = node->parent; + node = node->parent; + } + return node; +} + +/* Return the node at the given position < gl_tree_size (list). */ +static inline gl_list_node_t +node_at (gl_list_node_t root, size_t position) +{ + /* Here we know that root != NULL. */ + gl_list_node_t node = root; + + for (;;) + { + if (node->left != NULL) + { + if (position < node->left->branch_size) + { + node = node->left; + continue; + } + position -= node->left->branch_size; + } + if (position == 0) + break; + position--; + node = node->right; + } + return node; +} + +static const void * +gl_tree_get_at (gl_list_t list, size_t position) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); + return node->value; +} + +static gl_list_node_t +gl_tree_set_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); +#if WITH_HASHTABLE + if (elt != node->value) + { + size_t new_hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + + if (new_hashcode != node->h.hashcode) + { + remove_from_bucket (list, node); + node->value = elt; + node->h.hashcode = new_hashcode; + add_to_bucket (list, node); + } + else + node->value = elt; + } +#else + node->value = elt; +#endif + return node; +} + +#if !WITH_HASHTABLE + +static gl_list_node_t +gl_tree_search (gl_list_t list, const void *elt) +{ + gl_listelement_equals_fn equals = list->base.equals_fn; + /* Iterate across all elements. */ + gl_list_node_t node = list->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]) + return NULL; + stack_ptr--; + if (!stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return node; + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } +} + +static size_t +gl_tree_indexof (gl_list_t list, const void *elt) +{ + gl_listelement_equals_fn equals = list->base.equals_fn; + /* Iterate across all elements. */ + gl_list_node_t node = list->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + size_t index = 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]) + return (size_t)(-1); + stack_ptr--; + if (!stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return index; + index++; + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } +} + +#endif + +static gl_list_node_t +gl_tree_add_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = (list->root != NULL ? list->root->branch_size : 0); + + if (!(position <= count)) + /* Invalid argument. */ + abort (); + if (position == count) + return gl_tree_add_last (list, elt); + else + return gl_tree_add_before (list, node_at (list->root, position), elt); +} + +static bool +gl_tree_remove_at (gl_list_t list, size_t position) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); + return gl_tree_remove_node (list, node); +} + +static bool +gl_tree_remove (gl_list_t list, const void *elt) +{ + gl_list_node_t node = gl_tree_search (list, elt); + + if (node != NULL) + return gl_tree_remove_node (list, node); + else + return false; +} + +#if !WITH_HASHTABLE + +static void +gl_tree_list_free (gl_list_t list) +{ + /* Iterate across all elements in post-order. */ + gl_list_node_t node = list->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. */ + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + done_iterate: + free (list); +} + +#endif + +/* --------------------- gl_list_iterator_t Data Type --------------------- */ + +static gl_list_iterator_t +gl_tree_iterator (gl_list_t list) +{ + gl_list_iterator_t result; + gl_list_node_t node; + + result.vtable = list->base.vtable; + result.list = list; + /* Start node is the leftmost node. */ + node = list->root; + if (node != NULL) + while (node->left != NULL) + node = node->left; + result.p = node; + /* End point is past the rightmost node. */ + result.q = NULL; + + return result; +} + +static gl_list_iterator_t +gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) +{ + size_t count = (list->root != NULL ? list->root->branch_size : 0); + gl_list_iterator_t result; + + if (!(start_index <= end_index && end_index <= count)) + /* Invalid arguments. */ + abort (); + result.vtable = list->base.vtable; + result.list = list; + /* Start node is the node at position start_index. */ + result.p = (start_index < count ? node_at (list->root, start_index) : NULL); + /* End point is the node at position end_index. */ + result.q = (end_index < count ? node_at (list->root, end_index) : NULL); + + return result; +} + +static bool +gl_tree_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep) +{ + if (iterator->p != iterator->q) + { + gl_list_node_t node = (gl_list_node_t) iterator->p; + *eltp = node->value; + if (nodep != NULL) + *nodep = node; + /* 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_list_iterator_t *iterator) +{ +} + +/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ + +static gl_list_node_t +gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root; node != NULL; ) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost such + element. */ + gl_list_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + node = node->right; + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found = node; + node = node->left; + } + } + return found; + } + } + return NULL; +} + +static size_t +gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + size_t position; + + for (node = list->root, position = 0; node != NULL; ) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + if (node->left != NULL) + position += node->left->branch_size; + position++; + node = node->right; + } + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost such + element. */ + size_t found_position = + position + (node->left != NULL ? node->left->branch_size : 0); + node = node->left; + for (; node != NULL; ) + { + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + if (node->left != NULL) + position += node->left->branch_size; + position++; + node = node->right; + } + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found_position = + position + + (node->left != NULL ? node->left->branch_size : 0); + node = node->left; + } + } + return found_position; + } + } + return (size_t)(-1); +} + +static gl_list_node_t +gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node = list->root; + + if (node == NULL) + return gl_tree_add_first (list, elt); + + for (;;) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + if (node->right == NULL) + return gl_tree_add_after (list, node, elt); + node = node->right; + } + else if (cmp > 0) + { + if (node->left == NULL) + return gl_tree_add_before (list, node, elt); + node = node->left; + } + else /* cmp == 0 */ + return gl_tree_add_before (list, node, elt); + } +} + +static bool +gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt); + if (node != NULL) + return gl_tree_remove_node (list, node); + else + return false; +}
new file mode 100644 --- /dev/null +++ b/lib/gl_anytreehash_list1.h @@ -0,0 +1,291 @@ +/* Sequential list data type implemented by a hash table with a binary tree. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */ + +/* Hash table entry representing the same value at more than one position. */ +struct gl_multiple_nodes +{ + struct gl_hash_entry h; /* hash table entry fields; must be first */ + void *magic; /* used to distinguish from single node */ + gl_oset_t nodes; /* set of nodes, sorted by position */ +}; +/* A value that cannot occur at the corresponding field (->left) in + gl_list_node_impl. */ +#define MULTIPLE_NODES_MAGIC (void *) -1 + +/* Resize the hash table if needed, after list->count was incremented. */ +static inline void +hash_resize_after_add (gl_list_t list) +{ + size_t count = (list->root != 0 ? list->root->branch_size : 0); + size_t estimate = xsum (count, count / 2); /* 1.5 * count */ + if (estimate > list->table_size) + hash_resize (list, estimate); +} + +/* Return the position of the given node in the tree. */ +static size_t +node_position (gl_list_node_t node) +{ + size_t position = 0; + + if (node->left != NULL) + position += node->left->branch_size; + for (;;) + { + gl_list_node_t parent = node->parent; + + if (parent == NULL) + return position; + /* position is now relative to the subtree of node. */ + if (parent->right == node) + { + position += 1; + if (parent->left != NULL) + position += parent->left->branch_size; + } + /* position is now relative to the subtree of parent. */ + node = parent; + } +} + +/* Compares two nodes by their position in the tree. */ +static int +compare_by_position (const void *x1, const void *x2) +{ + gl_list_node_t node1 = (gl_list_node_t) x1; + gl_list_node_t node2 = (gl_list_node_t) x2; + size_t position1 = node_position (node1); + size_t position2 = node_position (node2); + + return (position1 > position2 ? 1 : + position1 < position2 ? -1 : 0); +} + +/* Return the first element of a non-empty ordered set of nodes. */ +static inline gl_list_node_t +gl_oset_first (gl_oset_t set) +{ + gl_oset_iterator_t iter = gl_oset_iterator (set); + const void *first; + + if (!gl_oset_iterator_next (&iter, &first)) + abort (); + gl_oset_iterator_free (&iter); + return (gl_list_node_t) first; +} + +/* Add a node to the hash table structure. + If duplicates are allowed, this function performs in average time + O((log n)^2): gl_oset_add may need to add an element to an ordered set of + size O(n), needing O(log n) comparison function calls. The comparison + function is compare_by_position, which is O(log n) worst-case. + If duplicates are forbidden, this function is O(1). */ +static void +add_to_bucket (gl_list_t list, gl_list_node_t new_node) +{ + size_t index = new_node->h.hashcode % list->table_size; + + /* If no duplicates are allowed, multiple nodes are not needed. */ + if (list->base.allow_duplicates) + { + size_t hashcode = new_node->h.hashcode; + const void *value = new_node->value; + gl_listelement_equals_fn equals = list->base.equals_fn; + gl_hash_entry_t *entryp; + + for (entryp = &list->table[index]; *entryp != NULL; entryp = &(*entryp)->hash_next) + { + gl_hash_entry_t entry = *entryp; + + if (entry->hashcode == hashcode) + { + if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) + { + /* An entry representing multiple nodes. */ + gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; + /* Only the first node is interesting. */ + gl_list_node_t node = gl_oset_first (nodes); + if (equals != NULL ? equals (value, node->value) : value == node->value) + { + /* Found already multiple nodes with the same value. + Add the new_node to it. */ + gl_oset_add (nodes, new_node); + return; + } + } + else + { + /* An entry representing a single node. */ + gl_list_node_t node = (struct gl_list_node_impl *) entry; + if (equals != NULL ? equals (value, node->value) : value == node->value) + { + /* Found already a node with the same value. Turn it + into an ordered set, and add new_node to it. */ + gl_oset_t nodes; + struct gl_multiple_nodes *multi_entry; + + nodes = + gl_oset_create_empty (OSET_TREE_FLAVOR, + compare_by_position); + + gl_oset_add (nodes, node); + gl_oset_add (nodes, new_node); + + multi_entry = + (struct gl_multiple_nodes *) xmalloc (sizeof (struct gl_multiple_nodes)); + multi_entry->h.hash_next = entry->hash_next; + multi_entry->h.hashcode = entry->hashcode; + multi_entry->magic = MULTIPLE_NODES_MAGIC; + multi_entry->nodes = nodes; + *entryp = &multi_entry->h; + return; + } + } + } + } + } + /* If no duplicates are allowed, multiple nodes are not needed. */ + new_node->h.hash_next = list->table[index]; + list->table[index] = &new_node->h; +} + +/* Remove a node from the hash table structure. + If duplicates are allowed, this function performs in average time + O((log n)^2): gl_oset_remove may need to remove an element from an ordered + set of size O(n), needing O(log n) comparison function calls. The + comparison function is compare_by_position, which is O(log n) worst-case. + If duplicates are forbidden, this function is O(1) on average. */ +static void +remove_from_bucket (gl_list_t list, gl_list_node_t old_node) +{ + size_t index = old_node->h.hashcode % list->table_size; + + if (list->base.allow_duplicates) + { + size_t hashcode = old_node->h.hashcode; + const void *value = old_node->value; + gl_listelement_equals_fn equals = list->base.equals_fn; + gl_hash_entry_t *entryp; + + for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next) + { + gl_hash_entry_t entry = *entryp; + + if (entry == &old_node->h) + { + /* Found old_node as a single node in the bucket. Remove it. */ + *entryp = old_node->h.hash_next; + break; + } + if (entry == NULL) + /* node is not in the right bucket. Did the hash codes + change inadvertently? */ + abort (); + if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC + && entry->hashcode == hashcode) + { + /* An entry representing multiple nodes. */ + gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; + /* Only the first node is interesting. */ + gl_list_node_t node = gl_oset_first (nodes); + if (equals != NULL ? equals (value, node->value) : value == node->value) + { + /* Found multiple nodes with the same value. + old_node must be one of them. Remove it. */ + if (!gl_oset_remove (nodes, old_node)) + abort (); + if (gl_oset_size (nodes) == 1) + { + /* Replace a one-element set with a single node. */ + node = gl_oset_first (nodes); + node->h.hash_next = entry->hash_next; + *entryp = &node->h; + gl_oset_free (nodes); + free (entry); + } + break; + } + } + } + } + else + { + /* If no duplicates are allowed, multiple nodes are not needed. */ + gl_hash_entry_t *entryp; + + for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next) + { + if (*entryp == &old_node->h) + { + *entryp = old_node->h.hash_next; + break; + } + if (*entryp == NULL) + /* node is not in the right bucket. Did the hash codes + change inadvertently? */ + abort (); + } + } +} + +/* Build up the hash table during initialization: Store all the nodes of + list->root in the hash table. */ +static inline void +add_nodes_to_buckets (gl_list_t list) +{ + /* Iterate across all nodes. */ + gl_list_node_t node = list->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]) + return; + stack_ptr--; + if (!stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Add the current node to the hash table. */ + node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (node->value) + : (size_t)(uintptr_t) node->value); + add_to_bucket (list, node); + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } +}
new file mode 100644 --- /dev/null +++ b/lib/gl_anytreehash_list2.h @@ -0,0 +1,152 @@ +/* Sequential list data type implemented by a hash table with a binary tree. + Copyright (C) 2006 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */ + +static gl_list_node_t +gl_tree_search (gl_list_t list, const void *elt) +{ + size_t hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t index = hashcode % list->table_size; + gl_listelement_equals_fn equals = list->base.equals_fn; + gl_hash_entry_t entry; + + if (list->base.allow_duplicates) + { + for (entry = list->table[index]; entry != NULL; entry = entry->hash_next) + if (entry->hashcode == hashcode) + { + if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) + { + /* An entry representing multiple nodes. */ + gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; + /* Only the first node is interesting. */ + gl_list_node_t node = gl_oset_first (nodes); + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + /* All nodes in the entry are equal to the given ELT. + But we have to return only the one at the minimal position, + and this is the first one in the ordered set. */ + return node; + } + else + { + /* An entry representing a single node. */ + gl_list_node_t node = (struct gl_list_node_impl *) entry; + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return node; + } + } + } + else + { + /* If no duplicates are allowed, multiple nodes are not needed. */ + for (entry = list->table[index]; entry != NULL; entry = entry->hash_next) + if (entry->hashcode == hashcode) + { + gl_list_node_t node = (struct gl_list_node_impl *) entry; + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return node; + } + } + + return NULL; +} + +static size_t +gl_tree_indexof (gl_list_t list, const void *elt) +{ + gl_list_node_t node = gl_tree_search (list, elt); + + if (node != NULL) + return node_position (node); + else + return (size_t)(-1); +} + +static void +gl_tree_list_free (gl_list_t list) +{ + if (list->base.allow_duplicates) + { + /* Free the ordered sets in the hash buckets. */ + size_t i; + + for (i = list->table_size; i > 0; ) + { + gl_hash_entry_t entry = list->table[--i]; + + while (entry != NULL) + { + gl_hash_entry_t next = entry->hash_next; + + if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) + { + gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; + + gl_oset_free (nodes); + free (entry); + } + + entry = next; + } + } + } + + /* Iterate across all elements in post-order. */ + { + gl_list_node_t node = list->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. */ + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + } + done_iterate: + free (list->table); + free (list); +}