napr_heap.h File Reference

A generic binary heap implementation (min-heap or max-heap). More...

#include <apr_pools.h>

Include dependency graph for napr_heap.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef struct napr_heap_t	napr_heap_t
	Opaque heap structure.
typedef int()	napr_heap_cmp_callback_fn_t(const void *, const void *)
	Callback function to compare two elements in the heap.
typedef void()	napr_heap_del_callback_fn_t(void *)
	Optional callback function to delete/deallocate an element when not using APR pools.

Functions
napr_heap_t *	napr_heap_make (apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp)
	Creates a new heap.
napr_heap_t *	napr_heap_make_r (apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp)
	Creates a new thread-safe heap.
int	napr_heap_insert (napr_heap_t *heap, void *datum)
	Inserts an element into the heap, maintaining the heap property.
void *	napr_heap_extract (napr_heap_t *heap)
	Removes and returns the element at the top of the heap (the min or max element).
void *	napr_heap_get_nth (const napr_heap_t *heap, unsigned int n)
	Gets the element at a specific index in the heap's internal array.
unsigned int	napr_heap_size (const napr_heap_t *heap)
	Gets the current number of elements in the heap.
int	napr_heap_insert_r (napr_heap_t *heap, void *datum)
	Inserts an element into a thread-safe heap.

Detailed Description

A generic binary heap implementation (min-heap or max-heap).

Definition in file napr_heap.h.

Typedef Documentation

napr_heap_cmp_callback_fn_t

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

Callback function to compare two elements in the heap.

Parameters

[in]	a	The first element.
[in]	b	The second element.

Returns

Should return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

Definition at line 38 of file napr_heap.h.

napr_heap_del_callback_fn_t

typedef void() napr_heap_del_callback_fn_t(void *)

Optional callback function to delete/deallocate an element when not using APR pools.

Parameters

[in]

data

The element to delete.

Definition at line 44 of file napr_heap.h.

Function Documentation

napr_heap_extract()

void * napr_heap_extract

(

napr_heap_t *

heap

)

Removes and returns the element at the top of the heap (the min or max element).

Parameters

[in]

heap

The heap.

Returns

A pointer to the top element, or NULL if the heap is empty.

Definition at line 122 of file napr_heap.c.

Referenced by ft_report_duplicates(), and ft_report_json().

Here is the caller graph for this function:

napr_heap_get_nth()

void * napr_heap_get_nth	(	const napr_heap_t *	heap,
		unsigned int	n
	)

Gets the element at a specific index in the heap's internal array.

Parameters

[in]	heap	The heap.
[in]	n	The index.

Returns

A pointer to the nth element, or NULL if the index is out of bounds.

Warning

Modifying the element in a way that changes its comparison order will violate the heap property and lead to incorrect behavior.

Definition at line 173 of file napr_heap.c.

napr_heap_insert()

int napr_heap_insert	(	napr_heap_t *	heap,
		void *	datum
	)

Inserts an element into the heap, maintaining the heap property.

Parameters

[in]	heap	The heap.
[in]	datum	The data item to insert.

Returns

0 on success, -1 on failure.

Definition at line 70 of file napr_heap.c.

References DEBUG_ERR.

Referenced by napr_heap_insert_r().

Here is the caller graph for this function:

napr_heap_insert_r()

int napr_heap_insert_r	(	napr_heap_t *	heap,
		void *	datum
	)

Inserts an element into a thread-safe heap.

Parameters

[in]	heap	The thread-safe heap.
[in]	datum	The data item to insert.

Returns

0 on success, -1 on failure.

Definition at line 204 of file napr_heap.c.

References DEBUG_ERR, and napr_heap_insert().

Here is the call graph for this function:

napr_heap_make()

napr_heap_t * napr_heap_make	(	apr_pool_t *	pool,
		napr_heap_cmp_callback_fn_t *	cmp
	)

Creates a new heap.

A heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. This implementation provides O(log n) time complexity for insertions and O(1) for finding the min/max element.

Parameters

[in]	pool	The APR pool to use for allocations.
[in]	cmp	The comparison function that defines the heap order.

Returns

A pointer to the new heap, or NULL on error.

Definition at line 48 of file napr_heap.c.

Referenced by napr_heap_make_r().

Here is the caller graph for this function:

napr_heap_make_r()

napr_heap_t * napr_heap_make_r	(	apr_pool_t *	pool,
		napr_heap_cmp_callback_fn_t *	cmp
	)

Creates a new thread-safe heap.

Parameters

[in]	pool	The APR pool to use for allocations.
[in]	cmp	The comparison function.

Returns

A pointer to the new thread-safe heap, or NULL on error.

Definition at line 189 of file napr_heap.c.

References napr_heap_make().

Here is the call graph for this function:

napr_heap_size()

unsigned int napr_heap_size

(

const napr_heap_t *

heap

)

Gets the current number of elements in the heap.

Parameters

[in]

heap

The heap.

Returns

The number of elements.

Definition at line 181 of file napr_heap.c.

Referenced by ftwin_main().

Here is the caller graph for this function: