cl_list.h File Reference

#include "allocator.h"
#include "cl_types.h"
#include "types.h"
#include <stdbool.h>

Go to the source code of this file.

Macros
#define	CL_LIST_FOREACH(__type, __name, __list, ...)
	Macro to iterate over the elements of the list.
#define	CL_LIST_FOREACH_PTR(__type, __name, __list, ...)
	Macro to iterate over the elements of the list with a pointer to the current element.

Typedefs
typedef struct __List	CL_List

Functions
CL_List *	CL_ListAlloc (MEM_Allocator *const alloc, u32 elem_sz)
	Initializes a new doubly-linked list with tail, with the allocated memory provided by the user.
void	CL_ListFree (CL_List *const list)
	Frees the memory previously assigned to the list.
CL_Error	CL_ListPushBack (CL_List *const list, const void *const elem)
	Adds an element at the end of the list.
CL_Error	CL_ListPushFront (CL_List *const list, const void *const elem)
	Adds an element at the front of the list.
void	CL_ListPopBack (CL_List *const list, void *out_elem)
	Removes the last element from the list, optionally returning it.
void	CL_ListPopFront (CL_List *const list, void *out_elem)
	Removes the first element from the list, optionally returning it.
CL_Error	CL_ListGet (const CL_List *const list, u32 index, void *out_elem)
	Gets an element at the specified index.
CL_Error	CL_ListGetPtr (const CL_List *const list, u32 index, void **out_elem)
	Gets an element at the specified index as a pointer, so the user can modify it.
CL_Error	CL_ListGetLast (const CL_List *const list, void *out_elem)
	Gets the last element from the list.
CL_Error	CL_ListGetLastPtr (const CL_List *const list, void **out_elem)
	Gets the last element from the list as a pointer, so the user can modify it.
CL_Error	CL_ListInsertAt (CL_List *const list, u32 index, const void *const elem)
	Inserts an element at the specified index.
CL_Error	CL_ListRemoveAt (CL_List *const list, u32 index, void *out_elem)
	Removes an element at the specified index.
bool	CL_ListSearch (const CL_List *const list, const void *const elem, CL_CompareFn compare_fn, u32 *out_index)
	Searches for an element in the list.
void	CL_ListClear (CL_List *const list)
	Removes all elements from the list.
u32	CL_ListSize (const CL_List *const list)
	Gets the number of elements in the list.
bool	CL_ListIsEmpty (const CL_List *const list)
	Checks if the list is empty.

Macro Definition Documentation

CL_LIST_FOREACH

#define CL_LIST_FOREACH	(		__type,
			__name,
			__list,
			...
	)

Value:

    for (u32 __i = 0; __i < CL_ListSize(__list); __i++)                                                                \
    {                                                                                                                  \
        __type __name;                                                                                                 \
        CL_ListGet(__list, __i, &(__name));                                                                            \
        __VA_ARGS__                                                                                                    \
    }

Macro to iterate over the elements of the list.

Parameters

__type	The type of the elements in the list.
__name	The name of the variable to hold the current element.
__list	The list to iterate over.
...	The code to execute for each element.

Definition at line 20 of file cl_list.h.

    {                                                                                                                  \
        __type __name;                                                                                                 \
        CL_ListGet(__list, __i, &(__name));                                                                            \
        __VA_ARGS__                                                                                                    \
    }

CL_LIST_FOREACH_PTR

#define CL_LIST_FOREACH_PTR	(		__type,
			__name,
			__list,
			...
	)

Value:

    for (u32 __i = 0; __i < CL_ListSize(__list); __i++)                                                                \
    {                                                                                                                  \
        __type *const __name;                                                                                          \
        CL_ListGetPtr(__list, __i, (void **)&(__name));                                                                \
        __VA_ARGS__                                                                                                    \
    }

Macro to iterate over the elements of the list with a pointer to the current element.

Parameters

__type	The type of the elements in the list.
__name	The name of the variable to hold the current element.
__list	The list to iterate over.
...	The code to execute for each element.

Definition at line 33 of file cl_list.h.

    {                                                                                                                  \
        __type *const __name;                                                                                          \
        CL_ListGetPtr(__list, __i, (void **)&(__name));                                                                \
        __VA_ARGS__                                                                                                    \
    }

Typedef Documentation

CL_List

typedef struct __List CL_List

Definition at line 11 of file cl_list.h.

Function Documentation

CL_ListAlloc()

CL_List * CL_ListAlloc	(	MEM_Allocator *const	alloc,
		u32	elem_sz
	)

Initializes a new doubly-linked list with tail, with the allocated memory provided by the user.

Parameters

alloc	The allocator to use for memory allocation.
elem_sz	The size of each element in the list.

Returns

Pointer to the new list or NULL on error.

Definition at line 43 of file cl_list.c.

{
    if (!alloc || !elem_sz)
        return NULL;
 
    CL_List *const list = MEM_Alloc(alloc, sizeof(CL_List));
    if (!list)
        return NULL;
 
    *list = (CL_List){
        .head = NULL,
        .tail = NULL,
        .size = 0,
        .elem_size = elem_sz,
        .allocator = alloc,
    };
 
    return list;
}

CL_ListClear()

void CL_ListClear

(

CL_List *const

list

)

Removes all elements from the list.

Parameters

list	The list to clear.

Definition at line 316 of file cl_list.c.

{
    if (!list || !list->size)
        return;
 
    struct __ListNode *current = list->head, *copy;
    while (current)
    {
        copy = current;
        current = current->next;
        MEM_Free(list->allocator, copy->data);
        MEM_Free(list->allocator, copy);
    }
 
    list->head = list->tail = NULL;
    list->size = 0;
}

CL_ListFree()

void CL_ListFree

(

CL_List *const

list

)

Frees the memory previously assigned to the list.

Parameters

list	The list to release the memory of.

Note

CL_List does not take ownership of the elements, so it's the user's responsibility to free them.

Definition at line 63 of file cl_list.c.

{
    if (!list)
        return;
 
    struct __ListNode *current = list->head, *copy;
    while (current)
    {
        copy = current;
        current = current->next;
        MEM_Free(list->allocator, copy->data);
        MEM_Free(list->allocator, copy);
    }
 
    MEM_Free(list->allocator, list);
}

CL_ListGet()

CL_Error CL_ListGet	(	const CL_List *const	list,
		u32	index,
		void *	out_elem
	)

Gets an element at the specified index.

Parameters

list	The list to get the element from.
index	The index of the element to get.
out_elem	[OUTPUT] The element at the specified index.

Returns

CL_Error The error code.

Note

This operation is not O(1) for lists. Consider using a vector if you need random access.

Definition at line 168 of file cl_list.c.

{
    if (!list || !out_elem)
        return CL_ERR_INVALID_PARAMS;
 
    if (index >= list->size)
        return CL_ERR_OUT_OF_BOUNDS;
 
    u32 idx = 0;
    struct __ListNode *current = list->head;
    while (idx++ < index)
        current = current->next;
 
    // Now current is the node at the specified index.
    memcpy(out_elem, current->data, list->elem_size);
    return CL_ERR_OK;
}

CL_ListGetLast()

CL_Error CL_ListGetLast	(	const CL_List *const	list,
		void *	out_elem
	)

Gets the last element from the list.

Parameters

list	The list to get the last element from.
out_elem	[OUTPUT] The last element.

Returns

CL_Error The error code.

Definition at line 204 of file cl_list.c.

{
    if (!list || !out_elem)
        return CL_ERR_INVALID_PARAMS;
 
    if (!list->size)
        return CL_ERR_EMPTY;
 
    memcpy(out_elem, list->tail->data, list->elem_size);
    return CL_ERR_OK;
}

CL_ListGetLastPtr()

CL_Error CL_ListGetLastPtr	(	const CL_List *const	list,
		void **	out_elem
	)

Gets the last element from the list as a pointer, so the user can modify it.

Parameters

list	The list to get the last element from.
out_elem	[OUTPUT] The last element, as a pointer.

Returns

CL_Error The error code.

Definition at line 216 of file cl_list.c.

{
    if (!list || !out_elem)
        return CL_ERR_INVALID_PARAMS;
 
    if (!list->size)
        return CL_ERR_EMPTY;
 
    *out_elem = list->tail->data;
    return CL_ERR_OK;
}

CL_ListGetPtr()

CL_Error CL_ListGetPtr	(	const CL_List *const	list,
		u32	index,
		void **	out_elem
	)

Gets an element at the specified index as a pointer, so the user can modify it.

Parameters

list	The list to get the element from.
index	The index of the element to get.
out_elem	[OUTPUT] A pointer to the element at the specified index.

Returns

CL_Error The error code.

Note

This operation is not O(1) for lists. Consider using a vector if you need random access.

Definition at line 186 of file cl_list.c.

{
    if (!list || !out_elem)
        return CL_ERR_INVALID_PARAMS;
 
    if (index >= list->size)
        return CL_ERR_OUT_OF_BOUNDS;
 
    u32 idx = 0;
    struct __ListNode *current = list->head;
    while (idx++ < index)
        current = current->next;
 
    // Now current is the node at the specified index.
    *out_elem = current->data;
    return CL_ERR_OK;
}

CL_ListInsertAt()

CL_Error CL_ListInsertAt	(	CL_List *const	list,
		u32	index,
		const void *const	elem
	)

Inserts an element at the specified index.

Parameters

list	The list to insert the element to.
index	The index to insert the element at.
elem	The element to insert.

Returns

CL_Error The error code.

Note

This operation is not O(1) for lists. Consider using a vector if you need random access.

Definition at line 228 of file cl_list.c.

{
    if (!list || !elem)
        return CL_ERR_INVALID_PARAMS;
 
    if (index > list->size) // list->size is a valid index to insert at (insert at the back).
        return CL_ERR_OUT_OF_BOUNDS;
 
    if (index == 0) // Insert at the front.
        return CL_ListPushFront(list, elem);
    else if (index == list->size) // Insert at the back.
        return CL_ListPushBack(list, elem);
 
    // If here, we need to insert in the middle.
    struct __ListNode *new_node = create_node(list, elem), *current = list->head;
    if (!new_node)
        return CL_ERR_NO_MEMORY;
 
    u32 idx = 0;
    while (idx++ < index)
        current = current->next;
 
    // Now current is the node at the specified index.
    new_node->prev = current->prev;
    new_node->next = current;
    current->prev = new_node;
    new_node->prev->next = new_node;
 
    list->size++;
    return CL_ERR_OK;
}

CL_ListIsEmpty()

bool CL_ListIsEmpty

(

const CL_List *const

list

)

Checks if the list is empty.

Parameters

list	The list to check.

Returns

true if the list is empty, false otherwise.

Definition at line 339 of file cl_list.c.

{
    return !list || !list->size;
}

CL_ListPopBack()

void CL_ListPopBack	(	CL_List *const	list,
		void *	out_elem
	)

Removes the last element from the list, optionally returning it.

Parameters

list	The list to remove the last element from.
out_elem	[OUTPUT] The removed element, if not NULL.

Definition at line 124 of file cl_list.c.

{
    if (!list || !list->size)
        return;
 
    struct __ListNode *last = list->tail;
    if (out_elem)
        memcpy(out_elem, last->data, list->elem_size);
 
    if (list->size == 1) // Only one element in the list, reset head and tail.
        list->head = list->tail = NULL;
    else
    {
        list->tail = last->prev; // Set the tail to the previous node.
        list->tail->next = NULL; // The new tail's next is NULL.
    }
 
    MEM_Free(list->allocator, last->data);
    MEM_Free(list->allocator, last);
    list->size--;
}

CL_ListPopFront()

void CL_ListPopFront	(	CL_List *const	list,
		void *	out_elem
	)

Removes the first element from the list, optionally returning it.

Parameters

list	The list to remove the first element from.
out_elem	[OUTPUT] The removed element, if not NULL.

Definition at line 146 of file cl_list.c.

{
    if (!list || !list->size)
        return;
 
    struct __ListNode *first = list->head;
    if (out_elem)
        memcpy(out_elem, first->data, list->elem_size);
 
    if (list->size == 1) // Only one element in the list, reset head and tail.
        list->head = list->tail = NULL;
    else
    {
        list->head = first->next; // Set the head to the next node;
        list->head->prev = NULL;  // The new head's previous is NULL.
    }
 
    MEM_Free(list->allocator, first->data);
    MEM_Free(list->allocator, first);
    list->size--;
}

CL_ListPushBack()

CL_Error CL_ListPushBack	(	CL_List *const	list,
		const void *const	elem
	)

Adds an element at the end of the list.

Parameters

list	The list to add the element to.
elem	The element to add.

Returns

CL_Error The error code.

Definition at line 80 of file cl_list.c.

{
    if (!list || !elem)
        return CL_ERR_INVALID_PARAMS;
 
    struct __ListNode *new_node = create_node(list, elem);
    if (!new_node)
        return CL_ERR_NO_MEMORY;
 
    if (!list->tail) // Empty list, set head and tail to the new node.
        list->head = list->tail = new_node;
    else
    {
        new_node->prev = list->tail; // Set the new node's previous to the current tail.
        list->tail->next = new_node; // Set the current tail's next to the new node.
        list->tail = new_node;       // The new node is now the tail.
    }
 
    list->size++;
    return CL_ERR_OK;
}

CL_ListPushFront()

CL_Error CL_ListPushFront	(	CL_List *const	list,
		const void *const	elem
	)

Adds an element at the front of the list.

Parameters

list	The list to add the element to.
elem	The element to add.

Returns

CL_Error The error code.

Definition at line 102 of file cl_list.c.

{
    if (!list || !elem)
        return CL_ERR_INVALID_PARAMS;
 
    struct __ListNode *new_node = create_node(list, elem);
    if (!new_node)
        return CL_ERR_NO_MEMORY;
 
    if (!list->head) // Empty list, set head and tail to the new node.
        list->head = list->tail = new_node;
    else
    {
        new_node->next = list->head; // Set the new node's next to the current head.
        list->head->prev = new_node; // Set the current head's previous to the new node.
        list->head = new_node;       // The new node is now the head.
    }
 
    list->size++;
    return CL_ERR_OK;
}

CL_ListRemoveAt()

CL_Error CL_ListRemoveAt	(	CL_List *const	list,
		u32	index,
		void *	out_elem
	)

Removes an element at the specified index.

Parameters

list	The list to remove the element from.
index	The index of the element to remove.
out_elem	[OUTPUT] The removed element, if not NULL.

Returns

CL_Error The error code.

Note

This operation is not O(1) for lists. Consider using a vector if you need random access.

Definition at line 260 of file cl_list.c.

{
    if (!list)
        return CL_ERR_INVALID_PARAMS;
 
    if (index >= list->size)
        return CL_ERR_OUT_OF_BOUNDS;
 
    if (index == 0) // Remove from the front.
        CL_ListPopFront(list, out_elem);
    else if (index == list->size - 1) // Remove from the back.
        CL_ListPopBack(list, out_elem);
    else
    {
        // If here, we need to remove from the middle.
        struct __ListNode *current = list->head;
        u32 idx = 0;
        while (idx++ < index)
            current = current->next;
 
        // Now current is the node at the specified index.
        current->prev->next = current->next;
        current->next->prev = current->prev;
 
        if (out_elem)
            memcpy(out_elem, current->data, list->elem_size);
 
        MEM_Free(list->allocator, current);
        list->size--;
    }
 
    return CL_ERR_OK;
}

CL_ListSearch()

bool CL_ListSearch	(	const CL_List *const	list,
		const void *const	elem,
		CL_CompareFn	compare_fn,
		u32 *	out_index
	)

Searches for an element in the list.

Parameters

list	The list to search in.
elem	The element to search for.
compare_fn	The comparison function.
out_elem	[OUTPUT] The index of the element, if found and not NULL.

Returns

true if the element was found, false otherwise.

Definition at line 294 of file cl_list.c.

{
    if (!list || !elem || !compare_fn)
        return false;
 
    struct __ListNode *current = list->head;
    u32 idx = 0;
    while (current)
    {
        if (compare_fn(current->data, elem) == 0)
        {
            if (out_index)
                *out_index = idx;
            return true;
        }
 
        current = current->next;
    }
 
    return false;
}

CL_ListSize()

u32 CL_ListSize

(

const CL_List *const

list

)

Gets the number of elements in the list.

Parameters

list	The list to get the size of.

Returns

The number of elements in the list.

Definition at line 334 of file cl_list.c.

{
    return list ? list->size : 0;
}