minmax_heap.h File Reference

Structures and prototypes for binary min-max 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 minmax_heap.h:

Go to the source code of this file.

Macros
#define	fr_minmax_heap_alloc(_ctx, _cmp, _type, _field, _init)    _fr_minmax_heap_alloc(_ctx, _cmp, NULL, (size_t)offsetof(_type, _field), _init)
	Creates a minmax heap that can be used with non-talloced elements. More...
#define	fr_minmax_heap_foreach(_hp, _type, _data)
	Iterate over the contents of a minmax_heap. More...
#define	fr_minmax_heap_talloc_alloc(_ctx, _cmp, _talloc_type, _field, _init)    _fr_minmax_heap_alloc(_ctx, _cmp, #_talloc_type, (size_t)offsetof(_talloc_type, _field), _init)
	Creates a minmax heap that verifies elements are of a specific talloc type. More...
#define	FR_MINMAX_HEAP_TALLOC_HEADERS   2
	How many talloc headers need to be pre-allocated for a minmax heap. More...
#define	FR_MINMAX_HEAP_VERIFY(_hp)   fr_minmax_heap_verify(__FILE__, __LINE__, _hp)

Typedefs
typedef int8_t(*	fr_minmax_heap_cmp_t) (void const *a, void const *b)
	Comparator to order elements. More...
typedef unsigned int	fr_minmax_heap_index_t
typedef unsigned int	fr_minmax_heap_iter_t
typedef struct fr_minmax_heap_s *	fr_minmax_heap_t
	The main minmax heap structure Note that fr_minmax_heap_t is a pointer to fr_minmax_heap_s. More...

Functions
fr_minmax_heap_t *	_fr_minmax_heap_alloc (TALLOC_CTX *ctx, fr_minmax_heap_cmp_t cmp, char const *talloc_type, size_t offset, unsigned int init))
static bool	fr_minmax_heap_entry_inserted (fr_minmax_heap_index_t heap_idx)
	Check if an entry is inserted into a heap. More...
int	fr_minmax_heap_extract (fr_minmax_heap_t *hp, void *data)
int	fr_minmax_heap_insert (fr_minmax_heap_t *hp, void *data)
void *	fr_minmax_heap_iter_init (fr_minmax_heap_t *hp, fr_minmax_heap_iter_t *iter)
	Iterate over entries in a minmax heap. More...
void *	fr_minmax_heap_iter_next (fr_minmax_heap_t *hp, fr_minmax_heap_iter_t *iter)
	Get the next entry in a minmax heap. More...
void *	fr_minmax_heap_max_peek (fr_minmax_heap_t *hp)
void *	fr_minmax_heap_max_pop (fr_minmax_heap_t *hp)
void *	fr_minmax_heap_min_peek (fr_minmax_heap_t *hp)
void *	fr_minmax_heap_min_pop (fr_minmax_heap_t *hp)
uint32_t	fr_minmax_heap_num_elements (fr_minmax_heap_t *hp)
	Return the number of elements in the minmax heap. More...
size_t	fr_minmax_heap_pre_alloc_size (unsigned int count)
void	fr_minmax_heap_verify (char const *file, int line, fr_minmax_heap_t const *hp)

Detailed Description

Structures and prototypes for binary min-max heaps.

Copyright

2021 Network RADIUS SAS (legal.nosp@m.@net.nosp@m.workr.nosp@m.adiu.nosp@m.s.com)

Definition in file minmax_heap.h.

Macro Definition Documentation

fr_minmax_heap_alloc

#define fr_minmax_heap_alloc	(		_ctx,
			_cmp,
			_type,
			_field,
			_init
	)		_fr_minmax_heap_alloc(_ctx, _cmp, NULL, (size_t)offsetof(_type, _field), _init)

Creates a minmax 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 70 of file minmax_heap.h.

fr_minmax_heap_foreach

#define fr_minmax_heap_foreach	(		_hp,
			_type,
			_data
	)

Value:

{ \
        fr_minmax_heap_iter_t _iter; \
        for (_type *_data = fr_minmax_heap_iter_init(_hp, &_iter); _data; _data = fr_minmax_heap_iter_next(_hp, &_iter))

Iterate over the contents of a minmax_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 therefore start with 1 open braces and end with 2 close braces, and shouldn't be followed with a semicolon. This may fake out code formatting programs, including editors.

Parameters

[in]	_hp	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 124 of file minmax_heap.h.

fr_minmax_heap_talloc_alloc

#define fr_minmax_heap_talloc_alloc	(		_ctx,
			_cmp,
			_talloc_type,
			_field,
			_init
	)		_fr_minmax_heap_alloc(_ctx, _cmp, #_talloc_type, (size_t)offsetof(_talloc_type, _field), _init)

Creates a minmax 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 minmax heap.
• NULL on error.

Definition at line 85 of file minmax_heap.h.

FR_MINMAX_HEAP_TALLOC_HEADERS

#define FR_MINMAX_HEAP_TALLOC_HEADERS   2

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

Definition at line 42 of file minmax_heap.h.

FR_MINMAX_HEAP_VERIFY

#define FR_MINMAX_HEAP_VERIFY

(

_hp

)

fr_minmax_heap_verify(__FILE__, __LINE__, _hp)

Definition at line 131 of file minmax_heap.h.

Typedef Documentation

fr_minmax_heap_cmp_t

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

Comparator to order elements.

Return a negative number if 'a' precedes 'b'. Return zero if the ordering of 'a' and 'b' doesn't matter. Return a positive number if 'b' precedes 'a'.

Definition at line 50 of file minmax_heap.h.

fr_minmax_heap_index_t

typedef unsigned int fr_minmax_heap_index_t

Definition at line 37 of file minmax_heap.h.

fr_minmax_heap_iter_t

typedef unsigned int fr_minmax_heap_iter_t

Definition at line 38 of file minmax_heap.h.

fr_minmax_heap_t

typedef struct fr_minmax_heap_s* fr_minmax_heap_t

The main minmax heap structure Note that fr_minmax_heap_t is a pointer to fr_minmax_heap_s.

This added level of indirection lets one allocate/reallocate the heap structure and the array of pointers to items in the minmax heap as a unit without affecting the caller.

Definition at line 57 of file minmax_heap.h.

Function Documentation

_fr_minmax_heap_alloc()

fr_minmax_heap_t* _fr_minmax_heap_alloc	(	TALLOC_CTX *	ctx,
		fr_minmax_heap_cmp_t	cmp,
		char const *	talloc_type,
		size_t	offset,
		unsigned int	init
	)

Definition at line 111 of file minmax_heap.c.

Here is the call graph for this function:

fr_minmax_heap_entry_inserted()

static bool fr_minmax_heap_entry_inserted ( fr_minmax_heap_index_t  heap_idx )

inlinestatic

Check if an entry is inserted into a heap.

Definition at line 93 of file minmax_heap.h.

Here is the caller graph for this function:

fr_minmax_heap_extract()

int fr_minmax_heap_extract	(	fr_minmax_heap_t *	hp,
		void *	data
	)

Definition at line 486 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_minmax_heap_insert()

int fr_minmax_heap_insert	(	fr_minmax_heap_t *	hp,
		void *	data
	)

Definition at line 424 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_minmax_heap_iter_init()

void* fr_minmax_heap_iter_init	(	fr_minmax_heap_t *	hp,
		fr_minmax_heap_iter_t *	iter
	)

Iterate over entries in a minmax heap.

Note

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

Parameters

[in]	hp	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 551 of file minmax_heap.c.

Here is the caller graph for this function:

fr_minmax_heap_iter_next()

void* fr_minmax_heap_iter_next	(	fr_minmax_heap_t *	hp,
		fr_minmax_heap_iter_t *	iter
	)

Get the next entry in a minmax heap.

Note

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

Parameters

[in]	hp	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 573 of file minmax_heap.c.

Here is the caller graph for this function:

fr_minmax_heap_max_peek()

void* fr_minmax_heap_max_peek

(

fr_minmax_heap_t *

hp

)

Definition at line 466 of file minmax_heap.c.

Here is the caller graph for this function:

fr_minmax_heap_max_pop()

void* fr_minmax_heap_max_pop

(

fr_minmax_heap_t *

hp

)

Definition at line 477 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_minmax_heap_min_peek()

void* fr_minmax_heap_min_peek

(

fr_minmax_heap_t *

hp

)

Definition at line 449 of file minmax_heap.c.

Here is the caller graph for this function:

fr_minmax_heap_min_pop()

void* fr_minmax_heap_min_pop

(

fr_minmax_heap_t *

hp

)

Definition at line 457 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_minmax_heap_num_elements()

uint32_t fr_minmax_heap_num_elements

(

fr_minmax_heap_t *

hp

)

Return the number of elements in the minmax heap.

Parameters

[in]

hp

to return the number of elements from.

Definition at line 533 of file minmax_heap.c.

Here is the caller graph for this function:

fr_minmax_heap_pre_alloc_size()

size_t fr_minmax_heap_pre_alloc_size

(

unsigned int

count

)

fr_minmax_heap_verify()

void fr_minmax_heap_verify	(	char const *	file,
		int	line,
		fr_minmax_heap_t const *	hp
	)

Definition at line 584 of file minmax_heap.c.

Here is the call graph for this function: