cl_prioqueue.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_PQUEUE_FOREACH(__type, __name, __queue, ...)

Typedefs
typedef struct __PQueue	CL_PQueue
typedef int(*	CL_PQueueCompareFn) (const void *, const void *)

Functions
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

CL_PQUEUE_FOREACH

#define CL_PQUEUE_FOREACH	(		__type,
			__name,
			__queue,
			...
	)

Value:

    for (u32 __i = 0; __i < CL_PQueueSize(__queue); __i++)                                                             \
    {                                                                                                                  \
        __type *__pq_arr = (__type *)CL_PQueueAsArray(__queue);                                                        \
        __type __name = __pq_arr[__i];                                                                                 \
        __VA_ARGS__                                                                                                    \
    }

Definition at line 15 of file cl_prioqueue.h.

    {                                                                                                                  \
        __type *__pq_arr = (__type *)CL_PQueueAsArray(__queue);                                                        \
        __type __name = __pq_arr[__i];                                                                                 \
        __VA_ARGS__                                                                                                    \
    }

Typedef Documentation

CL_PQueue

typedef struct __PQueue CL_PQueue

Definition at line 11 of file cl_prioqueue.h.

CL_PQueueCompareFn

typedef int(* CL_PQueueCompareFn) (const void *, const void *)

Definition at line 29 of file cl_prioqueue.h.

Function Documentation

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