libslack(list) - list module
#include <slack/std.h> #include <slack/list.h> typedef struct List List; typedef struct Lister Lister; typedef void list_release_t(void *item); typedef void *list_copy_t(const void *item); typedef int list_cmp_t(const void *a, const void *b); typedef void list_action_t(void *item, size_t *index, void *data); typedef void *list_map_t(void *item, size_t *index, void *data); typedef int list_query_t(void *item, size_t *index, void *data); List *list_create(list_release_t *destroy); List *list_make(list_release_t *destroy, ...); List *list_vmake(list_release_t *destroy, va_list args); List *list_copy(const List *src, list_copy_t *copy); List *list_create_with_locker(Locker *locker, list_release_t *destroy); List *list_make_with_locker(Locker *locker, list_release_t *destroy, ...); List *list_vmake_with_locker(Locker *locker, list_release_t *destroy, va_list args); List *list_copy_with_locker(Locker *locker, const List *src, list_copy_t *copy); int list_rdlock(const List *list); int list_wrlock(const List *list); int list_unlock(const List *list); void list_release(List *list); void *list_destroy(List **list); int list_own(List *list, list_release_t *destroy); int list_own_unlocked(List *list, list_release_t *destroy); list_release_t *list_disown(List *list); list_release_t *list_disown_unlocked(List *list); void *list_item(const List *list, ssize_t index); void *list_item_unlocked(const List *list, ssize_t index); int list_item_int(const List *list, ssize_t index); int list_item_int_unlocked(const List *list, ssize_t index); int list_empty(const List *list); int list_empty_unlocked(const List *list); ssize_t list_length(const List *list); ssize_t list_length_unlocked(const List *list); ssize_t list_last(const List *list); ssize_t list_last_unlocked(const List *list); List *list_remove(List *list, ssize_t index); List *list_remove_unlocked(List *list, ssize_t index); List *list_remove_range(List *list, ssize_t index, ssize_t range); List *list_remove_range_unlocked(List *list, ssize_t index, ssize_t range); List *list_insert(List *list, ssize_t index, void *item); List *list_insert_unlocked(List *list, ssize_t index, void *item); List *list_insert_int(List *list, ssize_t index, int item); List *list_insert_int_unlocked(List *list, ssize_t index, int item); List *list_insert_list(List *list, ssize_t index, const List *src, list_copy_t *copy); List *list_insert_list_unlocked(List *list, ssize_t index, const List *src, list_copy_t *copy); List *list_append(List *list, void *item); List *list_append_unlocked(List *list, void *item); List *list_append_int(List *list, int item); List *list_append_int_unlocked(List *list, int item); List *list_append_list(List *list, const List *src, list_copy_t *copy); List *list_append_list_unlocked(List *list, const List *src, list_copy_t *copy); List *list_prepend(List *list, void *item); List *list_prepend_unlocked(List *list, void *item); List *list_prepend_int(List *list, int item); List *list_prepend_int_unlocked(List *list, int item); List *list_prepend_list(List *list, const List *src, list_copy_t *copy); List *list_prepend_list_unlocked(List *list, const List *src, list_copy_t *copy); List *list_replace(List *list, ssize_t index, ssize_t range, void *item); List *list_replace_unlocked(List *list, ssize_t index, ssize_t range, void *item); List *list_replace_int(List *list, ssize_t index, ssize_t range, int item); List *list_replace_int_unlocked(List *list, ssize_t index, ssize_t range, int item); List *list_replace_list(List *list, ssize_t index, ssize_t range, const List *src, list_copy_t *copy); List *list_replace_list_unlocked(List *list, ssize_t index, ssize_t range, const List *src, list_copy_t *copy); List *list_extract(const List *list, ssize_t index, ssize_t range, list_copy_t *copy); List *list_extract_unlocked(const List *list, ssize_t index, ssize_t range, list_copy_t *copy); List *list_extract_with_locker(Locker *locker, const List *list, ssize_t index, ssize_t range, list_copy_t *copy); List *list_extract_with_locker_unlocked(Locker *locker, const List *list, ssize_t index, ssize_t range, list_copy_t *copy); List *list_push(List *list, void *item); List *list_push_unlocked(List *list, void *item); List *list_push_int(List *list, int item); List *list_push_int_unlocked(List *list, int item); void *list_pop(List *list); void *list_pop_unlocked(List *list); int list_pop_int(List *list); int list_pop_int_unlocked(List *list); void *list_shift(List *list); void *list_shift_unlocked(List *list); int list_shift_int(List *list); int list_shift_int_unlocked(List *list); List *list_unshift(List *list, void *item); List *list_unshift_unlocked(List *list, void *item); List *list_unshift_int(List *list, int item); List *list_unshift_int_unlocked(List *list, int item); List *list_splice(List *list, ssize_t index, ssize_t range, list_copy_t *copy); List *list_splice_unlocked(List *list, ssize_t index, ssize_t range, list_copy_t *copy); List *list_splice_with_locker(Locker *locker, List *list, ssize_t index, ssize_t range, list_copy_t *copy); List *list_splice_with_locker_unlocked(Locker *locker, List *list, ssize_t index, ssize_t range, list_copy_t *copy); List *list_sort(List *list, list_cmp_t *cmp); List *list_sort_unlocked(List *list, list_cmp_t *cmp); void list_apply(List *list, list_action_t *action, void *data); void list_apply_rdlocked(List *list, list_action_t *action, void *data); void list_apply_wrlocked(List *list, list_action_t *action, void *data); void list_apply_unlocked(List *list, list_action_t *action, void *data); List *list_map(List *list, list_release_t *destroy, list_map_t *map, void *data); List *list_map_unlocked(List *list, list_release_t *destroy, list_map_t *map, void *data); List *list_map_with_locker(Locker *locker, List *list, list_release_t *destroy, list_map_t *map, void *data); List *list_map_with_locker_unlocked(Locker *locker, List *list, list_release_t *destroy, list_map_t *map, void *data); List *list_grep(List *list, list_query_t *grep, void *data); List *list_grep_unlocked(List *list, list_query_t *grep, void *data); List *list_grep_with_locker(Locker *locker, List *list, list_query_t *grep, void *data); List *list_grep_with_locker_unlocked(Locker *locker, List *list, list_query_t *grep, void *data); ssize_t list_query(List *list, ssize_t *index, list_query_t *query, void *data); ssize_t list_query_unlocked(List *list, ssize_t *index, list_query_t *query, void *data); Lister *lister_create(List *list); Lister *lister_create_rdlocked(List *list); Lister *lister_create_wrlocked(List *list); Lister *lister_create_unlocked(const List *list); void lister_release(Lister *lister); void lister_release_unlocked(Lister *lister); void *lister_destroy(Lister **lister); void *lister_destroy_unlocked(Lister **lister); int lister_has_next(Lister *lister); void *lister_next(Lister *lister); int lister_next_int(Lister *lister); void lister_remove(Lister *lister); int list_has_next(List *list); void list_break(List *list); void *list_next(List *list); int list_next_int(List *list); void list_remove_current(List *list);
This module provides functions for manipulating and iterating over lists of
homogeneous data (or heterogeneous data if it's polymorphic). Lists may
own their items. Lists created with a non-null
destroy function use
that function to destroy an item when it is removed from the list and to
destroy each item when the list itself is destroyed. Be careful not to
insert items owned by one list into a list that doesn't own its own items
unless you know that the source list (and all of the shared items) will
outlive the destination list.
List *list_create(list_release_t *destroy)
Creates a List with destroy
as its item destructor. It is the caller's
responsibility to deallocate the new list with list_release(3) or
list_destroy(3). On success, returns the new list. On error, returns
null
with errno
set appropriately.
List *list_make(list_release_t *destroy, ...)
Creates a List with destroy
as its item destructor and the remaining
arguments as its initial items. It is the caller's responsibility to
deallocate the new list with list_release(3) or list_destroy(3). On
success, returns the new list. On error, return null
with errno
set
appropriately.
List *list_vmake(list_release_t *destroy, va_list args)
Equivalent to list_make(3) with the variable argument list specified directly as for vprintf(3).
List *list_copy(const List *src, list_copy_t *copy)
Creates a copy of src
using copy
as the copy constructor (if not
null
). It is the caller's responsibility to deallocate the new list with
list_release(3) or list_destroy(3). On success, returns the new copy.
On error, returns null
with errno
set appropriately.
List *list_create_with_locker(Locker *locker, list_release_t *destroy)
Equivalent to list_create(3) except that multiple threads accessing the
new list will be synchronised by locker
.
List *list_make_with_locker(Locker *locker, list_release_t *destroy, ...)
Equivalent to list_make(3) except that multiple threads accessing the new
list will be synchronised by locker
.
List *list_vmake_with_locker(Locker *locker, list_release_t *destroy, va_list args)
Equivalent to list_vmake(3) except that multiple threads accessing the
new list will be synchronised by locker
.
List *list_copy_with_locker(Locker *locker, const List *src, list_copy_t *copy)
Equivalent to list_copy(3) except that multiple threads accessing the new
list will be synchronised by locker
.
int list_rdlock(const List *list)
Claims a read lock on list
(if list
was created with a Locker).
This is needed when multiple read only list(3) module functions need to
be called atomically. It is the client's responsibility to call
list_unlock(3) after the atomic operation. The only functions that may be
called on list
between calls to list_rdlock(3) and list_unlock(3)
are any read only list(3) module functions whose name ends with
_unlocked
. On success, returns 0
. On error, returns an error code.
int list_wrlock(const List *list)
Claims a write lock on list
(if list
was created with a Locker).
This is needed when multiple read/write list(3) module functions need to
be called atomically. It is the client's responsibility to call
list_unlock(3) after the atomic operation. The only functions that may be
called on list
between calls to list_wrlock(3) and list_unlock(3)
are any list(3) module functions whose name ends with _unlocked
. On
success, returns 0
. On error, returns an error code.
int list_unlock(const List *list)
Unlocks a read or write lock on list
obtained with list_rdlock(3) or
list_wrlock(3) (if list
was created with a locker
). On success,
returns 0
. On error, returns an error code.
void list_release(List *list)
Releases (deallocates) list
, destroying its items if necessary. On error,
sets errno
appropriately.
void *list_destroy(List **list)
Destroys (deallocates and sets to null
) *list
. Returns null
.
Note: lists shared by multiple threads must not be destroyed until after
all threads have finished with it.
int list_own(List *list, list_release_t *destroy)
Causes list
to take ownership of its items. The items will be destroyed
using destroy
when they are removed or when list
is destroyed. On
success, returns 0
. On error, returns -1
with errno
set
appropriately.
int list_own_unlocked(List *list, list_release_t *destroy)
Equivalent to list_own(3) except that list
is not write locked.
list_release_t *list_disown(List *list)
Causes list
to relinquish ownership of its items. The items will not be
destroyed when they are removed from list
or when list
is destroyed.
On success, returns the previous destroy function, if any. On error, returns
null
with errno
set appropriately.
list_release_t *list_disown_unlocked(List *list)
Equivalent to list_disown(3) except that list
is not write locked.
void *list_item(const List *list, ssize_t index)
Returns the index
'th item in list
. If index
is negative, it refers
to an item position relative to the end of the list (-1
is the position
after the last item, -2
is the position of the last item and so on). On
error, returns null
with errno
set appropriately.
void *list_item_unlocked(const List *list, ssize_t index)
Equivalent to list_item(3) except that list
is not read locked.
int list_item_int(const List *list, ssize_t index)
Equivalent to list_item(3) except that the item is cast to an integer type.
int list_item_int_unlocked(const List *list, ssize_t index)
Equivalent to list_item_int(3) except that list
is not read locked.
int list_empty(const List *list)
Returns whether or not list
is empty. On error, returns -1
with
errno
set appropriately.
int list_empty_unlocked(const List *list)
Equivalent to list_empty(3) except that list
is not read locked.
ssize_t list_length(const List *list)
Returns the length of list
. On error, returns -1
with errno
set
appropriately.
ssize_t list_length_unlocked(const List *list)
Equivalent to list_length(3) except that list
is not read locked.
ssize_t list_last(const List *list)
Returns the index of the last item in list
, or -1
if there are no
items. On error, returns -1
with errno
set appropriately.
ssize_t list_last_unlocked(const List *list)
Equivalent to list_last(3) except that list
is not read locked.
List *list_remove(List *list, ssize_t index)
Removes the index
'th item from list
. If index
is negative, it
refers to an item position relative to the end of the list (-1
is the
position after the last item, -2
is the position of the last item and so
on). On success, returns list
. On error, returns null
with errno
set appropriately.
List *list_remove_unlocked(List *list, ssize_t index)
Equivalent to list_remove(3) except that list
is not write locked.
List *list_remove_range(List *list, ssize_t index, ssize_t range)
Removes range
items from list
starting at index
. If index
or
range
are negative, they refer to item positions relative to the end of
the list (-1
is the position after the last item, -2
is the position
of the last item and so on). On success, returns list
. On error, returns
null
with errno
set appropriately.
List *list_remove_range_unlocked(List *list, ssize_t index, ssize_t range)
Equivalent to list_remove_range(3) except that list
is not write
locked.
List *list_insert(List *list, ssize_t index, void *item)
Adds item
to list
at position index
. If index
is negative, it
refers to an item position relative to the end of the list (-1
is the
position after the last item, -2
is the position of the last item and so
on). On success, returns list
. On error, returns null
with errno
set appropriately.
List *list_insert_unlocked(List *list, ssize_t index, void *item)
Equivalent to list_insert(3) except that list
is not write locked.
List *list_insert_int(List *list, ssize_t index, int item)
Equivalent to list_insert(3) except that item
is an integer type.
List *list_insert_int_unlocked(List *list, ssize_t index, int item)
Equivalent to list_insert_int(3) except that list
is not write locked.
List *list_insert_list(List *list, ssize_t index, const List *src, list_copy_t *copy)
Inserts the items from src
into list
, starting at position index
using copy
as the copy constructor (if not null
). If index
is
negative, it refers to an item position relative to the end of the list
(-1
is the position after the last item, -2
is the position of the
last item and so on). On success, returns list
. On error, returns null
with errno
set appropriately.
List *list_insert_list_unlocked(List *list, ssize_t index, const List *src, list_copy_t *copy)
Equivalent to list_insert_list(3) except that list
is not write locked
and src
is not read locked. Note: If src
needs to be read locked, it
is the caller's responsibility to lock and unlock it explicitly with
list_rdlock(3) and list_unlock(3).
List *list_append(List *list, void *item)
Appends item
to list
. On success, returns list
. On error, returns
null
with errno
set appropriately.
List *list_append_unlocked(List *list, void *item)
Equivalent to list_append(3) except that list
is not write locked.
List *list_append_int(List *list, int item)
Equivalent to list_append(3) except that item
is an integer.
List *list_append_int_unlocked(List *list, int item)
Equivalent to list_append_int(3) except that list
is not write locked.
List *list_append_list(List *list, const List *src, list_copy_t *copy)
Appends the items in src
to list
using copy
as the copy constructor
(if not null
). On success, returns list
. On error, returns null
with errno
set appropriately.
List *list_append_list_unlocked(List *list, const List *src, list_copy_t *copy)
Equivalent to list_append_list(3) except that list
is not write
locked.
List *list_prepend(List *list, void *item)
Prepends item
to list
. On success, returns list
. On error, returns
null
with errno
set appropriately.
List *list_prepend_unlocked(List *list, void *item)
Equivalent to list_prepend(3) except that list
is not write locked.
List *list_prepend_int(List *list, int item)
Equivalent to list_prepend(3) except that item
is an integer.
List *list_prepend_int_unlocked(List *list, int item)
Equivalent to list_prepend_int(3) except that list
is not write
locked.
List *list_prepend_list(List *list, const List *src, list_copy_t *copy)
Prepends the items in src
to list
using copy
as the copy
constructor (if not null
). On success, returns list
. On error, returns
null
with errno
set appropriately.
List *list_prepend_list_unlocked(List *list, const List *src, list_copy_t *copy)
Equivalent to list_prepend_list(3) except that list
is not write
locked.
List *list_replace(List *list, ssize_t index, ssize_t range, void *item)
Replaces range
items in list
, starting at index
, with item
. If
index
or range
are negative, they refer to item positions relative to
the end of the list (-1
is the position after the last item, -2
is the
position of the last item and so on). On success, returns list
. On error,
returns null
with errno
set appropriately.
List *list_replace_unlocked(List *list, ssize_t index, ssize_t range, void *item)
Equivalent to list_replace(3) except that list
is not write locked.
List *list_replace_int(List *list, ssize_t index, ssize_t range, int item)
Equivalent to list_replace(3) except that item
is an integer type.
List *list_replace_int_unlocked(List *list, ssize_t index, ssize_t range, int item)
Equivalent to list_replace_int(3) except that list
is not write locked.
List *list_replace_list(List *list, ssize_t index, ssize_t range, const List *src, list_copy_t *copy)
Replaces range
items in list
, starting at index
, with the items in
src
using copy
as the copy constructor (if not null
). If index
or range
are negative, they refer to item positions relative to the end
of the list (-1
is the position after the last item, -2
is the
position of the last item and so on). On success, return list
. On error,
returns null
with errno
set appropriately.
List *list_replace_list_unlocked(List *list, ssize_t index, ssize_t range, const List *src, list_copy_t *copy)
Equivalent to list_replace_list(3) except that list
is not write
locked and src
is not read locked. Note: If src
needs to be read
locked, it is the caller's responsibility to lock and unlock it explicitly
with list_rdlock(3) and list_unlock(3).
List *list_extract(const List *list, ssize_t index, ssize_t range, list_copy_t *copy)
Creates a new list consisting of range
items from list
, starting at
index
, using copy
as the copy constructor (if not null
). If
index
or range
are negative, they refer to item positions relative to
the end of the list (-1
is the position after the last item, -2
is the
position of the last item and so on). It is the caller's responsibility to
deallocate the new list with list_release(3) or list_destroy(3). On
success, returns the new list. On error, returns null
with errno
set
appropriately.
List *list_extract_unlocked(const List *list, ssize_t index, ssize_t range, list_copy_t *copy)
Equivalent to list_extract(3) except that list
is not read locked.
List *list_extract_with_locker(Locker *locker, const List *list, ssize_t index, ssize_t range, list_copy_t *copy)
Equivalent to list_extract(3) except that multiple threads accessing the
new list will be synchronised by locker
.
List *list_extract_with_locker_unlocked(Locker *locker, const List *list, ssize_t index, ssize_t range, list_copy_t *copy)
Equivalent to list_extract_with_locker(3) except that list
is not read
locked.
List *list_push(List *list, void *item)
Pushes item
onto the end of list
. On success, returns list
. On
error, returns null
with errno
set appropriately.
List *list_push_unlocked(List *list, void *item)
Equivalent to list_push(3) except that list
is not write locked.
List *list_push_int(List *list, int item)
Equivalent to list_push(3) except that item
is an integer.
List *list_push_int_unlocked(List *list, int item)
Equivalent to list_push_int(3) except that list
is not write locked.
void *list_pop(List *list)
Pops the last item off list
. On success, returns the item popped. On
error, returns null
with errno
set appropriately.
void *list_pop_unlocked(List *list)
Equivalent to list_pop(3) except that list
is not write locked.
int list_pop_int(List *list)
Equivalent to list_pop(3) except that the item popped has an integer type.
int list_pop_int_unlocked(List *list)
Equivalent to list_pop_int(3) except that list
is not write locked.
void *list_shift(List *list)
Removes and returns the first item in list
. On success, returns the item
shifted. On error, returns null
with errno
set appropriately.
void *list_shift_unlocked(List *list)
Equivalent to list_shift(3) except that list
is not write locked.
int list_shift_int(List *list)
Equivalent to list_shift(3) except that the item shifted has an integer type.
int list_shift_int_unlocked(List *list)
Equivalent to list_shift_int(3) except that list
is not write locked.
List *list_unshift(List *list, void *item)
Inserts item
at the start of list
. On success, returns list
. On
error, returns null
with errno
set appropriately.
List *list_unshift_unlocked(List *list, void *item)
Equivalent to list_unshift(3) except that list
is not write locked.
List *list_unshift_int(List *list, int item)
Equivalent to list_unshift(3) except that item
is an integer.
List *list_unshift_int_unlocked(List *list, int item)
Equivalent to list_unshift_int(3) except that list
is not write
locked.
List *list_splice(List *list, ssize_t index, ssize_t range, list_copy_t *copy)
Removes a sublist from list
starting at index
with length range
after copying the items with copy
(if not null
). If index
or
range
are negative, they refer to item positions relative to the end of
the list (-1
is the position after the last item, -2
is the position
of the last item and so on). On success, returns the sublist. It is the
caller's responsibility to deallocate the new list with list_release(3)
or list_destroy(3). On error, returns null
with errno
set
appropriately.
List *list_splice_unlocked(List *list, ssize_t index, ssize_t range, list_copy_t *copy)
Equivalent to list_splice(3) except that list
is not write locked.
List *list_splice_with_locker(Locker *locker, List *list, ssize_t index, ssize_t range, list_copy_t *copy)
Equivalent to list_splice(3) except that multiple threads accessing the
new list will be synchronised by locker
.
List *list_splice_with_locker_unlocked(Locker *locker, List *list, ssize_t index, ssize_t range, list_copy_t *copy)
Equivalent to list_splice_with_locker(3) except that list
is not write
locked.
List *list_sort(List *list, list_cmp_t *cmp)
Sorts the items in list
using the item comparison function cmp
and
qsort(3) for lists of fewer than 10000 items and hsort(3) for larger
lists. On success, returns list
. On error, returns null
with errno
set appropriately.
List *list_sort_unlocked(List *list, list_cmp_t *cmp)
Equivalent to list_sort(3) except that list
is not write locked.
void list_apply(List *list, list_action_t *action, void *data)
Invokes action
for each of list
's items. The arguments passed to
action
are the item, a pointer to the loop variable containing the item's
position within list
and data
. On error, sets errno
appropriately.
void list_apply_rdlocked(List *list, list_action_t *action, void *data)
Equivalent to list_apply(3) except that list
is read locked rather
than write locked. Use this in preference to list_apply(3) when list
and its items will not be modified during the iteration.
void list_apply_wrlocked(List *list, list_action_t *action, void *data)
Equivalent to list_apply(3) except that this function name makes the fact
that list
is write locked explicit.
void list_apply_unlocked(List *list, list_action_t *action, void *data)
Equivalent to list_apply(3) except that list
is not write locked.
List *list_map(List *list, list_release_t *destroy, list_map_t *map, void *data)
Creates and returns a new list containing the return values of map
,
invoked once for each item in list
. The arguments passed to map
are
the item, a pointer to the loop variable containing the item's position
within list
and data
. destroy
will be the item destructor for the
new list. It is the caller's responsibility to deallocate the new list with
list_release(3) or list_destroy(3). On success, returns the new list.
On error, returns null
with errno
set appropriately.
List *list_map_unlocked(List *list, list_release_t *destroy, list_map_t *map, void *data)
Equivalent to list_map(3) except that list
is not read locked.
List *list_map_with_locker(Locker *locker, List *list, list_release_t *destroy, list_map_t *map, void *data)
Equivalent to list_map(3) except that multiple threads accessing the new
list will be synchronised by locker
.
List *list_map_with_locker_unlocked(Locker *locker, List *list, list_release_t *destroy, list_map_t *map, void *data)
Equivalent to list_map_with_locker(3) except that list
is not read
locked.
List *list_grep(List *list, list_query_t *grep, void *data)
Creates and returns a new list by invoking grep
for each item in list
,
and appending the items for which grep
returned a non-zero value. The
arguments passed to grep
are the item, a pointer to the loop variable
containing the item's position within list
and data
. It is the
caller's responsibility to deallocate the new list with list_release(3)
or list_destroy(3). Note that the new list does not own its items since
it does not copy them. On success, returns the new list. On error, returns
null
with errno
set appropriately.
List *list_grep_unlocked(List *list, list_query_t *grep, void *data)
Equivalent to list_grep(3) except that list
is not read locked.
List *list_grep_with_locker(Locker *locker, List *list, list_query_t *grep, void *data)
Equivalent to list_grep(3) except that multiple threads accessing the new
list will be synchronised by locker
.
List *list_grep_with_locker_unlocked(Locker *locker, List *list, list_query_t *grep, void *data)
Equivalent to list_grep_with_locker(3) except that list
is not read
locked.
ssize_t list_query(List *list, ssize_t *index, list_query_t *query, void *data)
Invokes query
on each item in list
, starting at *index
until
query
returns a non-zero value. The arguments passed to query
are the
item, index
and data
. Returns the index of the item that satisfied
query
, or -1
when query
is not satisfied by any remaining items.
The value pointed to by index
is set to the return value. On error, sets
errno
appropriately.
ssize_t list_query_unlocked(List *list, ssize_t *index, list_query_t *query, void *data)
Equivalent to list_query(3) except that list
is not read locked.
Lister *lister_create(List *list)
Creates an iterator for list
. It is the caller's responsibility to
deallocate the iterator with lister_release(3) or lister_destroy(3).
The iterator keeps list
write locked until it is released with
lister_release(3) or lister_destroy(3). Note that the iterator itself
is not locked so it must not be shared between threads. On success, returns
the iterator. On error, returns null
with errno
set appropriately.
Lister *lister_create_rdlocked(List *list)
Equivalent to lister_create(3) except that list
is read locked rather
than write locked. Use this in preference to lister_create(3) when no
calls to lister_remove(3) will be made during the iteration.
Lister *lister_create_wrlocked(List *list)
Equivalent to lister_create(3) except that this function name makes the
fact that list
is write locked explicit.
Lister *lister_create_unlocked(const List *list)
Equivalent to lister_create(3) except that list
is not write locked.
void lister_release(Lister *lister)
Releases (deallocates) lister
and unlocks the associated list.
void lister_release_unlocked(Lister *lister)
Equivalent to lister_release(3) except that the associated list is not unlocked.
void *lister_destroy(Lister **lister)
Destroys (deallocates and sets to null
) *lister
and unlocks the
associated list. Returns null
. On error, sets errno
appropriately.
void *lister_destroy_unlocked(Lister **lister)
Equivalent to lister_destroy(3) except that the associated list is not unlocked.
int lister_has_next(Lister *lister)
Returns whether or not there is another item in the list over which
lister
is iterating. On error, returns -1
with errno
set
appropriately.
void *lister_next(Lister *lister)
Returns the next item in the iteration, lister
. On error, returns null
with errno
set appropriately.
int lister_next_int(Lister *lister)
Equivalent to lister_next(3) except that the item returned is an integer.
void lister_remove(Lister *lister)
Removes the current item in the iteration, lister
. The next item in the
iteration is the item following the removed item, if any. This must be
called after lister_next(3) or lister_next_int(3). On error, sets
errno
appropriately.
int list_has_next(List *list)
Returns whether or not there is another item in list
using an internal
iterator. The first time this is called, a new internal Lister will be
created (Note: There can be only one). When there are no more items, returns
0
and destroys the internal iterator. When it returns 1
, use
list_next(3) or list_next_int(3) to retrieve the next item. On error,
returns -1
with errno
set appropriately.
Note: If an iteration using an internal iterator terminates before the end
of the list, it is the caller's responsibility to call list_break(3).
Failure to do so will cause the internal iterator to leak. It will also
break the next call to list_has_next(3) which will continue where the
current iteration stopped rather than starting at the beginning again.
list_release(3) assumes that there is no internal iterator so it is the
caller's responsibility to complete the iteration or call list_break(3)
before releasing list
with list_release(3) or list_destroy(3).
Note: The internal Lister does not lock list
so this function is not
threadsafe. It can only be used with lists created in the current function
(to guarantee that no other thread can access it). This practice should be
observed even in single threaded applications to avoid breaking iterator
semantics (possible with nested function calls). If list
is a parameter
or a variable declared outside the function, it is best to create an
explicit Lister instead. If this function is used on such lists instead,
it is the caller's responsibility to explicitly lock list
first with
list_wrlock(3) and explicitly unlock it with list_unlock(3). Do this
even if you are writing single threaded code in case your function may one
day be used in a multi threaded application.
void list_break(List *list)
Unlocks list
and destroys its internal iterator. Must be used only when
an iteration using an internal iterator has terminated before reaching the
end of list
. On error, returns null
with errno
set appropriately.
void *list_next(List *list)
Returns the next item in list
using it's internal iterator. On error,
returns null
with errno
set appropriately.
int list_next_int(List *list)
Equivalent to list_next(3) except that the item returned is an integer.
void list_remove_current(List *list)
Removes the current item in list
using it's internal iterator. The next
item in the iteration is the item following the removed item, if any. This
must be called after list_next(3). On error, sets errno
appropriately.
On error, errno
is set either by an underlying function, or as follows:
EINVAL
When arguments are null
or out of range.
MT-Disciplined
By default, Lists are not MT-Safe because most programs are single threaded and synchronisation doesn't come for free. Even in multi threaded programs, not all Lists are necessarily shared between multiple threads.
When a List is shared between multiple threads which need to be synchronised, the method of synchronisation must be carefully selected by the client code. There are tradeoffs between concurrency and overhead. The greater the concurrency, the greater the overhead. More locks give greater concurrency but have greater overhead. Readers/Writer locks can give greater concurrency than mutex locks but have greater overhead. One lock for each List may be required, or one lock for all (or a set of) Lists may be more appropriate.
Generally, the best synchronisation strategy for a given application can only be determined by testing/benchmarking the written application. It is important to be able to experiment with the synchronisation strategy at this stage of development without pain.
To facilitate this, Lists can be created with list_create_with_locker(3) which takes a Locker argument. The Locker specifies a lock and a set of functions for manipulating the lock. Each List can have it's own lock by creating a separate Locker for each List. Multiple Lists can share the same lock by sharing the same Locker. Only the application developer can determine what is appropriate for each application on a case by case basis.
MT-Disciplined means that the application developer has a mechanism for specifying the synchronisation requirements to be applied to library code.
Create a list that doesn't own its items, populate it and then iterate over its values with the internal iterator to print the values:
#include <slack/std.h> #include <slack/list.h> int main() { List *list; if (!(list = list_create(NULL))) return EXIT_FAILURE; list_append(list, "123"); list_append(list, "456"); list_append(list, "789"); while (list_has_next(list) == 1) printf("%s\n", (char *)list_next(list)); list_destroy(&list); return EXIT_SUCCESS; }
The same but create the list and populate it at the same time:
#include <slack/std.h> #include <slack/list.h> int main() { List *list; if (!(list = list_make(NULL, "123", "456", "789", NULL))) return EXIT_FAILURE; while (list_has_next(list) == 1) printf("%s\n", (char *)list_next(list)); list_destroy(&list); return EXIT_SUCCESS; }
Create a map that does own its items, populate it and then iterator over it with an external iterator to print its items.
#include <slack/std.h> #include <slack/list.h> int main() { List *list; Lister *lister; if (!(list = list_create(NULL))) return EXIT_FAILURE; list_append(list, "123"); list_append(list, "456"); list_append(list, "789"); if (!(lister = lister_create(list))) { list_destroy(&list); return EXIT_FAILURE; } while (lister_has_next(lister) == 1) printf("%s\n", (char *)lister_next(lister)); lister_destroy(&lister); list_destroy(&list); return EXIT_SUCCESS; }
The same but with an apply function:
#include <slack/std.h> #include <slack/list.h> void action(void *item, size_t *index, void *data) { printf("%s\n", (char *)item); } int main() { List *list; if (!(list = list_create(free))) return EXIT_FAILURE; list_append(list, strdup("123")); list_append(list, strdup("456")); list_append(list, strdup("789")); list_apply(list, action, NULL); list_destroy(&list); return EXIT_SUCCESS; }
The same but with a list of integers:
#include <slack/std.h> #include <slack/list.h> int main() { List *list; if (!(list = list_create(NULL))) return EXIT_FAILURE; list_append(list, (void *)123); list_append(list, (void *)456); list_append(list, (void *)789); while (list_has_next(list) == 1) printf("%d\n", list_next_int(list)); list_destroy(&list); return EXIT_SUCCESS; }
Create a copy of a list:
#include <slack/std.h> #include <slack/list.h> int main() { List *orig; List *copy; if (!(orig = list_make(free, strdup("123"), strdup("456"), strdup("789"), NULL))) return EXIT_FAILURE; if (!(copy = list_copy(orig, (list_copy_t *)strdup))) { list_destroy(&orig); return EXIT_FAILURE; } list_destroy(&orig); while (list_has_next(copy) == 1) printf("%s\n", (char *)list_next(copy)); list_destroy(©); return EXIT_SUCCESS; }
Transfer ownership from one list to another:
#include <slack/std.h> #include <slack/list.h> int main() { List *donor; List *recipient; if (!(donor = list_make(free, strdup("123"), strdup("456"), strdup("789"), NULL))) return EXIT_FAILURE; if (!(recipient = list_create(NULL))) { list_destroy(&donor); return EXIT_FAILURE; } while (list_has_next(donor) == 1) list_append(recipient, list_next(donor)); list_own(recipient, list_disown(donor)); list_destroy(&donor); while (list_has_next(recipient) == 1) printf("%s\n", (char *)list_next(recipient)); list_destroy(&recipient); return EXIT_SUCCESS; }
Manipulate a list, examine it, use apply, map, grep and query, remove items while iterating:
#include <slack/std.h> #include <slack/list.h> int cmp(const void *a, const void *b) { return strcmp(*(char **)a, *(char **)b); } void action(void *item, size_t *index, void *data) { printf("%s\n", (char *)item); } void *upper(void *item, size_t *index, void *data) { char *uc = strdup(item); if (uc) *uc = toupper(*uc); return uc; } int even(void *item, size_t *index, void *data) { return item && (*(char *)item & 1) == 0; } int main() { Lister *lister; List *list; void *item; List *res; ssize_t i; if (!(list = list_create(NULL))) return EXIT_FAILURE; // Manipulate a list printf("length %d empty %d\n", list_length(list), list_empty(list)); list_append(list, "a"); list_append(list, "b"); list_append(list, "c"); list_remove(list, 0); list_insert(list, 1, "d"); list_prepend(list, "e"); list_replace(list, 1, 2, "f"); list_push(list, "g"); list_push(list, "h"); list_push(list, "i"); item = list_pop(list); list_unshift(list, list_shift(list)); list_release(list_splice(list, 0, 1, NULL)); list_sort(list, cmp); printf("last %s\n", (char *)list_item(list, list_last(list))); // Apply an action to a list list_apply(list, action, NULL); // Map a list into another list res = list_map(list, free, upper, NULL); list_apply(res, action, NULL); list_destroy(&res); // Grep a list for items that match some criteria res = list_grep(list, even, NULL); list_apply(res, action, NULL); list_destroy(&res); // Locate a list's items that match some criteria for (i = 0; list_query(list, &i, even, NULL) != -1; ++i) printf("%d %s even\n", i, (char *)list_item(list, i)); // Remove elements via the internal iterator and break out of loop while (list_has_next(list) == 1) { item = list_next(list); list_remove_current(list); if (!strcmp(item, "f")) { list_break(list); break; } } // Remove elements via an external iterator for (lister = lister_create(list); lister_has_next(lister) == 1; ) { item = lister_next(lister); lister_remove(lister); } lister_destroy(&lister); list_destroy(&list); return EXIT_SUCCESS; }
Manipulate a list of integers:
#include <slack/std.h> #include <slack/list.h> int main() { Lister *lister; List *list; int item; int i; if (!(list = list_create(NULL))) return EXIT_FAILURE; // Manipulate a list list_append_int(list, 1); list_append_int(list, 2); list_append_int(list, 3); list_remove(list, 0); list_insert_int(list, 1, 4); list_prepend_int(list, 5); list_replace_int(list, 1, 2, 6); list_push_int(list, 7); list_push_int(list, 8); list_push_int(list, 9); item = list_pop_int(list); list_unshift_int(list, list_shift_int(list)); list_release(list_splice(list, 0, 1, NULL)); // Get items as integers for (i = 0; i < list_length(list); ++i) printf("%d\n", list_item_int(list, i)); // Remove elements via the internal iterator while (list_has_next(list) == 1) { item = list_next_int(list); list_remove_current(list); } // Remove elements via an external iterator for (lister = lister_create(list); lister_has_next(lister) == 1; ) { item = lister_next_int(lister); lister_remove(lister); } list_destroy(&list); return EXIT_SUCCESS; }
Append, insert, prepend and replace using another list, not just one item:
#include <slack/std.h> #include <slack/list.h> int main() { List *list; List *src; int i; if (!(list = list_create(NULL))) return EXIT_FAILURE; if (!(src = list_make(NULL, "a", "b", "c", NULL))) { list_destroy(&list); return EXIT_FAILURE; } list_append_list(list, src, NULL); list_insert_list(list, 1, src, NULL); list_prepend_list(list, src, NULL); list_replace_list(list, 1, 2, src, NULL); for (i = 0; i < list_length(list); ++i) printf("%s\n", (char *)list_item(list, i)); list_destroy(&list); return EXIT_SUCCESS; }
The same as the previous example but with a list that owns its items:
#include <slack/std.h> #include <slack/list.h> int main() { List *list; List *src; int i; if (!(list = list_create(free))) return EXIT_FAILURE; if (!(src = list_make(NULL, "a", "b", "c", NULL))) { list_destroy(&list); return EXIT_FAILURE; } list_append_list(list, src, (list_copy_t *)strdup); list_insert_list(list, 1, src, (list_copy_t *)strdup); list_prepend_list(list, src, (list_copy_t *)strdup); list_replace_list(list, 1, 2, src, (list_copy_t *)strdup); for (i = 0; i < list_length(list); ++i) printf("%s\n", (char *)list_item(list, i)); list_destroy(&list); return EXIT_SUCCESS; }
Little attempt is made to protect the client from sharing items between lists with differing ownership policies and getting it wrong. When copying items from any list to an owning list, a copy function must be supplied. When adding a single item to an owning list, it is assumed that the list may take over ownership of the item. When an owning list is destroyed, all of its items are destroyed. If any of these items had been shared with a non-owning list that outlived the owning list, then the non-owning list will contain items that point to deallocated memory.
If you use an internal iterator in a loop that terminates before the end of the list, and fail to call list_break(3), the internal iterator will leak.
Uses malloc(3). The type of memory used and the allocation strategy need to be decoupled from this code.
libslack(3), map(3), mem(3), hsort(3), qsort(3), locker(3)
20100612 raf <raf@raf.org>