Structures and prototypes for binary heaps. More...

#include <freeradius-devel/build.h>
#include <freeradius-devel/missing.h>
#include <freeradius-devel/util/talloc.h>
#include <stdint.h>
#include <sys/types.h>

Include dependency graph for heap.h:

Go to the source code of this file.

Data Structures
struct	fr_heap_t
	The main heap structure. More...

Macros
#define	_CONST const

#define	fr_heap_alloc(_ctx, _cmp, _type, _field, _init) _fr_heap_alloc(_ctx, _cmp, NULL, (size_t)offsetof(_type, _field), _init)
	Creates a heap that can be used with non-talloced elements. More...

#define	fr_heap_foreach(_heap, _type, _data)
	Iterate over the contents of a heap. More...

#define	FR_HEAP_INDEX_INVALID (0)

#define	fr_heap_talloc_alloc(_ctx, _cmp, _talloc_type, _field, _init) _fr_heap_alloc(_ctx, _cmp, #_talloc_type, (size_t)offsetof(_talloc_type, _field), _init)
	Creates a heap that verifies elements are of a specific talloc type. More...

#define	FR_HEAP_TALLOC_HEADERS 2
	How many talloc headers need to be pre-allocated for a heap. More...

#define	FR_HEAP_VERIFY(_heap) fr_heap_verify(__FILE__, __LINE__, _heap)

Typedefs
typedef int8_t(*	fr_heap_cmp_t) (void const a, void const b)
	Comparator to order heap elements. More...

typedef unsigned int	fr_heap_index_t

typedef unsigned int	fr_heap_iter_t

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

static bool	fr_heap_entry_inserted (fr_heap_index_t heap_idx)
	Check if an entry is inserted into a heap. More...

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

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

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

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

static unsigned int	fr_heap_num_elements (fr_heap_t *h)
	Return the number of elements in the heap. More...

static void *	fr_heap_peek (fr_heap_t *h)
	Return the item from the top of the heap but don't pop it. More...

static void *	fr_heap_peek_at (fr_heap_t *h, fr_heap_index_t idx)
	Peek at a specific index in the heap. More...

static void *	fr_heap_peek_tail (fr_heap_t *h)
	Peek at the last element in the heap (not necessarily the bottom) More...

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

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. More...

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

Detailed Description

Structures and prototypes for binary heaps.

Copyright: 2007 Alan DeKok

Definition in file heap.h.

Data Structure Documentation

◆ fr_heap_t

struct fr_heap_t

The main heap structure.

A heap entry is made of a pointer to the object, which contains the key. The heap itself is an array of pointers.

Heaps normally support only ordered insert, and extraction of the minimum element. The heap entry can contain an "int" field that holds the entries position in the heap. The offset of the field is held inside of the heap structure.

Definition at line 66 of file heap.h.

Data Fields
fr_heap_cmp_t _CONST	cmp	Comparator function.
unsigned int _CONST	min	Minimum number of elements we allow the heap to reduce down to.
unsigned int _CONST	num_elements	Number of nodes used.
size_t _CONST	offset	Offset of heap index in element structure.
void *_CONST	p[]	Array of nodes.
unsigned int _CONST	size	Number of nodes allocated.
char const *_CONST	type	Talloc type of elements.

Macro Definition Documentation

◆ _CONST

#define _CONST const

Definition at line 44 of file heap.h.

◆ fr_heap_alloc

#define fr_heap_alloc	(	_ctx,
		_cmp,
		_type,
		_field,
		_init
	)	_fr_heap_alloc(_ctx, _cmp, NULL, (size_t)offsetof(_type, _field), _init)

Creates a heap that can be used with non-talloced elements.

Parameters

[in]	_ctx	Talloc ctx to allocate heap in.
[in]	_cmp	Comparator used to compare elements.
[in]	_type	Of elements.
[in]	_field	to store heap indexes in.
[in]	_init	the initial number of elements to allocate. Pass 0 to use the default.

Definition at line 100 of file heap.h.

◆ fr_heap_foreach

#define fr_heap_foreach	(	_heap,
		_type,
		_data
	)

Value:

{ \
        fr_heap_iter_t _iter; \
        for (_type *_data = fr_heap_iter_init(_heap, &_iter); _data; _data = fr_heap_iter_next(_heap, &_iter))

Iterate over the contents of a heap.

Note: The initializer section of a for loop can't declare variables with distinct base types, so we require a containing block, and can't follow the standard do {...} while(0) dodge. The code to be run for each item in the heap should thus start with one open brace and end with two close braces, and shouldn't be followed with a semicolon. This may fake out code formatting programs and code-aware editors.

Parameters

[in]	_heap	to iterate over.
[in]	_type	of item the heap contains.
[in]	_data	Name of variable holding a pointer to the heap element. Will be declared in the scope of the loop.

Definition at line 205 of file heap.h.

◆ FR_HEAP_INDEX_INVALID

#define FR_HEAP_INDEX_INVALID (0)

Definition at line 83 of file heap.h.

◆ fr_heap_talloc_alloc

#define fr_heap_talloc_alloc	(	_ctx,
		_cmp,
		_talloc_type,
		_field,
		_init
	)	_fr_heap_alloc(_ctx, _cmp, #_talloc_type, (size_t)offsetof(_talloc_type, _field), _init)

Creates a heap that verifies elements are of a specific talloc type.

Parameters

[in]	_ctx	Talloc ctx to allocate heap in.
[in]	_cmp	Comparator used to compare elements.
[in]	_talloc_type	of elements.
[in]	_field	to store heap indexes in.
[in]	_init	the initial number of elements to allocate. Pass 0 to use the default.

Returns

A new heap.
NULL on error.

Definition at line 115 of file heap.h.

◆ FR_HEAP_TALLOC_HEADERS

#define FR_HEAP_TALLOC_HEADERS 2

How many talloc headers need to be pre-allocated for a heap.

Definition at line 87 of file heap.h.

◆ FR_HEAP_VERIFY

#define FR_HEAP_VERIFY ( _heap ) fr_heap_verify(__FILE__, __LINE__, _heap)

Definition at line 212 of file heap.h.

Typedef Documentation

◆ fr_heap_cmp_t

typedef int8_t(* fr_heap_cmp_t) (void const *a, void const *b)

Comparator to order heap elements.

Return negative numbers to put 'a' at the top of the heap. Return positive numbers to put 'b' at the top of the heap.

Definition at line 54 of file heap.h.

◆ fr_heap_index_t

typedef unsigned int fr_heap_index_t

Definition at line 80 of file heap.h.

◆ fr_heap_iter_t

typedef unsigned int fr_heap_iter_t

Definition at line 81 of file heap.h.

Function Documentation

◆ _fr_heap_alloc()

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

Definition at line 57 of file heap.c.

◆ fr_heap_entry_inserted()

static bool fr_heap_entry_inserted ( fr_heap_index_t heap_idx )

inlinestatic

Check if an entry is inserted into a heap.

Parameters

[in] heap_idx from object to check.

Definition at line 124 of file heap.h.

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_num_elements()

static unsigned int fr_heap_num_elements ( fr_heap_t * h )

inlinestatic

Return the number of elements in the heap.

Parameters

[in] h to return the number of elements from.

Definition at line 179 of file heap.h.

Here is the caller graph for this function:

◆ fr_heap_peek()

static void* fr_heap_peek ( fr_heap_t * h )

inlinestatic

Return the item from the top of the heap but don't pop it.

Parameters

[in] h to return element from.

Returns

Element at the top of the heap.
NULL if no elements remain in the heap.

Definition at line 136 of file heap.h.

Here is the caller graph for this function:

◆ fr_heap_peek_at()

static void* fr_heap_peek_at	(	fr_heap_t *	h,
		fr_heap_index_t	idx
	)

inlinestatic

Peek at a specific index in the heap.

Parameters

[in]	h	to return element from.
[in]	idx	to lookup

Returns

Element at the top of the heap.
NULL if index outside of the range of the heap.

Definition at line 151 of file heap.h.

Here is the caller graph for this function:

◆ fr_heap_peek_tail()

static void* fr_heap_peek_tail ( fr_heap_t * h )

inlinestatic

Peek at the last element in the heap (not necessarily the bottom)

Parameters

[in] h to return element from.

Returns

Last element in the heap.
NULL if no elements remain in the heap.

Definition at line 165 of file heap.h.

◆ 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 *	hp
	)

Definition at line 380 of file heap.c.

Here is the call graph for this function:

Data Structures

Macros

Typedefs

Functions

Detailed Description

Data Structure Documentation

◆ fr_heap_t

Macro Definition Documentation

◆ _CONST

◆ fr_heap_alloc

◆ fr_heap_foreach

◆ FR_HEAP_INDEX_INVALID

◆ fr_heap_talloc_alloc

◆ FR_HEAP_TALLOC_HEADERS

◆ FR_HEAP_VERIFY

Typedef Documentation

◆ fr_heap_cmp_t

◆ fr_heap_index_t

◆ fr_heap_iter_t

Function Documentation

◆ _fr_heap_alloc()

◆ fr_heap_entry_inserted()

◆ fr_heap_extract()

◆ fr_heap_insert()

◆ fr_heap_iter_init()

◆ fr_heap_iter_next()

◆ fr_heap_num_elements()

◆ fr_heap_peek()

◆ fr_heap_peek_at()

◆ fr_heap_peek_tail()

◆ fr_heap_pop()

◆ fr_heap_pre_alloc_size()

◆ fr_heap_verify()