diff options
Diffstat (limited to 'gnulib/lib/gl_anytreehash_list1.h')
| m--------- | gnulib | 0 | ||||
| -rw-r--r-- | gnulib/lib/gl_anytreehash_list1.h | 358 |
2 files changed, 358 insertions, 0 deletions
diff --git a/gnulib b/gnulib deleted file mode 160000 -Subproject 443bc5ffcf7429e557f4a371b0661abe98ddbc1 diff --git a/gnulib/lib/gl_anytreehash_list1.h b/gnulib/lib/gl_anytreehash_list1.h new file mode 100644 index 0000000..d3b8a06 --- /dev/null +++ b/gnulib/lib/gl_anytreehash_list1.h @@ -0,0 +1,358 @@ +/* Sequential list data type implemented by a hash table with a binary tree. + Copyright (C) 2006-2007, 2009-2011 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +/* Common code of gl_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); +} + +/* Compares a node's position in the tree with a given threshold. */ +static bool +compare_position_threshold (const void *x, const void *threshold) +{ + gl_list_node_t node = (gl_list_node_t) x; + size_t position = node_position (node); + return (position >= (uintptr_t)threshold); +} + +/* 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_nx_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). + Return 0 upon success, -1 upon out-of-memory. */ +static int +add_to_bucket (gl_list_t list, gl_list_node_t new_node) +{ + size_t bucket = 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[bucket]; *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. */ + return gl_oset_nx_add (nodes, new_node); + } + } + 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_nx_create_empty (OSET_TREE_FLAVOR, + compare_by_position, NULL); + if (nodes == NULL) + return -1; + + if (gl_oset_nx_add (nodes, node) < 0) + goto fail; + if (gl_oset_nx_add (nodes, new_node) < 0) + goto fail; + + multi_entry = + (struct gl_multiple_nodes *) malloc (sizeof (struct gl_multiple_nodes)); + if (multi_entry == NULL) + goto fail; + 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 0; + + fail: + gl_oset_free (nodes); + return -1; + } + } + } + } + } + /* If no duplicates are allowed, multiple nodes are not needed. */ + new_node->h.hash_next = list->table[bucket]; + list->table[bucket] = &new_node->h; + return 0; +} +/* Tell GCC that the likely return value is 0. */ +#if __GNUC__ >= 3 +# define add_to_bucket(list,node) \ + __builtin_expect ((add_to_bucket) (list, node), 0) +#endif + +/* 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 bucket = 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[bucket]; ; 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[bucket]; ; 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. + Return 0 upon success, -1 upon out-of-memory. */ +static inline int +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]) + goto done; + 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); + if (add_to_bucket (list, node) < 0) + goto fail; + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + done: + return 0; + + fail: + /* Undo everything. */ + for (;;) + { + /* Descend on left branch. */ + stack_ptr->rightp = false; + node = node->left; + stack_ptr++; + /* Descend on right branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + goto fail_done; + stack_ptr--; + if (stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Remove the current node from the hash table. */ + remove_from_bucket (list, node); + } + fail_done: + return -1; +} +/* Tell GCC that the likely return value is 0. */ +#if __GNUC__ >= 3 +# define add_nodes_to_buckets(list) \ + __builtin_expect ((add_nodes_to_buckets) (list), 0) +#endif |