burkey.co /docs/libflint/linkedlist
index linkedlist
~/docs/libflint/linkedlist.md
libflint

Linkedlist

libflint·Data Structures

A doubly linked list of void * values. The caller owns the List handle. The list allocates and frees nodes. Payloads are borrowed unless a destroy callback is set, in which case ll_destroy calls it on payloads still in the list.

Usage#

Initialize a caller-owned List. Pass NULL for destroy when payloads are borrowed, and NULL for match when ll_find is not used. On an empty list, ll_ins_next ignores its node argument.

List list;
int first = 1;
int second = 2;
void *data = NULL;

ll_init(&list, NULL, NULL);
if (ll_ins_next(&list, NULL, &first) == 0 &&
    ll_ins_next(&list, list.tail, &second) == 0 &&
    ll_remove(&list, list.head, &data) == 0) {
    /* *(int *)data == 1 */
}
ll_destroy(&list);

ll_destroy frees remaining nodes and, when destroy is non-NULL, calls it on each remaining payload from the tail toward the head. It does not free the List handle. It zeros the handle, so a second ll_destroy is a no-op. Remove and pop write the payload to the caller and do not call destroy. A removed ListNode is freed. Other node pointers stay valid, including across reverse and sort, which only relink them.

Structs#

List#

typedef struct {
    size_t size;

    void (*destroy)(void *data);

    int (*match)(const void *a, const void *b);

    struct ListNode *head;
    struct ListNode *tail;
} List;

size, head, and tail are maintained by the list functions. Do not write them. destroy is the optional payload destructor. match is the optional equality callback read by ll_find on each call; it returns 0 when the two payloads are equal. Set stores its equality callback in this field.

ListNode#

typedef struct ListNode {
    void *data;
    struct ListNode *next;
    struct ListNode *prev;
} ListNode;

data is the payload. next and prev are the neighboring nodes, or NULL at the ends. Insert and remove update the links.

Functions#

ll_init#

Initializes an empty list: size is 0, head and tail are NULL, and destroy and match are stored. Does not allocate. Do not call it on a list that still owns nodes; the previous nodes are not freed. list must be non-NULL.

void ll_init(List *list, void (*destroy)(void *data),
             int (*match)(const void *a, const void *b));

ll_destroy#

Frees every node. If destroy is non-NULL, calls it on each payload from the tail toward the head. Does not free the List handle. Zeros the handle, so a second call is a no-op. list must be non-NULL.

void ll_destroy(List *list);

ll_ins_next / ll_ins_prev#

Inserts a new node holding data after node, or before node. When the list is empty, node is ignored and the new node becomes both ends. When the list is not empty, node must already be in the list; a NULL node returns -1. Returns 0 on success and -1 if node allocation fails or the list is nonempty and node is NULL. Failure leaves the list unchanged. The new node stores data as a pointer. A NULL payload is allowed.

int ll_ins_next(List *list, ListNode *node, const void *data);

int ll_ins_prev(List *list, ListNode *node, const void *data);

ll_push_head / ll_push_tail#

Inserts before the head, or after the tail. Both work on an empty list. Returns 0 on success and -1 if node allocation fails. Failure leaves the list unchanged.

int ll_push_head(List *list, const void *data);

int ll_push_tail(List *list, const void *data);

ll_pop_head / ll_pop_tail#

Removes the head or the tail and writes the payload to *data. Returns 0 on success. Returns -1 if the list is empty or data is NULL, and leaves the list unchanged. Does not call destroy. A stored NULL payload is removed, and *data is set to NULL.

int ll_pop_head(List *list, void **data);

int ll_pop_tail(List *list, void **data);

ll_remove#

Frees node and writes its payload to *data. node must belong to list. Returns 0 on success. Returns -1 if node is NULL, data is NULL, or the list is empty, without modifying the list. Does not call destroy. After success the ListNode pointer is invalid. A stored NULL payload is removed, and *data is set to NULL.

int ll_remove(List *list, ListNode *node, void **data);

ll_remove_next / ll_remove_prev#

Removes the successor of node, or the predecessor. node must belong to list. Returns 0 and writes the payload to *data on success. Returns -1, without removing, if node is NULL, that neighbor does not exist, or data is NULL. Does not call destroy. The removed ListNode is invalid afterward.

int ll_remove_next(List *list, ListNode *node, void **data);

int ll_remove_prev(List *list, ListNode *node, void **data);

ll_find#

Returns the first node whose payload matches data, walking from the head. match is called as match(stored, key) and a return of 0 is a match. If match is NULL, the payload pointers are compared. Returns NULL if list is NULL or nothing matches.

ListNode *ll_find(const List *list, const void *data);

ll_reverse#

Reverses the list in place by swapping each node's next and prev, then swapping head and tail. Node pointers remain valid. An empty list or a one-node list is unchanged. O(n) time, O(1) extra space.

void ll_reverse(List *list);

ll_sort#

Sorts the nodes in place with a stable mergesort. It does not heap-allocate. cmp is called with payload pointers and returns negative if a < b, 0 if a == b, or positive if a > b. Equal elements keep their original order. A list of fewer than two nodes is unchanged. cmp must be non-NULL when the list has two or more nodes. Existing ListNode pointers remain valid; head, tail, next, and prev are updated. O(n log n) time.

void ll_sort(List *list, int (*cmp)(const void *a, const void *b));

ll_to_array#

Allocates an array of list->size borrowed payload pointers in list order. The caller frees the array with free. Freeing the array does not free the payloads. Returns NULL if list is NULL, the list is empty, or allocation fails, including a size overflow. The list is unchanged. ll_destroy does not free the array; a non-NULL destructor will free payloads the array still holds.

void **ll_to_array(const List *list);

Macros#

LL_FOREACH#

Walks from head until NULL. The second argument names the cursor, so loops can nest. The increment reads that cursor's next, so do not remove the cursor node in the body.

#define LL_FOREACH(list, n) \
    for (ListNode *n = (list)->head; (n) != NULL; (n) = (n)->next)

LL_FOREACH_REV#

Walks from tail until NULL. The second argument names the cursor. The increment reads that cursor's prev.

#define LL_FOREACH_REV(list, n) \
    for (ListNode *n = (list)->tail; (n) != NULL; (n) = (n)->prev)

LL_ITER#

Alias for LL_FOREACH(list, node). The cursor is named node.

#define LL_ITER(list) LL_FOREACH(list, node)

LL_ITER_REV#

Alias for LL_FOREACH_REV(list, node).

#define LL_ITER_REV(list) LL_FOREACH_REV(list, node)