minmax_heap.c File Reference

Functions for a minmax heap. More...

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

Include dependency graph for minmax_heap.c:

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

Go to the source code of this file.

Data Structures
struct	fr_minmax_heap_s

Macros
#define	HEAP_GRANDPARENT(_x)   HEAP_PARENT(HEAP_PARENT(_x))
#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	is_max_level_index(_i)   (!(is_min_level_index(_i)))
#define	OFFSET_RESET(_heap, _idx)   index_set(_heap, _heap->p[_idx], 0)
#define	OFFSET_SET(_heap, _idx)   index_set(_heap, _heap->p[_idx], _idx)

Typedefs
typedef struct fr_minmax_heap_s	minmax_heap_t

Functions
fr_minmax_heap_t *	_fr_minmax_heap_alloc (TALLOC_CTX *ctx, fr_minmax_heap_cmp_t cmp, char const *type, size_t offset, unsigned int init)
static uint8_t	depth (fr_minmax_heap_index_t i)
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)
unsigned int	fr_minmax_heap_num_elements (fr_minmax_heap_t *hp)
	Return the number of elements in the minmax heap. More...
void	fr_minmax_heap_verify (char const *file, int line, fr_minmax_heap_t const *hp)
static bool	has_children (minmax_heap_t *h, fr_minmax_heap_index_t idx)
static bool	has_grandchildren (minmax_heap_t *h, fr_minmax_heap_index_t i)
static fr_minmax_heap_index_t	index_get (minmax_heap_t *h, void *data)
static void	index_set (minmax_heap_t *h, void *data, fr_minmax_heap_index_t idx)
static bool	is_descendant (fr_minmax_heap_index_t candidate, fr_minmax_heap_index_t ancestor)
static bool	is_min_level_index (fr_minmax_heap_index_t i)
static fr_minmax_heap_index_t	max_child_or_grandchild (minmax_heap_t *h, fr_minmax_heap_index_t idx)
static fr_minmax_heap_index_t	min_child_or_grandchild (minmax_heap_t *h, fr_minmax_heap_index_t idx)
	Find the index of the minimum child or grandchild of the entry at a given index. More...
static int	minmax_heap_expand (fr_minmax_heap_t *hp)
static void	push_down (minmax_heap_t *h, fr_minmax_heap_index_t idx)
static void	push_down_max (minmax_heap_t *h, fr_minmax_heap_index_t idx)
	precondition: idx is the index of an existing entry on a max level (Just like push_down_min() save for reversal of ordering, so comments there apply, mutatis mutandis.) More...
static void	push_down_min (minmax_heap_t *h, fr_minmax_heap_index_t idx)
	precondition: idx is the index of an existing entry on a min level More...
static void	push_up (minmax_heap_t *h, fr_minmax_heap_index_t idx)
static void	push_up_max (minmax_heap_t *h, fr_minmax_heap_index_t idx)
static void	push_up_min (minmax_heap_t *h, fr_minmax_heap_index_t idx)

Detailed Description

Functions for a minmax heap.

Copyright

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

Definition in file minmax_heap.c.

---

Data Structure Documentation

fr_minmax_heap_s

struct fr_minmax_heap_s

Definition at line 53 of file minmax_heap.c.

Data Fields
fr_minmax_heap_cmp_t	cmp	Comparator function.
unsigned int	num_elements	Number of nodes used.
size_t	offset	Offset of heap index in element structure.
void *	p[]	Array of nodes.
unsigned int	size	Number of nodes allocated.
char const *	type	Talloc type of elements.

Macro Definition Documentation

HEAP_GRANDPARENT

#define HEAP_GRANDPARENT

(

_x

)

HEAP_PARENT(HEAP_PARENT(_x))

Definition at line 75 of file minmax_heap.c.

HEAP_LEFT

#define HEAP_LEFT

(

_x

)

(2 * (_x))

Definition at line 76 of file minmax_heap.c.

HEAP_PARENT

