Mercurial > hg > octave-lyh > gnulib-hg
changeset 7410:9704ff2cbdfe
Add bounded list search operations.
author | Bruno Haible <bruno@clisp.org> |
---|---|
date | Fri, 06 Oct 2006 12:06:07 +0000 |
parents | 830788a4cbd4 |
children | 67235cf9199a |
files | lib/ChangeLog lib/gl_anylinked_list2.h lib/gl_anytree_list2.h lib/gl_array_list.c lib/gl_avltree_list.c lib/gl_avltreehash_list.c lib/gl_carray_list.c lib/gl_linked_list.c lib/gl_linkedhash_list.c lib/gl_list.c lib/gl_list.h lib/gl_rbtree_list.c lib/gl_rbtreehash_list.c |
diffstat | 13 files changed, 442 insertions(+), 18 deletions(-) [+] |
line wrap: on
line diff
--- 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 <eggert@cs.ucla.edu> Fix some Darwin-7.9.0 porting problems reported by Bruno Haible in
--- a/lib/gl_anylinked_list2.h +++ b/lib/gl_anylinked_list2.h @@ -906,6 +906,54 @@ 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 @@ 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)
--- a/lib/gl_anytree_list2.h +++ b/lib/gl_anytree_list2.h @@ -601,6 +601,88 @@ 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 @@ 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)
--- a/lib/gl_array_list.c +++ b/lib/gl_array_list.c @@ -466,16 +466,16 @@ /* ---------------------- 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 @@ 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 @@ 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 };
--- a/lib/gl_avltree_list.c +++ b/lib/gl_avltree_list.c @@ -91,7 +91,9 @@ 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 };
--- a/lib/gl_avltreehash_list.c +++ b/lib/gl_avltreehash_list.c @@ -120,7 +120,9 @@ 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 };
--- a/lib/gl_carray_list.c +++ b/lib/gl_carray_list.c @@ -610,16 +610,16 @@ /* ---------------------- 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 @@ 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 @@ 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 };
--- a/lib/gl_linked_list.c +++ b/lib/gl_linked_list.c @@ -58,7 +58,9 @@ 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 };
--- a/lib/gl_linkedhash_list.c +++ b/lib/gl_linkedhash_list.c @@ -115,7 +115,9 @@ 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 };
--- a/lib/gl_list.c +++ b/lib/gl_list.c @@ -232,6 +232,14 @@ ->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 @@ ->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) {
--- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -85,7 +85,9 @@ 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 @@ /* 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 @@ 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 @@ 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 @@ ->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 @@ ->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)
--- a/lib/gl_rbtree_list.c +++ b/lib/gl_rbtree_list.c @@ -92,7 +92,9 @@ 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 };
--- a/lib/gl_rbtreehash_list.c +++ b/lib/gl_rbtreehash_list.c @@ -121,7 +121,9 @@ 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 };