From fca2f939ea0d8831cd89f89df4b52a9a47c210f2 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Fri, 6 Oct 2006 12:06:07 +0000 Subject: [PATCH] Add bounded list search operations. --- lib/ChangeLog | 29 ++++++++ lib/gl_anylinked_list2.h | 98 +++++++++++++++++++++++++++ lib/gl_anytree_list2.h | 168 ++++++++++++++++++++++++++++++++++++++++++++++ lib/gl_array_list.c | 40 ++++++++--- lib/gl_avltree_list.c | 2 + lib/gl_avltreehash_list.c | 2 + lib/gl_carray_list.c | 40 ++++++++--- lib/gl_linked_list.c | 2 + lib/gl_linkedhash_list.c | 2 + lib/gl_list.c | 16 +++++ lib/gl_list.h | 57 ++++++++++++++++ lib/gl_rbtree_list.c | 2 + lib/gl_rbtreehash_list.c | 2 + 13 files changed, 442 insertions(+), 18 deletions(-) diff --git a/lib/ChangeLog b/lib/ChangeLog index 666478792..0f958a25a 100644 --- a/lib/ChangeLog +++ b/lib/ChangeLog @@ -1,3 +1,32 @@ +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. + 2006-10-05 Paul Eggert Fix some Darwin-7.9.0 porting problems reported by Bruno Haible in diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h index 8368f276e..bc551edd6 100644 --- a/lib/gl_anylinked_list2.h +++ b/lib/gl_anylinked_list2.h @@ -906,6 +906,54 @@ gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, 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,6 +975,56 @@ gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 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 --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h index 00b285bdc..d2ff90081 100644 --- a/lib/gl_anytree_list2.h +++ b/lib/gl_anytree_list2.h @@ -601,6 +601,88 @@ gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, 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,6 +738,92 @@ gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 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 --git a/lib/gl_array_list.c b/lib/gl_array_list.c index 2b604ea6e..7623f02cc 100644 --- a/lib/gl_array_list.c +++ b/lib/gl_array_list.c @@ -466,16 +466,16 @@ gl_array_iterator_free (gl_list_iterator_t *iterator) /* ---------------------- 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) +gl_array_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 (count > 0) + if (!(low <= high && high <= list->count)) + /* Invalid arguments. */ + abort (); + if (low < high) { - 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 @@ -524,11 +524,31 @@ gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 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 (list, compar, elt); + size_t index = + gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); return INDEX_TO_NODE (index); } @@ -598,7 +618,9 @@ const struct gl_list_implementation gl_array_list_implementation = 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 --git a/lib/gl_avltree_list.c b/lib/gl_avltree_list.c index d943ebcd3..d0f0c5ed2 100644 --- a/lib/gl_avltree_list.c +++ b/lib/gl_avltree_list.c @@ -91,7 +91,9 @@ const struct gl_list_implementation gl_avltree_list_implementation = 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 --git a/lib/gl_avltreehash_list.c b/lib/gl_avltreehash_list.c index dbdb58b87..576bf7f53 100644 --- a/lib/gl_avltreehash_list.c +++ b/lib/gl_avltreehash_list.c @@ -120,7 +120,9 @@ const struct gl_list_implementation gl_avltreehash_list_implementation = 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 --git a/lib/gl_carray_list.c b/lib/gl_carray_list.c index 7e22d8e15..755ad6f62 100644 --- a/lib/gl_carray_list.c +++ b/lib/gl_carray_list.c @@ -610,16 +610,16 @@ gl_carray_iterator_free (gl_list_iterator_t *iterator) /* ---------------------- 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) +gl_carray_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 (count > 0) + if (!(low <= high && high <= list->count)) + /* Invalid arguments. */ + abort (); + if (low < high) { - 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 @@ -682,11 +682,31 @@ gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 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 (list, compar, elt); + size_t index = + gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); return INDEX_TO_NODE (index); } @@ -763,7 +783,9 @@ const struct gl_list_implementation gl_carray_list_implementation = 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 --git a/lib/gl_linked_list.c b/lib/gl_linked_list.c index d35e6bc47..546766d59 100644 --- a/lib/gl_linked_list.c +++ b/lib/gl_linked_list.c @@ -58,7 +58,9 @@ const struct gl_list_implementation gl_linked_list_implementation = 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 --git a/lib/gl_linkedhash_list.c b/lib/gl_linkedhash_list.c index 4580cbb38..73c2f448a 100644 --- a/lib/gl_linkedhash_list.c +++ b/lib/gl_linkedhash_list.c @@ -115,7 +115,9 @@ const struct gl_list_implementation gl_linkedhash_list_implementation = 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 --git a/lib/gl_list.c b/lib/gl_list.c index 1cdefe524..cbc765a94 100644 --- a/lib/gl_list.c +++ b/lib/gl_list.c @@ -232,6 +232,14 @@ gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const voi ->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,6 +247,14 @@ gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const vo ->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 --git a/lib/gl_list.h b/lib/gl_list.h index 9ce5aa3af..b935b0f3f 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -85,7 +85,9 @@ extern "C" { 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,6 +305,20 @@ extern gl_list_node_t gl_sortedlist_search (gl_list_t list, /* 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,6 +326,20 @@ extern size_t gl_sortedlist_indexof (gl_list_t list, 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,9 +404,18 @@ struct gl_list_implementation 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,6 +673,15 @@ gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const voi ->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,6 +690,15 @@ gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const vo ->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 --git a/lib/gl_rbtree_list.c b/lib/gl_rbtree_list.c index 3d77827fa..4b9133859 100644 --- a/lib/gl_rbtree_list.c +++ b/lib/gl_rbtree_list.c @@ -92,7 +92,9 @@ const struct gl_list_implementation gl_rbtree_list_implementation = 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 --git a/lib/gl_rbtreehash_list.c b/lib/gl_rbtreehash_list.c index 63eb8768e..9598d148d 100644 --- a/lib/gl_rbtreehash_list.c +++ b/lib/gl_rbtreehash_list.c @@ -121,7 +121,9 @@ const struct gl_list_implementation gl_rbtreehash_list_implementation = 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 }; -- 2.11.0