Mercurial > gnulib
changeset 7403:2fbd1f779c5f
Add a search_atleast operation.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Wed, 04 Oct 2006 17:28:15 +0000 |
| parents | 82dc76cfd521 |
| children | 71b958155bb9 |
| files | lib/ChangeLog lib/gl_anytree_oset.h lib/gl_array_oset.c lib/gl_avltree_oset.c lib/gl_oset.c lib/gl_oset.h lib/gl_rbtree_oset.c |
| diffstat | 7 files changed, 138 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/lib/ChangeLog Wed Oct 04 17:21:22 2006 +0000 +++ b/lib/ChangeLog Wed Oct 04 17:28:15 2006 +0000 @@ -1,3 +1,16 @@ +2006-10-03 Bruno Haible <bruno@clisp.org> + + * gl_oset.h (gl_setelement_threshold_fn): New type. + (gl_oset_search_atleast): New declaration. + (struct gl_oset_implementation): Add field 'search_atleast'. + (gl_oset_search_atleast): New inline function. + * gl_oset.c (gl_oset_search_atleast): New function. + * gl_array_oset.c (gl_array_search_atleast): New function. + (gl_array_oset_implementation): Update. + * gl_anytree_oset.h (gl_tree_search_atleast): New function. + * gl_avltree_oset.c (gl_avltree_oset_implementation): Update. + * gl_rbtree_oset.c (gl_rbtree_oset_implementation): Update. + 2006-10-04 Jim Meyering <jim@meyering.net> * fts.c (fts_open): Tiny comment change.
--- a/lib/gl_anytree_oset.h Wed Oct 04 17:21:22 2006 +0000 +++ b/lib/gl_anytree_oset.h Wed Oct 04 17:28:15 2006 +0000 @@ -73,6 +73,41 @@ return false; } +static bool +gl_tree_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, + const void **eltp) +{ + gl_oset_node_t node; + + for (node = set->root; node != NULL; ) + { + if (! threshold_fn (node->value, threshold)) + node = node->right; + else + { + /* We have an element >= VALUE. But we need the leftmost such + element. */ + gl_oset_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + if (! threshold_fn (node->value, threshold)) + node = node->right; + else + { + found = node; + node = node->left; + } + } + *eltp = found; + return true; + } + } + return false; +} + static gl_oset_node_t gl_tree_search_node (gl_oset_t set, const void *elt) {
--- a/lib/gl_array_oset.c Wed Oct 04 17:21:22 2006 +0000 +++ b/lib/gl_array_oset.c Wed Oct 04 17:28:15 2006 +0000 @@ -105,6 +105,56 @@ return gl_array_indexof (set, elt) != (size_t)(-1); } +static bool +gl_array_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, + const void **eltp) +{ + size_t count = set->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 THRESHOLD; for indices >= high the values are nonexistent. + So, if an element >= THRESHOLD occurs in the list, it is at + low <= position < high. */ + do + { + size_t mid = low + (high - low) / 2; /* low <= mid < high */ + + if (! threshold_fn (set->elements[mid], threshold)) + low = mid + 1; + else + { + /* We have an element >= THRESHOLD at index MID. But we need the + minimal such index. */ + high = mid; + /* At each loop iteration, low <= high and + compar (list->elements[high], value) >= 0, + and we know that the first occurrence of the element is at + low <= position <= high. */ + while (low < high) + { + size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */ + + if (! threshold_fn (set->elements[mid2], threshold)) + low = mid2 + 1; + else + high = mid2; + } + *eltp = set->elements[low]; + return true; + } + } + while (low < high); + } + return false; +} + /* Ensure that set->allocated > set->count. */ static void grow (gl_oset_t set) @@ -273,6 +323,7 @@ gl_array_create_empty, gl_array_size, gl_array_search, + gl_array_search_atleast, gl_array_add, gl_array_remove, gl_array_free,
--- a/lib/gl_avltree_oset.c Wed Oct 04 17:21:22 2006 +0000 +++ b/lib/gl_avltree_oset.c Wed Oct 04 17:28:15 2006 +0000 @@ -565,6 +565,7 @@ gl_tree_create_empty, gl_tree_size, gl_tree_search, + gl_tree_search_atleast, gl_tree_add, gl_tree_remove, gl_tree_oset_free,
--- a/lib/gl_oset.c Wed Oct 04 17:21:22 2006 +0000 +++ b/lib/gl_oset.c Wed Oct 04 17:28:15 2006 +0000 @@ -47,6 +47,15 @@ } bool +gl_oset_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, const void **eltp) +{ + return ((const struct gl_oset_impl_base *) set)->vtable + ->search_atleast (set, threshold_fn, threshold, eltp); +} + +bool gl_oset_add (gl_oset_t set, const void *elt) { return ((const struct gl_oset_impl_base *) set)->vtable->add (set, elt);
--- a/lib/gl_oset.h Wed Oct 04 17:21:22 2006 +0000 +++ b/lib/gl_oset.h Wed Oct 04 17:28:15 2006 +0000 @@ -59,6 +59,7 @@ gl_oset_add O(n) O(log n) gl_oset_remove O(n) O(log n) gl_oset_search O(log n) O(log n) + gl_oset_search_atleast O(log n) O(log n) gl_oset_iterator O(1) O(log n) gl_oset_iterator_next O(1) O(log n) */ @@ -69,6 +70,10 @@ NULL denotes pointer comparison. */ typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2); +/* Type of function used to compare an element with a threshold. + Return true if the element is greater or equal than the threshold. */ +typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold); + struct gl_oset_impl; /* Type representing an entire ordered set. */ typedef struct gl_oset_impl * gl_oset_t; @@ -90,6 +95,16 @@ Return true if found, or false if not present in the set. */ extern bool gl_oset_search (gl_oset_t set, const void *elt); +/* Search the least element in the ordered set that compares greater or equal + to the given THRESHOLD. The representation of the THRESHOLD is defined + by the THRESHOLD_FN. + Return true and store the found element in *ELTP if found, otherwise return + false. */ +extern bool gl_oset_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, + const void **eltp); + /* Add an element to an ordered set. Return true if it was not already in the set and added. */ extern bool gl_oset_add (gl_oset_t set, const void *elt); @@ -143,6 +158,9 @@ gl_setelement_compar_fn compar_fn); size_t (*size) (gl_oset_t set); bool (*search) (gl_oset_t set, const void *elt); + bool (*search_atleast) (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, const void **eltp); bool (*add) (gl_oset_t set, const void *elt); bool (*remove) (gl_oset_t set, const void *elt); void (*oset_free) (gl_oset_t set); @@ -186,6 +204,16 @@ return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt); } +# define gl_oset_search_atleast gl_oset_search_atleast_inline +static inline bool +gl_oset_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, const void **eltp) +{ + return ((const struct gl_oset_impl_base *) set)->vtable + ->search_atleast (set, threshold_fn, threshold, eltp); +} + # define gl_oset_add gl_oset_add_inline static inline bool gl_oset_add (gl_oset_t set, const void *elt)