/src/freeradius-server/src/freeradius-devel/util/tlist.h

Source (jump to first uncovered line)
#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

Coverage Report

Created: 2023-12-08 06:56