X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytree_list2.h;h=143348eda16ee006be21cad385acfe2135997e3a;hb=3aa0d4da24ba7b52282b1d124b4118e4e8a46a2b;hp=00b285bdca3f4e315aa057145e4fc4df8cfa786d;hpb=407400d9367b16a628b57b2d9b8565bb5a08ffae;p=gnulib.git diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h index 00b285bdc..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) { @@ -459,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. */ @@ -601,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) @@ -656,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)