diff options
Diffstat (limited to 'lib/gl_anytree_list2.h')
-rw-r--r-- | lib/gl_anytree_list2.h | 547 |
1 files changed, 547 insertions, 0 deletions
diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h new file mode 100644 index 0000000000..19ecae5f70 --- /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; +} |