NAME

libslack(list) - list module

SYNOPSIS

#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);

DESCRIPTION

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). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. 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). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. 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). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. 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). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. 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). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. 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). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. 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). It is strongly recommended to use list_destroy(3), because it also sets the pointer variable to null. Note that the new list does not own its items, because 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). It is strongly recommended to use lister_destroy(3), because it also sets the pointer variable to null. 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 at any time for a given list). 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 its 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 its 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.

ERRORS

On error, errno is set either by an underlying function, or as follows:

EINVAL

When arguments are null or out of range.

MT-Level

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 its 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.

EXAMPLES

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 list 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(&copy);

    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;
}

CAVEAT

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. This must be avoided.

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. This must be avoided.

BUGS

Uses malloc(3) directly. The type of memory used and the allocation strategy should be decoupled from this code.

SEE ALSO

libslack(3), map(3), mem(3), hsort(3), qsort(3), locker(3)

AUTHOR

20230824 raf <raf@raf.org>