[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
'sublist' module (2/3): add bounded list search operations to 'list' mod
From: |
Bruno Haible |
Subject: |
'sublist' module (2/3): add bounded list search operations to 'list' modules |
Date: |
Fri, 6 Oct 2006 14:05:37 +0200 |
User-agent: |
KMail/1.9.1 |
When searching a sublist of a sorted list, the number of comparisons
performed can be significantly reduced. I'm therefore adding such a
"bounded search" operation.
2006-10-03 Bruno Haible
* gl_list.h (gl_sortedlist_search_from_to,
gl_sortedlist_indexof_from_to): New declarations.
(gl_list_implementation): New fields sortedlist_search_from_to,
sortedlist_indexof_from_to.
(gl_sortedlist_search_from_to, gl_sortedlist_indexof_from_to): New
inline functions.
* gl_list.c (gl_sortedlist_search_from_to,
gl_sortedlist_indexof_from_to): New functions.
* gl_array_list.c (gl_array_sortedlist_indexof_from_to): New function.
(gl_array_sortedlist_indexof, gl_array_sortedlist_search): Use it.
(gl_array_sortedlist_search_from_to): New function.
(gl_array_list_implementation): Update.
* gl_carray_list.c (gl_carray_sortedlist_indexof_from_to): New function.
(gl_carray_sortedlist_indexof, gl_carray_sortedlist_search): Use it.
(gl_carray_sortedlist_search_from_to): New function.
(gl_carray_list_implementation): Update.
* gl_anylinked_list2.h (gl_linked_sortedlist_search_from_to,
gl_linked_sortedlist_indexof_from_to): New functions.
* gl_linked_list.c (gl_linked_list_implementation): Update.
* gl_linkedhash_list.c (gl_linkedhash_list_implementation): Update.
* gl_anytree_list2.h (gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof_from_to): New functions.
* gl_avltree_list.c (gl_avltree_list_implementation): Update.
* gl_avltreehash_list.c (gl_avltreehash_list_implementation): Update.
* gl_rbtree_list.c (gl_rbtree_list_implementation): Update.
* gl_rbtreehash_list.c (gl_avltreehash_list_implementation): Update.
diff -c -3 -r1.2 gl_list.h
*** lib/gl_list.h 5 Oct 2006 12:45:16 -0000 1.2
--- lib/gl_list.h 6 Oct 2006 12:02:24 -0000
***************
*** 85,91 ****
--- 85,93 ----
gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n)
gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n)
gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n)
+ gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n)
gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n)
+ gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n)
gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log
n)²)/O(log n)
gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log
n)²)/O(log n)
*/
***************
*** 303,308 ****
--- 305,324 ----
/* Search whether an element is already in the list.
The list is assumed to be sorted with COMPAR.
+ Only list elements with indices >= START_INDEX and < END_INDEX are
+ considered; the implementation uses these bounds to minimize the number
+ of COMPAR invocations.
+ Return its node if found, or NULL if not present in the list.
+ If the list contains several copies of ELT, the node of the leftmost one is
+ returned. */
+ extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn
compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+
+ /* Search whether an element is already in the list.
+ The list is assumed to be sorted with COMPAR.
Return its position if found, or (size_t)(-1) if not present in the list.
If the list contains several copies of ELT, the position of the leftmost
one
is returned. */
***************
*** 310,315 ****
--- 326,345 ----
gl_listelement_compar_fn compar,
const void *elt);
+ /* Search whether an element is already in the list.
+ The list is assumed to be sorted with COMPAR.
+ Only list elements with indices >= START_INDEX and < END_INDEX are
+ considered; the implementation uses these bounds to minimize the number
+ of COMPAR invocations.
+ Return its position if found, or (size_t)(-1) if not present in the list.
+ If the list contains several copies of ELT, the position of the leftmost
one
+ is returned. */
+ extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+
/* Add an element at the appropriate position in the list.
The list is assumed to be sorted with COMPAR.
Return its node. */
***************
*** 374,382 ****
--- 404,421 ----
gl_list_node_t (*sortedlist_search) (gl_list_t list,
gl_listelement_compar_fn compar,
const void *elt);
+ gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
size_t (*sortedlist_indexof) (gl_list_t list,
gl_listelement_compar_fn compar,
const void *elt);
+ size_t (*sortedlist_indexof_from_to) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index, size_t end_index,
+ const void *elt);
gl_list_node_t (*sortedlist_add) (gl_list_t list,
gl_listelement_compar_fn compar,
const void *elt);
***************
*** 634,639 ****
--- 673,687 ----
->sortedlist_search (list, compar, elt);
}
+ # define gl_sortedlist_search_from_to gl_sortedlist_search_from_to_inline
+ static inline gl_list_node_t
+ gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn
compar, size_t start_index, size_t end_index, const void *elt)
+ {
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_search_from_to (list, compar, start_index, end_index,
+ elt);
+ }
+
# define gl_sortedlist_indexof gl_sortedlist_indexof_inline
static inline size_t
gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const
void *elt)
***************
*** 642,647 ****
--- 690,704 ----
->sortedlist_indexof (list, compar, elt);
}
+ # define gl_sortedlist_indexof_from_to gl_sortedlist_indexof_from_to_inline
+ static inline size_t
+ gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn
compar, size_t start_index, size_t end_index, const void *elt)
+ {
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
+ elt);
+ }
+
# define gl_sortedlist_add gl_sortedlist_add_inline
static inline gl_list_node_t
gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const
void *elt)
diff -c -3 -r1.3 gl_list.c
*** lib/gl_list.c 5 Oct 2006 12:45:16 -0000 1.3
--- lib/gl_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 232,237 ****
--- 232,245 ----
->sortedlist_search (list, compar, elt);
}
+ gl_list_node_t
+ gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn
compar, size_t start_index, size_t end_index, const void *elt)
+ {
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_search_from_to (list, compar, start_index, end_index,
+ elt);
+ }
+
size_t
gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const
void *elt)
{
***************
*** 239,244 ****
--- 247,260 ----
->sortedlist_indexof (list, compar, elt);
}
+ size_t
+ gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn
compar, size_t start_index, size_t end_index, const void *elt)
+ {
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
+ elt);
+ }
+
gl_list_node_t
gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const
void *elt)
{
diff -c -3 -r1.4 gl_anylinked_list2.h
*** lib/gl_anylinked_list2.h 5 Oct 2006 12:45:16 -0000 1.4
--- lib/gl_anylinked_list2.h 6 Oct 2006 12:02:23 -0000
***************
*** 906,911 ****
--- 906,959 ----
return NULL;
}
+ static gl_list_node_t
+ gl_linked_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+ {
+ size_t count = list->count;
+
+ if (!(low <= high && high <= list->count))
+ /* Invalid arguments. */
+ abort ();
+
+ high -= low;
+ if (high > 0)
+ {
+ /* Here we know low < count. */
+ size_t position = low;
+ gl_list_node_t node;
+
+ if (position <= ((count - 1) / 2))
+ {
+ node = list->root.next;
+ for (; position > 0; position--)
+ node = node->next;
+ }
+ else
+ {
+ position = count - 1 - position;
+ node = list->root.prev;
+ for (; position > 0; position--)
+ node = node->prev;
+ }
+
+ do
+ {
+ int cmp = compar (node->value, elt);
+
+ if (cmp > 0)
+ break;
+ if (cmp == 0)
+ return node;
+ node = node->next;
+ }
+ while (--high > 0);
+ }
+ return NULL;
+ }
+
static size_t
gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
***************
*** 927,932 ****
--- 975,1030 ----
return (size_t)(-1);
}
+ static size_t
+ gl_linked_sortedlist_indexof_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+ {
+ size_t count = list->count;
+
+ if (!(low <= high && high <= list->count))
+ /* Invalid arguments. */
+ abort ();
+
+ high -= low;
+ if (high > 0)
+ {
+ /* Here we know low < count. */
+ size_t index = low;
+ size_t position = low;
+ gl_list_node_t node;
+
+ if (position <= ((count - 1) / 2))
+ {
+ node = list->root.next;
+ for (; position > 0; position--)
+ node = node->next;
+ }
+ else
+ {
+ position = count - 1 - position;
+ node = list->root.prev;
+ for (; position > 0; position--)
+ node = node->prev;
+ }
+
+ do
+ {
+ int cmp = compar (node->value, elt);
+
+ if (cmp > 0)
+ break;
+ if (cmp == 0)
+ return index;
+ node = node->next;
+ index++;
+ }
+ while (--high > 0);
+ }
+ return (size_t)(-1);
+ }
+
static gl_list_node_t
gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
diff -c -3 -r1.3 gl_anytree_list2.h
*** lib/gl_anytree_list2.h 5 Oct 2006 12:45:16 -0000 1.3
--- lib/gl_anytree_list2.h 6 Oct 2006 12:02:23 -0000
***************
*** 601,606 ****
--- 601,688 ----
return NULL;
}
+ static gl_list_node_t
+ gl_tree_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+ {
+ gl_list_node_t node;
+
+ if (!(low <= high
+ && high <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+
+ for (node = list->root; node != NULL; )
+ {
+ size_t left_branch_size =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size)
+ {
+ low -= left_branch_size + 1;
+ high -= left_branch_size + 1;
+ node = node->right;
+ }
+ else if (high <= left_branch_size)
+ node = node->left;
+ else
+ {
+ /* Here low <= left_branch_size < high. */
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ {
+ low = 0;
+ high -= left_branch_size + 1;
+ node = node->right;
+ }
+ else if (cmp > 0)
+ node = node->left;
+ else /* cmp == 0 */
+ {
+ /* We have an element equal to ELT. But we need the leftmost
+ such element. */
+ gl_list_node_t found = node;
+ node = node->left;
+ for (; node != NULL; )
+ {
+ size_t left_branch_size2 =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size2)
+ {
+ low -= left_branch_size2 + 1;
+ node = node->right;
+ }
+ else
+ {
+ /* Here low <= left_branch_size2. */
+ int cmp2 = compar (node->value, elt);
+
+ if (cmp2 < 0)
+ {
+ low = 0;
+ node = node->right;
+ }
+ else if (cmp2 > 0)
+ /* The list was not sorted. */
+ abort ();
+ else /* cmp2 == 0 */
+ {
+ found = node;
+ node = node->left;
+ }
+ }
+ }
+ return found;
+ }
+ }
+ }
+ return NULL;
+ }
+
static size_t
gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
***************
*** 656,661 ****
--- 738,829 ----
return (size_t)(-1);
}
+ static size_t
+ gl_tree_sortedlist_indexof_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+ {
+ gl_list_node_t node;
+ size_t position;
+
+ if (!(low <= high
+ && high <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+
+ for (node = list->root, position = 0; node != NULL; )
+ {
+ size_t left_branch_size =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size)
+ {
+ low -= left_branch_size + 1;
+ high -= left_branch_size + 1;
+ position += left_branch_size + 1;
+ node = node->right;
+ }
+ else if (high <= left_branch_size)
+ node = node->left;
+ else
+ {
+ /* Here low <= left_branch_size < high. */
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ {
+ low = 0;
+ high -= left_branch_size + 1;
+ position += left_branch_size + 1;
+ node = node->right;
+ }
+ else if (cmp > 0)
+ node = node->left;
+ else /* cmp == 0 */
+ {
+ /* We have an element equal to ELT. But we need the leftmost
+ such element. */
+ size_t found_position =
+ position + (node->left != NULL ? node->left->branch_size : 0);
+ node = node->left;
+ for (; node != NULL; )
+ {
+ size_t left_branch_size2 =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size2)
+ {
+ low -= left_branch_size2 + 1;
+ node = node->right;
+ }
+ else
+ {
+ /* Here low <= left_branch_size2. */
+ int cmp2 = compar (node->value, elt);
+
+ if (cmp2 < 0)
+ {
+ position += left_branch_size2 + 1;
+ node = node->right;
+ }
+ else if (cmp2 > 0)
+ /* The list was not sorted. */
+ abort ();
+ else /* cmp2 == 0 */
+ {
+ found_position = position + left_branch_size2;
+ node = node->left;
+ }
+ }
+ }
+ return found_position;
+ }
+ }
+ }
+ return (size_t)(-1);
+ }
+
static gl_list_node_t
gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
diff -c -3 -r1.5 gl_array_list.c
*** lib/gl_array_list.c 5 Oct 2006 12:45:16 -0000 1.5
--- lib/gl_array_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 466,481 ****
/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
static size_t
! gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
! const void *elt)
{
! size_t count = list->count;
!
! if (count > 0)
{
- size_t low = 0;
- size_t high = count;
-
/* At each loop iteration, low < high; for indices < low the values
are smaller than ELT; for indices >= high the values are greater
than ELT. So, if the element occurs in the list, it is at
--- 466,481 ----
/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
static size_t
! gl_array_sortedlist_indexof_from_to (gl_list_t list,
! gl_listelement_compar_fn compar,
! size_t low, size_t high,
! const void *elt)
{
! if (!(low <= high && high <= list->count))
! /* Invalid arguments. */
! abort ();
! if (low < high)
{
/* At each loop iteration, low < high; for indices < low the values
are smaller than ELT; for indices >= high the values are greater
than ELT. So, if the element occurs in the list, it is at
***************
*** 524,534 ****
return (size_t)(-1);
}
static gl_list_node_t
gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
{
! size_t index = gl_array_sortedlist_indexof (list, compar, elt);
return INDEX_TO_NODE (index);
}
--- 524,554 ----
return (size_t)(-1);
}
+ static size_t
+ gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+ const void *elt)
+ {
+ return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count,
+ elt);
+ }
+
+ static gl_list_node_t
+ gl_array_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+ {
+ size_t index =
+ gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
+ return INDEX_TO_NODE (index);
+ }
+
static gl_list_node_t
gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
{
! size_t index =
! gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
return INDEX_TO_NODE (index);
}
***************
*** 598,604 ****
--- 618,626 ----
gl_array_iterator_next,
gl_array_iterator_free,
gl_array_sortedlist_search,
+ gl_array_sortedlist_search_from_to,
gl_array_sortedlist_indexof,
+ gl_array_sortedlist_indexof_from_to,
gl_array_sortedlist_add,
gl_array_sortedlist_remove
};
diff -c -3 -r1.3 gl_avltree_list.c
*** lib/gl_avltree_list.c 5 Oct 2006 12:45:16 -0000 1.3
--- lib/gl_avltree_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 91,97 ****
--- 91,99 ----
gl_tree_iterator_next,
gl_tree_iterator_free,
gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
gl_tree_sortedlist_add,
gl_tree_sortedlist_remove
};
diff -c -3 -r1.4 gl_avltreehash_list.c
*** lib/gl_avltreehash_list.c 5 Oct 2006 12:45:16 -0000 1.4
--- lib/gl_avltreehash_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 120,126 ****
--- 120,128 ----
gl_tree_iterator_next,
gl_tree_iterator_free,
gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
gl_tree_sortedlist_add,
gl_tree_sortedlist_remove
};
diff -c -3 -r1.5 gl_carray_list.c
*** lib/gl_carray_list.c 5 Oct 2006 12:45:16 -0000 1.5
--- lib/gl_carray_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 610,625 ****
/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
static size_t
! gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
! const void *elt)
{
! size_t count = list->count;
!
! if (count > 0)
{
- size_t low = 0;
- size_t high = count;
-
/* At each loop iteration, low < high; for indices < low the values
are smaller than ELT; for indices >= high the values are greater
than ELT. So, if the element occurs in the list, it is at
--- 610,625 ----
/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
static size_t
! gl_carray_sortedlist_indexof_from_to (gl_list_t list,
! gl_listelement_compar_fn compar,
! size_t low, size_t high,
! const void *elt)
{
! if (!(low <= high && high <= list->count))
! /* Invalid arguments. */
! abort ();
! if (low < high)
{
/* At each loop iteration, low < high; for indices < low the values
are smaller than ELT; for indices >= high the values are greater
than ELT. So, if the element occurs in the list, it is at
***************
*** 682,692 ****
return (size_t)(-1);
}
static gl_list_node_t
gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
{
! size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
return INDEX_TO_NODE (index);
}
--- 682,712 ----
return (size_t)(-1);
}
+ static size_t
+ gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+ const void *elt)
+ {
+ return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
+ elt);
+ }
+
+ static gl_list_node_t
+ gl_carray_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+ {
+ size_t index =
+ gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
+ return INDEX_TO_NODE (index);
+ }
+
static gl_list_node_t
gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
{
! size_t index =
! gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
return INDEX_TO_NODE (index);
}
***************
*** 763,769 ****
--- 783,791 ----
gl_carray_iterator_next,
gl_carray_iterator_free,
gl_carray_sortedlist_search,
+ gl_carray_sortedlist_search_from_to,
gl_carray_sortedlist_indexof,
+ gl_carray_sortedlist_indexof_from_to,
gl_carray_sortedlist_add,
gl_carray_sortedlist_remove
};
diff -c -3 -r1.3 gl_linked_list.c
*** lib/gl_linked_list.c 5 Oct 2006 12:45:16 -0000 1.3
--- lib/gl_linked_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 58,64 ****
--- 58,66 ----
gl_linked_iterator_next,
gl_linked_iterator_free,
gl_linked_sortedlist_search,
+ gl_linked_sortedlist_search_from_to,
gl_linked_sortedlist_indexof,
+ gl_linked_sortedlist_indexof_from_to,
gl_linked_sortedlist_add,
gl_linked_sortedlist_remove
};
diff -c -3 -r1.5 gl_linkedhash_list.c
*** lib/gl_linkedhash_list.c 5 Oct 2006 12:45:16 -0000 1.5
--- lib/gl_linkedhash_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 115,121 ****
--- 115,123 ----
gl_linked_iterator_next,
gl_linked_iterator_free,
gl_linked_sortedlist_search,
+ gl_linked_sortedlist_search_from_to,
gl_linked_sortedlist_indexof,
+ gl_linked_sortedlist_indexof_from_to,
gl_linked_sortedlist_add,
gl_linked_sortedlist_remove
};
diff -c -3 -r1.3 gl_rbtree_list.c
*** lib/gl_rbtree_list.c 5 Oct 2006 12:45:16 -0000 1.3
--- lib/gl_rbtree_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 92,98 ****
--- 92,100 ----
gl_tree_iterator_next,
gl_tree_iterator_free,
gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
gl_tree_sortedlist_add,
gl_tree_sortedlist_remove
};
diff -c -3 -r1.5 gl_rbtreehash_list.c
*** lib/gl_rbtreehash_list.c 5 Oct 2006 12:45:16 -0000 1.5
--- lib/gl_rbtreehash_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 121,127 ****
--- 121,129 ----
gl_tree_iterator_next,
gl_tree_iterator_free,
gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
gl_tree_sortedlist_add,
gl_tree_sortedlist_remove
};
- 'sublist' module (1/3), Bruno Haible, 2006/10/05
- 'sublist' module (2/3): add bounded list search operations to 'list' modules,
Bruno Haible <=