X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_list.h;h=e58fc3bcd8906b7bf252e8439d222a3fc5f8ca34;hb=5d0b385594bc914e6233988bfb6bc1b92a2184b5;hp=9ce5aa3afb343c0d8c639dc044d4fe8a33165648;hpb=407400d9367b16a628b57b2d9b8565bb5a08ffae;p=gnulib.git diff --git a/lib/gl_list.h b/lib/gl_list.h index 9ce5aa3af..e58fc3bcd 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -1,5 +1,5 @@ /* Abstract sequential list data type. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2007 Free Software Foundation, Inc. Written by Bruno Haible , 2006. This program is free software; you can redistribute it and/or modify @@ -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) */ @@ -100,6 +102,10 @@ typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2); NULL denotes a function that depends only on the pointer itself. */ typedef size_t (*gl_listelement_hashcode_fn) (const void *elt); +/* Type of function used to dispose an element once it's removed from a list. + NULL denotes a no-op. */ +typedef void (*gl_listelement_dispose_fn) (const void *elt); + struct gl_list_impl; /* Type representing an entire list. */ typedef struct gl_list_impl * gl_list_t; @@ -120,11 +126,13 @@ typedef const struct gl_list_implementation * gl_list_implementation_t; GL_RBTREEHASH_LIST. EQUALS_FN is an element comparison function or NULL. HASHCODE_FN is an element hash code function or NULL. + DISPOSE_FN is an element disposal function or NULL. ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in the list. The implementation may verify this at runtime. */ extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, gl_listelement_equals_fn equals_fn, gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, bool allow_duplicates); /* Create a list with given contents. @@ -133,6 +141,7 @@ extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, GL_RBTREEHASH_LIST. EQUALS_FN is an element comparison function or NULL. HASHCODE_FN is an element hash code function or NULL. + DISPOSE_FN is an element disposal function or NULL. ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in the list. The implementation may verify this at runtime. COUNT is the number of initial elements. @@ -140,6 +149,7 @@ extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, extern gl_list_t gl_list_create (gl_list_implementation_t implementation, gl_listelement_equals_fn equals_fn, gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, bool allow_duplicates, size_t count, const void **contents); @@ -303,6 +313,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 +334,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. */ @@ -330,14 +368,16 @@ 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, + gl_listelement_dispose_fn dispose_fn, bool allow_duplicates); gl_list_t (*create) (gl_list_implementation_t implementation, gl_listelement_equals_fn equals_fn, gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, bool allow_duplicates, size_t count, const void **contents); size_t (*size) (gl_list_t list); @@ -362,7 +402,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, @@ -370,13 +410,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); @@ -390,6 +439,7 @@ struct gl_list_impl_base const struct gl_list_implementation *vtable; gl_listelement_equals_fn equals_fn; gl_listelement_hashcode_fn hashcode_fn; + gl_listelement_dispose_fn dispose_fn; bool allow_duplicates; }; @@ -404,10 +454,11 @@ static inline gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, gl_listelement_equals_fn equals_fn, gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, bool allow_duplicates) { return implementation->create_empty (implementation, equals_fn, hashcode_fn, - allow_duplicates); + dispose_fn, allow_duplicates); } # define gl_list_create gl_list_create_inline @@ -415,11 +466,12 @@ static inline gl_list_t gl_list_create (gl_list_implementation_t implementation, gl_listelement_equals_fn equals_fn, gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, bool allow_duplicates, size_t count, const void **contents) { return implementation->create (implementation, equals_fn, hashcode_fn, - allow_duplicates, count, contents); + dispose_fn, allow_duplicates, count, contents); } # define gl_list_size gl_list_size_inline @@ -634,6 +686,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 +703,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)