/* Abstract sequential list data type.
- Copyright (C) 2006 Free Software Foundation, Inc.
+ Copyright (C) 2006-2009 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 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
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 <http://www.gnu.org/licenses/>. */
#ifndef _GL_LIST_H
#define _GL_LIST_H
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)
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;
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.
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.
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);
/* 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);
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);
const void *elt);
bool (*remove_node) (gl_list_t list, gl_list_node_t node);
bool (*remove_at) (gl_list_t list, size_t position);
- bool (*remove) (gl_list_t list, const void *elt);
+ bool (*remove_elt) (gl_list_t list, const void *elt);
void (*list_free) (gl_list_t list);
/* gl_list_iterator_t functions. */
gl_list_iterator_t (*iterator) (gl_list_t list);
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;
};
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
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
->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)
gl_list_remove (gl_list_t list, const void *elt)
{
return ((const struct gl_list_impl_base *) list)->vtable
- ->remove (list, elt);
+ ->remove_elt (list, elt);
}
# define gl_list_free gl_list_free_inline