Functions for a basic binary heaps. More...

#include <freeradius-devel/util/debug.h>
#include <freeradius-devel/util/heap.h>
#include <freeradius-devel/util/misc.h>
#include <freeradius-devel/util/strerror.h>

Include dependency graph for heap.c:

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

Go to the source code of this file.

Macros
#define	_HEAP_PRIVATE 1

#define	HEAP_LEFT(_x) (2 * (_x))

#define	HEAP_PARENT(_x) ((_x) >> 1)

#define	HEAP_RIGHT(_x) (2 * (_x) + 1 )

#define	HEAP_SWAP(_a, _b) do { void *_tmp = _a; _a = _b; _b = _tmp; } while (0)

#define	INITIAL_CAPACITY 2048

#define	OFFSET_RESET(_heap, _idx) index_set(_heap, _heap->p[_idx], 0)

#define	OFFSET_SET(_heap, _idx) index_set(_heap, _heap->p[_idx], _idx)

Functions
fr_heap_t *	_fr_heap_alloc (TALLOC_CTX ctx, fr_heap_cmp_t cmp, char const type, size_t offset, unsigned int init)

static void	fr_heap_bubble (fr_heap_t *h, fr_heap_index_t child)

int	fr_heap_extract (fr_heap_t *hp, void data)
	Remove a node from the heap.

int	fr_heap_insert (fr_heap_t *hp, void data)
	Insert a new element into the heap.

void *	fr_heap_iter_init (fr_heap_t h, fr_heap_iter_t iter)
	Iterate over entries in heap.

void *	fr_heap_iter_next (fr_heap_t h, fr_heap_iter_t iter)
	Get the next entry in a heap.

void *	fr_heap_pop (fr_heap_t **hp)
	Remove a node from the heap.

size_t	fr_heap_pre_alloc_size (unsigned int count)
	Return how many bytes need to be allocated to hold a heap of a given size.

void	fr_heap_verify (char const file, int line, fr_heap_t h)

static fr_heap_index_t	index_get (fr_heap_t h, void data)

static void	index_set (fr_heap_t h, void data, fr_heap_index_t idx)

static int	realloc_heap (fr_heap_t **hp, unsigned int n_size)

Detailed Description

Functions for a basic binary heaps.

Copyright: 2005,2006 The FreeRADIUS server project

Definition in file heap.c.

Macro Definition Documentation

◆ _HEAP_PRIVATE

#define _HEAP_PRIVATE 1

Definition at line 25 of file heap.c.

◆ HEAP_LEFT

#define HEAP_LEFT ( _x ) (2 * (_x))

Definition at line 39 of file heap.c.

◆ HEAP_PARENT

#define HEAP_PARENT ( _x ) ((_x) >> 1)

Definition at line 38 of file heap.c.

◆ HEAP_RIGHT

#define HEAP_RIGHT ( _x ) (2 * (_x) + 1 )

Definition at line 40 of file heap.c.

◆ HEAP_SWAP

#define HEAP_SWAP	(	_a,
		_b
	)	do { void *_tmp = _a; _a = _b; _b = _tmp; } while (0)

Definition at line 41 of file heap.c.

◆ INITIAL_CAPACITY

#define INITIAL_CAPACITY 2048

Definition at line 31 of file heap.c.

◆ OFFSET_RESET

#define OFFSET_RESET	(	_heap,
		_idx
	)	index_set(_heap, _heap->p[_idx], 0)

Definition at line 103 of file heap.c.

◆ OFFSET_SET

#define OFFSET_SET	(	_heap,
		_idx
	)	index_set(_heap, _heap->p[_idx], _idx)

Definition at line 102 of file heap.c.

Function Documentation

◆ _fr_heap_alloc()

fr_heap_t * _fr_heap_alloc	(	TALLOC_CTX *	ctx,
		fr_heap_cmp_t	cmp,
		char const *	type,
		size_t	offset,
		unsigned int	init
	)

Definition at line 57 of file heap.c.

◆ fr_heap_bubble()

static void fr_heap_bubble	(	fr_heap_t *	h,
		fr_heap_index_t	child
	)

inlinestatic

Definition at line 204 of file heap.c.

Here is the caller graph for this function:

◆ fr_heap_extract()

int fr_heap_extract	(	fr_heap_t **	hp,
		void *	data
	)

Remove a node from the heap.

Parameters

[in,out]	hp	The heap to extract an element from. A new pointer value will be written to hp if the heap is resized.
[in]	data	Data to extract from the heap.

Returns

0 on success.
-1 on failure (no elements or data not found).

Definition at line 239 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_heap_insert()

int fr_heap_insert	(	fr_heap_t **	hp,
		void *	data
	)

Insert a new element into the heap.

Insert element in heap. Normally, p != NULL, we insert p in a new position and bubble up. If p == NULL, then the element is already in place, and key is the position where to start the bubble-up.

Returns -1 on failure (cannot allocate new heap entry)

If offset > 0 the position (index, int) of the element in the heap is also stored in the element itself at the given offset in bytes.

Parameters

[in,out]	hp	The heap to extract an element from. A new pointer value will be written to hp if the heap is resized.
[in]	data	Data to insert into the heap.

Returns

0 on success.
-1 on failure (heap full or malloc error).

Definition at line 146 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_heap_iter_init()

void * fr_heap_iter_init	(	fr_heap_t *	h,
		fr_heap_iter_t *	iter
	)

Iterate over entries in heap.

Note: If the heap is modified the iterator should be considered invalidated.

Parameters

[in]	h	to iterate over.
[in]	iter	Pointer to an iterator struct, used to maintain state between calls.

Returns

User data.
NULL if at the end of the list.

Definition at line 351 of file heap.c.

◆ fr_heap_iter_next()

void * fr_heap_iter_next	(	fr_heap_t *	h,
		fr_heap_iter_t *	iter
	)

Get the next entry in a heap.

Note: If the heap is modified the iterator should be considered invalidated.

Parameters

[in]	h	to iterate over.
[in]	iter	Pointer to an iterator struct, used to maintain state between calls.

Returns

User data.
NULL if at the end of the list.

Definition at line 371 of file heap.c.

◆ fr_heap_pop()

void * fr_heap_pop ( fr_heap_t ** hp )

Remove a node from the heap.

Parameters

[in,out] hp The heap to pop an element from. A new pointer value will be written to hp if the heap is resized.

Returns

The item that was popped.
NULL on error.

Definition at line 322 of file heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_heap_pre_alloc_size()

size_t fr_heap_pre_alloc_size ( unsigned int count )

Return how many bytes need to be allocated to hold a heap of a given size.

This is useful for passing to talloc[_zero]_pooled_object to avoid additional mallocs.

Parameters

[in] count The initial element count.

Returns: The number of bytes to pre-allocate.

Definition at line 52 of file heap.c.

◆ fr_heap_verify()

void fr_heap_verify	(	char const *	file,
		int	line,
		fr_heap_t *	h
	)

Definition at line 380 of file heap.c.

Here is the call graph for this function:

◆ index_get()

static fr_heap_index_t index_get	(	fr_heap_t *	h,
		void *	data
	)

inlinestatic

Definition at line 92 of file heap.c.

Here is the caller graph for this function:

◆ index_set()

static void index_set	(	fr_heap_t *	h,
		void *	data,
		fr_heap_index_t	idx
	)

inlinestatic

Definition at line 97 of file heap.c.

◆ realloc_heap()

static int realloc_heap	(	fr_heap_t **	hp,
		unsigned int	n_size
	)

inlinestatic

Definition at line 106 of file heap.c.

Here is the caller graph for this function:

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ _HEAP_PRIVATE

◆ HEAP_LEFT

◆ HEAP_PARENT

◆ HEAP_RIGHT

◆ HEAP_SWAP

◆ INITIAL_CAPACITY

◆ OFFSET_RESET

◆ OFFSET_SET

Function Documentation

◆ _fr_heap_alloc()

◆ fr_heap_bubble()

◆ fr_heap_extract()

◆ fr_heap_insert()

◆ fr_heap_iter_init()

◆ fr_heap_iter_next()

◆ fr_heap_pop()

◆ fr_heap_pre_alloc_size()

◆ fr_heap_verify()

◆ index_get()

◆ index_set()

◆ realloc_heap()