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.
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.
int	fr_minmax_heap_max_peek (void **out, fr_minmax_heap_t *hp)
int	fr_minmax_heap_max_pop (void **out, fr_minmax_heap_t *hp)
void *	fr_minmax_heap_min_peek (fr_minmax_heap_t *hp)
int	fr_minmax_heap_min_pop (void **out, 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.
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 int	max_child_or_grandchild (fr_minmax_heap_index_t *out, minmax_heap_t *h, fr_minmax_heap_index_t idx)
static int	min_child_or_grandchild (fr_minmax_heap_index_t *out, 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.
static int	minmax_heap_expand (fr_minmax_heap_t *hp)
static int	push_down (minmax_heap_t *h, fr_minmax_heap_index_t idx)
static int	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.)
static int	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
static int	push_up (minmax_heap_t *h, fr_minmax_heap_index_t idx)
static int	push_up_max (minmax_heap_t *h, fr_minmax_heap_index_t idx)
static int	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 65 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 595 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 520 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 661 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 683 of file minmax_heap.c.

Here is the caller graph for this function:

fr_minmax_heap_max_peek()

int fr_minmax_heap_max_peek	(	void **	out,
		fr_minmax_heap_t *	hp
	)

Definition at line 563 of file minmax_heap.c.

Here is the caller graph for this function:

fr_minmax_heap_max_pop()

int fr_minmax_heap_max_pop	(	void **	out,
		fr_minmax_heap_t *	hp
	)

Definition at line 583 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 544 of file minmax_heap.c.

Here is the caller graph for this function:

fr_minmax_heap_min_pop()

int fr_minmax_heap_min_pop	(	void **	out,
		fr_minmax_heap_t *	hp
	)

Definition at line 552 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 643 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 694 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 int max_child_or_grandchild ( fr_minmax_heap_index_t *  out, minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 278 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 int min_child_or_grandchild ( fr_minmax_heap_index_t *  out, 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 int push_down ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 420 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 int 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 379 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 int 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 322 of file minmax_heap.c.

Here is the call graph for this function:

Here is the caller graph for this function:

push_up()

static int push_up ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 475 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 int push_up_max ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 452 of file minmax_heap.c.

Here is the caller graph for this function:

push_up_min()

static int push_up_min ( minmax_heap_t *  h, fr_minmax_heap_index_t  idx  )

static

Definition at line 429 of file minmax_heap.c.

Here is the caller graph for this function: