X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_list.h;h=ca4f476b34f6e3cb693517703ea58ba07627e5ff;hb=bd606be378ddd8404641cad023dd43f1f676b26e;hp=9ce5aa3afb343c0d8c639dc044d4fe8a33165648;hpb=407400d9367b16a628b57b2d9b8565bb5a08ffae;p=gnulib.git diff --git a/lib/gl_list.h b/lib/gl_list.h index 9ce5aa3af..ca4f476b3 100644 --- a/lib/gl_list.h +++ b/lib/gl_list.h @@ -1,11 +1,11 @@ /* Abstract sequential list data type. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2008 Free Software Foundation, Inc. Written by Bruno Haible , 2006. - This program is free software; you can redistribute it and/or modify + This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -13,8 +13,7 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software Foundation, - Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + along with this program. If not, see . */ #ifndef _GL_LIST_H #define _GL_LIST_H @@ -63,6 +62,7 @@ extern "C" { gl_list_size O(1) O(1) O(1) O(1) O(1) gl_list_node_value O(1) O(1) O(1) O(1) O(1) + gl_list_node_set_value O(1) O(1) O(1) O(1) O((log n)²)/O(1) gl_list_next_node O(1) O(1) O(log n) O(1) O(log n) gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n) gl_list_get_at O(1) O(n) O(log n) O(n) O(log n) @@ -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); @@ -149,6 +159,10 @@ extern size_t gl_list_size (gl_list_t list); /* Return the element value represented by a list node. */ extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node); +/* Replace the element value represented by a list node. */ +extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node, + const void *elt); + /* Return the node immediately after the given node in the list, or NULL if the given node is the last (rightmost) one in the list. */ extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node); @@ -303,6 +317,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 +338,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,18 +372,21 @@ 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); const void * (*node_value) (gl_list_t list, gl_list_node_t node); + void (*node_set_value) (gl_list_t list, gl_list_node_t node, const void *elt); gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node); 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); @@ -362,7 +407,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 +415,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 +444,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 +459,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 +471,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 @@ -438,6 +495,14 @@ gl_list_node_value (gl_list_t list, gl_list_node_t node) ->node_value (list, node); } +# define gl_list_node_set_value gl_list_node_set_value_inline +static inline void +gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +{ + ((const struct gl_list_impl_base *) list)->vtable + ->node_set_value (list, node, elt); +} + # define gl_list_next_node gl_list_next_node_inline static inline gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node) @@ -634,6 +699,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 +716,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)