#define HEAP_PARENT

(

_x

)

((_x) >> 1)

Definition at line 74 of file minmax_heap.c.

HEAP_RIGHT

#define HEAP_RIGHT

(

_x

)

(2 * (_x) + 1 )

Definition at line 77 of file minmax_heap.c.

HEAP_SWAP

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

Definition at line 78 of file minmax_heap.c.

INITIAL_CAPACITY

#define INITIAL_CAPACITY   2048

Definition at line 67 of file minmax_heap.c.

is_max_level_index

#define is_max_level_index

(

_i

)

(!(is_min_level_index(_i)))

Definition at line 109 of file minmax_heap.c.

OFFSET_RESET

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

Definition at line 209 of file minmax_heap.c.

OFFSET_SET

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

Definition at line 208 of file minmax_heap.c.

Typedef Documentation

minmax_heap_t

typedef struct fr_minmax_heap_s minmax_heap_t

Definition at line 1 of file minmax_heap.c.

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 *	type,
		size_t	offset,
		unsigned int	init
	)

Definition at line 111 of file minmax_heap.c.

Here is the call graph for this function:

depth()

static uint8_t depth ( fr_minmax_heap_index_t  i )

inlinestatic

Definition at line 83 of file minmax_heap.c.

Here is the call 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()

unsigned int 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_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:

has_children()

static bool has_children ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

inlinestatic

Definition at line 198 of file minmax_heap.c.

Here is the caller graph for this function:

has_grandchildren()

static bool has_grandchildren ( minmax_heap_t *  h, fr_minmax_heap_index_t  i  )

inlinestatic

Definition at line 203 of file minmax_heap.c.

Here is the caller graph for this function:

index_get()

static fr_minmax_heap_index_t index_get ( minmax_heap_t *  h, void *  data  )

inlinestatic

Definition at line 188 of file minmax_heap.c.

Here is the caller graph for this function:

index_set()

static void index_set ( minmax_heap_t *  h, void *  data, fr_minmax_heap_index_t  idx  )

inlinestatic

Definition at line 193 of file minmax_heap.c.

is_descendant()

static bool is_descendant ( fr_minmax_heap_index_t  candidate, fr_minmax_heap_index_t  ancestor  )

inlinestatic

Definition at line 93 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

is_min_level_index()

static bool is_min_level_index ( fr_minmax_heap_index_t  i )

inlinestatic

Definition at line 88 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

max_child_or_grandchild()

static fr_minmax_heap_index_t max_child_or_grandchild ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 268 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

min_child_or_grandchild()

static fr_minmax_heap_index_t min_child_or_grandchild ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Find the index of the minimum child or grandchild of the entry at a given index.

precondition: has_children(h, idx), i.e. there is stuff in the heap below idx.

These functions are called by push_down_{min, max}() with idx the index of an element moved into that position but which may or may not be where it should ultimately go. The minmax heap property still holds for its (positional, at least) descendants, though. That lets us cut down on the number of comparisons over brute force iteration over every child and grandchild.

In the case where the desired item must be a child, there are at most two, so we just do it inlne; no loop needed.

Definition at line 237 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

minmax_heap_expand()

static int minmax_heap_expand ( fr_minmax_heap_t *  hp )

static

Definition at line 154 of file minmax_heap.c.

Here is the caller graph for this function:

push_down()

static void push_down ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 351 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

push_down_max()

static void push_down_max ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

precondition: idx is the index of an existing entry on a max level (Just like push_down_min() save for reversal of ordering, so comments there apply, mutatis mutandis.)

Definition at line 332 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

push_down_min()

static void push_down_min ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

inlinestatic

precondition: idx is the index of an existing entry on a min level

Definition at line 302 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

push_up()

static void push_up ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 384 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

push_up_max()

static void push_up_max ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 372 of file minmax_heap.c.

Here is the caller graph for this function:

push_up_min()

static void push_up_min ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 360 of file minmax_heap.c.

Here is the caller graph for this function: