cl_prioqueue.c File Reference

#include "cl_prioqueue.h"
#include <alloca.h>
#include <stdlib.h>
#include <string.h>

Go to the source code of this file.

Classes
struct	__PQueue

Macros
#define	RESZ_FACTOR   2
#define	BASE_CAPACITY   10
#define	PARENT(i)   ((i - 1) / 2)
#define	LEFT(i)   (2 * i + 1)
#define	RIGHT(i)   (2 * i + 2)

Functions
_PRIVATE void	pSwap (void *const a, void *const b, u32 size)
_PRIVATE void	bubble_up_leaf (CL_PQueue *const pq)
_PRIVATE void	bubble_down_root (CL_PQueue *const pq)
_PRIVATE void *	realloc_data (CL_PQueue *const pq, u32 new_capacity)
CL_PQueue *	CL_PQueueAllocWithCapacity (MEM_Allocator *const alloc, u32 capacity, u32 elem_sz, CL_PQueueCompareFn compare_fn)
	Initializes a priority queue with the allocated memory provided by the user.
CL_PQueue *	CL_PQueueAlloc (MEM_Allocator *const alloc, u32 elem_sz, CL_PQueueCompareFn compare_fn)
	Initializes a priority queue with a default capacity.
void	CL_PQueueFree (CL_PQueue *const pq)
	Frees the memory previously assigned to the priority queue.
CL_Error	CL_PQueueEnqueue (CL_PQueue *const pq, const void *const elem)
	Adds an element to the priority queue.
CL_Error	CL_PQueueDequeue (CL_PQueue *const pq, void *out_elem)
	Removes the element with the highest priority from the priority queue.
CL_Error	CL_PQueuePeek (const CL_PQueue *const pq, void *out_elem)
	Gets the element with the highest priority from the priority queue without removing it.
u32	CL_PQueueSize (const CL_PQueue *const pq)
	Gets the number of elements in the priority queue.
bool	CL_PQueueIsEmpty (const CL_PQueue *const pq)
	Checks if the priority queue is empty.

Macro Definition Documentation

BASE_CAPACITY

#define BASE_CAPACITY   10

Definition at line 18 of file cl_prioqueue.c.

LEFT

#define LEFT

(

i

)

(2 * i + 1)

Definition at line 26 of file cl_prioqueue.c.

PARENT

#define PARENT

(

i

)

((i - 1) / 2)

Definition at line 25 of file cl_prioqueue.c.

RESZ_FACTOR

#define RESZ_FACTOR   2

Definition at line 17 of file cl_prioqueue.c.

RIGHT

#define RIGHT

(

i

)

(2 * i + 2)

Definition at line 27 of file cl_prioqueue.c.

Function Documentation

bubble_down_root()

_PRIVATE void bubble_down_root

(

CL_PQueue *const

pq

)

Definition at line 61 of file cl_prioqueue.c.

{
    if (!pq)
        return;
 
    u32 idx = 0, smallest_idx = 0;
    u8 *root_elem, *left_elem, *smallest_elem;
 
    // Comparing the root with its children. If the root has a lower priority
    // than one of its children, we need to swap them and continue bubbling down.
    // The parent node is the first element of the array, i.e. at index 0. The left
    // one follows at index 1, and the right one at index 2, etc. We iterate until
    // we reach the leaf nodes (i.e. the last level of the tree). Leaf nodes DO NOT
    // have children, so LEFT (and RIGHT) will be out of bounds. Since LEFT is lower
    // than RIGHT, we use it as stopping condition.
    while (LEFT(idx) < pq->size)
    {
        root_elem = (u8 *)(pq->data) + (idx * pq->elem_size);
        left_elem = (u8 *)(pq->data) + (LEFT(idx) * pq->elem_size);
        smallest_idx = idx;
 
        // If the left child has a higher priority than the root
        if (pq->compare_fn(left_elem, root_elem) < 0)
            smallest_idx = LEFT(idx);
 
        // Comparing the current smallest (could be the root or the left child) with the right child.
        if (RIGHT(idx) < pq->size && pq->compare_fn((u8 *)(pq->data) + (RIGHT(idx) * pq->elem_size),
                                                    (u8 *)(pq->data) + (smallest_idx * pq->elem_size)) < 0)
            smallest_idx = RIGHT(idx);
 
        // If the root has a higher priority than both children
        if (smallest_idx == idx)
            break; // We're done.
 
        // Swapping the root with the child that has a higher priority.
        smallest_elem = (u8 *)(pq->data) + (smallest_idx * pq->elem_size);
        pSwap(root_elem, smallest_elem, pq->elem_size);
        idx = smallest_idx; // Moving down the tree.
    }
}

bubble_up_leaf()

_PRIVATE void bubble_up_leaf

(

CL_PQueue *const

pq

)

Definition at line 40 of file cl_prioqueue.c.

{
    if (!pq)
        return;
 
    u32 new_idx = pq->size - 1;
    u8 *parent_elem, *new_elem;
    while (new_idx > 0)
    {
        parent_elem = (u8 *)(pq->data) + (PARENT(new_idx) * pq->elem_size);
        new_elem = (u8 *)(pq->data) + (new_idx * pq->elem_size);
        if (pq->compare_fn(new_elem, parent_elem) < 0)
            pSwap(parent_elem, new_elem, pq->elem_size);
 
        new_idx = PARENT(new_idx); // Moving up the tree.
    }
}

CL_PQueueAlloc()

CL_PQueue * CL_PQueueAlloc	(	MEM_Allocator *const	alloc,
		u32	elem_sz,
		CL_PQueueCompareFn	compare_fn
	)

Initializes a priority queue with a default capacity.

Parameters

alloc	The memory allocator to use.
elem_sz	The size of each element.
compare_fn	The comparison function to use for handling priorities.

Returns

Pointer to the new priority queue or NULL on error.

Definition at line 143 of file cl_prioqueue.c.

{
    return CL_PQueueAllocWithCapacity(alloc, BASE_CAPACITY, elem_sz, compare_fn);
}

CL_PQueueAllocWithCapacity()

CL_PQueue * CL_PQueueAllocWithCapacity	(	MEM_Allocator *const	alloc,
		u32	capacity,
		u32	elem_sz,
		CL_PQueueCompareFn	compare_fn
	)

Initializes a priority queue with the allocated memory provided by the user.

Parameters

allocator	The memory allocator to use.
capacity	The initial capacity of the priority queue.
elem_sz	The size of each element.
compare_fn	The comparison function to use for handling priorities.

Returns

Pointer to the new priority queue or NULL on error.

Definition at line 115 of file cl_prioqueue.c.

{
    if (!alloc || !capacity || !elem_sz || !compare_fn)
        return NULL;
 
    CL_PQueue *const pq = MEM_Alloc(alloc, sizeof(CL_PQueue));
    if (!pq)
        return NULL;
 
    *pq = (CL_PQueue){
        .data = MEM_Alloc(alloc, capacity * elem_sz),
        .size = 0,
        .capacity = capacity,
        .elem_size = elem_sz,
        .compare_fn = compare_fn,
        .allocator = alloc,
    };
 
    if (!pq->data)
    {
        MEM_Free(alloc, pq);
        return NULL;
    }
 
    return pq;
}

CL_PQueueDequeue()

CL_Error CL_PQueueDequeue	(	CL_PQueue *const	pq,
		void *	out_elem
	)

Removes the element with the highest priority from the priority queue.

Parameters

pq	The priority queue to remove the element from.
out_elem	[OUTPUT] The element with the highest priority.

Returns

CL_Error The error code.

Definition at line 179 of file cl_prioqueue.c.

