X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytreehash_list2.h;h=4e22bb7c07ff3632e304ac940bc08a691e54bcf2;hb=3cdd75d6d78830ecc5633df781baaf2be2c4a7e9;hp=10fbe109d4fcd94fdf9739f39df3d20b8018767b;hpb=0a51cf1590113188ff1dc78dc79d2924c262a865;p=gnulib.git diff --git a/lib/gl_anytreehash_list2.h b/lib/gl_anytreehash_list2.h index 10fbe109d..4e22bb7c0 100644 --- a/lib/gl_anytreehash_list2.h +++ b/lib/gl_anytreehash_list2.h @@ -1,11 +1,11 @@ /* Sequential list data type implemented by a hash table with a binary tree. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2007 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,67 +13,126 @@ 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_avltreehash_list.c and gl_rbtreehash_list.c. */ 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) { - 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; - } - } + if (!(start_index <= end_index + && end_index <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + { + size_t hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = 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[bucket]; 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; + /* 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. */ + if (start_index == 0) + { + /* We have to return only the one at the minimal + position, and this is the first one in the ordered + set. */ + if (end_index == list->root->branch_size + || node_position (node) < end_index) + return node; + } + else + { + /* We have to return only the one at the minimal + position >= start_index. */ + const void *elt; + if (gl_oset_search_atleast (nodes, + compare_position_threshold, + (void *)(uintptr_t)start_index, + &elt)) + { + node = (gl_list_node_t) elt; + if (end_index == list->root->branch_size + || node_position (node) < end_index) + return node; + } + } + break; + } + } + 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) + { + bool position_in_bounds; + if (start_index == 0 && end_index == list->root->branch_size) + position_in_bounds = true; + else + { + size_t position = node_position (node); + position_in_bounds = + (position >= start_index && position < end_index); + } + if (position_in_bounds) + return node; + break; + } + } + } + } + else + { + /* If no duplicates are allowed, multiple nodes are not needed. */ + for (entry = list->table[bucket]; 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) + { + bool position_in_bounds; + if (start_index == 0 && end_index == list->root->branch_size) + position_in_bounds = true; + else + { + size_t position = node_position (node); + position_in_bounds = + (position >= start_index && position < end_index); + } + if (position_in_bounds) + return node; + break; + } + } + } - return NULL; + return NULL; + } } 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_list_node_t node = gl_tree_search (list, elt); + gl_list_node_t node = + gl_tree_search_from_to (list, start_index, end_index, elt); if (node != NULL) return node_position (node); @@ -138,6 +197,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. */