/* 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-2014 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 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
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 <http://www.gnu.org/licenses/>. */
/* 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);
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. */
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:
projects / gnulib.git / blobdiff