/* Abstract sequential list data type.
- Copyright (C) 2006 Free Software Foundation, Inc.
+ Copyright (C) 2006-2008 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)
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)
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)
*/
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);
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);
/* 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. */
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. */
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);
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,
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,
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);
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)
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 (list, elt);
+ ->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_from_to (list, start_index, end_index, elt);
}
# define gl_list_add_first gl_list_add_first_inline
->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)
->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)
projects / gnulib.git / blobdiff