Functions for a Leftmost Skeleton Tree. More...

#include <freeradius-devel/util/lst.h>
#include <freeradius-devel/util/misc.h>
#include <freeradius-devel/util/rand.h>
#include <freeradius-devel/util/strerror.h>

Include dependency graph for lst.c:

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

Go to the source code of this file.

Data Structures
struct	fr_lst_s

struct	pivot_stack_t

Macros
#define	INITIAL_CAPACITY 2048

#define	is_power_of_2(_n) ((_n) && (((_n) & ((_n) - 1)) == 0))

Typedefs
typedef unsigned int	stack_index_t

Functions
fr_lst_t *	_fr_lst_alloc (TALLOC_CTX ctx, fr_lst_cmp_t cmp, char const type, size_t offset, fr_lst_index_t init)

static void	_fr_lst_extract (fr_lst_t lst, stack_index_t stack_index, void data)

static void	_fr_lst_insert (fr_lst_t lst, stack_index_t stack_index, void data)

static void *	_fr_lst_peek (fr_lst_t *lst, stack_index_t stack_index)

static void *	_fr_lst_pop (fr_lst_t *lst, stack_index_t stack_index)

static void	bucket_add (fr_lst_t lst, stack_index_t stack_index, void data)
	Add data to the bucket of a specified (sub)tree.

static void	bucket_delete (fr_lst_t lst, stack_index_t stack_index, void data)

static fr_lst_index_t	bucket_lwb (fr_lst_t const *lst, stack_index_t stack_index)

static fr_lst_index_t	bucket_upb (fr_lst_t const *lst, stack_index_t stack_index)

int	fr_lst_extract (fr_lst_t lst, void data)
	Remove an element from an LST.

int	fr_lst_insert (fr_lst_t lst, void data)

void *	fr_lst_iter_init (fr_lst_t lst, fr_lst_iter_t iter)
	Iterate over entries in LST.

void *	fr_lst_iter_next (fr_lst_t lst, fr_lst_iter_t iter)
	Get the next entry in an LST.

unsigned int	fr_lst_num_elements (fr_lst_t *lst)

void *	fr_lst_peek (fr_lst_t *lst)

void *	fr_lst_pop (fr_lst_t *lst)

void	fr_lst_verify (char const file, int line, fr_lst_t const lst)

static void *	index_addr (fr_lst_t const lst, void data)

static fr_lst_index_t	index_reduce (fr_lst_t const *lst, fr_lst_index_t idx)

static bool	is_bucket (fr_lst_t const *lst, stack_index_t idx)

static bool	is_equivalent (fr_lst_t const *lst, fr_lst_index_t idx1, fr_lst_index_t idx2)

static void *	item (fr_lst_t const *lst, fr_lst_index_t idx)

static fr_lst_index_t	item_index (fr_lst_t const lst, void data)

static void	item_index_set (fr_lst_t lst, void data, fr_lst_index_t idx)

static void	item_set (fr_lst_t lst, fr_lst_index_t idx, void data)

static bool	lst_expand (fr_lst_t *lst)
	Make more space available in an LST.

static void	lst_flatten (fr_lst_t *lst, stack_index_t stack_index)
	Flatten an LST, i.e.

static void	lst_indices_reduce (fr_lst_t *lst)
	Reduce pivot stack indices based on their difference from lst->idx, and then reduce lst->idx.

static stack_index_t	lst_length (fr_lst_t const *lst, stack_index_t stack_index)
	The length function for LSTs (how many buckets it contains)

static void	lst_move (fr_lst_t lst, fr_lst_index_t location, void data)
	Move data to a specific location in an LST's array.

static fr_lst_index_t	lst_size (fr_lst_t *lst, stack_index_t stack_index)
	The size function for LSTs (number of items a (sub)tree contains)

static void	partition (fr_lst_t *lst, stack_index_t stack_index)

static void *	pivot_item (fr_lst_t const *lst, stack_index_t idx)

static fr_lst_index_t	raw_item_index (fr_lst_t const lst, void data)

static stack_index_t	stack_depth (pivot_stack_t const *s)

static bool	stack_expand (fr_lst_t lst, pivot_stack_t s)

static fr_lst_index_t	stack_item (pivot_stack_t const *s, stack_index_t idx)

static void	stack_pop (pivot_stack_t *s, unsigned int n)

static int	stack_push (fr_lst_t lst, pivot_stack_t s, fr_lst_index_t pivot)

static void	stack_set (pivot_stack_t *s, stack_index_t idx, fr_lst_index_t new_value)

Detailed Description

Functions for a Leftmost Skeleton Tree.

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

Definition in file lst.c.

Data Structure Documentation

◆ fr_lst_s

struct fr_lst_s

Definition at line 60 of file lst.c.

Collaboration diagram for fr_lst_s:

Data Fields
unsigned int	capacity	Number of elements that will fit.
fr_lst_cmp_t	cmp	Comparator function.
fr_lst_index_t	idx	Starting index, initially zero.
unsigned int	num_elements	Number of elements in the LST.
size_t	offset	Offset of heap index in element structure.
void **	p	Array of elements.
fr_fast_rand_t	rand_ctx	Seed for random choices.
pivot_stack_t	s	Stack of pivots, always with depth >= 1.
char const *	type	Type of elements.

◆ pivot_stack_t

struct pivot_stack_t

Definition at line 54 of file lst.c.

Data Fields
fr_lst_index_t *	data	Array of indices of the pivots (sometimes called roots)
stack_index_t	depth	The current stack depth.
unsigned int	size	The current stack size (number of frames)

Macro Definition Documentation

◆ INITIAL_CAPACITY

#define INITIAL_CAPACITY 2048

Definition at line 48 of file lst.c.

◆ is_power_of_2

#define is_power_of_2 ( _n ) ((_n) && (((_n) & ((_n) - 1)) == 0))

Definition at line 50 of file lst.c.

Typedef Documentation

◆ stack_index_t

typedef unsigned int stack_index_t

Definition at line 52 of file lst.c.

Function Documentation

◆ _fr_lst_alloc()

fr_lst_t * _fr_lst_alloc	(	TALLOC_CTX *	ctx,
		fr_lst_cmp_t	cmp,
		char const *	type,
		size_t	offset,
		fr_lst_index_t	init
	)

Definition at line 222 of file lst.c.

Here is the call graph for this function:

◆ _fr_lst_extract()

static void _fr_lst_extract	(	fr_lst_t *	lst,
		stack_index_t	stack_index,
		void *	data
	)

inlinestatic

Definition at line 628 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _fr_lst_insert()

static void _fr_lst_insert	(	fr_lst_t *	lst,
		stack_index_t	stack_index,
		void *	data
	)

inlinestatic

Definition at line 663 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _fr_lst_peek()

static void * _fr_lst_peek	(	fr_lst_t *	lst,
		stack_index_t	stack_index
	)

inlinestatic

Definition at line 606 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _fr_lst_pop()

static void * _fr_lst_pop	(	fr_lst_t *	lst,
		stack_index_t	stack_index
	)

inlinestatic

Definition at line 582 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bucket_add()

static void bucket_add	(	fr_lst_t *	lst,
		stack_index_t	stack_index,
		void *	data
	)

static

Add data to the bucket of a specified (sub)tree.

Definition at line 333 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bucket_delete()

static void bucket_delete	(	fr_lst_t *	lst,
		stack_index_t	stack_index,
		void *	data
	)

static

Definition at line 531 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bucket_lwb()

static fr_lst_index_t bucket_lwb	(	fr_lst_t const *	lst,
		stack_index_t	stack_index
	)

inlinestatic

Definition at line 441 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bucket_upb()

static fr_lst_index_t bucket_upb	(	fr_lst_t const *	lst,
		stack_index_t	stack_index
	)

inlinestatic

Definition at line 451 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_lst_extract()

int fr_lst_extract	(	fr_lst_t *	lst,
		void *	data
	)

Remove an element from an LST.

Parameters

[in]	lst	the LST to remove an element from
[in]	data	the element to remove

Returns

0 if removal succeeds
- -1 if removal fails

Definition at line 715 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_lst_insert()

int fr_lst_insert	(	fr_lst_t *	lst,
		void *	data
	)

Definition at line 731 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_lst_iter_init()

void * fr_lst_iter_init	(	fr_lst_t *	lst,
		fr_lst_iter_t *	iter
	)

Iterate over entries in LST.

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

Parameters

[in]	lst	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 766 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_lst_iter_next()

void * fr_lst_iter_next	(	fr_lst_t *	lst,
		fr_lst_iter_t *	iter
	)

Get the next entry in an LST.

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

Parameters

[in]	lst	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 785 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_lst_num_elements()

unsigned int fr_lst_num_elements ( fr_lst_t * lst )

Definition at line 750 of file lst.c.

Here is the caller graph for this function:

◆ fr_lst_peek()

void * fr_lst_peek ( fr_lst_t * lst )

Definition at line 701 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_lst_pop()

void * fr_lst_pop ( fr_lst_t * lst )

Definition at line 695 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_lst_verify()

void fr_lst_verify	(	char const *	file,
		int	line,
		fr_lst_t const *	lst
	)

Definition at line 794 of file lst.c.

Here is the call graph for this function:

◆ index_addr()

static void * index_addr	(	fr_lst_t const *	lst,
		void *	data
	)

inlinestatic

Definition at line 75 of file lst.c.

Here is the caller graph for this function:

◆ index_reduce()

static fr_lst_index_t index_reduce	(	fr_lst_t const *	lst,
		fr_lst_index_t	idx
	)

inlinestatic

Definition at line 106 of file lst.c.

Here is the caller graph for this function:

◆ is_bucket()

static bool is_bucket	(	fr_lst_t const *	lst,
		stack_index_t	idx
	)

inlinestatic

Definition at line 152 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_equivalent()

static bool is_equivalent	(	fr_lst_t const *	lst,
		fr_lst_index_t	idx1,
		fr_lst_index_t	idx2
	)

inlinestatic

Definition at line 112 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ item()

static void * item	(	fr_lst_t const *	lst,
		fr_lst_index_t	idx
	)

inlinestatic

Definition at line 122 of file lst.c.

Here is the call graph for this function:

◆ item_index()

static fr_lst_index_t item_index	(	fr_lst_t const *	lst,
		void *	data
	)

inlinestatic

Definition at line 96 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ item_index_set()

static void item_index_set	(	fr_lst_t *	lst,
		void *	data,
		fr_lst_index_t	idx
	)

inlinestatic

Definition at line 101 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ item_set()

static void item_set	(	fr_lst_t *	lst,
		fr_lst_index_t	idx,
		void *	data
	)

inlinestatic

Definition at line 117 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lst_expand()

static bool lst_expand ( fr_lst_t * lst )

static

Make more space available in an LST.

The LST paper only mentions this option in passing, pointing out that it's O(n); the only constructor in the paper lets you hand it an array of items to initially insert in the LST, so elements will have to be removed to make room for more (though it's easy to see how one could specify extra space).

Were it not for the circular array optimization, it would be talloc_realloc() and done; it works or it doesn't. (That's still O(n), since it may require copying the data.)

With the circular array optimization, if lst->idx refers to something other than the beginning of the array, you have to move the elements preceding it to beginning of the newly-available space so it's still contiguous, and keep pivot stack entries consistent with the positions of the elements.

Definition at line 402 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lst_flatten()

static void lst_flatten	(	fr_lst_t *	lst,
		stack_index_t	stack_index
	)

inlinestatic

Flatten an LST, i.e.

turn it into the base-case one bucket [sub]tree

NOTE: so doing leaves the passed stack_index valid–we just add everything once in the left subtree to it.

Definition at line 314 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lst_indices_reduce()

static void lst_indices_reduce ( fr_lst_t * lst )

static

Reduce pivot stack indices based on their difference from lst->idx, and then reduce lst->idx.

Definition at line 377 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lst_length()

static stack_index_t lst_length	(	fr_lst_t const *	lst,
		stack_index_t	stack_index
	)

inlinestatic

The length function for LSTs (how many buckets it contains)

Definition at line 287 of file lst.c.

Here is the caller graph for this function:

◆ lst_move()

static void lst_move	(	fr_lst_t *	lst,
		fr_lst_index_t	location,
		void *	data
	)

inlinestatic

Move data to a specific location in an LST's array.

The caller must have made sure the location is available and exists in said array.

Definition at line 324 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lst_size()

static fr_lst_index_t lst_size	(	fr_lst_t *	lst,
		stack_index_t	stack_index
	)

static

The size function for LSTs (number of items a (sub)tree contains)

Definition at line 295 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ partition()

static void partition	(	fr_lst_t *	lst,
		stack_index_t	stack_index
	)

static

Definition at line 461 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pivot_item()

static void * pivot_item	(	fr_lst_t const *	lst,
		stack_index_t	idx
	)

inlinestatic

Definition at line 127 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ raw_item_index()

static fr_lst_index_t raw_item_index	(	fr_lst_t const *	lst,
		void *	data
	)

inlinestatic

Definition at line 91 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ stack_depth()

static stack_index_t stack_depth ( pivot_stack_t const * s )

inlinestatic

Definition at line 206 of file lst.c.

◆ stack_expand()

static bool stack_expand	(	fr_lst_t *	lst,
		pivot_stack_t *	s
	)

static

Definition at line 157 of file lst.c.

Here is the caller graph for this function:

◆ stack_item()

static fr_lst_index_t stack_item	(	pivot_stack_t const *	s,
		stack_index_t	idx
	)

inlinestatic

Definition at line 211 of file lst.c.

Here is the caller graph for this function:

◆ stack_pop()

static void stack_pop	(	pivot_stack_t *	s,
		unsigned int	n
	)

inlinestatic

Definition at line 201 of file lst.c.

Here is the caller graph for this function:

◆ stack_push()

static int stack_push	(	fr_lst_t *	lst,
		pivot_stack_t *	s,
		fr_lst_index_t	pivot
	)

inlinestatic

Definition at line 193 of file lst.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ stack_set()

static void stack_set	(	pivot_stack_t *	s,
		stack_index_t	idx,
		fr_lst_index_t	new_value
	)

inlinestatic

Definition at line 217 of file lst.c.

Here is the caller graph for this function:

Data Structures

Macros

Typedefs

Functions

Detailed Description

Data Structure Documentation

◆ fr_lst_s

◆ pivot_stack_t

Macro Definition Documentation

◆ INITIAL_CAPACITY

◆ is_power_of_2

Typedef Documentation

◆ stack_index_t

Function Documentation

◆ _fr_lst_alloc()

◆ _fr_lst_extract()

◆ _fr_lst_insert()

◆ _fr_lst_peek()

◆ _fr_lst_pop()

◆ bucket_add()

◆ bucket_delete()

◆ bucket_lwb()

◆ bucket_upb()

◆ fr_lst_extract()

◆ fr_lst_insert()

◆ fr_lst_iter_init()

◆ fr_lst_iter_next()

◆ fr_lst_num_elements()

◆ fr_lst_peek()

◆ fr_lst_pop()

◆ fr_lst_verify()

◆ index_addr()

◆ index_reduce()

◆ is_bucket()

◆ is_equivalent()

◆ item()

◆ item_index()

◆ item_index_set()

◆ item_set()

◆ lst_expand()

◆ lst_flatten()

◆ lst_indices_reduce()

◆ lst_length()

◆ lst_move()

◆ lst_size()

◆ partition()

◆ pivot_item()

◆ raw_item_index()

◆ stack_depth()

◆ stack_expand()

◆ stack_item()

◆ stack_pop()

◆ stack_push()

◆ stack_set()