lst.h File Reference

Structures and prototypes for leftmost skeleton trees (LSTs) More...

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

Include dependency graph for lst.h:

Go to the source code of this file.

Macros
#define	fr_lst_alloc(_ctx, _cmp, _type, _field, _init)    _fr_lst_alloc(_ctx, _cmp, NULL, (size_t)offsetof(_type, _field), _init)
	Creates an LST that can be used with non-talloced elements. More...
#define	fr_lst_foreach(_lst, _type, _data)
	Iterate over the contents of an LST. More...
#define	fr_lst_talloc_alloc(_ctx, _cmp, _talloc_type, _field, _init)    _fr_lst_alloc(_ctx, _cmp, #_talloc_type, (size_t)offsetof(_talloc_type, _field), _init)
	Creates an LST that verifies elements are of a specific talloc type. More...
#define	FR_LST_VERIFY(_lst)   fr_lst_verify(__FILE__, __LINE__, _lst)

Typedefs
typedef int8_t(*	fr_lst_cmp_t) (void const *a, void const *b)
typedef unsigned int	fr_lst_index_t
typedef fr_lst_index_t	fr_lst_iter_t
typedef struct fr_lst_s	fr_lst_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 bool	fr_lst_entry_inserted (fr_lst_index_t lst_id)
	Check if an entry is inserted into an LST. More...
int	fr_lst_extract (fr_lst_t *lst, void *data)
	Remove an element from an LST. More...
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. More...
void *	fr_lst_iter_next (fr_lst_t *lst, fr_lst_iter_t *iter)
	Get the next entry in an LST. More...
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)

Detailed Description

Structures and prototypes for leftmost skeleton trees (LSTs)

Copyright

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

Definition in file lst.h.

Macro Definition Documentation

fr_lst_alloc

#define fr_lst_alloc	(		_ctx,
			_cmp,
			_type,
			_field,
			_init
	)		_fr_lst_alloc(_ctx, _cmp, NULL, (size_t)offsetof(_type, _field), _init)

Creates an LST that can be used with non-talloced elements.

Parameters

[in]	_ctx	Talloc ctx to allocate LST in.
[in]	_cmp	Comparator used to compare elements.
[in]	_type	Of elements.
[in]	_field	to store LST indexes in.
[in]	_init	initial capacity (0 for default initial size); the capacity will be rounded up to a power of two.

Returns

• A pointer to the new LST.
• NULL on error

Definition at line 65 of file lst.h.

fr_lst_foreach

#define fr_lst_foreach	(		_lst,
			_type,
			_data
	)

Value:

{ \
        fr_lst_iter_t _iter; \
        for (_type *_data = fr_lst_iter_init(_lst, &_iter); _data; _data = fr_lst_iter_next(_lst, &_iter))

Iterate over the contents of an LST.

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 LST 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]	_lst	to iterate over.
[in]	_type	of item the heap contains.
[in]	_data	Name of variable holding a pointer to the LST element. Will be declared in the scope of the loop.

Definition at line 140 of file lst.h.

fr_lst_talloc_alloc

#define fr_lst_talloc_alloc	(		_ctx,
			_cmp,
			_talloc_type,
			_field,
			_init
	)		_fr_lst_alloc(_ctx, _cmp, #_talloc_type, (size_t)offsetof(_talloc_type, _field), _init)

Creates an LST that verifies elements are of a specific talloc type.

Parameters

[in]	_ctx	Talloc ctx to allocate LST in.
[in]	_cmp	Comparator used to compare elements.
[in]	_talloc_type	of elements.
[in]	_field	to store heap indexes in.
[in]	_init	initial capacity (0 for default initial size); the capacity will be rounded up to a power of two.

Returns

• A pointer to the new LST.
• NULL on error.

Definition at line 80 of file lst.h.

FR_LST_VERIFY

#define FR_LST_VERIFY

(

_lst

)

fr_lst_verify(__FILE__, __LINE__, _lst)

Definition at line 119 of file lst.h.

Typedef Documentation

fr_lst_cmp_t

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

Definition at line 51 of file lst.h.

fr_lst_index_t

typedef unsigned int fr_lst_index_t

Definition at line 43 of file lst.h.

fr_lst_iter_t

typedef fr_lst_index_t fr_lst_iter_t

Definition at line 45 of file lst.h.

fr_lst_t

typedef struct fr_lst_s fr_lst_t

Definition at line 1 of file lst.h.

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

static bool fr_lst_entry_inserted ( fr_lst_index_t  lst_id )

inlinestatic

Check if an entry is inserted into an LST.

Parameters

[in]

lst_id

An fr_lst_index_t value as stored in an item

Thus one should only pass this function an index as retrieved directly from the item, not the value returned by item_index() (q.v.).

This checks a necessary condition for a fr_lst_index_t value to be that of an inserted entry. A more complete check would need the entry itself and a pointer to the fr_lst_t it may be inserted in. Provided here to let heap users move to LSTs.

Definition at line 97 of file lst.h.

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: