+2006-10-03 Bruno Haible <bruno@clisp.org>
+
+ * gl_list.h (gl_list_search_from, gl_list_search_from_to,
+ gl_list_indexof_from, gl_list_indexof_from_to): New declarations.
+ (struct gl_list_implementation): Add fields search_from_to,
+ indexof_from_to. Remove fields search, indexof.
+ (gl_list_search): Use the search_from_to method.
+ (gl_list_search_from, gl_list_search_from_to): New functions.
+ (gl_list_indexof): Use the indexof_from_to method.
+ (gl_list_indexof_from, gl_list_indexof_from_to): New functions.
+ * gl_list.c (gl_list_search): Use the search_from_to method.
+ (gl_list_search_from, gl_list_search_from_to): New functions.
+ (gl_list_indexof): Use the indexof_from_to method.
+ (gl_list_indexof_from, gl_list_indexof_from_to): New functions.
+ * gl_array_list.c (gl_array_indexof_from_to): Renamed from
+ gl_array_indexof. Add start_index, end_index arguments.
+ (gl_array_search_from_to): Renamed from gl_array_search. Add
+ start_index, end_index arguments.
+ (gl_array_remove, gl_array_list_implementation): Update.
+ * gl_carray_list.c (gl_carray_indexof_from_to): Renamed from
+ gl_carray_indexof. Add start_index, end_index arguments.
+ (gl_carray_search_from_to): Renamed from gl_carray_search. Add
+ start_index, end_index arguments.
+ (gl_carray_remove, gl_carray_list_implementation): Update.
+ * gl_anylinked_list2.h (gl_linked_search_from_to): Renamed from
+ gl_linked_search. Add start_index, end_index arguments.
+ (gl_linked_indexof_from_to): Renamed from gl_linked_indexof. Add
+ start_index, end_index arguments.
+ (gl_linked_remove): Update.
+ * gl_linked_list.c (gl_linked_list_implementation): Update.
+ * gl_linkedhash_list.c (gl_linkedhash_list_implementation): Update.
+ * gl_anytree_list1.h (iterstack_item_t): Change type of 'rightp' field
+ to 'size_t'.
+ * gl_anytree_list2.h (gl_tree_search_from_to): Renamed from
+ gl_tree_search. Add start_index, end_index arguments.
+ (gl_tree_indexof_from_to): Renamed from gl_tree_indexof. Add
+ start_index, end_index arguments.
+ (gl_tree_remove): Update.
+ * gl_avltree_list.c (gl_avltree_list_implementation): Update.
+ * gl_rbtree_list.c (gl_rbtree_list_implementation): Update.
+ * gl_anytreehash_list1.h (compare_position_threshold): New function.
+ * gl_anytreehash_list2.h (gl_tree_search_from_to): Renamed from
+ gl_tree_search. Add start_index, end_index arguments.
+ (gl_tree_indexof_from_to): Renamed from gl_tree_indexof. Add
+ start_index, end_index arguments.
+ * gl_avltreehash_list.c (gl_avltreehash_list_implementation): Update.
+ * gl_rbtreehash_list.c (gl_rbtreehash_list_implementation): Update.
+
2006-10-04 Bruno Haible <bruno@clisp.org>
* fatal-signal.c (fatal_signals) [WOE32]: Add the SIGBREAK signal.
}
static gl_list_node_t
-gl_linked_search (gl_list_t list, const void *elt)
+gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
{
-#if WITH_HASHTABLE
- 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;
-
- if (!list->base.allow_duplicates)
- {
- /* Look for the first match in the hash bucket. */
- gl_list_node_t node;
-
- for (node = (gl_list_node_t) list->table[index];
- node != NULL;
- node = (gl_list_node_t) node->h.hash_next)
- if (node->h.hashcode == hashcode
- && (equals != NULL
- ? equals (elt, node->value)
- : elt == node->value))
- return node;
- return NULL;
- }
- else
- {
- /* Look whether there is more than one match in the hash bucket. */
- bool multiple_matches = false;
- gl_list_node_t first_match = NULL;
- gl_list_node_t node;
+ size_t count = list->count;
- for (node = (gl_list_node_t) list->table[index];
- node != NULL;
- node = (gl_list_node_t) node->h.hash_next)
- if (node->h.hashcode == hashcode
- && (equals != NULL
- ? equals (elt, node->value)
- : elt == node->value))
+ if (!(start_index <= end_index && end_index <= count))
+ /* Invalid arguments. */
+ abort ();
+ {
+#if WITH_HASHTABLE
+ 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;
+
+ if (!list->base.allow_duplicates)
+ {
+ /* Look for the first match in the hash bucket. */
+ gl_list_node_t found = NULL;
+ gl_list_node_t node;
+
+ for (node = (gl_list_node_t) list->table[index];
+ node != NULL;
+ node = (gl_list_node_t) node->h.hash_next)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->value))
+ {
+ found = node;
+ break;
+ }
+ if (start_index > 0)
+ /* Look whether found's index is < start_index. */
+ for (node = list->root.next; ; node = node->next)
+ {
+ if (node == found)
+ return NULL;
+ if (--start_index == 0)
+ break;
+ }
+ if (end_index < count)
+ /* Look whether found's index is >= end_index. */
{
- if (first_match == NULL)
- first_match = node;
- else
+ end_index = count - end_index;
+ for (node = list->root.prev; ; node = node->prev)
{
- multiple_matches = true;
- break;
+ if (node == found)
+ return NULL;
+ if (--end_index == 0)
+ break;
}
}
- if (!multiple_matches)
- return first_match;
- else
- {
- /* We need the match with the smallest index. But we don't have
- a fast mapping node -> index. So we have to walk the list. */
- for (node = list->root.next; node != &list->root; node = node->next)
- if (node->h.hashcode == hashcode
- && (equals != NULL
- ? equals (elt, node->value)
- : elt == node->value))
- return node;
- /* We know there are at least two matches. */
- abort ();
- }
- }
+ return found;
+ }
+ else
+ {
+ /* Look whether there is more than one match in the hash bucket. */
+ bool multiple_matches = false;
+ gl_list_node_t first_match = NULL;
+ gl_list_node_t node;
+
+ for (node = (gl_list_node_t) list->table[index];
+ node != NULL;
+ node = (gl_list_node_t) node->h.hash_next)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->value))
+ {
+ if (first_match == NULL)
+ first_match = node;
+ else
+ {
+ multiple_matches = true;
+ break;
+ }
+ }
+ if (multiple_matches)
+ {
+ /* We need the match with the smallest index. But we don't have
+ a fast mapping node -> index. So we have to walk the list. */
+ end_index -= start_index;
+ node = list->root.next;
+ for (; start_index > 0; start_index--)
+ node = node->next;
+
+ for (;
+ end_index > 0;
+ node = node->next, end_index--)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->value))
+ return node;
+ /* The matches must have all been at indices < start_index or
+ >= end_index. */
+ return NULL;
+ }
+ else
+ {
+ if (start_index > 0)
+ /* Look whether first_match's index is < start_index. */
+ for (node = list->root.next; node != &list->root; node = node->next)
+ {
+ if (node == first_match)
+ return NULL;
+ if (--start_index == 0)
+ break;
+ }
+ if (end_index < list->count)
+ /* Look whether first_match's index is >= end_index. */
+ {
+ end_index = list->count - end_index;
+ for (node = list->root.prev; ; node = node->prev)
+ {
+ if (node == first_match)
+ return NULL;
+ if (--end_index == 0)
+ break;
+ }
+ }
+ return first_match;
+ }
+ }
#else
- gl_listelement_equals_fn equals = list->base.equals_fn;
- gl_list_node_t node;
-
- if (equals != NULL)
- {
- for (node = list->root.next; node != &list->root; node = node->next)
- if (equals (elt, node->value))
- return node;
- }
- else
- {
- for (node = list->root.next; node != &list->root; node = node->next)
- if (elt == node->value)
- return node;
- }
- return NULL;
+ gl_listelement_equals_fn equals = list->base.equals_fn;
+ gl_list_node_t node = list->root.next;
+
+ end_index -= start_index;
+ for (; start_index > 0; start_index--)
+ node = node->next;
+
+ if (equals != NULL)
+ {
+ for (; end_index > 0; node = node->next, end_index--)
+ if (equals (elt, node->value))
+ return node;
+ }
+ else
+ {
+ for (; end_index > 0; node = node->next, end_index--)
+ if (elt == node->value)
+ return node;
+ }
+ return NULL;
#endif
+ }
}
static size_t
-gl_linked_indexof (gl_list_t list, const void *elt)
+gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
{
-#if WITH_HASHTABLE
- /* Here the hash table doesn't help much. It only allows us to minimize
- the number of equals() calls, by looking up first the node and then
- its index. */
- 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_list_node_t node;
+ size_t count = list->count;
- /* First step: Look up the node. */
- if (!list->base.allow_duplicates)
- {
- /* Look for the first match in the hash bucket. */
- for (node = (gl_list_node_t) list->table[index];
- node != NULL;
- node = (gl_list_node_t) node->h.hash_next)
- if (node->h.hashcode == hashcode
- && (equals != NULL
- ? equals (elt, node->value)
- : elt == node->value))
- break;
- }
- else
- {
- /* Look whether there is more than one match in the hash bucket. */
- bool multiple_matches = false;
- gl_list_node_t first_match = NULL;
-
- for (node = (gl_list_node_t) list->table[index];
- node != NULL;
- node = (gl_list_node_t) node->h.hash_next)
- if (node->h.hashcode == hashcode
- && (equals != NULL
- ? equals (elt, node->value)
- : elt == node->value))
+ if (!(start_index <= end_index && end_index <= count))
+ /* Invalid arguments. */
+ abort ();
+ {
+#if WITH_HASHTABLE
+ /* Here the hash table doesn't help much. It only allows us to minimize
+ the number of equals() calls, by looking up first the node and then
+ its index. */
+ 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_list_node_t node;
+
+ /* First step: Look up the node. */
+ if (!list->base.allow_duplicates)
+ {
+ /* Look for the first match in the hash bucket. */
+ for (node = (gl_list_node_t) list->table[index];
+ node != NULL;
+ node = (gl_list_node_t) node->h.hash_next)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->value))
+ break;
+ }
+ else
+ {
+ /* Look whether there is more than one match in the hash bucket. */
+ bool multiple_matches = false;
+ gl_list_node_t first_match = NULL;
+
+ for (node = (gl_list_node_t) list->table[index];
+ node != NULL;
+ node = (gl_list_node_t) node->h.hash_next)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->value))
+ {
+ if (first_match == NULL)
+ first_match = node;
+ else
+ {
+ multiple_matches = true;
+ break;
+ }
+ }
+ if (multiple_matches)
{
- if (first_match == NULL)
- first_match = node;
- else
- {
- multiple_matches = true;
- break;
- }
+ /* We need the match with the smallest index. But we don't have
+ a fast mapping node -> index. So we have to walk the list. */
+ size_t index;
+
+ index = start_index;
+ node = list->root.next;
+ for (; start_index > 0; start_index--)
+ node = node->next;
+
+ for (;
+ index < end_index;
+ node = node->next, index++)
+ if (node->h.hashcode == hashcode
+ && (equals != NULL
+ ? equals (elt, node->value)
+ : elt == node->value))
+ return index;
+ /* The matches must have all been at indices < start_index or
+ >= end_index. */
+ return (size_t)(-1);
}
- if (multiple_matches)
- {
- /* We need the match with the smallest index. But we don't have
- a fast mapping node -> index. So we have to walk the list. */
- size_t index;
-
- for (node = list->root.next, index = 0;
- node != &list->root;
- node = node->next, index++)
- if (node->h.hashcode == hashcode
- && (equals != NULL
- ? equals (elt, node->value)
- : elt == node->value))
- return index;
- /* We know there are at least two matches. */
- abort ();
- }
- node = first_match;
- }
+ node = first_match;
+ }
- /* Second step: Look up the index of the node. */
- if (node == NULL)
- return (size_t)(-1);
- else
- {
- size_t index = 0;
+ /* Second step: Look up the index of the node. */
+ if (node == NULL)
+ return (size_t)(-1);
+ else
+ {
+ size_t index = 0;
- for (; node->prev != &list->root; node = node->prev)
- index++;
+ for (; node->prev != &list->root; node = node->prev)
+ index++;
- return index;
- }
-#else
- gl_listelement_equals_fn equals = list->base.equals_fn;
- gl_list_node_t node;
-
- if (equals != NULL)
- {
- size_t index;
- for (node = list->root.next, index = 0;
- node != &list->root;
- node = node->next, index++)
- if (equals (elt, node->value))
+ if (index >= start_index && index < end_index)
return index;
- }
- else
- {
- size_t index;
- for (node = list->root.next, index = 0;
- node != &list->root;
- node = node->next, index++)
- if (elt == node->value)
- return index;
- }
- return (size_t)(-1);
+ else
+ return (size_t)(-1);
+ }
+#else
+ gl_listelement_equals_fn equals = list->base.equals_fn;
+ size_t index = start_index;
+ gl_list_node_t node = list->root.next;
+
+ for (; start_index > 0; start_index--)
+ node = node->next;
+
+ if (equals != NULL)
+ {
+ for (;
+ index < end_index;
+ node = node->next, index++)
+ if (equals (elt, node->value))
+ return index;
+ }
+ else
+ {
+ for (;
+ index < end_index;
+ node = node->next, index++)
+ if (elt == node->value)
+ return index;
+ }
+ return (size_t)(-1);
#endif
+ }
}
static gl_list_node_t
static bool
gl_linked_remove (gl_list_t list, const void *elt)
{
- gl_list_node_t node = gl_linked_search (list, elt);
+ gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
if (node != NULL)
return gl_linked_remove_node (list, node);
typedef struct
{
gl_list_node_t node;
- bool rightp;
+ size_t rightp;
} iterstack_item_t;
/* A stack used for iterating across the elements. */
#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
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
position1 < position2 ? -1 : 0);
}
+/* Compares a node's position in the tree with a given threshold. */
+static bool
+compare_position_threshold (const void *x, const void *threshold)
+{
+ gl_list_node_t node = (gl_list_node_t) x;
+ size_t position = node_position (node);
+ return (position >= (uintptr_t)threshold);
+}
+
/* Return the first element of a non-empty ordered set of nodes. */
static inline gl_list_node_t
gl_oset_first (gl_oset_t set)
/* 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 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;
+ /* 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[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)
+ {
+ 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);
}
static size_t
-gl_array_indexof (gl_list_t list, const void *elt)
+gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
{
size_t count = list->count;
- if (count > 0)
+
+ if (!(start_index <= end_index && end_index <= count))
+ /* Invalid arguments. */
+ abort ();
+
+ if (start_index < end_index)
{
gl_listelement_equals_fn equals = list->base.equals_fn;
if (equals != NULL)
{
size_t i;
- for (i = 0;;)
+ for (i = start_index;;)
{
if (equals (elt, list->elements[i]))
return i;
i++;
- if (i == count)
+ if (i == end_index)
break;
}
}
{
size_t i;
- for (i = 0;;)
+ for (i = start_index;;)
{
if (elt == list->elements[i])
return i;
i++;
- if (i == count)
+ if (i == end_index)
break;
}
}
}
static gl_list_node_t
-gl_array_search (gl_list_t list, const void *elt)
+gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
{
- size_t index = gl_array_indexof (list, elt);
+ size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt);
return INDEX_TO_NODE (index);
}
static bool
gl_array_remove (gl_list_t list, const void *elt)
{
- size_t position = gl_array_indexof (list, elt);
+ size_t position = gl_array_indexof_from_to (list, 0, list->count, elt);
if (position == (size_t)(-1))
return false;
else
gl_array_previous_node,
gl_array_get_at,
gl_array_set_at,
- gl_array_search,
- gl_array_indexof,
+ gl_array_search_from_to,
+ gl_array_indexof_from_to,
gl_array_add_first,
gl_array_add_last,
gl_array_add_before,
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
- gl_tree_search,
- gl_tree_indexof,
+ gl_tree_search_from_to,
+ gl_tree_indexof_from_to,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
- gl_tree_search,
- gl_tree_indexof,
+ gl_tree_search_from_to,
+ gl_tree_indexof_from_to,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
}
static size_t
-gl_carray_indexof (gl_list_t list, const void *elt)
+gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
{
size_t count = list->count;
- if (count > 0)
+
+ if (!(start_index <= end_index && end_index <= count))
+ /* Invalid arguments. */
+ abort ();
+
+ if (start_index < end_index)
{
gl_listelement_equals_fn equals = list->base.equals_fn;
size_t allocated = list->allocated;
size_t i_end;
- i_end = list->offset + list->count;
+ i_end = list->offset + end_index;
if (i_end >= allocated)
i_end -= allocated;
{
size_t i;
- for (i = list->offset;;)
+ i = list->offset + start_index;
+ if (i >= allocated) /* can only happen if start_index > 0 */
+ i -= allocated;
+
+ for (;;)
{
if (equals (elt, list->elements[i]))
return (i >= list->offset ? i : i + allocated) - list->offset;
{
size_t i;
- for (i = list->offset;;)
+ i = list->offset + start_index;
+ if (i >= allocated) /* can only happen if start_index > 0 */
+ i -= allocated;
+
+ for (;;)
{
if (elt == list->elements[i])
return (i >= list->offset ? i : i + allocated) - list->offset;
}
static gl_list_node_t
-gl_carray_search (gl_list_t list, const void *elt)
+gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
{
- size_t index = gl_carray_indexof (list, elt);
+ size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
return INDEX_TO_NODE (index);
}
static bool
gl_carray_remove (gl_list_t list, const void *elt)
{
- size_t position = gl_carray_indexof (list, elt);
+ size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
if (position == (size_t)(-1))
return false;
else
gl_carray_previous_node,
gl_carray_get_at,
gl_carray_set_at,
- gl_carray_search,
- gl_carray_indexof,
+ gl_carray_search_from_to,
+ gl_carray_indexof_from_to,
gl_carray_add_first,
gl_carray_add_last,
gl_carray_add_before,
gl_linked_previous_node,
gl_linked_get_at,
gl_linked_set_at,
- gl_linked_search,
- gl_linked_indexof,
+ gl_linked_search_from_to,
+ gl_linked_indexof_from_to,
gl_linked_add_first,
gl_linked_add_last,
gl_linked_add_before,
gl_linked_previous_node,
gl_linked_get_at,
gl_linked_set_at,
- gl_linked_search,
- gl_linked_indexof,
+ gl_linked_search_from_to,
+ gl_linked_indexof_from_to,
gl_linked_add_first,
gl_linked_add_last,
gl_linked_add_before,
gl_list_node_t
gl_list_search (gl_list_t list, const void *elt)
{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
return ((const struct gl_list_impl_base *) list)->vtable
- ->search (list, elt);
+ ->search_from_to (list, 0, size, elt);
+}
+
+gl_list_node_t
+gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
+{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->search_from_to (list, start_index, size, elt);
+}
+
+gl_list_node_t
+gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->search_from_to (list, start_index, end_index, elt);
}
size_t
gl_list_indexof (gl_list_t list, const void *elt)
{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->indexof_from_to (list, 0, size, elt);
+}
+
+size_t
+gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
+{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->indexof_from_to (list, start_index, size, elt);
+}
+
+size_t
+gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, const void *elt)
+{
return ((const struct gl_list_impl_base *) list)->vtable
- ->indexof (list, elt);
+ ->indexof_from_to (list, start_index, end_index, elt);
}
gl_list_node_t
gl_list_get_at O(1) O(n) O(log n) O(n) O(log n)
gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n)
gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1)
+ gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
+ gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n)
gl_list_indexof O(n) O(n) O(n) O(n) O(log n)
+ gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
+ gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n)
gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n)
gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n)
Return its node if found, or NULL if not present in the list. */
extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
+/* Search whether an element is already in the list,
+ at a position >= START_INDEX.
+ Return its node if found, or NULL if not present in the list. */
+extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
+ const void *elt);
+
+/* Search whether an element is already in the list,
+ at a position >= START_INDEX and < END_INDEX.
+ Return its node if found, or NULL if not present in the list. */
+extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+
/* Search whether an element is already in the list.
Return its position if found, or (size_t)(-1) if not present in the list. */
extern size_t gl_list_indexof (gl_list_t list, const void *elt);
+/* Search whether an element is already in the list,
+ at a position >= START_INDEX.
+ Return its position if found, or (size_t)(-1) if not present in the list. */
+extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
+ const void *elt);
+
+/* Search whether an element is already in the list,
+ at a position >= START_INDEX and < END_INDEX.
+ Return its position if found, or (size_t)(-1) if not present in the list. */
+extern size_t gl_list_indexof_from_to (gl_list_t list,
+ size_t start_index, size_t end_index,
+ const void *elt);
+
/* Add an element as the first element of the list.
Return its node. */
extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
const void * (*get_at) (gl_list_t list, size_t position);
gl_list_node_t (*set_at) (gl_list_t list, size_t position, const void *elt);
- gl_list_node_t (*search) (gl_list_t list, const void *elt);
- size_t (*indexof) (gl_list_t list, const void *elt);
+ gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
+ size_t end_index, const void *elt);
+ size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
+ size_t end_index, const void *elt);
gl_list_node_t (*add_first) (gl_list_t list, const void *elt);
gl_list_node_t (*add_last) (gl_list_t list, const void *elt);
gl_list_node_t (*add_before) (gl_list_t list, gl_list_node_t node,
static inline gl_list_node_t
gl_list_search (gl_list_t list, const void *elt)
{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->search_from_to (list, 0, size, elt);
+}
+
+# define gl_list_search_from gl_list_search_from_inline
+static inline gl_list_node_t
+gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
+{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
return ((const struct gl_list_impl_base *) list)->vtable
- ->search (list, elt);
+ ->search_from_to (list, start_index, size, elt);
+}
+
+# define gl_list_search_from_to gl_list_search_from_to_inline
+static inline gl_list_node_t
+gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->search_from_to (list, start_index, end_index, elt);
}
# define gl_list_indexof gl_list_indexof_inline
static inline size_t
gl_list_indexof (gl_list_t list, const void *elt)
{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->indexof_from_to (list, 0, size, elt);
+}
+
+# define gl_list_indexof_from gl_list_indexof_from_inline
+static inline size_t
+gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
+{
+ size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->indexof_from_to (list, start_index, size, elt);
+}
+
+# define gl_list_indexof_from_to gl_list_indexof_from_to_inline
+static inline size_t
+gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
+{
return ((const struct gl_list_impl_base *) list)->vtable
- ->indexof (list, elt);
+ ->indexof_from_to (list, start_index, end_index, elt);
}
# define gl_list_add_first gl_list_add_first_inline
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
- gl_tree_search,
- gl_tree_indexof,
+ gl_tree_search_from_to,
+ gl_tree_indexof_from_to,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
- gl_tree_search,
- gl_tree_indexof,
+ gl_tree_search_from_to,
+ gl_tree_indexof_from_to,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
projects / gnulib.git / commitdiff