napr_heap.c File Reference

Implementation of the generic binary heap. More...

#include <apr_thread_mutex.h>
#include <string.h>
#include "debug.h"
#include "napr_heap.h"

Include dependency graph for napr_heap.c:

Go to the source code of this file.

Functions
napr_heap_t *	napr_heap_make (apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp)
	Creates a new 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.
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_r (napr_heap_t *heap, void *datum)
	Inserts an element into a thread-safe heap.

Detailed Description

Implementation of the generic binary heap.

Definition in file napr_heap.c.

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: