Skip to content

ssfll.md

Latest commit

 

History

History
821 lines (550 loc) · 25.1 KB

ssfll.md

File metadata and controls

821 lines (550 loc) · 25.1 KB

ssfll — Linked List Interface

SSF | Data Structures

Doubly-linked list supporting FIFO, stack, and arbitrary-position insert/remove operations.

The key to using the linked list is to embed an SSFLLItem_t as the first field of any struct you want to track. The API casts between SSFLLItem_t * and your struct pointer, allowing any struct to participate in the list without separate allocation.

Dependencies | Notes | Configuration | API Summary | Function Reference

↑ Dependencies

↑ Notes

  • SSFLLItem_t must be the first field of any struct added to a list.
  • An item already in one list cannot be inserted into another list or the same list again; attempting to do so triggers an assertion.
  • SSFLLDeInit() asserts if the list is not empty; remove all items before de-initializing.
  • SSFLLInit() asserts if the list is already initialized.
  • SSF_LL_PUT() inserts inItem after locItem. Pass NULL as locItem to insert at head.
  • SSF_LL_GET() removes locItem itself from the list.

↑ Configuration

This module has no compile-time configuration options in ssfoptions.h.

↑ API Summary

Definitions

Symbol Kind Description
SSFLLItem_t Struct List item handle; must be the first field of any struct tracked by the list. Do not access fields directly.
SSFLL_t Struct List instance; pass by pointer to all API functions. Do not access fields directly.
SSF_LL_LOC_t Enum Insertion/removal location selector
SSF_LL_LOC_HEAD Constant Operate on the head of the list
SSF_LL_LOC_TAIL Constant Operate on the tail of the list
SSF_LL_LOC_ITEM Constant Operate relative to a specific item (locItem)

Functions

Function / Macro Description
e.g. void SSFLLInit(ll, maxSize) Initialize a linked list
e.g. void SSFLLDeInit(ll) De-initialize an empty linked list
e.g. bool SSFLLIsInited(ll) Returns true if the list is initialized
e.g. void SSFLLPutItem(ll, inItem, loc, locItem) Insert an item at a specified location
e.g. bool SSFLLGetItem(ll, outItem, loc, locItem) Remove and return an item from a specified location
e.g. bool SSFLLIsEmpty(ll) Returns true if the list contains no items
e.g. bool SSFLLIsFull(ll) Returns true if the list has reached its maximum item count
e.g. uint32_t SSFLLSize(ll) Returns the maximum item count
e.g. uint32_t SSFLLLen(ll) Returns the current item count
e.g. uint32_t SSFLLUnused(ll) Returns the number of additional items that can be added
e.g. void SSF_LL_STACK_PUSH(ll, inItem) Macro: push item onto head (LIFO)
e.g. bool SSF_LL_STACK_POP(ll, outItem) Macro: pop item from head (LIFO)
e.g. void SSF_LL_FIFO_PUSH(ll, inItem) Macro: enqueue item at head
e.g. bool SSF_LL_FIFO_POP(ll, outItem) Macro: dequeue item from tail
e.g. void SSF_LL_PUT(ll, inItem, locItem) Macro: insert inItem after locItem
e.g. bool SSF_LL_GET(ll, outItem, locItem) Macro: remove locItem from the list
e.g. SSFLLItem_t *SSF_LL_HEAD(ll) Macro: pointer to the head item (NULL if empty)
e.g. SSFLLItem_t *SSF_LL_TAIL(ll) Macro: pointer to the tail item (NULL if empty)
e.g. SSFLLItem_t *SSF_LL_NEXT_ITEM(item) Macro: pointer to the next item (NULL if at tail)
e.g. SSFLLItem_t *SSF_LL_PREV_ITEM(item) Macro: pointer to the previous item (NULL if at head)

↑ Function Reference

↑ void SSFLLInit()

void SSFLLInit(SSFLL_t *ll, uint32_t maxSize);

Initializes a linked list. maxSize sets an upper bound on the number of items the list may hold; SSFLLIsFull() returns true when maxSize items are present. The list must not already be initialized; asserting otherwise.

Parameter Direction Type Description
ll out SSFLL_t * Pointer to the list structure to initialize. Must not be NULL. Must not already be initialized.
maxSize in uint32_t Maximum number of items the list may hold. Must be greater than 0. Pass UINT32_MAX for an effectively unlimited list.

