[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
'sublist' module (1/3)
|
From: |
Bruno Haible |
|
Subject: |
'sublist' module (1/3) |
|
Date: |
Thu, 5 Oct 2006 14:45:23 +0200 |
|
User-agent: |
KMail/1.9.1 |
Hi,
The 'list' datatype lacks primitives for fast searching of elements, limited
to a subsequence of the list. I'm adding this. It's the first step towards
a 'sublist' module.
2006-10-03 Bruno Haible <address@hidden>
* 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.
*** gnulib-20060928/lib/gl_list.h 2006-10-03 14:43:10.000000000 +0200
--- gnulib-20060928-modified/lib/gl_list.h 2006-10-03 20:08:07.000000000
+0200
***************
*** 68,74 ****
--- 68,78 ----
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)
***************
*** 169,178 ****
--- 173,209 ----
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);
***************
*** 343,350 ****
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 (*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,
--- 374,383 ----
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_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,
***************
*** 477,492 ****
static inline gl_list_node_t
gl_list_search (gl_list_t list, const void *elt)
{
return ((const struct gl_list_impl_base *) list)->vtable
! ->search (list, elt);
}
# define gl_list_indexof gl_list_indexof_inline
static inline size_t
gl_list_indexof (gl_list_t list, const void *elt)
{
return ((const struct gl_list_impl_base *) list)->vtable
! ->indexof (list, elt);
}
# define gl_list_add_first gl_list_add_first_inline
--- 510,563 ----
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_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_from_to (list, start_index, end_index, elt);
}
# define gl_list_add_first gl_list_add_first_inline
*** gnulib-20060928/lib/gl_list.c 2006-10-03 14:43:10.000000000 +0200
--- gnulib-20060928-modified/lib/gl_list.c 2006-10-03 20:10:15.000000000
+0200
***************
*** 93,107 ****
gl_list_node_t
gl_list_search (gl_list_t list, const void *elt)
{
return ((const struct gl_list_impl_base *) list)->vtable
! ->search (list, elt);
}
size_t
gl_list_indexof (gl_list_t list, const void *elt)
{
return ((const struct gl_list_impl_base *) list)->vtable
! ->indexof (list, elt);
}
gl_list_node_t
--- 93,139 ----
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);
! }
!
! 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_from_to (list, start_index, end_index, elt);
}
gl_list_node_t
*** gnulib-20060928/lib/gl_array_list.c 2006-10-03 19:21:05.000000000 +0200
--- gnulib-20060928-modified/lib/gl_array_list.c 2006-10-03
20:14:10.000000000 +0200
***************
*** 167,188 ****
}
static size_t
! gl_array_indexof (gl_list_t list, const void *elt)
{
size_t count = list->count;
! if (count > 0)
{
gl_listelement_equals_fn equals = list->base.equals_fn;
if (equals != NULL)
{
size_t i;
! for (i = 0;;)
{
if (equals (elt, list->elements[i]))
return i;
i++;
! if (i == count)
break;
}
}
--- 167,194 ----
}
static size_t
! 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 (!(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 = start_index;;)
{
if (equals (elt, list->elements[i]))
return i;
i++;
! if (i == end_index)
break;
}
}
***************
*** 190,201 ****
{
size_t i;
! for (i = 0;;)
{
if (elt == list->elements[i])
return i;
i++;
! if (i == count)
break;
}
}
--- 196,207 ----
{
size_t i;
! for (i = start_index;;)
{
if (elt == list->elements[i])
return i;
i++;
! if (i == end_index)
break;
}
}
***************
*** 204,212 ****
}
static gl_list_node_t
! gl_array_search (gl_list_t list, const void *elt)
{
! size_t index = gl_array_indexof (list, elt);
return INDEX_TO_NODE (index);
}
--- 210,219 ----
}
static gl_list_node_t
! 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_from_to (list, start_index, end_index, elt);
return INDEX_TO_NODE (index);
}
***************
*** 367,373 ****
static bool
gl_array_remove (gl_list_t list, const void *elt)
{
! size_t position = gl_array_indexof (list, elt);
if (position == (size_t)(-1))
return false;
else
--- 374,380 ----
static bool
gl_array_remove (gl_list_t list, const void *elt)
{
! size_t position = gl_array_indexof_from_to (list, 0, list->count, elt);
if (position == (size_t)(-1))
return false;
else
***************
*** 595,602 ****
gl_array_previous_node,
gl_array_get_at,
gl_array_set_at,
! gl_array_search,
! gl_array_indexof,
gl_array_add_first,
gl_array_add_last,
gl_array_add_before,
--- 602,609 ----
gl_array_previous_node,
gl_array_get_at,
gl_array_set_at,
! gl_array_search_from_to,
! gl_array_indexof_from_to,
gl_array_add_first,
gl_array_add_last,
gl_array_add_before,
*** gnulib-20060928/lib/gl_carray_list.c 2006-10-03 19:21:05.000000000
+0200
--- gnulib-20060928-modified/lib/gl_carray_list.c 2006-10-03
21:14:22.000000000 +0200
***************
*** 185,200 ****
}
static size_t
! gl_carray_indexof (gl_list_t list, const void *elt)
{
size_t count = list->count;
! if (count > 0)
{
gl_listelement_equals_fn equals = list->base.equals_fn;
size_t allocated = list->allocated;
size_t i_end;
! i_end = list->offset + list->count;
if (i_end >= allocated)
i_end -= allocated;
--- 185,206 ----
}
static size_t
! 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 (!(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 + end_index;
if (i_end >= allocated)
i_end -= allocated;
***************
*** 202,208 ****
{
size_t i;
! for (i = list->offset;;)
{
if (equals (elt, list->elements[i]))
return (i >= list->offset ? i : i + allocated) - list->offset;
--- 208,218 ----
{
size_t i;
! 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;
***************
*** 217,223 ****
{
size_t i;
! for (i = list->offset;;)
{
if (elt == list->elements[i])
return (i >= list->offset ? i : i + allocated) - list->offset;
--- 227,237 ----
{
size_t i;
! 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;
***************
*** 233,241 ****
}
static gl_list_node_t
! gl_carray_search (gl_list_t list, const void *elt)
{
! size_t index = gl_carray_indexof (list, elt);
return INDEX_TO_NODE (index);
}
--- 247,256 ----
}
static gl_list_node_t
! 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_from_to (list, start_index, end_index,
elt);
return INDEX_TO_NODE (index);
}
***************
*** 501,507 ****
static bool
gl_carray_remove (gl_list_t list, const void *elt)
{
! size_t position = gl_carray_indexof (list, elt);
if (position == (size_t)(-1))
return false;
else
--- 516,522 ----
static bool
gl_carray_remove (gl_list_t list, const void *elt)
{
! size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
if (position == (size_t)(-1))
return false;
else
***************
*** 752,759 ****
gl_carray_previous_node,
gl_carray_get_at,
gl_carray_set_at,
! gl_carray_search,
! gl_carray_indexof,
gl_carray_add_first,
gl_carray_add_last,
gl_carray_add_before,
--- 767,774 ----
gl_carray_previous_node,
gl_carray_get_at,
gl_carray_set_at,
! gl_carray_search_from_to,
! gl_carray_indexof_from_to,
gl_carray_add_first,
gl_carray_add_last,
gl_carray_add_before,
*** gnulib-20060928/lib/gl_anylinked_list2.h 2006-10-03 14:43:10.000000000
+0200
--- gnulib-20060928-modified/lib/gl_anylinked_list2.h 2006-10-03
21:15:24.000000000 +0200
***************
*** 215,410 ****
}
static gl_list_node_t
! gl_linked_search (gl_list_t list, 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;
! 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)
! 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 ();
! }
! }
#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;
#endif
}
static size_t
! gl_linked_indexof (gl_list_t list, 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;
! /* 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)
! {
! /* 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;
! }
!
! /* 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++;
! 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))
! 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);
#endif
}
static gl_list_node_t
--- 215,497 ----
}
static gl_list_node_t
! gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t
end_index,
! const void *elt)
{
! size_t count = list->count;
! 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. */
{
! end_index = count - end_index;
! for (node = list->root.prev; ; node = node->prev)
{
! if (node == found)
! return NULL;
! if (--end_index == 0)
! break;
}
}
! 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 = 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_from_to (gl_list_t list, size_t start_index, size_t
end_index,
! const void *elt)
{
! size_t count = list->count;
! 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)
{
! /* 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);
}
! node = first_match;
! }
! /* 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++;
! if (index >= start_index && index < end_index)
return index;
! 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
***************
*** 661,667 ****
static bool
gl_linked_remove (gl_list_t list, const void *elt)
{
! gl_list_node_t node = gl_linked_search (list, elt);
if (node != NULL)
return gl_linked_remove_node (list, node);
--- 748,754 ----
static bool
gl_linked_remove (gl_list_t list, const void *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);
*** gnulib-20060928/lib/gl_linked_list.c 2006-10-03 14:43:10.000000000
+0200
--- gnulib-20060928-modified/lib/gl_linked_list.c 2006-10-03
20:34:55.000000000 +0200
***************
*** 42,49 ****
gl_linked_previous_node,
gl_linked_get_at,
gl_linked_set_at,
! gl_linked_search,
! gl_linked_indexof,
gl_linked_add_first,
gl_linked_add_last,
gl_linked_add_before,
--- 42,49 ----
gl_linked_previous_node,
gl_linked_get_at,
gl_linked_set_at,
! gl_linked_search_from_to,
! gl_linked_indexof_from_to,
gl_linked_add_first,
gl_linked_add_last,
gl_linked_add_before,
*** gnulib-20060928/lib/gl_linkedhash_list.c 2006-10-03 14:43:10.000000000
+0200
--- gnulib-20060928-modified/lib/gl_linkedhash_list.c 2006-10-03
20:35:07.000000000 +0200
***************
*** 99,106 ****
gl_linked_previous_node,
gl_linked_get_at,
gl_linked_set_at,
! gl_linked_search,
! gl_linked_indexof,
gl_linked_add_first,
gl_linked_add_last,
gl_linked_add_before,
--- 99,106 ----
gl_linked_previous_node,
gl_linked_get_at,
gl_linked_set_at,
! gl_linked_search_from_to,
! gl_linked_indexof_from_to,
gl_linked_add_first,
gl_linked_add_last,
gl_linked_add_before,
*** gnulib-20060928/lib/gl_anytree_list1.h 2006-07-17 00:31:17.000000000
+0200
--- gnulib-20060928-modified/lib/gl_anytree_list1.h 2006-10-03
17:23:12.000000000 +0200
***************
*** 23,29 ****
typedef struct
{
gl_list_node_t node;
! bool rightp;
} iterstack_item_t;
/* A stack used for iterating across the elements. */
--- 23,29 ----
typedef struct
{
gl_list_node_t node;
! size_t rightp;
} iterstack_item_t;
/* A stack used for iterating across the elements. */
*** gnulib-20060928/lib/gl_anytree_list2.h 2006-10-03 14:43:10.000000000
+0200
--- gnulib-20060928-modified/lib/gl_anytree_list2.h 2006-10-03
21:19:35.000000000 +0200
***************
*** 164,250 ****
#if !WITH_HASHTABLE
static gl_list_node_t
! gl_tree_search (gl_list_t list, 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++;
! }
}
static size_t
! gl_tree_indexof (gl_list_t list, 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++;
! }
}
#endif
--- 164,388 ----
#if !WITH_HASHTABLE
static gl_list_node_t
! gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
! const void *elt)
{
! 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_from_to (gl_list_t list, size_t start_index, size_t end_index,
! const void *elt)
{
! 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
***************
*** 278,289 ****
static bool
gl_tree_remove (gl_list_t list, const void *elt)
{
! gl_list_node_t node = gl_tree_search (list, elt);
! if (node != NULL)
! return gl_tree_remove_node (list, node);
! else
! return false;
}
#if !WITH_HASHTABLE
--- 416,430 ----
static bool
gl_tree_remove (gl_list_t list, const void *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);
! }
! return false;
}
#if !WITH_HASHTABLE
*** gnulib-20060928/lib/gl_avltree_list.c 2006-10-03 14:43:10.000000000
+0200
--- gnulib-20060928-modified/lib/gl_avltree_list.c 2006-10-03
20:34:36.000000000 +0200
***************
*** 75,82 ****
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
! gl_tree_search,
! gl_tree_indexof,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
--- 75,82 ----
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
! gl_tree_search_from_to,
! gl_tree_indexof_from_to,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
*** gnulib-20060928/lib/gl_rbtree_list.c 2006-10-03 14:43:10.000000000
+0200
--- gnulib-20060928-modified/lib/gl_rbtree_list.c 2006-10-03
20:35:19.000000000 +0200
***************
*** 76,83 ****
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
! gl_tree_search,
! gl_tree_indexof,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
--- 76,83 ----
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
! gl_tree_search_from_to,
! gl_tree_indexof_from_to,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
*** gnulib-20060928/lib/gl_anytreehash_list1.h 2006-07-17 00:47:21.000000000
+0200
--- gnulib-20060928-modified/lib/gl_anytreehash_list1.h 2006-10-03
19:54:49.000000000 +0200
***************
*** 78,83 ****
--- 78,92 ----
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)
*** gnulib-20060928/lib/gl_anytreehash_list2.h 2006-07-17 00:03:48.000000000
+0200
--- gnulib-20060928-modified/lib/gl_anytreehash_list2.h 2006-10-03
21:20:55.000000000 +0200
***************
*** 19,79 ****
/* 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)
{
! 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;
! }
! }
! return NULL;
}
static size_t
! gl_tree_indexof (gl_list_t list, const void *elt)
{
! gl_list_node_t node = gl_tree_search (list, elt);
if (node != NULL)
return node_position (node);
--- 19,139 ----
/* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */
static gl_list_node_t
! gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
! const void *elt)
{
! 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;
! }
}
static size_t
! 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_from_to (list, start_index, end_index, elt);
if (node != NULL)
return node_position (node);
*** gnulib-20060928/lib/gl_avltreehash_list.c 2006-10-03 14:43:10.000000000
+0200
--- gnulib-20060928-modified/lib/gl_avltreehash_list.c 2006-10-03
20:34:46.000000000 +0200
***************
*** 104,111 ****
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
! gl_tree_search,
! gl_tree_indexof,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
--- 104,111 ----
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
! gl_tree_search_from_to,
! gl_tree_indexof_from_to,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
*** gnulib-20060928/lib/gl_rbtreehash_list.c 2006-10-03 14:43:10.000000000
+0200
--- gnulib-20060928-modified/lib/gl_rbtreehash_list.c 2006-10-03
20:35:28.000000000 +0200
***************
*** 105,112 ****
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
! gl_tree_search,
! gl_tree_indexof,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
--- 105,112 ----
gl_tree_previous_node,
gl_tree_get_at,
gl_tree_set_at,
! gl_tree_search_from_to,
! gl_tree_indexof_from_to,
gl_tree_add_first,
gl_tree_add_last,
gl_tree_add_before,
- 'sublist' module (1/3),
Bruno Haible <=