X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_list.h;h=b97a6a42a3dde50bf1e5e51f25b597b6b87e3dd5;hb=c68c756f05b4d51ffa5a12b391ff996990deee14;hp=6df8bfddc7a9c9c2c8714f80163e1faf1682c5de;hpb=c2f1b9b91eace2249cc9bb9df6c308341310a9b4;p=gnulib.git diff --git a/lib/gl_list.h b/lib/gl_list.h index 6df8bfddc..b97a6a42a 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -68,7 +68,11 @@ extern "C" { 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) @@ -81,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) */ @@ -167,10 +173,37 @@ extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position, 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); @@ -272,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. */ @@ -279,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. */ @@ -299,7 +360,7 @@ extern bool gl_sortedlist_remove (gl_list_t list, struct gl_list_implementation { - // gl_list_t functions. + /* gl_list_t functions. */ gl_list_t (*create_empty) (gl_list_implementation_t implementation, gl_listelement_equals_fn equals_fn, gl_listelement_hashcode_fn hashcode_fn, @@ -315,8 +376,10 @@ struct gl_list_implementation 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 (*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, @@ -329,7 +392,7 @@ struct gl_list_implementation bool (*remove_at) (gl_list_t list, size_t position); bool (*remove) (gl_list_t list, const void *elt); void (*list_free) (gl_list_t list); - // gl_list_iterator_t functions. + /* gl_list_iterator_t functions. */ gl_list_iterator_t (*iterator) (gl_list_t list); gl_list_iterator_t (*iterator_from_to) (gl_list_t list, size_t start_index, @@ -337,13 +400,22 @@ struct gl_list_implementation bool (*iterator_next) (gl_list_iterator_t *iterator, const void **eltp, gl_list_node_t *nodep); void (*iterator_free) (gl_list_iterator_t *iterator); - // Sorted gl_list_t functions. + /* Sorted gl_list_t functions. */ 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); @@ -441,16 +513,54 @@ gl_list_set_at (gl_list_t list, size_t position, const void *elt) 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 (list, elt); + ->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 (list, elt); + ->indexof_from_to (list, start_index, end_index, elt); } # define gl_list_add_first gl_list_add_first_inline @@ -563,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) @@ -571,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)