Returns: Nothing.

Example:

SSFLL_t ll;

SSFLLInit(&ll, 10u);
/* ll is ready, capacity 10 items */

↑ void SSFLLDeInit()

void SSFLLDeInit(SSFLL_t *ll);

De-initializes an empty linked list, clearing its internal magic marker. The list must be empty before calling; asserting otherwise.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized, empty linked list. Must not be NULL.

Returns: Nothing.

Example:

SSFLL_t ll;

SSFLLInit(&ll, 10u);
SSFLLDeInit(&ll);
/* ll is no longer valid */

↑ bool SSFLLIsInited()

bool SSFLLIsInited(SSFLL_t *ll);

Checks whether a linked list has been initialized. Safe to call before SSFLLInit() on a zero-initialized struct to test readiness.

Parameter Direction Type Description
ll in SSFLL_t * Pointer to the linked list to check. Must not be NULL.

Returns: true if the list is initialized; false otherwise.

Example:

static SSFLL_t ll;   /* zero-initialized */

SSFLLIsInited(&ll);   /* returns false */
SSFLLInit(&ll, 10u);
SSFLLIsInited(&ll);   /* returns true */
SSFLLDeInit(&ll);
SSFLLIsInited(&ll);   /* returns false */

↑ void SSFLLPutItem()

void SSFLLPutItem(SSFLL_t *ll, SSFLLItem_t *inItem, SSF_LL_LOC_t loc, SSFLLItem_t *locItem);

Inserts inItem into the list at the position specified by loc. The item must not already be in any list; asserting otherwise. The list must not be full; asserting otherwise. Prefer the convenience macros for common use cases.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized linked list. Must not be NULL. Must not be full.
inItem in SSFLLItem_t * Pointer to the item to insert. Must not be NULL. Must not currently be in any list. Must be the first field of the caller's struct.
loc in SSF_LL_LOC_t Insertion location: SSF_LL_LOC_HEAD inserts before all items; SSF_LL_LOC_TAIL inserts after all items; SSF_LL_LOC_ITEM inserts after locItem (NULL locItem inserts at head).
locItem in SSFLLItem_t * Reference item when loc == SSF_LL_LOC_ITEM; inItem is inserted after this item. Must be NULL for SSF_LL_LOC_HEAD and SSF_LL_LOC_TAIL.

Returns: Nothing.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 0xA0u}, b = {{0}, 0xB0u}, c = {{0}, 0xC0u};

SSFLLInit(&ll, 10u);
SSFLLPutItem(&ll, (SSFLLItem_t *)&a, SSF_LL_LOC_HEAD, NULL); /* list: a */
SSFLLPutItem(&ll, (SSFLLItem_t *)&b, SSF_LL_LOC_TAIL, NULL); /* list: a → b */
SSFLLPutItem(&ll, (SSFLLItem_t *)&c, SSF_LL_LOC_ITEM,        /* list: a → c → b */
             (SSFLLItem_t *)&a);

↑ bool SSFLLGetItem()

bool SSFLLGetItem(SSFLL_t *ll, SSFLLItem_t **outItem, SSF_LL_LOC_t loc, SSFLLItem_t *locItem);

Removes an item from the list at the position specified by loc and writes a pointer to it in *outItem. The caller is responsible for the removed item's lifetime.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized linked list. Must not be NULL.
outItem out SSFLLItem_t ** Receives a pointer to the removed item on success. Must not be NULL.
loc in SSF_LL_LOC_t Removal location: SSF_LL_LOC_HEAD removes the head item; SSF_LL_LOC_TAIL removes the tail item; SSF_LL_LOC_ITEM removes locItem specifically.
locItem in SSFLLItem_t * The specific item to remove when loc == SSF_LL_LOC_ITEM. Must not be NULL when using SSF_LL_LOC_ITEM. Must be NULL for SSF_LL_LOC_HEAD and SSF_LL_LOC_TAIL.

Returns: true if an item was removed and written to *outItem; false if the list is empty.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 0xA0u}, b = {{0}, 0xB0u};
MyItem_t *out;

SSFLLInit(&ll, 10u);
SSFLLPutItem(&ll, (SSFLLItem_t *)&a, SSF_LL_LOC_TAIL, NULL); /* list: a */
SSFLLPutItem(&ll, (SSFLLItem_t *)&b, SSF_LL_LOC_TAIL, NULL); /* list: a → b */

if (SSFLLGetItem(&ll, (SSFLLItem_t **)&out, SSF_LL_LOC_HEAD, NULL))
{
    /* out == &a, out->data == 0xA0 */
}
if (SSFLLGetItem(&ll, (SSFLLItem_t **)&out, SSF_LL_LOC_ITEM,
                 (SSFLLItem_t *)&b))
{
    /* out == &b, out->data == 0xB0 */
}

↑ bool SSFLLIsEmpty()

bool SSFLLIsEmpty(const SSFLL_t *ll);

Returns true if the list contains no items.

Parameter Direction Type Description
ll in const SSFLL_t * Pointer to an initialized linked list. Must not be NULL.

Returns: true if the list is empty; false otherwise.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u};

SSFLLInit(&ll, 10u);
SSFLLIsEmpty(&ll);   /* returns true */

SSFLLPutItem(&ll, (SSFLLItem_t *)&a, SSF_LL_LOC_HEAD, NULL);
SSFLLIsEmpty(&ll);   /* returns false */

↑ bool SSFLLIsFull()

bool SSFLLIsFull(const SSFLL_t *ll);

Returns true if the list contains maxSize items and no more can be inserted.

Parameter Direction Type Description
ll in const SSFLL_t * Pointer to an initialized linked list. Must not be NULL.

Returns: true if the list is full; false otherwise.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};

SSFLLInit(&ll, 2u);
SSFLLIsFull(&ll);   /* returns false */

SSFLLPutItem(&ll, (SSFLLItem_t *)&a, SSF_LL_LOC_HEAD, NULL);
SSFLLPutItem(&ll, (SSFLLItem_t *)&b, SSF_LL_LOC_HEAD, NULL);
SSFLLIsFull(&ll);   /* returns true */

↑ uint32_t SSFLLSize()

uint32_t SSFLLSize(const SSFLL_t *ll);

Returns the maximum number of items the list can hold.

Parameter Direction Type Description
ll in const SSFLL_t * Pointer to an initialized linked list. Must not be NULL.

Returns: The maxSize value passed to SSFLLInit().

Example:

SSFLL_t ll;

SSFLLInit(&ll, 10u);
SSFLLSize(&ll);   /* returns 10 */

↑ uint32_t SSFLLLen()

uint32_t SSFLLLen(const SSFLL_t *ll);

Returns the current number of items in the list.

Parameter Direction Type Description
ll in const SSFLL_t * Pointer to an initialized linked list. Must not be NULL.

Returns: Current item count.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};

SSFLLInit(&ll, 10u);
SSFLLPutItem(&ll, (SSFLLItem_t *)&a, SSF_LL_LOC_HEAD, NULL);
SSFLLPutItem(&ll, (SSFLLItem_t *)&b, SSF_LL_LOC_HEAD, NULL);
SSFLLLen(&ll);   /* returns 2 */

↑ uint32_t SSFLLUnused()

uint32_t SSFLLUnused(const SSFLL_t *ll);

Returns the number of additional items that can be inserted before the list is full (Size - Len).

Parameter Direction Type Description
ll in const SSFLL_t * Pointer to an initialized linked list. Must not be NULL.

Returns: Number of free slots remaining (Size - Len).

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u};

SSFLLInit(&ll, 10u);
SSFLLPutItem(&ll, (SSFLLItem_t *)&a, SSF_LL_LOC_HEAD, NULL);
SSFLLUnused(&ll);   /* returns 9 */

↑ Convenience Macros

Macros that wrap SSFLLPutItem() and SSFLLGetItem() with fixed location arguments, plus direct field-access macros for list traversal. Use these in preference to calling SSFLLPutItem() / SSFLLGetItem() directly for common patterns.

↑ void SSF_LL_STACK_PUSH()

#define SSF_LL_STACK_PUSH(ll, inItem) \
    SSFLLPutItem(ll, (SSFLLItem_t *)inItem, SSF_LL_LOC_HEAD, NULL)

Inserts inItem at the head of the list. Pair with SSF_LL_STACK_POP() for LIFO (stack) behavior.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized, non-full list. Must not be NULL.
inItem in void * Pointer to a struct whose first field is SSFLLItem_t. Must not be NULL. Must not be in any list.

Returns: Nothing.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};