{
    if (!pq || !out_elem)
        return CL_ERR_INVALID_PARAMS;
 
    if (!pq->size)
        return CL_ERR_EMPTY;
 
    // Getting the element with the highest priority (i.e. the root of the tree).
    memcpy(out_elem, pq->data, pq->elem_size);
    pq->size--;
 
    // Moving the last element to the root and bubbling it down.
    const u32 last_elem_offset = pq->size * pq->elem_size;
    memcpy(pq->data, (u8 *)(pq->data) + last_elem_offset, pq->elem_size);
    bubble_down_root(pq);
    return CL_ERR_OK;
}

CL_PQueueEnqueue()

CL_Error CL_PQueueEnqueue	(	CL_PQueue *const	pq,
		const void *const	elem
	)

Adds an element to the priority queue.

Parameters

pq	The priority queue to add the element to.
elem	The element to add.

Returns

CL_Error The error code.

Definition at line 157 of file cl_prioqueue.c.

{
    if (!pq || !elem)
        return CL_ERR_INVALID_PARAMS;
 
    if (pq->size >= pq->capacity)
    {
        const u32 new_capacity = pq->capacity * RESZ_FACTOR;
        if (!realloc_data(pq, new_capacity))
            return CL_ERR_NO_MEMORY;
    }
 
    // Adding the element at the end (queues are FIFO)
    const u32 offset = pq->size * pq->elem_size;
    memcpy((u8 *)(pq->data) + offset, elem, pq->elem_size);
    pq->size++;
 
    // Bubbling up the new element to its correct position.
    bubble_up_leaf(pq);
    return CL_ERR_OK;
}

CL_PQueueFree()

void CL_PQueueFree

(

CL_PQueue *const

pq

)

Frees the memory previously assigned to the priority queue.

Parameters

pq	The priority queue to release the memory of.

Note

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

Definition at line 148 of file cl_prioqueue.c.

{
    if (!pq)
        return;
 
    MEM_Free(pq->allocator, pq->data);
    MEM_Free(pq->allocator, pq);
}

CL_PQueueIsEmpty()

bool CL_PQueueIsEmpty

(

const CL_PQueue *const

pq

)

Checks if the priority queue is empty.

Parameters

pq	The priority queue to check.

Returns

Whether the priority queue is empty.

Definition at line 216 of file cl_prioqueue.c.

{
    return pq ? pq->size == 0 : true;
}

CL_PQueuePeek()

CL_Error CL_PQueuePeek	(	const CL_PQueue *const	pq,
		void *	out_elem
	)

Gets the element with the highest priority from the priority queue without removing it.

Parameters

pq	The priority queue to get the element from.
out_elem	[OUTPUT] The element with the highest priority.

Returns

CL_Error The error code.

Definition at line 198 of file cl_prioqueue.c.

{
    if (!pq || !out_elem)
        return CL_ERR_INVALID_PARAMS;
 
    if (!pq->size)
        return CL_ERR_EMPTY;
 
    // Getting the element with the highest priority (i.e. the root of the tree).
    memcpy(out_elem, pq->data, pq->elem_size);
    return CL_ERR_OK;
}

CL_PQueueSize()

u32 CL_PQueueSize

(

const CL_PQueue *const

pq

)

Gets the number of elements in the priority queue.

Parameters

pq	The priority queue to get the number of elements from.

Returns

The number of elements in the priority queue.

Definition at line 211 of file cl_prioqueue.c.

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

pSwap()

_PRIVATE void pSwap ( void *const  a, void *const  b, u32  size  )

inline

Definition at line 29 of file cl_prioqueue.c.

{
    void *temp = alloca(size);
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
}

realloc_data()

_PRIVATE void * realloc_data ( CL_PQueue *const  pq, u32  new_capacity  )

inline

Definition at line 102 of file cl_prioqueue.c.

{
    void *new_data = MEM_Realloc(pq->allocator, pq->data, new_capacity * pq->elem_size);
    if (!new_data)
        return NULL;
 
    pq->data = new_data;
    pq->capacity = new_capacity;
    return new_data;
}