X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytreehash_list2.h;h=d2cb1e607a8d24fc7cba7d117ac8e0aa5291a66a;hb=2726ca8984e8d2d8edf288b4d1d7007bfca0d82e;hp=10fbe109d4fcd94fdf9739f39df3d20b8018767b;hpb=0a51cf1590113188ff1dc78dc79d2924c262a865;p=gnulib.git diff --git a/lib/gl_anytreehash_list2.h b/lib/gl_anytreehash_list2.h index 10fbe109d..d2cb1e607 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, 2009-2011 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); @@ -90,24 +149,24 @@ gl_tree_list_free (gl_list_t list) size_t i; for (i = list->table_size; i > 0; ) - { - gl_hash_entry_t entry = list->table[--i]; + { + gl_hash_entry_t entry = list->table[--i]; - while (entry != NULL) - { - gl_hash_entry_t next = entry->hash_next; + while (entry != NULL) + { + gl_hash_entry_t next = entry->hash_next; - if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) - { - gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; + if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC) + { + gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes; - gl_oset_free (nodes); - free (entry); - } + gl_oset_free (nodes); + free (entry); + } - entry = next; - } - } + entry = next; + } + } } /* Iterate across all elements in post-order. */ @@ -118,32 +177,34 @@ gl_tree_list_free (gl_list_t list) 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++; + /* 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. */ + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; } } done_iterate: