Doubly linked list implementation. More...

#include <freeradius-devel/build.h>
#include <freeradius-devel/missing.h>
#include <freeradius-devel/util/debug.h>
#include <freeradius-devel/util/misc.h>
#include <freeradius-devel/util/talloc.h>

Include dependency graph for dlist.h:

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

Go to the source code of this file.

Data Structures
struct	fr_dlist_head_t
	Head of a doubly linked list. More...

struct	fr_dlist_s
	Entry in a doubly linked list. More...

Macros
#define	CHECK_ELEMENT_COUNT(_head, _add)
	Verify we're not going to overflow the element count. More...

#define	FR_DLIST_ENTRY(_name) _name ## _entry_t
	Expands to the type name used for the entry wrapper structure. More...

#define	FR_DLIST_ENTRY_INITIALISER(_entry) { .next = &_entry, .prev = &_entry }
	Static initialiser for entries. More...

#define	fr_dlist_foreach(_list_head, _type, _iter) for (_type *_iter = fr_dlist_head(_list_head); _iter; _iter = fr_dlist_next(_list_head, _iter))
	Iterate over the contents of a list. More...

#define	fr_dlist_foreach_safe(_list_head, _type, _iter)
	Iterate over the contents of a list allowing for removals. More...

#define	FR_DLIST_FUNCS(_name, _element_type, _element_entry)
	Define type specific wrapper functions for dlists. More...

#define	FR_DLIST_HEAD(_name) _name ## _head_t
	Expands to the type name used for the head wrapper structure. More...

#define	FR_DLIST_HEAD_INITIALISER(_head) { .entry = FR_DLIST_ENTRY_INITIALISER((_head).entry) }
	Static initialiser for list heads. More...

#define	fr_dlist_init(_head, _type, _field) _Generic((((_type *)0)->_field), fr_dlist_t: _fr_dlist_init(_head, offsetof(_type, _field), NULL))
	Initialise the head structure of a doubly linked list. More...

#define	fr_dlist_talloc_init(_head, _type, _field) _Generic((((_type *)0)->_field), fr_dlist_t: _fr_dlist_init(_head, offsetof(_type, _field), #_type))
	Initialise the head structure of a doubly linked list. More...

#define	FR_DLIST_TYPEDEFS(_name, _head, _entry)
	Define friendly names for type specific dlist head and entry structures. More...

#define	FR_DLIST_TYPES(_name)
	Define type specific wrapper structs for dlists. More...

#define	fr_dlist_verify(_head) _fr_dlist_verify(__FILE__, __LINE__, _head)

Typedefs
typedef struct fr_dlist_s	fr_dlist_t

Functions
static void	_fr_dlist_init (fr_dlist_head_t list_head, size_t offset, char const type)
	Initialise common fields in a dlist. More...

static void	_fr_dlist_verify (char const file, int line, fr_dlist_head_t const list_head)
	Check all items in the list are valid. More...

static void	fr_dlist_clear (fr_dlist_head_t *list_head)
	Efficiently remove all elements in a dlist. More...

static bool	fr_dlist_empty (fr_dlist_head_t const *list_head)
	Check whether a list has any items. More...

static bool	fr_dlist_entry_in_list (fr_dlist_t const *entry)
	Check if a list entry is part of a list. More...

static void	fr_dlist_entry_init (fr_dlist_t *entry)
	Initialise a linked list without metadata. More...

static void	fr_dlist_entry_link_after (fr_dlist_t entry, fr_dlist_t to_link)
	Link in a single entry after the current entry. More...

static void	fr_dlist_entry_link_before (fr_dlist_t entry, fr_dlist_t to_link)
	Link in a single entry before the current entry. More...

static void	fr_dlist_entry_move (fr_dlist_t dst, fr_dlist_t src)
	Link in a sublist before the current entry. More...

static void	fr_dlist_entry_replace (fr_dlist_t entry, fr_dlist_t replacement)
	Replace one entry with another. More...

static void *	fr_dlist_entry_to_item (size_t offset, fr_dlist_t const *entry)
	Get the item from a fr_dlist_t. More...

static void	fr_dlist_entry_unlink (fr_dlist_t *entry)
	Remove an item from the dlist when we don't have access to the head. More...

static void *	fr_dlist_head (fr_dlist_head_t const *list_head)
	Return the HEAD item of a list or NULL if the list is empty. More...

static bool	fr_dlist_in_list (fr_dlist_head_t list_head, void ptr)
	Check if a list entry is part of a list. More...

static bool	fr_dlist_initialised (fr_dlist_head_t const *list_head)
	Check if the list head is initialised. More...

static int	fr_dlist_insert_after (fr_dlist_head_t list_head, void pos, void *ptr)
	Insert an item after an item already in the list. More...

static int	fr_dlist_insert_before (fr_dlist_head_t list_head, void pos, void *ptr)
	Insert an item before an item already in the list. More...

static int	fr_dlist_insert_head (fr_dlist_head_t list_head, void ptr)
	Insert an item into the head of a list. More...

static int	fr_dlist_insert_tail (fr_dlist_head_t list_head, void ptr)
	Insert an item into the tail of a list. More...

static fr_dlist_t *	fr_dlist_item_to_entry (size_t offset, void const *item)
	Find the dlist pointers within a list item. More...

static int	fr_dlist_move (fr_dlist_head_t list_dst, fr_dlist_head_t list_src)
	Merge two lists, inserting the source at the tail of the destination. More...

static int	fr_dlist_move_head (fr_dlist_head_t list_dst, fr_dlist_head_t list_src)
	Merge two lists, inserting the source at the head of the destination. More...

static void *	fr_dlist_next (fr_dlist_head_t const list_head, void const ptr)
	Get the next item in a list. More...

static void	fr_dlist_noop (void)

static unsigned int	fr_dlist_num_elements (fr_dlist_head_t const *head)
	Return the number of elements in the dlist. More...

static void *	fr_dlist_pop_head (fr_dlist_head_t *list_head)
	Remove the head item in a list. More...

static void *	fr_dlist_pop_tail (fr_dlist_head_t *list_head)
	Remove the tail item in a list. More...

static void *	fr_dlist_prev (fr_dlist_head_t const list_head, void const ptr)
	Get the previous item in a list. More...

static void	fr_dlist_recursive_sort (fr_dlist_head_t head, void *ptr, fr_cmp_t cmp)
	Recursive sort routine for dlist. More...

static void *	fr_dlist_remove (fr_dlist_head_t list_head, void ptr)
	Remove an item from the list. More...

static void *	fr_dlist_replace (fr_dlist_head_t list_head, void item, void *ptr)
	Replace an item in a dlist. More...

static void	fr_dlist_sort (fr_dlist_head_t *list, fr_cmp_t cmp)
	Sort a dlist using merge sort. More...

static void *	fr_dlist_sort_merge (fr_dlist_head_t head, void a, void *b, fr_cmp_t cmp)
	Merge phase of a merge sort of a dlist. More...

static void	fr_dlist_sort_split (fr_dlist_head_t head, void source, void front, void *back)
	Split phase of a merge sort of a dlist. More...

static void *	fr_dlist_tail (fr_dlist_head_t const *list_head)
	Return the TAIL item of a list or NULL if the list is empty. More...

static void	fr_dlist_talloc_free (fr_dlist_head_t *head)
	Free all items in a doubly linked list (with talloc) More...

static void	fr_dlist_talloc_free_head (fr_dlist_head_t *list_head)
	Free the first item in the list. More...

static void *	fr_dlist_talloc_free_item (fr_dlist_head_t list_head, void ptr)
	Free the item specified. More...

static void	fr_dlist_talloc_free_tail (fr_dlist_head_t *list_head)
	Free the last item in the list. More...

static void	fr_dlist_talloc_free_to_tail (fr_dlist_head_t head, void ptr)
	Free items in a doubly linked list (with talloc) More...

static void	fr_dlist_talloc_reverse_free (fr_dlist_head_t *head)
	Free all items in a doubly linked list from the tail backwards. More...

Detailed Description

Doubly linked list implementation.

Copyright: 2016 Alan DeKok (aland.nosp@m.@fre.nosp@m.eradi.nosp@m.us.o.nosp@m.rg)

Definition in file dlist.h.

Data Structure Documentation

◆ fr_dlist_head_t

struct fr_dlist_head_t

Head of a doubly linked list.

Holds additional information about the list items, like at which offset the next/prev pointers can be found.

Definition at line 51 of file dlist.h.

Collaboration diagram for fr_dlist_head_t:

Data Fields
fr_dlist_t	entry	Struct holding the head and tail of the list. First for efficient traversal.
unsigned int	num_elements	Number of elements contained within the dlist.
unsigned int	offset	Positive offset from start of structure to fr_dlist_t. Yes, this should really be size_t, but we shave 8 bytes off each head structure by making it unsigned int.
char const *	type	of items contained within the list. Used for talloc validation.

◆ fr_dlist_s

struct fr_dlist_s

Entry in a doubly linked list.

Definition at line 41 of file dlist.h.

Collaboration diagram for fr_dlist_s:

Data Fields
fr_dlist_t *	next
fr_dlist_t *	prev

Macro Definition Documentation

◆ CHECK_ELEMENT_COUNT

#define CHECK_ELEMENT_COUNT	(	_head,
		_add
	)

Value:

        if (unlikely((_head)->num_elements > (UINT_MAX - (_add)))) do { \
                fr_strerror_const("Maximum elements in list"); \
                return -1; \
        } while (0)

Verify we're not going to overflow the element count.

Definition at line 304 of file dlist.h.

◆ FR_DLIST_ENTRY

#define FR_DLIST_ENTRY ( _name ) _name ## _entry_t

Expands to the type name used for the entry wrapper structure.

Parameters

[in] _name Prefix we add to type-specific structures.

Returns: fr_dlist_<name>_entry_t

Definition at line 1115 of file dlist.h.

◆ FR_DLIST_ENTRY_INITIALISER

#define FR_DLIST_ENTRY_INITIALISER ( _entry ) { .next = &_entry, .prev = &_entry }

Static initialiser for entries.

fr_dlist_entry_t my_entry = FR_DLIST_INITIALISER(my_entry)

Parameters

[in] _entry what's being initialised.

Definition at line 75 of file dlist.h.

◆ fr_dlist_foreach

#define fr_dlist_foreach	(	_list_head,
		_type,
		_iter
	)	for (_type *_iter = fr_dlist_head(_list_head); _iter; _iter = fr_dlist_next(_list_head, _iter))

Iterate over the contents of a list.

Parameters

[in]	_list_head	to iterate over.
[in]	_type	of item the list contains.
[in]	_iter	Name of iteration variable. Will be declared in the scope of the loop.

Definition at line 94 of file dlist.h.

◆ fr_dlist_foreach_safe

#define fr_dlist_foreach_safe	(	_list_head,
		_type,
		_iter
	)

Value:

{ \
        _type *_iter; \
        fr_dlist_t _tmp ## _iter; \
        for (_iter = fr_dlist_head(_list_head), \
             _tmp ## _iter = fr_dlist_head(_list_head) ? *fr_dlist_item_to_entry((_list_head)->offset, fr_dlist_head(_list_head)) : (fr_dlist_t){ .prev = NULL, .next = NULL }; \
             _iter; \
             _iter = _tmp ## _iter.next && (_tmp ## _iter.next != &(_list_head)->entry) ? fr_dlist_entry_to_item((_list_head)->offset, _tmp ## _iter.next) : NULL, \
             _tmp ## _iter = _tmp ## _iter.next && (_tmp ## _iter.next != &(_list_head)->entry) ? *_tmp ## _iter.next : (fr_dlist_t){ .prev = NULL, .next = NULL })

Iterate over the contents of a list allowing for removals.

Note: foreach block must end with double curlybrace }}. We need to use another scoping section as we can't declare variables of multiple types within the initialiser of a for loop.

Parameters

[in]	_list_head	to iterate over.
[in]	_type	of item the list contains.
[in]	_iter	Name of iteration variable. Will be declared in the scope of the loop.

Definition at line 108 of file dlist.h.

◆ FR_DLIST_FUNCS

#define FR_DLIST_FUNCS	(	_name,
		_element_type,
		_element_entry
	)

Define type specific wrapper functions for dlists.

Note: This macro should be used inside the source file that will use the type specific functions.

Parameters

[in]	_name	Prefix we add to type-specific dlist functions.
[in]	_element_type	Type of structure that'll be inserted into the dlist.
[in]	_element_entry	Field in the _element_type that holds the dlist entry information.

Definition at line 1152 of file dlist.h.

◆ FR_DLIST_HEAD

#define FR_DLIST_HEAD ( _name ) _name ## _head_t

Expands to the type name used for the head wrapper structure.

Parameters

[in] _name Prefix we add to type-specific structures.

Returns: fr_dlist_<name>_head_t

Definition at line 1122 of file dlist.h.

◆ FR_DLIST_HEAD_INITIALISER

#define FR_DLIST_HEAD_INITIALISER ( _head ) { .entry = FR_DLIST_ENTRY_INITIALISER((_head).entry) }

Static initialiser for list heads.

fr_dlist_head_t my_head = FR_DLIST_INITIALISER(my_head)

fr_dlist_head_t

Head of a doubly linked list.

Definition: dlist.h:51

Parameters

[in] _head what's being initialised.

Definition at line 85 of file dlist.h.

◆ fr_dlist_init

#define fr_dlist_init	(	_head,
		_type,
		_field
	)	_Generic((((_type *)0)->_field), fr_dlist_t: _fr_dlist_init(_head, offsetof(_type, _field), NULL))

Initialise the head structure of a doubly linked list.

Note: This variant does not perform talloc validation.

typedef struct {
      fr_dlist_t      dlist;
      char const      *field_a;
      int             *field_b;
      ...
} my_struct_t;
 
int my_func(my_struct_t *a, my_struct_t *b)
{
      fr_dlist_head_t head;
 
      fr_dlist_init(&head, my_struct_t, dlist);
      fr_dlist_insert_head(&head, a);
      fr_dlist_insert_head(&head, b);
}

Parameters

[in]	_head	structure to initialise.
[in]	_type	of item being stored in the list, e.g. fr_value_box_t, fr_dict_attr_t etc...
[in]	_field	Containing the fr_dlist_t within item being stored.

Definition at line 260 of file dlist.h.

◆ fr_dlist_talloc_init

#define fr_dlist_talloc_init	(	_head,
		_type,
		_field
	)	_Generic((((_type *)0)->_field), fr_dlist_t: _fr_dlist_init(_head, offsetof(_type, _field), #_type))

Initialise the head structure of a doubly linked list.

Note: This variant DOES perform talloc validation. All items inserted into the list must be allocated with talloc.

Initialise the head structure of a doubly linked list.

Parameters

[in]	_head	structure to initialise.
[in]	_type	of item being stored in the list, e.g. fr_value_box_t, fr_dict_attr_t etc...
[in]	_field	Containing the fr_dlist_t within item being stored.

Definition at line 275 of file dlist.h.

◆ FR_DLIST_TYPEDEFS

#define FR_DLIST_TYPEDEFS	(	_name,
		_head,
		_entry
	)

Value:

typedef FR_DLIST_HEAD(_name) _head; \

typedef FR_DLIST_ENTRY(_name) _entry;

FR_DLIST_ENTRY

#define FR_DLIST_ENTRY(_name)

Expands to the type name used for the entry wrapper structure.

Definition: dlist.h:1115

FR_DLIST_HEAD

#define FR_DLIST_HEAD(_name)

Expands to the type name used for the head wrapper structure.

Definition: dlist.h:1122

Define friendly names for type specific dlist head and entry structures.

Parameters

[in]	_name	Prefix we add to type-specific structures.
[in]	_head	Name to use for head structure.
[in]	_entry	Name to use for entry structure.

Definition at line 1139 of file dlist.h.

◆ FR_DLIST_TYPES

#define FR_DLIST_TYPES ( _name )

Value:

typedef struct { fr_dlist_t entry; } FR_DLIST_ENTRY(_name); \

typedef struct { fr_dlist_head_t head; } FR_DLIST_HEAD(_name); \

Define type specific wrapper structs for dlists.

Note: This macro should be used inside the header for the area of code which will use type specific functions.

Definition at line 1129 of file dlist.h.

◆ fr_dlist_verify

#define fr_dlist_verify ( _head ) _fr_dlist_verify(__FILE__, __LINE__, _head)

Definition at line 755 of file dlist.h.

Typedef Documentation

◆ fr_dlist_t

typedef struct fr_dlist_s fr_dlist_t

Definition at line 1 of file dlist.h.

Function Documentation

◆ _fr_dlist_init()

static void _fr_dlist_init	(	fr_dlist_head_t *	list_head,
		size_t	offset,
		char const *	type
	)

inlinestatic

Initialise common fields in a dlist.

Definition at line 281 of file dlist.h.

Here is the call graph for this function:

◆ _fr_dlist_verify()

static void _fr_dlist_verify	(	char const *	file,
		int	line,
		fr_dlist_head_t const *	list_head
	)

inlinestatic

Check all items in the list are valid.

Checks item talloc headers and types to ensure they're consistent with what we expect.

Does nothing if the list was not initialised with fr_dlist_talloc_init.

Definition at line 735 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_clear()

static void fr_dlist_clear ( fr_dlist_head_t * list_head )

inlinestatic

Efficiently remove all elements in a dlist.

Parameters

[in] list_head to clear.

Definition at line 295 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_empty()

static bool fr_dlist_empty ( fr_dlist_head_t const * list_head )

inlinestatic

Check whether a list has any items.

Returns

True if it does not.
False if it does.

Definition at line 501 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_entry_in_list()

static bool fr_dlist_entry_in_list ( fr_dlist_t const * entry )

inlinestatic

Check if a list entry is part of a list.

This works because the fr_dlist_head_t has an entry in the list. So if next and prev both point to the entry for the object being passed in, then it can't be part of a list with a fr_dlist_head_t.

Returns

True if in a list.
False otherwise.

Definition at line 163 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_entry_init()

static void fr_dlist_entry_init ( fr_dlist_t * entry )

inlinestatic

Initialise a linked list without metadata.

Definition at line 138 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_entry_link_after()

static void fr_dlist_entry_link_after	(	fr_dlist_t *	entry,
		fr_dlist_t *	to_link
	)

inlinestatic

Link in a single entry after the current entry.

Parameters

[in]	entry	to link in entry after.
[in]	to_link	entry to link in after.

Definition at line 176 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_entry_link_before()

static void fr_dlist_entry_link_before	(	fr_dlist_t *	entry,
		fr_dlist_t *	to_link
	)

inlinestatic

Link in a single entry before the current entry.

Parameters

[in]	entry	to link in entry before.
[in]	to_link	entry to link in before.

Definition at line 189 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_entry_move()

static void fr_dlist_entry_move	(	fr_dlist_t *	dst,
		fr_dlist_t *	src
	)

inlinestatic

Link in a sublist before the current entry.

Note: This is not suitable for moving elements from a fr_dlist_head_t as we need to snip out the head element. This is only suitable if the two entries are not part of lists with head elements.

Parameters

[in]	dst	to link src in before.
[in]	src	to link in before dst.

Definition at line 206 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_entry_replace()

static void fr_dlist_entry_replace	(	fr_dlist_t *	entry,
		fr_dlist_t *	replacement
	)

inlinestatic

Replace one entry with another.

Parameters

[in]	entry	to replace.
[in]	replacement	to link in.

Definition at line 221 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_entry_to_item()

static void* fr_dlist_entry_to_item	(	size_t	offset,
		fr_dlist_t const *	entry
	)

inlinestatic

Get the item from a fr_dlist_t.

Definition at line 130 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_entry_unlink()

static void fr_dlist_entry_unlink ( fr_dlist_t * entry )

inlinestatic

Remove an item from the dlist when we don't have access to the head.

Definition at line 146 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_head()

static void* fr_dlist_head ( fr_dlist_head_t const * list_head )

inlinestatic

Return the HEAD item of a list or NULL if the list is empty.

Parameters

[in] list_head to return the HEAD item from.

Returns

The HEAD item.
NULL if no items exist in the list.

Definition at line 486 of file dlist.h.

Here is the call graph for this function:

◆ fr_dlist_in_list()

static bool fr_dlist_in_list	(	fr_dlist_head_t *	list_head,
		void *	ptr
	)

inlinestatic

Check if a list entry is part of a list.

This works because the fr_dlist_head_t has an entry in the list. So if next and prev both point to the entry for the object being passed in, then it can't be part of a list with a fr_dlist_head_t.

Returns

True if in a list.
False otherwise.

Definition at line 320 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_initialised()

static bool fr_dlist_initialised ( fr_dlist_head_t const * list_head )

inlinestatic

Check if the list head is initialised.

Memory must be zeroed out or initialised.

Returns

True if dlist initialised.
False if dlist not initialised

Definition at line 515 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_insert_after()

static int fr_dlist_insert_after	(	fr_dlist_head_t *	list_head,
		void *	pos,
		void *	ptr
	)

inlinestatic

Insert an item after an item already in the list.

Note: If fr_dlist_talloc_init was used to initialise fr_dlist_head_t ptr must be a talloced chunk of the type passed to fr_dlist_talloc_init.

Parameters

[in]	list_head	to insert ptr into.
[in]	pos	to insert ptr after.
[in]	ptr	to insert.

Definition at line 414 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_insert_before()

static int fr_dlist_insert_before	(	fr_dlist_head_t *	list_head,
		void *	pos,
		void *	ptr
	)

inlinestatic

Insert an item before an item already in the list.

Note: If fr_dlist_talloc_init was used to initialise fr_dlist_head_t ptr must be a talloced chunk of the type passed to fr_dlist_talloc_init.

Parameters

[in]	list_head	to insert ptr into.
[in]	pos	to insert ptr before.
[in]	ptr	to insert.

Definition at line 450 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_insert_head()

static int fr_dlist_insert_head	(	fr_dlist_head_t *	list_head,
		void *	ptr
	)

inlinestatic

Insert an item into the head of a list.

Note: If fr_dlist_talloc_init was used to initialise fr_dlist_head_t ptr must be a talloced chunk of the type passed to fr_dlist_talloc_init.

Parameters

[in]	list_head	to insert ptr into.
[in]	ptr	to insert.

Returns

0 on success.

-1 on failure.

Definition at line 338 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_insert_tail()

static int fr_dlist_insert_tail	(	fr_dlist_head_t *	list_head,
		void *	ptr
	)

inlinestatic

Insert an item into the tail of a list.

Note: If fr_dlist_talloc_init was used to initialise fr_dlist_head_t ptr must be a talloced chunk of the type passed to fr_dlist_talloc_init.

Parameters

[in]	list_head	to insert ptr into.
[in]	ptr	to insert.

Returns

0 on success.

-1 on failure.

Definition at line 378 of file dlist.h.

Here is the call graph for this function:

◆ fr_dlist_item_to_entry()

static fr_dlist_t* fr_dlist_item_to_entry	(	size_t	offset,
		void const *	item
	)

inlinestatic

Find the dlist pointers within a list item.

Definition at line 122 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_move()

static int fr_dlist_move	(	fr_dlist_head_t *	list_dst,
		fr_dlist_head_t *	list_src
	)

inlinestatic

Merge two lists, inserting the source at the tail of the destination.

Returns

0 on success.

-1 on failure.

Definition at line 763 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_move_head()

static int fr_dlist_move_head	(	fr_dlist_head_t *	list_dst,
		fr_dlist_head_t *	list_src
	)

inlinestatic

Merge two lists, inserting the source at the head of the destination.

Returns

0 on success.

-1 on failure.

Definition at line 812 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_next()

static void* fr_dlist_next	(	fr_dlist_head_t const *	list_head,
		void const *	ptr
	)

inlinestatic

Get the next item in a list.

Note: If fr_dlist_talloc_init was used to initialise fr_dlist_head_t ptr must be a talloced chunk of the type passed to fr_dlist_talloc_init.

Parameters

[in]	list_head	containing ptr.
[in]	ptr	to retrieve the next item from. If ptr is NULL, the HEAD of the list will be returned.

Returns

The next item in the list if ptr is not NULL.
The head of the list if ptr is NULL.
NULL if ptr is the tail of the list (no more items).

Definition at line 555 of file dlist.h.

Here is the call graph for this function:

◆ fr_dlist_noop()

static void fr_dlist_noop ( void )

inlinestatic

Definition at line 1105 of file dlist.h.

◆ fr_dlist_num_elements()

static unsigned int fr_dlist_num_elements ( fr_dlist_head_t const * head )

inlinestatic

Return the number of elements in the dlist.

Parameters

[in] head of list to count elements for.

Definition at line 939 of file dlist.h.

Here is the caller graph for this function:

◆ fr_dlist_pop_head()

static void* fr_dlist_pop_head ( fr_dlist_head_t * list_head )

inlinestatic

Remove the head item in a list.

Parameters

[in] list_head to remove head item from.

Returns

The item removed.
NULL if not items in dlist.

Definition at line 672 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_pop_tail()

static void* fr_dlist_pop_tail ( fr_dlist_head_t * list_head )

inlinestatic

Remove the tail item in a list.

Parameters

[in] list_head to remove tail item from.

Returns

The item removed.
NULL if not items in dlist.

Definition at line 688 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_prev()

static void* fr_dlist_prev	(	fr_dlist_head_t const *	list_head,
		void const *	ptr
	)

inlinestatic

Get the previous item in a list.

Note: If fr_dlist_talloc_init was used to initialise fr_dlist_head_t ptr must be a talloced chunk of the type passed to fr_dlist_talloc_init.

Parameters

[in]	list_head	containing ptr.
[in]	ptr	to retrieve the previous item to. If ptr is NULL, the TAIL of the list will be returned.

Returns

The previous item in the list if ptr is not NULL.
The tail of the list if ptr is NULL.
NULL if ptr is the head of the list (no more items).

Definition at line 588 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_recursive_sort()

static void fr_dlist_recursive_sort	(	fr_dlist_head_t *	head,
		void **	ptr,
		fr_cmp_t	cmp
	)

inlinestatic

Recursive sort routine for dlist.

Parameters

[in]	head	of the list being sorted
[in,out]	ptr	to the first item in the current section of the list being sorted.
[in]	cmp	comparison function to sort with

Definition at line 1038 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_remove()

static void* fr_dlist_remove	(	fr_dlist_head_t *	list_head,
		void *	ptr
	)

inlinestatic

Remove an item from the list.

Note: If fr_dlist_talloc_init was used to initialise fr_dlist_head_t ptr must be a talloced chunk of the type passed to fr_dlist_talloc_init.

When removing items in an iteration loop, the iterator variable must be assigned the item returned by this function.

If the iterator variable is not updated, the item removed will be the last item iterated over, as its next/prev pointers are set to point to itself.

my_item_t *item = NULL;
 
while ((item = fr_dlist_next(&head, item))) {
 if (item->should_be_removed) {
                 ...do things with item
                 item = fr_dlist_remove(&head, item);
                 continue;
         }
}

Parameters

[in]	list_head	to remove ptr from.
[in]	ptr	to remove.

Returns

The previous item in the list (makes iteration easier).
NULL if we just removed the head of the list.

Definition at line 638 of file dlist.h.

Here is the call graph for this function:

◆ fr_dlist_replace()

static void* fr_dlist_replace	(	fr_dlist_head_t *	list_head,
		void *	item,
		void *	ptr
	)

inlinestatic

Replace an item in a dlist.

Parameters

list_head	in which the original item is.
item	to replace.
ptr	replacement item.

Returns

The item replaced
NULL if nothing replaced

Definition at line 706 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_sort()

static void fr_dlist_sort	(	fr_dlist_head_t *	list,
		fr_cmp_t	cmp
	)

inlinestatic

Sort a dlist using merge sort.

Note: This routine temporarily breaks the doubly linked nature of the list

Parameters

[in,out]	list	to sort
[in]	cmp	comparison function to sort with

Definition at line 1064 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_sort_merge()

static void* fr_dlist_sort_merge	(	fr_dlist_head_t *	head,
		void **	a,
		void **	b,
		fr_cmp_t	cmp
	)

inlinestatic

Merge phase of a merge sort of a dlist.

Note: Only to be used within a merge sort

Parameters

[in]	head	of the original list being sorted
[in]	a	first element of first list being merged
[in]	b	first element of second list being merged
[in]	cmp	comparison function for the sort

Returns: pointer to first item in merged list

Definition at line 1002 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_sort_split()

static void fr_dlist_sort_split	(	fr_dlist_head_t *	head,
		void **	source,
		void **	front,
		void **	back
	)

inlinestatic

Split phase of a merge sort of a dlist.

Note: Only to be used within a merge sort

Parameters

[in]	head	of the original list being sorted
[in]	source	first item in the section of the list to split
[out]	front	first item of the first half of the split list
[out]	back	first item of the second half of the split list

Definition at line 953 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_tail()

static void* fr_dlist_tail ( fr_dlist_head_t const * list_head )

inlinestatic

Return the TAIL item of a list or NULL if the list is empty.

Parameters

[in] list_head to return the TAIL item from.

Returns

The TAIL item.
NULL if no items exist in the list.

Definition at line 531 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_talloc_free()

static void fr_dlist_talloc_free ( fr_dlist_head_t * head )

inlinestatic

Free all items in a doubly linked list (with talloc)

Parameters

[in] head of list to free.

Definition at line 908 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_talloc_free_head()

static void fr_dlist_talloc_free_head ( fr_dlist_head_t * list_head )

inlinestatic

Free the first item in the list.

Parameters

[in] list_head to free head item in.

Definition at line 854 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_talloc_free_item()

static void* fr_dlist_talloc_free_item	(	fr_dlist_head_t *	list_head,
		void *	ptr
	)

inlinestatic

Free the item specified.

Parameters

[in]	list_head	to free item in.
[in]	ptr	to remove and free.

Returns

NULL if no more items in the list.
Previous item in the list

Definition at line 876 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_talloc_free_tail()

static void fr_dlist_talloc_free_tail ( fr_dlist_head_t * list_head )

inlinestatic

Free the last item in the list.

Parameters

[in] list_head to free tail item in.

Definition at line 863 of file dlist.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dlist_talloc_free_to_tail()

static void fr_dlist_talloc_free_to_tail	(	fr_dlist_head_t *	head,
		void *	ptr
	)

inlinestatic

Free items in a doubly linked list (with talloc)

Parameters

[in]	head	of list to free.
[in]	ptr	remove and free from this to the tail.

Definition at line 889 of file dlist.h.

Here is the call graph for this function:

◆ fr_dlist_talloc_reverse_free()

static void fr_dlist_talloc_reverse_free ( fr_dlist_head_t * head )

inlinestatic

Free all items in a doubly linked list from the tail backwards.

Parameters

[in] head of list to free.

Definition at line 923 of file dlist.h.

Here is the call graph for this function:

Data Structures

Macros

Typedefs

Functions

Detailed Description

Data Structure Documentation

◆ fr_dlist_head_t

◆ fr_dlist_s

Macro Definition Documentation

◆ CHECK_ELEMENT_COUNT

◆ FR_DLIST_ENTRY

◆ FR_DLIST_ENTRY_INITIALISER

◆ fr_dlist_foreach

◆ fr_dlist_foreach_safe

◆ FR_DLIST_FUNCS

◆ FR_DLIST_HEAD

◆ FR_DLIST_HEAD_INITIALISER

◆ fr_dlist_init

◆ fr_dlist_talloc_init

◆ FR_DLIST_TYPEDEFS

◆ FR_DLIST_TYPES

◆ fr_dlist_verify

Typedef Documentation

◆ fr_dlist_t

Function Documentation

◆ _fr_dlist_init()

◆ _fr_dlist_verify()

◆ fr_dlist_clear()

◆ fr_dlist_empty()

◆ fr_dlist_entry_in_list()

◆ fr_dlist_entry_init()

◆ fr_dlist_entry_link_after()

◆ fr_dlist_entry_link_before()

◆ fr_dlist_entry_move()

◆ fr_dlist_entry_replace()

◆ fr_dlist_entry_to_item()

◆ fr_dlist_entry_unlink()

◆ fr_dlist_head()

◆ fr_dlist_in_list()

◆ fr_dlist_initialised()

◆ fr_dlist_insert_after()

◆ fr_dlist_insert_before()

◆ fr_dlist_insert_head()

◆ fr_dlist_insert_tail()

◆ fr_dlist_item_to_entry()

◆ fr_dlist_move()

◆ fr_dlist_move_head()

◆ fr_dlist_next()

◆ fr_dlist_noop()

◆ fr_dlist_num_elements()

◆ fr_dlist_pop_head()

◆ fr_dlist_pop_tail()

◆ fr_dlist_prev()

◆ fr_dlist_recursive_sort()

◆ fr_dlist_remove()

◆ fr_dlist_replace()

◆ fr_dlist_sort()

◆ fr_dlist_sort_merge()

◆ fr_dlist_sort_split()

◆ fr_dlist_tail()

◆ fr_dlist_talloc_free()

◆ fr_dlist_talloc_free_head()

◆ fr_dlist_talloc_free_item()

◆ fr_dlist_talloc_free_tail()

◆ fr_dlist_talloc_free_to_tail()

◆ fr_dlist_talloc_reverse_free()