SSFLLInit(&ll, 10u);
SSF_LL_STACK_PUSH(&ll, &a);   /* head: a */
SSF_LL_STACK_PUSH(&ll, &b);   /* head: b → a */

↑ bool SSF_LL_STACK_POP()

#define SSF_LL_STACK_POP(ll, outItem) \
    SSFLLGetItem(ll, (SSFLLItem_t **)outItem, SSF_LL_LOC_HEAD, NULL)

Removes and returns the head item. Pair with SSF_LL_STACK_PUSH() for LIFO (stack) behavior.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized list. Must not be NULL.
outItem out void ** Pointer to a struct pointer whose first field is SSFLLItem_t. Receives the removed item on success.

Returns: true if an item was removed; false if the list is empty.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};
MyItem_t *out;

SSFLLInit(&ll, 10u);
SSF_LL_STACK_PUSH(&ll, &a);
SSF_LL_STACK_PUSH(&ll, &b);         /* head: b → a */

if (SSF_LL_STACK_POP(&ll, &out)) { /* out == &b (LIFO) */ }
if (SSF_LL_STACK_POP(&ll, &out)) { /* out == &a */ }

↑ void SSF_LL_FIFO_PUSH()

#define SSF_LL_FIFO_PUSH(ll, inItem) \
    SSFLLPutItem(ll, (SSFLLItem_t *)inItem, SSF_LL_LOC_HEAD, NULL)

Inserts inItem at the head of the list. Pair with SSF_LL_FIFO_POP() for FIFO (queue) behavior; items pushed at the head are dequeued from the tail in insertion order.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized, non-full list. Must not be NULL.
inItem in void * Pointer to a struct whose first field is SSFLLItem_t. Must not be NULL. Must not be in any list.

Returns: Nothing.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};

SSFLLInit(&ll, 10u);
SSF_LL_FIFO_PUSH(&ll, &a);   /* head: a */
SSF_LL_FIFO_PUSH(&ll, &b);   /* head: b → a */

↑ bool SSF_LL_FIFO_POP()

#define SSF_LL_FIFO_POP(ll, outItem) \
    SSFLLGetItem(ll, (SSFLLItem_t **)outItem, SSF_LL_LOC_TAIL, NULL)

Removes and returns the tail item. Pair with SSF_LL_FIFO_PUSH() for FIFO (queue) behavior.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized list. Must not be NULL.
outItem out void ** Pointer to a struct pointer whose first field is SSFLLItem_t. Receives the removed item on success.

Returns: true if an item was removed; false if the list is empty.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};
MyItem_t *out;

SSFLLInit(&ll, 10u);
SSF_LL_FIFO_PUSH(&ll, &a);
SSF_LL_FIFO_PUSH(&ll, &b);         /* head: b → a (tail) */

if (SSF_LL_FIFO_POP(&ll, &out)) { /* out == &a (FIFO: first pushed, first popped) */ }
if (SSF_LL_FIFO_POP(&ll, &out)) { /* out == &b */ }

↑ void SSF_LL_PUT()

#define SSF_LL_PUT(ll, inItem, locItem) \
    SSFLLPutItem(ll, (SSFLLItem_t *)inItem, SSF_LL_LOC_ITEM, (SSFLLItem_t *)locItem)

Inserts inItem immediately after locItem in the list. Pass NULL as locItem to insert at the head.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized, non-full list. Must not be NULL.
inItem in void * Pointer to a struct whose first field is SSFLLItem_t. Must not be NULL. Must not be in any list.
locItem in void * Item after which inItem is inserted. Pass NULL to insert at head. If not NULL, must be in ll.

Returns: Nothing.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u}, c = {{0}, 3u};

SSFLLInit(&ll, 10u);
SSF_LL_STACK_PUSH(&ll, &a);   /* list: a */
SSF_LL_STACK_PUSH(&ll, &b);   /* list: b → a */
SSF_LL_PUT(&ll, &c, &b);      /* inserts c after b: b → c → a */

↑ bool SSF_LL_GET()

#define SSF_LL_GET(ll, outItem, locItem) \
    SSFLLGetItem(ll, (SSFLLItem_t **)outItem, SSF_LL_LOC_ITEM, (SSFLLItem_t *)locItem)

Removes locItem from the list and writes a pointer to it in *outItem.

