/* Abstract sequential list data type.
- Copyright (C) 2006 Free Software Foundation, Inc.
+ Copyright (C) 2006-2007 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 2006.
This program is free software; you can redistribute it and/or modify
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);
/* 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);
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
->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