/src/freeradius-server/src/lib/util/lst.c

Source
/*
 *   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
 */

/** Functions for a Leftmost Skeleton Tree
 *
 * @file src/lib/util/lst.c
 *
 * @copyright 2021 Network RADIUS SAS (legal@networkradius.com)
 */
RCSID("$Id: 81a67a2ef49d1d39b2ef4350b6383feecaef029d $")

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

/*
 * Leftmost Skeleton Trees are defined in "Stronger Quickheaps" (Gonzalo Navarro,
 * Rodrigo Paredes, Patricio V. Poblete, and Peter Sanders) International Journal
 * of Foundations of Computer Science, November 2011. As the title suggests, it
 * is inspired by quickheaps, and indeed the underlying representation looks
 * like a quickheap.
 *
 * heap/priority queue operations are defined in the paper in terms of LST
 * operations.
 */

/*
 * The LST as defined in the paper has a fixed size set at creation.
 * Here, as with quickheaps, but we want to allow for expansion...
 * though given that, as the paper shows, the expected stack depth
 * is proportion to the log of the number of items in the LST, expanding
 * the pivot stack may be a rare event.
 */
#define INITIAL_CAPACITY  2048

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

typedef unsigned int stack_index_t;

typedef struct {
  stack_index_t depth;    //!< The current stack depth.
  unsigned int  size;   //!< The current stack size (number of frames)
  fr_lst_index_t  *data;    //!< Array of indices of the pivots (sometimes called roots)
} pivot_stack_t;

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

static inline fr_lst_index_t stack_item(pivot_stack_t const *s, stack_index_t idx) CC_HINT(always_inline, nonnull);
static inline stack_index_t lst_length(fr_lst_t const *lst, stack_index_t stack_index) CC_HINT(always_inline, nonnull);

static inline CC_HINT(always_inline, nonnull) void *index_addr(fr_lst_t const *lst, void *data)
{
  return ((uint8_t *)data) + (lst)->offset;
}

/*
 * Concerning item_index() and item_index_set():
 * To let zero be the value *as stored in an item* that indicates not being in an LST,
 * we add one to the real index when storing it and subtract one when retrieving it.
 *
 * This lets the LST functions use item indices in [0, lst->capacity), important for
 * 1. the circular array, which allows an important optimization for fr_lst_pop()
 * 2. quick reduction of indices
 *
 * fr_item_insert() needs to see the value actually stored, hence raw_item_index().
 */
static inline CC_HINT(always_inline, nonnull) fr_lst_index_t raw_item_index(fr_lst_t const *lst, void *data)
{
  return *(fr_lst_index_t *)index_addr(lst, data);
}

static inline CC_HINT(always_inline, nonnull) fr_lst_index_t item_index(fr_lst_t const *lst, void *data)
{
  return  raw_item_index(lst, data) - 1;
}

static inline CC_HINT(always_inline, nonnull) void item_index_set(fr_lst_t *lst, void *data, fr_lst_index_t idx)
{
  (*(fr_lst_index_t *)index_addr(lst, data)) = idx + 1;
}

static inline CC_HINT(always_inline, nonnull) fr_lst_index_t index_reduce(fr_lst_t const *lst, fr_lst_index_t idx)
{
  return idx & ((lst)->capacity - 1);
}

static inline CC_HINT(always_inline, nonnull)
bool is_equivalent(fr_lst_t const *lst, fr_lst_index_t idx1, fr_lst_index_t idx2)
{
  return (index_reduce(lst, idx1 - idx2) == 0);
}

static inline CC_HINT(always_inline, nonnull) void item_set(fr_lst_t *lst, fr_lst_index_t idx, void *data)
{
  lst->p[index_reduce(lst, idx)] = data;
}

static inline CC_HINT(always_inline, nonnull) void *item(fr_lst_t const *lst, fr_lst_index_t idx)
{
  return (lst->p[index_reduce(lst, idx)]);
}

static inline CC_HINT(always_inline, nonnull) void *pivot_item(fr_lst_t const *lst, stack_index_t idx)
{
  return item(lst, stack_item(&lst->s, idx));
}

/*
 * The paper defines randomized priority queue operations appropriately for the
 * sum type definition the authors use for LSTs, which are used to implement the
 * RPQ operations. This code, however, deals with the internal representation,
 * including the root/pivot stack, which must change as the LST changes. Also, an
 * insertion or deletion may shift the position of any number of buckets or change
 * the number of buckets.
 *
 * So... for those operations, we will pass in the pointer to the LST, but
 * internally, we'll represent it and its subtrees with an (LST pointer, stack index)
 * pair. The index is that of the least pivot greater than or equal to all items in
 * the subtree (considering the "fictitious" pivot greater than anything, so (lst, 0)
 * represents the entire tree.
 *
 * The fictitious pivot at the bottom of the stack isn't actually in the array,
 * so don't try to refer to what's there.
 *
 * The index is visible for the size and length functions, since they need
 * to know the subtree they're working on.
 */
static inline CC_HINT(always_inline, nonnull) bool is_bucket(fr_lst_t const *lst, stack_index_t idx)
{
  return lst_length(lst, idx) == 1;
}

static bool stack_expand(fr_lst_t *lst, pivot_stack_t *s)
{
  fr_lst_index_t  *n;
  unsigned int  n_size;

#ifndef NDEBUG
  /*
   *  This likely can't happen, we just include
   *  the guard to keep static analysis happy.
   */
  if (unlikely(s->size > (UINT_MAX - s->size))) {
    if (s->size == UINT_MAX) {
      fr_strerror_const("lst stack is full");
      return false;
    } else {
      n_size = UINT_MAX;
    }
  } else {
#endif
    n_size = s->size * 2;
#ifndef NDEBUG
  }
#endif

  n = talloc_realloc(lst, s->data, fr_lst_index_t, n_size);
  if (unlikely(!n)) {
    fr_strerror_printf("Failed expanding lst stack to %u elements (%zu bytes)",
           n_size, n_size * sizeof(fr_lst_index_t));
    return false;
  }

  s->size = n_size;
  s->data = n;
  return true;
}

static inline CC_HINT(always_inline, nonnull) int stack_push(fr_lst_t *lst, pivot_stack_t *s, fr_lst_index_t pivot)
{
  if (unlikely(s->depth == s->size && !stack_expand(lst, s))) return -1;

  s->data[s->depth++] = pivot;
  return 0;
}

static inline CC_HINT(always_inline, nonnull) void stack_pop(pivot_stack_t *s, unsigned int n)
{
  s->depth -= n;
}

static inline CC_HINT(always_inline, nonnull) stack_index_t stack_depth(pivot_stack_t const *s)
{
  return s->depth;
}

static inline fr_lst_index_t stack_item(pivot_stack_t const *s, stack_index_t idx)
{
  return s->data[idx];
}

static inline CC_HINT(always_inline, nonnull)
void stack_set(pivot_stack_t *s, stack_index_t idx, fr_lst_index_t new_value)
{
  s->data[idx] = new_value;
}

fr_lst_t *_fr_lst_alloc(TALLOC_CTX *ctx, fr_cmp_t cmp, char const *type, size_t offset, fr_lst_index_t init)
{
  fr_lst_t  *lst;
  pivot_stack_t *s;
  unsigned int  initial_stack_capacity;

  if (!init) {
    init = INITIAL_CAPACITY;
  } else if (!is_power_of_2(init)) {
    init = 1 << fr_high_bit_pos(init);
  }

  for (initial_stack_capacity = 1; (1U << initial_stack_capacity) < init; initial_stack_capacity++) ;

  /*
   *  Pre-allocate stack memory as it is
   *  unlikely to need to grow in practice.
   *
   *  We don't pre-allocate the array of elements
   *  If we pre-allocated the array of elements
   *  we'd end up wasting that memory as soon as
   *  we needed to expand the array.
   *
   *  Pre-allocating three chunks appears to be
   *  the optimum.
   */
  lst = talloc_zero_pooled_object(ctx, fr_lst_t, 3, (initial_stack_capacity * sizeof(fr_lst_index_t)));
  if (unlikely(!lst)) return NULL;

  lst->capacity = init;
  lst->p = talloc_array(lst, void *, lst->capacity);
  if (unlikely(!lst->p)) {
  cleanup:
    talloc_free(lst);
    return NULL;
  }

  /*
   *  Allocate the initial stack
   */
  s = &lst->s;
  s->data = talloc_array(lst, fr_lst_index_t, initial_stack_capacity);
  if (unlikely(!s->data)) goto cleanup;
  s->depth = 0;
  s->size = initial_stack_capacity;

  /* Initially the LST is empty and we start at the beginning of the array */
  stack_push(lst, &lst->s, 0);

  lst->idx = 0;

  /* Prepare for random choices */
  lst->rand_ctx.a = fr_rand();
  lst->rand_ctx.b = fr_rand();

  lst->type = type;
  lst->cmp = cmp;
  lst->offset = offset;

  return lst;
}

/** The length function for LSTs (how many buckets it contains)
 *
 */
static inline stack_index_t lst_length(fr_lst_t const *lst, stack_index_t stack_index)
{
  return stack_depth(&lst->s) - stack_index;
}

/** The size function for LSTs (number of items a (sub)tree contains)
 *
 */
static CC_HINT(nonnull) fr_lst_index_t lst_size(fr_lst_t *lst, stack_index_t stack_index)
{
  fr_lst_index_t  reduced_right, reduced_idx;

  if (stack_index == 0) return lst->num_elements;

  reduced_right = index_reduce(lst, stack_item(&lst->s, stack_index));
  reduced_idx = index_reduce(lst, lst->idx);

  if (reduced_idx <= reduced_right) return reduced_right - reduced_idx; /* No wraparound--easy. */

  return (lst->capacity - reduced_idx) + reduced_right;
}

/** Flatten an LST, i.e. turn it into the base-case one bucket [sub]tree
 *
 * NOTE: so doing leaves the passed stack_index valid--we just add
 * everything once in the left subtree to it.
 */
static inline CC_HINT(always_inline, nonnull) void lst_flatten(fr_lst_t *lst, stack_index_t stack_index)
{
  stack_pop(&lst->s, stack_depth(&lst->s) - stack_index);
}

/** Move data to a specific location in an LST's array.
 *
 * The caller must have made sure the location is available and exists
 * in said array.
 */
static inline CC_HINT(always_inline, nonnull) void lst_move(fr_lst_t *lst, fr_lst_index_t location, void *data)
{
  item_set(lst, location, data);
  item_index_set(lst, data, index_reduce(lst, location));
}

/** Add data to the bucket of a specified (sub)tree.
 *
 */
static void bucket_add(fr_lst_t *lst, stack_index_t stack_index, void *data)
{
  fr_lst_index_t  new_space;
  stack_index_t ridx;

  /*
   * For each bucket to the right, starting from the top,
   * make a space available at the top and move the bottom item
   * into it. Since ordering within a bucket doesn't matter, we
   * can do that, minimizing moving and index adjustment.
   *
   * The fictitious pivot doesn't correspond to an actual value,
   * so we save pivot moving for the end of the loop.
   */
  for (ridx = 0; ridx < stack_index; ridx++) {
    fr_lst_index_t  prev_pivot_index = stack_item(&lst->s, ridx + 1);
    bool    empty_bucket;

    new_space = stack_item(&lst->s, ridx);
    empty_bucket = (new_space - prev_pivot_index) == 1;
    stack_set(&lst->s, ridx, new_space + 1);

    if (!empty_bucket) lst_move(lst, new_space, item(lst, prev_pivot_index + 1));

    /* move the pivot up, leaving space for the next bucket */
    lst_move(lst, prev_pivot_index + 1, item(lst, prev_pivot_index));
  }

  /*
   * If the bucket isn't the leftmost, the above loop has made space
   * available where the pivot used to be.
   * If it is the leftmost, the loop wasn't executed, but the fictitious
   * pivot isn't there, which is just as good.
   */
  new_space = stack_item(&lst->s, stack_index);
  stack_set(&lst->s, stack_index, new_space + 1);
  lst_move(lst, new_space, data);

  lst->num_elements++;
}

/** Reduce pivot stack indices based on their difference from lst->idx, and then reduce lst->idx
 *
 */
static void lst_indices_reduce(fr_lst_t *lst)
{
  fr_lst_index_t  reduced_idx = index_reduce(lst, lst->idx);
  stack_index_t depth = stack_depth(&lst->s), i;

  for (i = 0; i < depth; i++) stack_set(&lst->s, i, reduced_idx + stack_item(&lst->s, i) - lst->idx);

  lst->idx = reduced_idx;
}

/** Make more space available in an LST
 *
 * The LST paper only mentions this option in passing, pointing out that it's O(n); the only
 * constructor in the paper lets you hand it an array of items to initially insert
 * in the LST, so elements will have to be removed to make room for more (though it's
 * easy to see how one could specify extra space).
 *
 * Were it not for the circular array optimization, it would be talloc_realloc() and done;
 * it works or it doesn't. (That's still O(n), since it may require copying the data.)
 *
 * With the circular array optimization, if lst->idx refers to something other than the
 * beginning of the array, you have to move the elements preceding it to beginning of the
 * newly-available space so it's still contiguous, and keep pivot stack entries consistent
 * with the positions of the elements.
 */
static bool lst_expand(fr_lst_t *lst)
{
  void    **n;
  unsigned int  old_capacity = lst->capacity, n_capacity;
  fr_lst_index_t  i;

  if (unlikely(old_capacity > (UINT_MAX - old_capacity))) {
    if (old_capacity == UINT_MAX) {
      fr_strerror_const("lst is full");
      return false;
    } else {
      n_capacity = UINT_MAX;
    }
  } else {
    n_capacity = old_capacity * 2;
  }

  n = talloc_realloc(lst, lst->p, void *, n_capacity);
  if (unlikely(!n)) {
    fr_strerror_printf("Failed expanding lst to %u elements (%zu bytes)",
           n_capacity, n_capacity * sizeof(void *));
    return false;
  }

  lst->p = n;
  lst->capacity = n_capacity;

  lst_indices_reduce(lst);

  for (i = 0; i < lst->idx; i++) {
    void    *to_be_moved = item(lst, i);
    fr_lst_index_t  new_index = item_index(lst, to_be_moved) + old_capacity;

    lst_move(lst, new_index, to_be_moved);
  }

  return true;
}

static inline CC_HINT(always_inline, nonnull) fr_lst_index_t bucket_lwb(fr_lst_t const *lst, stack_index_t stack_index)
{
  if (is_bucket(lst, stack_index)) return lst->idx;

  return stack_item(&lst->s, stack_index + 1) + 1;
}

/*
 * Note: buckets can be empty,
 */
static inline CC_HINT(always_inline, nonnull) fr_lst_index_t bucket_upb(fr_lst_t const *lst, stack_index_t stack_index)
{
  return stack_item(&lst->s, stack_index) - 1;
}

/*
 * Partition an LST
 * It's only called for trees that are a single nonempty bucket;
 * if it's a subtree, it is thus necessarily the leftmost.
 */
static bool partition(fr_lst_t *lst, stack_index_t stack_index)
{
  fr_lst_index_t  low = bucket_lwb(lst, stack_index);
  fr_lst_index_t  high = bucket_upb(lst, stack_index);
  fr_lst_index_t  l, h;
  fr_lst_index_t  pivot_index;
  void    *pivot;
  void    *temp;

  /*
   * Hoare partition doesn't do the trivial case, so catch it here.
   */
  if (is_equivalent(lst, low, high)) {
    return (stack_push(lst, &lst->s, low) >= 0);
  }

  pivot_index = low + (fr_fast_rand(&lst->rand_ctx) % (high + 1 - low));
  pivot = item(lst, pivot_index);

  if (pivot_index != low) {
    lst_move(lst, pivot_index, item(lst, low));
    lst_move(lst, low, pivot);
  }

  /*
   * Hoare partition; on the avaerage, it does a third the swaps of
   * Lomuto.
   */
  l = low - 1;
  h = high + 1;
  for (;;) {
    while (lst->cmp(item(lst, --h), pivot) > 0) ;
    while (lst->cmp(item(lst, ++l), pivot) < 0) ;
    if (l >= h) break;
    temp = item(lst, l);
    lst_move(lst, l, item(lst, h));
    lst_move(lst, h, temp);
  }

  /*
   * Hoare partition doesn't guarantee the pivot sits at location h
   * the way Lomuto does and LST needs, so first get its location...
   */
  pivot_index = item_index(lst, pivot);
  if (pivot_index >= index_reduce(lst, low)) {
    pivot_index = low + pivot_index - index_reduce(lst, low);
  } else {
    pivot_index = high - (index_reduce(lst, high) - pivot_index);
  }

  /*
   * ...and then move it if need be.
   */
  if (pivot_index < h) {
    lst_move(lst, pivot_index, item(lst, h));
    lst_move(lst, h, pivot);
  }
  if (pivot_index > h) {
    h++;
    lst_move(lst, pivot_index, item(lst, h));
    lst_move(lst, h, pivot);
  }

  return (stack_push(lst, &lst->s, h) >= 0);
}

/*
 * Delete an item from a bucket in an LST
 */
static void bucket_delete(fr_lst_t *lst, stack_index_t stack_index, void *data)
{
  fr_lst_index_t  location = item_index(lst, data);
  fr_lst_index_t  top;

  if (is_equivalent(lst, location, lst->idx)) {
    lst->idx++;
    if (is_equivalent(lst, lst->idx, 0)) lst_indices_reduce(lst);
  } else {
    for (;;) {
      top = bucket_upb(lst, stack_index);
      if (!is_equivalent(lst, location, top)) lst_move(lst, location, item(lst, top));
      stack_set(&lst->s, stack_index, top);
      if (stack_index == 0) break;
      lst_move(lst, top, item(lst, top + 1));
      stack_index--;
      location = top + 1;
    }
  }

  lst->num_elements--;
  item_index_set(lst, data, -1);
}

/*
 * We precede each function that does the real work with a Pythonish
 * (but colon-free) version of the pseudocode from the paper.
 *
 * clang, in version 13, will have a way to force tail call optimization
 * with a "musttail" attribute. gcc has -f-foptimize-sibling-calls, but
 * it works only with -O[23s]. For now, -O2 will assure TCO. In its absence,
 * the recursion depth is bounded by the number of pivot stack entries, aka
 * the "length" of the LST, which has an expected value proportional to
 * log(number of nodes).
 *
 * NOTE: inlining a recursive function is not advisable, so no
 * always_inline here.
 */

/*
 * ExtractMin(LST T ) // assumes s(T ) > 0
 *  If T = bucket(B) Then
 *    Partition(T ) // O(|B|)
 *  Let T = tree(r, L, B )
 *  If s(L) = 0 Then
 *    Flatten T into bucket(B ) // O(1)
 *    Remove r from bucket B // O(1)
 *    Return r
 *  Else
 *    Return ExtractMin(L)
 */
static inline CC_HINT(nonnull) void *_fr_lst_pop(fr_lst_t *lst, stack_index_t stack_index)
{
  if (is_bucket(lst, stack_index) && !partition(lst, stack_index)) return NULL;
  ++stack_index;
  if (lst_size(lst, stack_index) == 0) {
    void *min = pivot_item(lst, stack_index);

    lst_flatten(lst, stack_index);
    bucket_delete(lst, stack_index, min);
    return min;
  }
  return _fr_lst_pop(lst, stack_index);
}

/*
 * FindMin(LST T ) // assumes s(T ) > 0
 *  If T = bucket(B) Then
 *    Partition(T ) // O(|B|)
 *  Let T = tree(r, L, B )
 *  If s(L) = 0 Then
 *    Return r
 *  Else
 *    Return FindMin(L)
 */
static inline CC_HINT(nonnull) void *_fr_lst_peek(fr_lst_t *lst, stack_index_t stack_index)
{
  if (is_bucket(lst, stack_index) && !partition(lst, stack_index)) return NULL;
  ++stack_index;
  if (lst_size(lst, stack_index) == 0) return pivot_item(lst, stack_index);
  return _fr_lst_peek(lst, stack_index);
}

/*
 * Delete(LST T, x ∈ Z)
 *  If T = bucket(B) Then
 *    Remove x from bucket B // O(depth)
 *  Else
 *    Let T = tree(r, L, B′)
 *    If x < r Then
 *      Delete(L, x)
 *    Else If x > r Then
 *      Remove x from bucket B ′ // O(depth)
 *    Else
 *      Flatten T into bucket(B′′) // O(1)
 *      Remove x from bucket B′′ // O(depth)
 */
static inline CC_HINT(nonnull) void _fr_lst_extract(fr_lst_t *lst,  stack_index_t stack_index, void *data)
{
  int8_t  cmp;

  if (is_bucket(lst, stack_index)) {
    bucket_delete(lst, stack_index, data);
    return;
  }
  stack_index++;
  cmp = lst->cmp(data, pivot_item(lst, stack_index));
  if (cmp < 0) {
    _fr_lst_extract(lst, stack_index, data);
  } else if (cmp > 0) {
    bucket_delete(lst, stack_index - 1, data);
  } else {
    lst_flatten(lst, stack_index);
    bucket_delete(lst, stack_index, data);
  }
}

/*
 * Insert(LST T, x ∈ Z)
 *  If T = bucket(B) Then
 *    Add x to bucket B // O(depth)
 *  Else
 *    Let T = tree(r, L, B)
 *    If random(s(T) + 1) != 1 Then
 *      If x < r Then
 *        Insert(L, x)
 *      Else
 *        Add x to bucket B // O(depth)
 *    Else
 *      Flatten T into bucket(B′) // O(1)
 *      Add x to bucket B′ // O(depth)
 */
static inline CC_HINT(nonnull) void _fr_lst_insert(fr_lst_t *lst, stack_index_t stack_index, void *data)
{
#ifndef TALLOC_GET_TYPE_ABORT_NOOP
  if (lst->type) (void)_talloc_get_type_abort(data, lst->type, __location__);
#endif

  if (is_bucket(lst, stack_index)) {
    bucket_add(lst, stack_index, data);
    return;
  }
  stack_index++;
  if (fr_fast_rand(&lst->rand_ctx) % (lst_size(lst, stack_index) + 1) != 0) {
    if (lst->cmp(data, pivot_item(lst, stack_index)) < 0) {
      _fr_lst_insert(lst, stack_index, data);
    } else {
      bucket_add(lst, stack_index - 1, data);
    }
  } else {
    lst_flatten(lst, stack_index);
    bucket_add(lst, stack_index, data);
  }
}

/*
 * We represent a (sub)tree with an (lst, stack index) pair, so
 * fr_lst_pop(), fr_lst_peek(), and fr_lst_extract() are minimal
 * wrappers that
 *
 * (1) hide our representation from the user and preserve the interface
 * (2) check preconditions
 */

void *fr_lst_pop(fr_lst_t *lst)
{
  if (unlikely(lst->num_elements == 0)) return NULL;
  return _fr_lst_pop(lst, 0);
}

void *fr_lst_peek(fr_lst_t *lst)
{
  if (unlikely(lst->num_elements == 0)) return NULL;
  return _fr_lst_peek(lst, 0);
}

/** Remove an element from an LST
 *
 * @param[in] lst   the LST to remove an element from
 * @param[in] data    the element to remove
 * @return
 *  - 0 if removal succeeds
 *  - -1 if removal fails
 */
int fr_lst_extract(fr_lst_t *lst, void *data)
{
  if (unlikely(lst->num_elements == 0)) {
    fr_strerror_const("Tried to extract element from empty LST");
    return -1;
  }

  if (unlikely(raw_item_index(lst, data) == 0)) {
    fr_strerror_const("Tried to extract element not in LST");
    return -1;
  }

  _fr_lst_extract(lst, 0, data);
  return 0;
}

int fr_lst_insert(fr_lst_t *lst, void *data)
{
  /*
   * Expand if need be. Not in the paper, but we want the capability.
   */
  if (unlikely((lst->num_elements == lst->capacity) && !lst_expand(lst))) return -1;

  /*
   * Don't insert something that looks like it's already in an LST.
   */
  if (unlikely(raw_item_index(lst, data) > 0)) {
    fr_strerror_const("Node is already in the LST");
    return -1;
  }

  _fr_lst_insert(lst, 0, data);
  return 0;
}

unsigned int fr_lst_num_elements(fr_lst_t *lst)
{
  return lst->num_elements;
}

/** Iterate over entries in LST
 *
 * @note If the LST is modified, the iterator should be considered invalidated.
 *
 * @param[in] lst to iterate over.
 * @param[in] iter  Pointer to an iterator struct, used to maintain
 *      state between calls.
 * @return
 *  - User data.
 *  - NULL if at the end of the list.
 */
void *fr_lst_iter_init(fr_lst_t *lst, fr_lst_iter_t *iter)
{
  if (unlikely(lst->num_elements == 0)) return NULL;

  *iter = lst->idx;
  return item(lst, *iter);
}

/** Get the next entry in an LST
 *
 * @note If the LST is modified, the iterator should be considered invalidated.
 *
 * @param[in] lst to iterate over.
 * @param[in] iter  Pointer to an iterator struct, used to maintain
 *      state between calls.
 * @return
 *  - User data.
 *  - NULL if at the end of the list.
 */
void *fr_lst_iter_next(fr_lst_t *lst, fr_lst_iter_t *iter)
{
  if ((*iter + 1) >= stack_item(&lst->s, 0)) return NULL;
  *iter += 1;

  return item(lst, *iter);
}

#ifndef TALLOC_GET_TYPE_ABORT_NOOP
void fr_lst_verify(char const *file, int line, fr_lst_t const *lst)
{
  fr_lst_index_t  fake_pivot_index, reduced_fake_pivot_index, reduced_end;
  stack_index_t depth = stack_depth(&(lst->s));
  int   bucket_size_sum;
  bool    pivots_in_order = true;
  bool    pivot_indices_in_order = true;

  fr_fatal_assert_msg(lst, "CONSISTENCY CHECK FAILED %s[%i]: LST pointer NULL", file, line);
  talloc_get_type_abort(lst, fr_lst_t);

  /*
   *  There must be at least the fictitious pivot.
   */
  fr_fatal_assert_msg(depth >= 1, "CONSISTENCY CHECK FAILED %s[%i]: LST pivot stack empty", file, line);

  /*
   *  Modulo circularity, idx + the number of elements should be the index
   *  of the fictitious pivot.
   */
  fake_pivot_index = stack_item(&(lst->s), 0);
  reduced_fake_pivot_index = index_reduce(lst, fake_pivot_index);
  reduced_end = index_reduce(lst, lst->idx + lst->num_elements);
  fr_fatal_assert_msg(reduced_fake_pivot_index == reduced_end,
          "CONSISTENCY CHECK FAILED %s[%i]: fictitious pivot doesn't point past last element",
          file, line);

  /*
   *  Bucket sizes must make sense.
   */
  if (lst->num_elements) {
    bucket_size_sum = 0;

    for (stack_index_t stack_index = 0; stack_index < depth; stack_index++)  {
      fr_lst_index_t bucket_size = bucket_upb(lst, stack_index) - bucket_lwb(lst, stack_index) + 1;
      fr_fatal_assert_msg(bucket_size <= lst->num_elements,
              "CONSISTENCY CHECK FAILED %s[%i]: bucket %u size %u is invalid",
              file, line, stack_index, bucket_size);
      bucket_size_sum += bucket_size;
    }

    fr_fatal_assert_msg(bucket_size_sum + depth - 1 == lst->num_elements,
            "CONSISTENCY CHECK FAILED %s[%i]: buckets inconsistent with number of elements",
            file, line);
  }

  /*
   *  No elements should be NULL;
   *  they should have the correct index stored,
   *  and if a type is specified, they should point at something of that type,
   */
  for (fr_lst_index_t i = 0; i < lst->num_elements; i++) {
    void  *element = item(lst, lst->idx + i);

    fr_fatal_assert_msg(element, "CONSISTENCY CHECK FAILED %s[%i]: null element pointer at %u",
            file, line, lst->idx + i);
    fr_fatal_assert_msg(is_equivalent(lst, lst->idx + i, item_index(lst, element)),
            "CONSISTENCY CHECK FAILED %s[%i]: element %u index mismatch", file, line, i);
    if (lst->type)  (void) _talloc_get_type_abort(element, lst->type, __location__);
  }

  /*
   * There's nothing more to check for a one-bucket tree.
   */
  if (is_bucket(lst, 0)) return;

  /*
   * Otherwise, first, pivots from left to right (aside from the fictitious
   * one) should be in ascending order.
   */
  for (stack_index_t stack_index = 1; stack_index + 1 < depth; stack_index++) {
    void  *current_pivot = pivot_item(lst, stack_index);
    void  *next_pivot = pivot_item(lst, stack_index + 1);

    if (current_pivot && next_pivot && lst->cmp(current_pivot, next_pivot) < 0) pivots_in_order = false;
  }
  fr_fatal_assert_msg(pivots_in_order, "CONSISTENCY CHECK FAILED %s[%i]: pivots not in ascending order",
          file, line);

  /*
   * Next, the stacked pivot indices should decrease as you ascend from
   * the bottom of the pivot stack. Here we *do* include the fictitious
   * pivot; we're just comparing indices.
   */
  for (stack_index_t stack_index = 0; stack_index + 1 < depth; stack_index++) {
    fr_lst_index_t current_pivot_index = stack_item(&(lst->s), stack_index);
    fr_lst_index_t previous_pivot_index = stack_item(&(lst->s), stack_index + 1);

    if (previous_pivot_index >= current_pivot_index) pivot_indices_in_order = false;
  }
  fr_fatal_assert_msg(pivot_indices_in_order, "CONSISTENCY CHECK FAILED %s[%i]: pivots indices not in order",
          file, line);

  /*
   * Finally...
   * values in buckets shouldn't "follow" the pivot to the immediate right (if it exists)
   * and shouldn't "precede" the pivot to the immediate left (if it exists)
   */
  for (stack_index_t stack_index = 0; stack_index < depth; stack_index++) {
    fr_lst_index_t  lwb, upb, pivot_index;
    void    *pivot_item, *element;

    if (stack_index > 0) {
      lwb = (stack_index + 1 == depth) ? lst->idx : stack_item(&(lst->s), stack_index + 1);
      pivot_index = upb = stack_item(&(lst->s), stack_index);
      pivot_item = item(lst, pivot_index);
      for (fr_lst_index_t index = lwb; index < upb; index++) {
        element = item(lst, index);
        fr_fatal_assert_msg(!element || !pivot_item || lst->cmp(element, pivot_item) <= 0,
                "CONSISTENCY CHECK FAILED %s[%i]: element at %u > pivot at %u",
                file, line, index, pivot_index);
      }
    }
    if (stack_index + 1 < depth) {
      upb = stack_item(&(lst->s), stack_index);
      lwb = pivot_index = stack_item(&(lst->s), stack_index + 1);
      pivot_item = item(lst, pivot_index);
      for (fr_lst_index_t index = lwb; index < upb; index++) {
        element = item(lst, index);
        fr_fatal_assert_msg(!element || !pivot_item || lst->cmp(pivot_item, element) <= 0,
                "CONSISTENCY CHECK FAILED %s[%i]: element at %u < pivot at %u",
                file, line, index, pivot_index);
      }
    }
  }
}
#endif

Coverage Report

Created: 2026-08-14 07:17