Parameter Direction Type Description
ll in-out SSFLL_t * Pointer to an initialized list. Must not be NULL.
outItem out void ** Pointer to a struct pointer whose first field is SSFLLItem_t. Receives locItem on success. Must not be NULL.
locItem in void * The specific item to remove. Must not be NULL. Must be in ll.

Returns: true if an item was removed and written to *outItem; false if the list is empty.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};
MyItem_t *out;

SSFLLInit(&ll, 10u);
SSF_LL_STACK_PUSH(&ll, &a);
SSF_LL_STACK_PUSH(&ll, &b);   /* list: b → a */

if (SSF_LL_GET(&ll, &out, &a)) { /* removes a, out == &a; list: b */ }

↑ SSFLLItem_t *SSF_LL_HEAD()

#define SSF_LL_HEAD(ll) ((ll)->head)

Returns a pointer to the head item without removing it. Returns NULL if the list is empty.

Parameter Direction Type Description
ll in SSFLL_t * Pointer to an initialized list. Must not be NULL.

Returns: SSFLLItem_t * pointing to the head item, or NULL if empty.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};

SSFLLInit(&ll, 10u);
SSF_LL_STACK_PUSH(&ll, &a);
SSF_LL_STACK_PUSH(&ll, &b);   /* list: b → a */

((MyItem_t *)SSF_LL_HEAD(&ll))->data;   /* == 2 (b is head) */

↑ SSFLLItem_t *SSF_LL_TAIL()

#define SSF_LL_TAIL(ll) ((ll)->tail)

Returns a pointer to the tail item without removing it. Returns NULL if the list is empty.

Parameter Direction Type Description
ll in SSFLL_t * Pointer to an initialized list. Must not be NULL.

Returns: SSFLLItem_t * pointing to the tail item, or NULL if empty.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u};

SSFLLInit(&ll, 10u);
SSF_LL_STACK_PUSH(&ll, &a);
SSF_LL_STACK_PUSH(&ll, &b);   /* list: b → a */

((MyItem_t *)SSF_LL_TAIL(&ll))->data;   /* == 1 (a is tail) */

↑ SSFLLItem_t *SSF_LL_NEXT_ITEM()

#define SSF_LL_NEXT_ITEM(item) ((item)->next)

Returns a pointer to the item that follows item in the list. Used for forward (head-to-tail) traversal. Returns NULL if item is the tail.

Parameter Direction Type Description
item in SSFLLItem_t * Pointer to an item currently in the list. Must not be NULL.

Returns: SSFLLItem_t * pointing to the next item, or NULL if item is the tail.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u}, c = {{0}, 3u};
MyItem_t *cur;

SSFLLInit(&ll, 10u);
SSF_LL_FIFO_PUSH(&ll, &a);
SSF_LL_FIFO_PUSH(&ll, &b);
SSF_LL_FIFO_PUSH(&ll, &c);   /* head → tail: c → b → a */

for (cur = (MyItem_t *)SSF_LL_HEAD(&ll); cur != NULL;
     cur = (MyItem_t *)SSF_LL_NEXT_ITEM(&cur->item))
{
    /* cur->data: 3, then 2, then 1 */
}

↑ SSFLLItem_t *SSF_LL_PREV_ITEM()

#define SSF_LL_PREV_ITEM(item) ((item)->prev)

Returns a pointer to the item that precedes item in the list. Used for backward (tail-to-head) traversal. Returns NULL if item is the head.

Parameter Direction Type Description
item in SSFLLItem_t * Pointer to an item currently in the list. Must not be NULL.

Returns: SSFLLItem_t * pointing to the previous item, or NULL if item is the head.

Example:

typedef struct { SSFLLItem_t item; uint32_t data; } MyItem_t;

SSFLL_t ll;
MyItem_t a = {{0}, 1u}, b = {{0}, 2u}, c = {{0}, 3u};
MyItem_t *cur;

SSFLLInit(&ll, 10u);
SSF_LL_FIFO_PUSH(&ll, &a);
SSF_LL_FIFO_PUSH(&ll, &b);
SSF_LL_FIFO_PUSH(&ll, &c);   /* head → tail: c → b → a */

for (cur = (MyItem_t *)SSF_LL_TAIL(&ll); cur != NULL;
     cur = (MyItem_t *)SSF_LL_PREV_ITEM(&cur->item))
{
    /* cur->data: 1, then 2, then 3 */
}