X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_list.h;h=ca4f476b34f6e3cb693517703ea58ba07627e5ff;hb=8ec8f4b42e39d3aaf2dda06c38b8db00efcc69f5;hp=b935b0f3fb5e0bbbd2e36449609f68ec3f0a2758;hpb=fca2f939ea0d8831cd89f89df4b52a9a47c210f2;p=gnulib.git diff --git a/lib/gl_list.h b/lib/gl_list.h index b935b0f3f..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) @@ -102,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; @@ -122,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. @@ -135,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. @@ -142,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); @@ -151,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); @@ -360,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); @@ -392,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, @@ -400,7 +415,7 @@ 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); @@ -429,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; }; @@ -443,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 @@ -454,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 @@ -477,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)