X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytree_list2.h;h=143348eda16ee006be21cad385acfe2135997e3a;hb=1a2869593e115e4a6c74aaa0b23ca612357403ce;hp=a0154596d7957cbcc8c0ae6b6734c15b22d15b6b;hpb=a42a50dc6f5c48c557920c21c8f05d31f26fea73;p=gnulib.git diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h index a0154596d..143348eda 100644 --- a/lib/gl_anytree_list2.h +++ b/lib/gl_anytree_list2.h @@ -1,11 +1,11 @@ /* Sequential list data type implemented by a binary tree. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2008 Free Software Foundation, Inc. Written by Bruno Haible , 2006. - This program is free software; you can redistribute it and/or modify + 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. + 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 @@ -13,8 +13,7 @@ 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. */ + along with this program. If not, see . */ /* Common code of gl_avltree_list.c, gl_rbtree_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c. */ @@ -23,19 +22,19 @@ 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, + gl_listelement_dispose_fn dispose_fn, bool allow_duplicates) { - struct gl_list_impl *list = - (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl)); + struct gl_list_impl *list = XMALLOC (struct gl_list_impl); list->base.vtable = implementation; list->base.equals_fn = equals_fn; list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; list->base.allow_duplicates = allow_duplicates; #if WITH_HASHTABLE list->table_size = 11; - list->table = - (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t)); + list->table = XCALLOC (list->table_size, gl_hash_entry_t); #endif list->root = NULL; @@ -54,6 +53,32 @@ gl_tree_node_value (gl_list_t list, gl_list_node_t node) return node->value; } +static void +gl_tree_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +{ +#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 +} + static gl_list_node_t gl_tree_next_node (gl_list_t list, gl_list_node_t node) { @@ -164,87 +189,225 @@ gl_tree_set_at (gl_list_t list, size_t position, const void *elt) #if !WITH_HASHTABLE static gl_list_node_t -gl_tree_search (gl_list_t list, const void *elt) +gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index, + 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++; - } + if (!(start_index <= end_index + && end_index <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + { + 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; + + if (start_index == 0) + { + /* Consider all elements. */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + 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; + index++; + if (index >= end_index) + return NULL; + /* Descend on right branch. */ + stack_ptr->rightp = 1; + node = node->right; + stack_ptr++; + } + } + else + { + /* Consider only elements at indices >= start_index. + In this case, rightp contains the difference between the start_index + for the parent node and the one for the child node (0 when the child + node is the parent's left child, > 0 when the child is the parent's + right child). */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + if (node->branch_size <= start_index) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return NULL; + stack_ptr--; + if (!stack_ptr->rightp) + break; + start_index += stack_ptr->rightp; + } + node = stack_ptr->node; + { + size_t left_branch_size1 = + (node->left != NULL ? node->left->branch_size : 0) + 1; + if (start_index < left_branch_size1) + { + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return node; + /* Now that we have considered all indices < left_branch_size1, + we can increment start_index. */ + start_index = left_branch_size1; + } + index++; + if (index >= end_index) + return NULL; + /* Descend on right branch. */ + start_index -= left_branch_size1; + stack_ptr->rightp = left_branch_size1; + } + node = node->right; + stack_ptr++; + } + } + } } static size_t -gl_tree_indexof (gl_list_t list, const void *elt) +gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, + 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++; - } + if (!(start_index <= end_index + && end_index <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + { + 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; + + if (start_index == 0) + { + /* Consider all elements. */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + 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++; + if (index >= end_index) + return (size_t)(-1); + /* Descend on right branch. */ + stack_ptr->rightp = 1; + node = node->right; + stack_ptr++; + } + } + else + { + /* Consider only elements at indices >= start_index. + In this case, rightp contains the difference between the start_index + for the parent node and the one for the child node (0 when the child + node is the parent's left child, > 0 when the child is the parent's + right child). */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + if (node->branch_size <= start_index) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + 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; + start_index += stack_ptr->rightp; + } + node = stack_ptr->node; + { + size_t left_branch_size1 = + (node->left != NULL ? node->left->branch_size : 0) + 1; + if (start_index < left_branch_size1) + { + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return index; + /* Now that we have considered all indices < left_branch_size1, + we can increment start_index. */ + start_index = left_branch_size1; + } + index++; + if (index >= end_index) + return (size_t)(-1); + /* Descend on right branch. */ + start_index -= left_branch_size1; + stack_ptr->rightp = left_branch_size1; + } + node = node->right; + stack_ptr++; + } + } + } } #endif @@ -278,12 +441,15 @@ gl_tree_remove_at (gl_list_t list, size_t position) static bool gl_tree_remove (gl_list_t list, const void *elt) { - gl_list_node_t node = gl_tree_search (list, elt); + if (list->root != NULL) + { + gl_list_node_t node = + gl_tree_search_from_to (list, 0, list->root->branch_size, elt); - if (node != NULL) - return gl_tree_remove_node (list, node); - else - return false; + if (node != NULL) + return gl_tree_remove_node (list, node); + } + return false; } #if !WITH_HASHTABLE @@ -318,6 +484,8 @@ gl_tree_list_free (gl_list_t list) if (!stack_ptr->rightp) break; /* Free the current node. */ + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); free (node); } /* Descend on right branch. */ @@ -460,6 +628,88 @@ gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, return NULL; } +static gl_list_node_t +gl_tree_sortedlist_search_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + gl_list_node_t node; + + if (!(low <= high + && high <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + + for (node = list->root; node != NULL; ) + { + size_t left_branch_size = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size) + { + low -= left_branch_size + 1; + high -= left_branch_size + 1; + node = node->right; + } + else if (high <= left_branch_size) + node = node->left; + else + { + /* Here low <= left_branch_size < high. */ + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + low = 0; + high -= left_branch_size + 1; + 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; ) + { + size_t left_branch_size2 = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size2) + { + low -= left_branch_size2 + 1; + node = node->right; + } + else + { + /* Here low <= left_branch_size2. */ + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + low = 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) @@ -515,6 +765,92 @@ gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, return (size_t)(-1); } +static size_t +gl_tree_sortedlist_indexof_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + gl_list_node_t node; + size_t position; + + if (!(low <= high + && high <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + + for (node = list->root, position = 0; node != NULL; ) + { + size_t left_branch_size = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size) + { + low -= left_branch_size + 1; + high -= left_branch_size + 1; + position += left_branch_size + 1; + node = node->right; + } + else if (high <= left_branch_size) + node = node->left; + else + { + /* Here low <= left_branch_size < high. */ + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + low = 0; + high -= left_branch_size + 1; + position += left_branch_size + 1; + 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; ) + { + size_t left_branch_size2 = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size2) + { + low -= left_branch_size2 + 1; + node = node->right; + } + else + { + /* Here low <= left_branch_size2. */ + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + position += left_branch_size2 + 1; + node = node->right; + } + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found_position = position + left_branch_size2; + 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)