#pragma once
/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */

/** Tree list implementation
 *
 * @file src/lib/util/tlist.h
 *
 * @copyright 2022 Network RADIUS SAS (legal@networkradius.com)
 */
RCSIDH(tlist_h, "$Id: 5d6d3918a13b36a43049c5a0d32f9a3c2c3cbfea $")

#ifdef __cplusplus
extern "C" {
#endif

#include <freeradius-devel/util/dlist.h>

typedef struct fr_tlist_head_s fr_tlist_head_t;
typedef struct fr_tlist_s fr_tlist_t;

struct fr_tlist_head_s {
	fr_tlist_t	*parent;	//!< the parent entry which holds this list.  May be NULL.

	fr_dlist_head_t	dlist_head;
};

#define tlist_type(_list) ((_list)->dlist_head.type)

struct fr_tlist_s {
	fr_tlist_head_t	*list_head;	//!< the list which holds this entry
	fr_tlist_head_t	*children;	//!< any child list
	fr_dlist_t	dlist_entry;	//!< the doubly linked list of entries.
};


/** Find the tlist pointers within a list item
 *
 */
static inline fr_tlist_t *fr_tlist_item_to_entry(fr_tlist_head_t const *list_head, void const *item)
{
	return (fr_tlist_t *)(((uintptr_t) item) + list_head->dlist_head.offset - offsetof(fr_tlist_t, dlist_entry));
}

/** Get the item from a fr_tlist_t
 *
 */
static inline void *fr_tlist_entry_to_item(fr_tlist_head_t const *list_head, fr_tlist_t const *entry)
{
	return (void *)(((uintptr_t) entry) - list_head->dlist_head.offset + offsetof(fr_tlist_t, dlist_entry));
}

/** Get a fr_tlist_head_t from a fr_dlist_head_t
 *
 */
static inline fr_tlist_head_t *fr_tlist_head_from_dlist(fr_dlist_head_t *dlist_head)
{
	return (fr_tlist_head_t *)(((uintptr_t) dlist_head) - offsetof(fr_tlist_head_t, dlist_head));
}

/** Initialise a linked list without metadata
 *
 */
static inline void fr_tlist_entry_init(fr_tlist_t *entry)
{
	fr_dlist_entry_init(&entry->dlist_entry);
	entry->list_head = NULL;
}

static inline CC_HINT(nonnull) void fr_tlist_entry_unlink(fr_tlist_t *entry)
{
	fr_dlist_entry_unlink(&entry->dlist_entry);
	entry->list_head = NULL;
}

/** Check if a list entry is part of a list
 *
 * This works because the fr_tlist_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_tlist_head_t.
 *
 * @return
 *	- True if in a list.
 *	- False otherwise.
 */
static inline CC_HINT(nonnull) bool fr_tlist_entry_in_a_list(fr_tlist_t const *entry)
{
	return (entry->list_head != NULL);
}


// no fr_tlist_entry_link_after(), fr_tlist_entry_link_before(), fr_tlist_entry_move(), fr_tlist_entry_replace()

/** Initialise the head structure of a tlist
 *
 * @note This variant does not perform talloc validation.
 *
 * This function should only be called for the top level of the list.
 * Please call fr_tlist_add_child() when adding a child list to an
 * existing entry.
 *
 @code{.c}
   typedef struct {
   	fr_tlist_t	tlist;
   	char const	*field_a;
   	int		*field_b;
   	...
   } my_struct_t;

   int my_func(my_struct_t *a, my_struct_t *b)
   {
   	fr_tlist_head_t	head;

   	fr_tlist_init(&head, my_struct_t, tlist);
   	fr_tlist_insert_head(&head, a);
   	fr_tlist_insert_head(&head, b);
   }
 @endcode
 *
 * @param[in] _head	structure to initialise.
 * @param[in] _type	of item being stored in the list, e.g. fr_value_box_t,
 *			fr_dict_attr_t etc...
 * @param[in] _field	Containing the #fr_tlist_t within item being stored.
 */
#define fr_tlist_init(_head, _type, _field) \
	_Generic((((_type *)0)->_field), fr_tlist_t: _fr_tlist_init(_head, offsetof(_type, _field), NULL))

/** Initialise the head structure of a tlist
 *
 * @note This variant *DOES* perform talloc validation.  All items inserted
 *	 into the list must be allocated with talloc.
 *
 * @copybrief fr_tlist_init
 *
 * @param[in] _head	structure to initialise.
 * @param[in] _type	of item being stored in the list, e.g. fr_value_box_t,
 *			fr_dict_attr_t etc...
 * @param[in] _field	Containing the #fr_tlist_t within item being stored.
 */
#define fr_tlist_talloc_init(_head, _type, _field) \
	_Generic((((_type *)0)->_field), fr_tlist_t: _fr_tlist_init(_head, offsetof(_type, _field), #_type))

/** Initialise common fields in a tlist
 *
 *  The dlist entries point to the tlist structure, which then points to the real structure.
 */
static inline void _fr_tlist_init(fr_tlist_head_t *list_head, size_t offset, char const *type)
{
	list_head->parent = NULL;

	/*
	 *	Initialize the dlist, but point to the ENCLOSING data
	 *	structure and type, not to the #fr_tlist_t.
	 */
	fr_dlist_init(&list_head->dlist_head, fr_tlist_t, dlist_entry);
	list_head->dlist_head.offset += offset;
	list_head->dlist_head.type = type;
}

/** Iterate over the contents of a list, only one level
 *
 * @param[in] _list_head	to iterate over.
 * @param[in] _iter		Name of iteration variable.
 *				Will be declared in the scope of the loop.
 */
#define fr_tlist_foreach_entry(_list_head, _iter) \
	for (void *_iter = fr_dlist_head(&_list_head->dlist_head); _iter; _iter = fr_dlist_next(&_list_head->dlist_head, _iter))

/** Remove all elements in a tlist
 *
 * @param[in] list_head	to clear.
 */
static inline void fr_tlist_clear(fr_tlist_head_t *list_head)
{
	fr_tlist_foreach_entry(list_head, item) {
		fr_tlist_t *entry = fr_tlist_item_to_entry(list_head, item);

		entry->list_head = NULL;
	}
	fr_dlist_clear(&list_head->dlist_head);
}

/** Check if a list entry is part of a tlist
 *
 * This works because the fr_tlist_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_tlist_head_t.
 *
 * @return
 *	- True if in a list.
 *	- False otherwise.
 */
static inline CC_HINT(nonnull) bool fr_tlist_in_list(fr_tlist_head_t *list_head, void *ptr)
{
	fr_tlist_t *entry = fr_tlist_item_to_entry(list_head, ptr);

	return (entry->list_head == list_head);
}

/** Insert an item into the head of a list
 *
 * @note If #fr_tlist_talloc_init was used to initialise #fr_tlist_head_t
 *	 ptr must be a talloced chunk of the type passed to #fr_tlist_talloc_init.
 *
 * @param[in] list_head	to insert ptr into.
 * @param[in] ptr	to insert.
 * @return
 * 	- 0 on success.
 *	- -1 on failure.
 */
static inline CC_HINT(nonnull) int fr_tlist_insert_head(fr_tlist_head_t *list_head, void *ptr)
{
	fr_tlist_t *entry = fr_tlist_item_to_entry(list_head, ptr);

	if (fr_dlist_insert_head(&list_head->dlist_head, ptr) < 0) return -1;

	entry->list_head = list_head;
	return 0;
}

/** Insert an item into the tail of a list
 *
 * @note If #fr_tlist_talloc_init was used to initialise #fr_tlist_head_t
 *	 ptr must be a talloced chunk of the type passed to #fr_tlist_talloc_init.
 *
 * @param[in] list_head	to insert ptr into.
 * @param[in] ptr	to insert.
 * @return
 * 	- 0 on success.
 *	- -1 on failure.
 */
static inline CC_HINT(nonnull) int fr_tlist_insert_tail(fr_tlist_head_t *list_head, void *ptr)
{
	fr_tlist_t *entry = fr_tlist_item_to_entry(list_head, ptr);

	if (fr_dlist_insert_tail(&list_head->dlist_head, ptr) < 0) return -1;

	entry->list_head = list_head;
	return 0;
}

/** Insert an item after an item already in the list
 *
 * @note If #fr_tlist_talloc_init was used to initialise #fr_tlist_head_t
 *	 ptr must be a talloced chunk of the type passed to #fr_tlist_talloc_init.
 *
 * @param[in] list_head	to insert ptr into.
 * @param[in] pos	to insert ptr after.
 * @param[in] ptr	to insert.
 * @return
 * 	- 0 on success.
 *	- -1 on failure.
 */
static inline CC_HINT(nonnull(1,3)) int fr_tlist_insert_after(fr_tlist_head_t *list_head, void *pos, void *ptr)
{
	fr_tlist_t *entry = fr_tlist_item_to_entry(list_head, ptr);

	if (fr_dlist_insert_after(&list_head->dlist_head, pos, ptr) < 0) return -1;

	entry->list_head = list_head;
	return 0;
}

/** Insert an item after an item already in the list
 *
 * @note If #fr_tlist_talloc_init was used to initialise #fr_tlist_head_t
 *	 ptr must be a talloced chunk of the type passed to #fr_tlist_talloc_init.
 *
 * @param[in] list_head	to insert ptr into.
 * @param[in] pos	to insert ptr before.
 * @param[in] ptr	to insert.
 * @return
 * 	- 0 on success.
 *	- -1 on failure.
 */
static inline CC_HINT(nonnull(1,3)) int fr_tlist_insert_before(fr_tlist_head_t *list_head, void *pos, void *ptr)
{
	fr_tlist_t *entry = fr_tlist_item_to_entry(list_head, ptr);

	if (fr_dlist_insert_before(&list_head->dlist_head, pos, ptr) < 0) return -1;

	entry->list_head = list_head;
	return 0;
}

/** Return the HEAD item of a list or NULL if the list is empty
 *
 * @param[in] list_head		to return the HEAD item from.
 * @return
 *	- The HEAD item.
 *	- NULL if no items exist in the list.
 */
static inline CC_HINT(nonnull) void *fr_tlist_head(fr_tlist_head_t const *list_head)
{
	return fr_dlist_head(&list_head->dlist_head);
}

/** Check whether a list has any items.
 *
 * @return
 *	- True if it does not.
 *	- False if it does.
 */
static inline bool fr_tlist_empty(fr_tlist_head_t const *list_head)
{
	if (!list_head) return true;

	return fr_dlist_empty(&list_head->dlist_head);
}

/** Check if the list head is initialised
 *
 * Memory must be zeroed out or initialised.
 *
 * @return
 *	- True if tlist initialised.
 *	- False if tlist not initialised
 */
static inline CC_HINT(nonnull) bool fr_tlist_initialised(fr_tlist_head_t const *list_head)
{
	return fr_dlist_initialised(&list_head->dlist_head);
}

/** Return the TAIL item of a list or NULL if the list is empty
 *
 * @param[in] list_head		to return the TAIL item from.
 * @return
 *	- The TAIL item.
 *	- NULL if no items exist in the list.
 */
static inline CC_HINT(nonnull) void *fr_tlist_tail(fr_tlist_head_t const *list_head)
{
	return fr_dlist_tail(&list_head->dlist_head);
}

/** 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_tlist_talloc_init.
 *
 * @param[in] list_head		containing ptr.
 * @param[in] ptr		to retrieve the next item from.
 *				If ptr is NULL, the HEAD of the list will be returned.
 * @return
 *	- 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).
 */
static inline CC_HINT(nonnull(1)) void *fr_tlist_next(fr_tlist_head_t const *list_head, void const *ptr)
{
	return fr_dlist_next(&list_head->dlist_head, ptr);
}

/** 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_tlist_talloc_init.
 *
 * @param[in] list_head		containing ptr.
 * @param[in] ptr		to retrieve the prev item from.
 *				If ptr is NULL, the HEAD of the list will be returned.
 * @return
 *	- The prev 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).
 */
static inline CC_HINT(nonnull(1)) void *fr_tlist_prev(fr_tlist_head_t const *list_head, void const *ptr)
{
	return fr_dlist_prev(&list_head->dlist_head, ptr);
}

/** Remove an item from the list
 *
 * @note If #fr_tlist_talloc_init was used to initialise #fr_tlist_head_t
 *	 ptr must be a talloced chunk of the type passed to #fr_tlist_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 prev/prev pointers are set to point to itself.
 @code{.c}
	my_item_t *item = NULL;

	while ((item = fr_tlist_prev(&head, item))) {
		if (item->should_be_removed) {
   			...do things with item
   			item = fr_tlist_remove(&head, item);
   			continue;
   		}
	}
 @endcode
 *
 * @param[in] list_head	to remove ptr from.
 * @param[in] ptr	to remove.
 * @return
 *	- The previous item in the list (makes iteration easier).
 *	- NULL if we just removed the head of the list.
 */
static inline CC_HINT(nonnull(1)) void *fr_tlist_remove(fr_tlist_head_t *list_head, void *ptr)
{
	fr_tlist_t *entry = fr_tlist_item_to_entry(list_head, ptr);

	entry->list_head = NULL;

	return fr_dlist_remove(&list_head->dlist_head, ptr);
}

/** Remove the head item in a list
 *
 * @param[in] list_head to remove head item from.
 * @return
 *	- The item removed.
 *	- NULL if not items in tlist.
 */
static inline CC_HINT(nonnull(1)) void *fr_tlist_pop_head(fr_tlist_head_t *list_head)
{
	void *item = fr_tlist_head(list_head);

	(void) fr_tlist_remove(list_head, item);

	return item;
}

/** Remove the tail item in a list
 *
 * @param[in] list_head to remove tail item from.
 * @return
 *	- The item removed.
 *	- NULL if not items in tlist.
 */
static inline CC_HINT(nonnull(1)) void *fr_tlist_pop_tail(fr_tlist_head_t *list_head)
{
	void *item = fr_dlist_tail(&list_head->dlist_head);

	(void) fr_dlist_remove(&list_head->dlist_head, item);

	return item;
}

/** Replace an item in a dlist
 *
 * @param list_head in which the original item is.
 * @param item to replace.
 * @param ptr replacement item.
 * @return
 *	- The item replaced
 *	- NULL if nothing replaced
 */
static inline CC_HINT(nonnull) void *fr_tlist_replace(fr_tlist_head_t *list_head, void *item, void *ptr)
{
	fr_tlist_t *item_entry;
	fr_tlist_t *ptr_entry;

	if (!fr_tlist_in_list(list_head, item)) return NULL;

	ptr_entry = fr_tlist_item_to_entry(list_head, ptr);
	fr_dlist_replace(&list_head->dlist_head, item, ptr);
	ptr_entry->list_head = list_head;

	item_entry = fr_tlist_item_to_entry(list_head, item);
	item_entry->list_head = NULL;

	return item;
}


/** 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_tlist_talloc_init.
 */
#ifndef TALLOC_GET_TYPE_ABORT_NOOP
static inline CC_HINT(nonnull) void fr_tlist_verify(char const *file, int line, fr_tlist_head_t const *list_head)
{
	void *item;

	if (!tlist_type(list_head)) return;

	fr_assert_msg(fr_tlist_initialised(list_head), "CONSISTENCY CHECK FAILED %s[%i]: tlist not initialised",
		      file, line);

	for (item = fr_tlist_head(list_head);
	     item;
	     item = fr_tlist_next(list_head, item)) {
		fr_tlist_t *entry = fr_tlist_item_to_entry(list_head, item);

		fr_assert_msg(entry->list_head == list_head, "CONSISTENCY CHECK FAILED %s[%i]: tlist entry %p has wrong parent",
			      file, line, entry);

		item = _talloc_get_type_abort(item, tlist_type(list_head), __location__);

		if (entry->children) {
			fr_assert_msg(tlist_type(entry->children) != NULL, "CONSISTENCY CHECK FAILED %s[%i]: tlist entry %p has non-talloc'd child list",
				      file, line, entry);

			fr_assert_msg(strcmp(tlist_type(entry->children), tlist_type(list_head)) == 0,
				      "CONSISTENCY CHECK FAILED %s[%i]: tlist entry %p has different child type from parent",
				      file, line, entry);

			fr_tlist_verify(file, line, entry->children);
		}
	}
}
#  define FR_TLIST_VERIFY(_head) fr_tlist_verify(__FILE__, __LINE__, _head)
#elif !defined(NDEBUG)
#  define FR_TLIST_VERIFY(_head) fr_assert(_head)
#else
#  define FR_TLIST_VERIFY(_head)
#endif


/** Merge two lists, inserting the source at the tail of the destination
 *
 * @return
 * 	- 0 on success.
 *	- -1 on failure.
 */
static inline CC_HINT(nonnull) int fr_tlist_move(fr_tlist_head_t *list_dst, fr_tlist_head_t *list_src)
{
	void *item;

#ifdef WITH_VERIFY_PTR
	/*
	 *	Must be both talloced or both not
	 */
	if (!fr_cond_assert((tlist_type(list_dst) && tlist_type(list_src)) || (!tlist_type(list_dst) && !tlist_type(list_src)))) return -1;

	/*
	 *	Must be of the same type
	 */
	if (!fr_cond_assert(!tlist_type(list_dst) || (strcmp(tlist_type(list_dst), tlist_type(list_src)) == 0))) return -1;
#endif

	item = fr_dlist_head(&list_src->dlist_head);
	if (!item) return 0;

	if (fr_dlist_move(&list_dst->dlist_head, &list_src->dlist_head) < 0) return -1;

	/*
	 *	Update new parent from the middle of the list to the end.
	 */
	do {
		fr_tlist_t *entry = fr_tlist_item_to_entry(list_src, item);
		entry->list_head = list_dst;
	} while ((item = fr_dlist_next(&list_dst->dlist_head, item)) != NULL);

	return 0;
}

/** Merge two lists, inserting the source at the head of the destination
 *
 * @return
 * 	- 0 on success.
 *	- -1 on failure.
 */
static inline CC_HINT(nonnull) int fr_tlist_move_head(fr_tlist_head_t *list_dst, fr_tlist_head_t *list_src)
{
	void *item, *middle;

#ifdef WITH_VERIFY_PTR
	/*
	 *	Must be both talloced or both not
	 */
	if (!fr_cond_assert((tlist_type(list_dst) && tlist_type(list_src)) || (!tlist_type(list_dst) && !tlist_type(list_src)))) return -1;

	/*
	 *	Must be of the same type
	 */
	if (!fr_cond_assert(!tlist_type(list_dst) || (strcmp(tlist_type(list_dst), tlist_type(list_src)) == 0))) return -1;
#endif

	middle = fr_dlist_head(&list_dst->dlist_head);

	if (fr_dlist_move_head(&list_dst->dlist_head, &list_src->dlist_head) < 0) return -1;

	/*
	 *	Update new parent from the start of the list to the middle.
	 */
	for (item = fr_tlist_head(list_dst);
	     item && (item != middle);
	     item = fr_tlist_next(list_dst, item)) {
		fr_tlist_t *entry = fr_tlist_item_to_entry(list_src, item);
		entry->list_head = list_dst;
	}

	return 0;
}

/** Free the first item in the list
 *
 * @param[in] list_head		to free head item in.
 */
static inline void fr_tlist_talloc_free_head(fr_tlist_head_t *list_head)
{
	talloc_free(fr_tlist_pop_head(list_head));
}

/** Free the last item in the list
 *
 * @param[in] list_head		to free tail item in.
 */
static inline void fr_tlist_talloc_free_tail(fr_tlist_head_t *list_head)
{
	talloc_free(fr_tlist_pop_head(list_head));
}

/** Free the item specified
 *
 * @param[in] list_head		to free item in.
 * @param[in] ptr		to remove and free.
 * @return
 *	- NULL if no more items in the list.
 *	- Previous item in the list
 */
static inline void *fr_tlist_talloc_free_item(fr_tlist_head_t *list_head, void *ptr)
{
	void *prev;

	prev = fr_tlist_remove(list_head, ptr);
	talloc_free(ptr);
	return prev;
}

/** Free items in a doubly linked list (with talloc)
 *
 * @param[in] head	of list to free.
 * @param[in] ptr	remove and free from this to the tail.
 */
static inline void fr_tlist_talloc_free_to_tail(fr_tlist_head_t *head, void *ptr)
{
	void *e = ptr, *p;

	if (!ptr) return;	/* uninitialized means don't do anything */

	while (e) {
		p = fr_tlist_next(head, e);
		(void) fr_tlist_remove(head, e);
		talloc_free(e);
		e = p;
	}
}

/** Free all items in a doubly linked list (with talloc)
 *
 * @param[in] head of list to free.
 */
static inline void fr_tlist_talloc_free(fr_tlist_head_t *head)
{
	void *e = NULL, *p;

	while ((e = fr_tlist_next(head, e))) {
		p = fr_tlist_remove(head, e);
		talloc_free(e);
		e = p;
	}
}

/** Free all items in a doubly linked list from the tail backwards
 *
 * @param[in] head of list to free.
 */
static inline void fr_tlist_talloc_reverse_free(fr_tlist_head_t *head)
{
	void *e = NULL, *p;

	e = fr_tlist_tail(head);
	do {
		p = fr_tlist_remove(head, e);
		talloc_free(e);
		e = p;
	} while (e);
}

/** Return the number of elements in the tlist
 *
 * @param[in] list_head of list to count elements for.
 */
static inline unsigned int fr_tlist_num_elements(fr_tlist_head_t const *list_head)
{
	return fr_dlist_num_elements(&list_head->dlist_head);
}

/** Split phase of a merge sort of a dlist
 *
 * @note Only to be used within a merge sort
 *
 * @param[in] head	of the original list being sorted
 * @param[in] source	first item in the section of the list to split
 * @param[out] front	first item of the first half of the split list
 * @param[out] back	first item of the second half of the split list
 */
static inline void fr_tlist_sort_split(fr_tlist_head_t *head, void **source, void **front, void **back)
{
	fr_dlist_sort_split(&head->dlist_head, source, front, back);
}

/** Merge phase of a merge sort of a dlist
 *
 * @note Only to be used within a merge sort
 *
 * @param[in] head	of the original list being sorted
 * @param[in] a		first element of first list being merged
 * @param[in] b		first element of second list being merged
 * @param[in] cmp	comparison function for the sort
 * @returns pointer to first item in merged list
 */
static inline void *fr_tlist_sort_merge(fr_tlist_head_t *head, void **a, void **b, fr_cmp_t cmp)
{
	return fr_dlist_sort_merge(&head->dlist_head, a, b, cmp);
}

/** Recursive sort routine for tlist
 *
 * @param[in] head	of the list being sorted
 * @param[in,out] ptr	to the first item in the current section of the list being sorted.
 * @param[in] cmp	comparison function to sort with
 */
static inline void fr_tlist_recursive_sort(fr_tlist_head_t *head, void **ptr, fr_cmp_t cmp)
{
	fr_dlist_recursive_sort(&head->dlist_head, ptr, cmp);
}

/** Sort a tlist using merge sort
 *
 * @note This routine temporarily breaks the doubly linked nature of the list
 *
 * @param[in,out] list	to sort
 * @param[in] cmp	comparison function to sort with
 */
static inline void fr_tlist_sort(fr_tlist_head_t *list, fr_cmp_t cmp)
{
	fr_dlist_sort(&list->dlist_head, cmp);
}

static inline void fr_tlist_noop(void)
{
	return;
}


/** Expands to the type name used for the entry wrapper structure
 *
 * @param[in] _name	Prefix we add to type-specific structures.
 * @return fr_tlist_<name>_entry_t
 */
#define FR_TLIST_ENTRY(_name) _name ## _entry_t

/** Expands to the type name used for the head wrapper structure
 *
 * @param[in] _name	Prefix we add to type-specific structures.
 * @return fr_tlist_<name>_head_t
 */
#define FR_TLIST_HEAD(_name) _name ## _head_t

/** Define type specific wrapper structs for tlists
 *
 * @note This macro should be used inside the header for the area of code
 * which will use type specific functions.
 */
#define FR_TLIST_TYPES(_name) \
	typedef struct { fr_tlist_t entry; } FR_TLIST_ENTRY(_name); \
	typedef struct { fr_tlist_head_t head; } FR_TLIST_HEAD(_name); \


/** Define type specific wrapper functions for tlists
 *
 * @note This macro should be used inside the source file that will use
 * the type specific functions.
 *
 * @param[in] _name		Prefix we add to type-specific tlist functions.
 * @param[in] _element_type	Type of structure that'll be inserted into the tlist.
 * @param[in] _element_entry	Field in the _element_type that holds the tlist entry information.
 */
#define FR_TLIST_FUNCS(_name, _element_type, _element_entry) \
DIAG_OFF(unused-function) \
	_Static_assert(IS_FIELD_COMPATIBLE(_element_type, _element_entry, FR_TLIST_ENTRY(_name)) == 1, "Bad tlist entry field type");\
	static inline	fr_tlist_head_t *_name ## _list_head(FR_TLIST_HEAD(_name) const *list) \
		{ return	UNCONST(fr_tlist_head_t *, &list->head); } \
\
	static inline	fr_dlist_head_t *_name ## _dlist_head(FR_TLIST_HEAD(_name) const *list) \
		{ return	UNCONST(fr_dlist_head_t *, &list->head.dlist_head); } \
\
	static inline	void _name ## _entry_init(_element_type *entry) \
		{ \
			_Generic((&entry->_element_entry), \
				 FR_TLIST_ENTRY(_name) *: fr_tlist_entry_init(UNCONST(fr_tlist_t *, &entry->_element_entry.entry)), \
				 FR_TLIST_ENTRY(_name) const *: fr_tlist_noop()\
			); \
		} \
\
	static inline	void _name ## _init(FR_TLIST_HEAD(_name) *list) \
		{		_fr_tlist_init(&list->head, offsetof(_element_type, _element_entry), NULL); } \
\
	static inline	void _name ## _talloc_init(FR_TLIST_HEAD(_name) *list) \
		{		_fr_tlist_init(&list->head, offsetof(_element_type, _element_entry), #_element_type); } \
\
	static inline	void _name ## _clear(FR_TLIST_HEAD(_name) *list) \
		{		fr_tlist_clear(&list->head); } \
\
	static inline	bool _name ## _in_list(FR_TLIST_HEAD(_name) *list, _element_type *ptr) \
		{ return	fr_tlist_in_list(&list->head, ptr); } \
\
	static inline	bool _name ## _in_a_list(_element_type *ptr) \
		{ return	fr_tlist_entry_in_a_list(&ptr->_element_entry.entry); } \
\
	static inline	int _name ## _insert_head(FR_TLIST_HEAD(_name) *list, _element_type *ptr) \
		{ return	fr_tlist_insert_head(&list->head, ptr); } \
\
	static inline	int _name ## _insert_tail(FR_TLIST_HEAD(_name) *list, _element_type *ptr) \
		{ return	fr_tlist_insert_tail(&list->head, ptr); } \
\
	static inline	int _name ## _insert_after(FR_TLIST_HEAD(_name) *list, _element_type *pos, _element_type *ptr) \
		{ return	fr_tlist_insert_after(&list->head, pos, ptr); } \
\
	static inline	int _name ## _insert_before(FR_TLIST_HEAD(_name) *list, _element_type *pos, _element_type *ptr) \
		{ return	fr_tlist_insert_before(&list->head, pos, ptr); } \
\
	static inline	_element_type *_name ## _head(FR_TLIST_HEAD(_name) const *list) \
		{ return	fr_tlist_head(&list->head); } \
\
	static inline	bool _name ## _empty(FR_TLIST_HEAD(_name) const *list) \
		{ return	fr_tlist_empty(&list->head); } \
\
	static inline	bool _name ## _initialised(FR_TLIST_HEAD(_name) const *list) \
		{ return	fr_tlist_initialised(&list->head); } \
\
	static inline	_element_type *_name ## _tail(FR_TLIST_HEAD(_name) const *list) \
		{ return	fr_tlist_tail(&list->head); } \
\
	static inline _element_type *_name ## _next(FR_TLIST_HEAD(_name) const *list, _element_type const *ptr) \
		{ return	fr_tlist_next(&list->head, ptr); } \
\
	static inline	_element_type *_name ## _prev(FR_TLIST_HEAD(_name) const *list, _element_type const *ptr) \
		{ return	fr_tlist_prev(&list->head, ptr); } \
\
	static inline	_element_type *_name ## _remove(FR_TLIST_HEAD(_name) *list, _element_type *ptr) \
		{ return	fr_tlist_remove(&list->head, ptr); } \
\
	static inline	_element_type *_name ## _pop_head(FR_TLIST_HEAD(_name) *list) \
		{ return	fr_tlist_pop_head(&list->head); } \
\
	static inline	_element_type *_name ## _pop_tail(FR_TLIST_HEAD(_name) *list) \
		{ return	fr_tlist_pop_tail(&list->head); } \
\
	static inline	_element_type *_name ## _replace(FR_TLIST_HEAD(_name) *list, _element_type *item, _element_type *ptr) \
		{ return	fr_tlist_replace(&list->head, item, ptr); } \
\
	static inline	int _name ## _move(FR_TLIST_HEAD(_name) *dst, FR_TLIST_HEAD(_name) *src) \
		{ return	fr_tlist_move(&dst->head, &src->head); } \
\
	static inline	int _name ## _move_head(FR_TLIST_HEAD(_name) *dst, FR_TLIST_HEAD(_name) *src) \
		{ return	fr_tlist_move_head(&dst->head, &src->head); } \
\
	static inline	void _name ## _talloc_free_head(FR_TLIST_HEAD(_name) *list) \
		{		fr_tlist_talloc_free_head(&list->head); } \
\
	static inline	void _name ## _talloc_free_tail(FR_TLIST_HEAD(_name) *list) \
		{		fr_tlist_talloc_free_tail(&list->head); } \
\
	static inline	void _name ## _talloc_free_item(FR_TLIST_HEAD(_name) *list, _element_type *ptr) \
		{		fr_tlist_talloc_free_item(&list->head, ptr); } \
\
	static inline	void _name ## _talloc_free(FR_TLIST_HEAD(_name) *list) \
		{		fr_tlist_talloc_free(&list->head); } \
\
	static inline	void _name ## _talloc_free_to_tail(FR_TLIST_HEAD(_name) *list, _element_type *ptr) \
		{		fr_tlist_talloc_free_to_tail(&list->head, ptr); } \
\
	static inline	void _name ## _talloc_reverse_free(FR_TLIST_HEAD(_name) *list) \
		{		fr_tlist_talloc_reverse_free(&list->head); } \
\
	static inline	unsigned int _name ## _num_elements(FR_TLIST_HEAD(_name) const *list) \
		{ return	fr_tlist_num_elements(&list->head); } \
\
	static inline	void _name ## _sort(FR_TLIST_HEAD(_name) *list, fr_cmp_t cmp) \
		{		fr_tlist_sort(&list->head, cmp); } \
\
	static inline FR_TLIST_HEAD(_name) *_name ## _parent(const _element_type *ptr) \
		{		return (FR_TLIST_HEAD(_name) *) (ptr->_element_entry.entry.list_head); } \
\
	static inline FR_TLIST_HEAD(_name) *_name ## _children(_element_type *ptr) \
		{		return (FR_TLIST_HEAD(_name) *) (ptr->_element_entry.entry.children); } \
\
	static inline void _name ## _talloc_init_children(_element_type *ptr, FR_TLIST_HEAD(_name) *children) \
		{		_name ## _talloc_init(children); ptr->_element_entry.entry.children = &children->head; } \
\
	static inline void _name ## _add_children(_element_type *ptr, FR_TLIST_HEAD(_name) *children) \
		{		fr_tlist_add_children(&ptr->_element_entry.entry, &children->head); } \
\
	static inline FR_TLIST_HEAD(_name) * _name ## _remove_children(_element_type *ptr) \
		{		return (FR_TLIST_HEAD(_name) *) fr_tlist_remove_children(&ptr->_element_entry.entry); } \
\
	static inline void _name ## _set_head(fr_tlist_head_t *list, _element_type *ptr) \
		{		ptr->_element_entry.entry.list_head = list; }
DIAG_ON(unused-function)

static inline void *fr_tlist_parent(fr_tlist_head_t *list_head, void const *ptr)
{
	fr_tlist_t *entry;

	if (!ptr || !list_head) return NULL;

	entry = fr_tlist_item_to_entry(list_head, ptr);
	if (!entry->list_head) return NULL;

	if (!entry->list_head->parent) return NULL;

	return fr_tlist_entry_to_item(entry->list_head, entry->list_head->parent);
}

/** Initialize a child tlist based on a parent entry
 *
 * @param[in] entry	the entry which will be the parent of the children
 * @param[in] children	structure to initialise.  Usually in the same parent structure as "entry"
 */
static inline void fr_tlist_init_children(fr_tlist_t *entry, fr_tlist_head_t *children)
{
	fr_tlist_head_t *list_head;

	fr_assert(entry->children == NULL);
	fr_assert(entry->list_head != NULL);

	list_head = entry->list_head;

	/*
	 *	Manually re-do fr_tlist_init() here, as we copy offset/type from the parent list.
	 */
	fr_dlist_init(&children->dlist_head, fr_tlist_t, dlist_entry);
	children->dlist_head.offset = list_head->dlist_head.offset;
	children->dlist_head.type = list_head->dlist_head.type;

	children->parent = NULL;

	entry->children = children;
}

/** Add a pre-initialized child tlist to a parent entry.
 *
 * @param[in] entry	the entry which will be the parent of the children
 * @param[in] children	structure to initialise.  Usually in the same parent structure as "entry"
 */
static inline int fr_tlist_add_children(fr_tlist_t *entry, fr_tlist_head_t *children)
{
	if (entry->children) return -1;

	children->parent = entry;

	entry->children = children;

	return 0;
}


/** Remove a child tlist from a parent entry
 *
 * @param[in] entry	the entry which will have the children removed
 */
static inline fr_tlist_head_t *fr_tlist_remove_children(fr_tlist_t *entry)
{
	fr_tlist_head_t *children = entry->children;

	if (!entry->children) return NULL;

	entry->children->parent = NULL;
	entry->children = NULL;

	return children;
}

#ifdef __cplusplus
}
#endif
