// SPDX-License-Identifier: LicenseRef-Skiplist-BSD-0-Clause

/*

 * Copyright 1990 William Pugh

 *

 * Permission to include in quagga provide on March 31, 2016

 */

/*

 * Skip List implementation based on code from William Pugh.

 * ftp://ftp.cs.umd.edu/pub/skipLists/

 *

 * Skip Lists are a probabilistic alternative to balanced trees, as

 * described in the June 1990 issue of CACM and were invented by

 * William Pugh in 1987.

 *

 * This file contains source code to implement a dictionary using

 * skip lists and a test driver to test the routines.

 *

 * A couple of comments about this implementation:

 *   The routine randomLevel has been hard-coded to generate random

 *   levels using p=0.25. It can be easily changed.

 *

 *   The insertion routine has been implemented so as to use the

 *   dirty hack described in the CACM paper: if a random level is

 *   generated that is more than the current maximum level, the

 *   current maximum level plus one is used instead.

 *

 *   Levels start at zero and go up to MaxLevel (which is equal to

 *  (MaxNumberOfLevels-1).

 *

 * The run-time flag SKIPLIST_FLAG_ALLOW_DUPLICATES determines whether or

 * not duplicates are allowed for a given list. If set, duplicates are

 * allowed and act in a FIFO manner. If not set, an insertion of a value

 * already in the list updates the previously existing binding.

 *

 * BitsInRandom is defined to be the number of bits returned by a call to

 * random(). For most all machines with 32-bit integers, this is 31 bits

 * as currently set.

 */

#include <zebra.h>

#include "memory.h"

#include "log.h"

#include "vty.h"

#include "skiplist.h"

#include "lib_errors.h"

#include "network.h"

DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List");

DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node");

DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_STATS, "Skiplist Counters");

#define BitsInRandom 31

#define MaxNumberOfLevels 16

#define MaxLevel (MaxNumberOfLevels-1)

#define newNodeOfLevel(l)                                                      \

  XCALLOC(MTYPE_SKIP_LIST_NODE,                                          \

    sizeof(struct skiplistnode)                                    \

      + (l) * sizeof(struct skiplistnode *))

/* XXX must match type of (struct skiplist).level_stats */

#define newStatsOfLevel(l)                                                     \

  XCALLOC(MTYPE_SKIP_LIST_STATS, ((l) + 1) * sizeof(int))

static int randomsLeft;

static int randomBits;

#ifdef SKIPLIST_DEBUG

#define CHECKLAST(sl)                                                          \

  do {                                                                   \

    if ((sl)->header->forward[0] && !(sl)->last)                   \

      assert(0);                                             \

    if (!(sl)->header->forward[0] && (sl)->last)                   \

      assert(0);                                             \

  } while (0)

#else

#define CHECKLAST(sl)

#endif

static int randomLevel(void)

{

  register int level = 0;

  register int b;

  do {

    if (randomsLeft <= 0) {

      randomBits = frr_weak_random();

      randomsLeft = BitsInRandom / 2;

    }

    b = randomBits & 3;

    randomBits >>= 2;

    --randomsLeft;

    if (!b) {

      level++;

      if (level >= MaxLevel)

        return MaxLevel;

    }

  } while (!b);

  return level;

}

static int default_cmp(const void *key1, const void *key2)

{

  if (key1 < key2)

    return -1;

  if (key1 > key2)

    return 1;

  return 0;

}

unsigned int skiplist_count(struct skiplist *l)

{

  return l->count;

}

struct skiplist *skiplist_new(int flags,

            int (*cmp)(const void *key1, const void *key2),

            void (*del)(void *val))

{

  struct skiplist *new;

  new = XCALLOC(MTYPE_SKIP_LIST, sizeof(struct skiplist));

  assert(new);

  new->level = 0;

  new->count = 0;

  new->header = newNodeOfLevel(MaxNumberOfLevels);

  new->level_stats = newStatsOfLevel(MaxNumberOfLevels);

  new->flags = flags;

  if (cmp)

    new->cmp = cmp;

  else

    new->cmp = default_cmp;

  if (del)

    new->del = del;

  return new;

}

void skiplist_free(struct skiplist *l)

{

  register struct skiplistnode *p, *q;

  p = l->header;

  do {

    q = p->forward[0];

    if (l->del && p != l->header)

      (*l->del)(p->value);

    XFREE(MTYPE_SKIP_LIST_NODE, p);

    p = q;

  } while (p);

  XFREE(MTYPE_SKIP_LIST_STATS, l->level_stats);

  XFREE(MTYPE_SKIP_LIST, l);

}

int skiplist_insert(register struct skiplist *l, register void *key,

        register void *value)

{

  register int k;

  struct skiplistnode *update[MaxNumberOfLevels];

  register struct skiplistnode *p, *q;

  CHECKLAST(l);

#ifdef SKIPLIST_DEBUG

  /* DEBUG */

  if (!key) {

    flog_err(EC_LIB_DEVELOPMENT, "%s: key is 0, value is %p",

       __func__, value);

  }

#endif

  p = l->header;

  k = l->level;

  do {

    while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)

      p = q;

    update[k] = p;

  } while (--k >= 0);

  if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) && q

      && ((*l->cmp)(q->key, key) == 0)) {

    return -1;

  }

  k = randomLevel();

  assert(k >= 0);

  if (k > l->level) {

    k = ++l->level;

    update[k] = l->header;

  }

  q = newNodeOfLevel(k);

  q->key = key;

  q->value = value;

#ifdef SKIPLIST_0TIMER_DEBUG

  q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */

#endif

  ++(l->level_stats[k]);

#ifdef SKIPLIST_DEBUG

  zlog_debug("%s: incremented level_stats @%p:%d, now %d", __func__, l, k,

       l->level_stats[k]);

#endif

  do {

    p = update[k];

    q->forward[k] = p->forward[k];

    p->forward[k] = q;

  } while (--k >= 0);

  /*

   * If this is the last item in the list, update the "last" pointer

   */

  if (!q->forward[0]) {

    l->last = q;

  }

  ++(l->count);

  CHECKLAST(l);

  return 0;

}

int skiplist_delete(register struct skiplist *l, register void *key,

        register void *value) /* used only if duplicates allowed */

{

  register int k, m;

  struct skiplistnode *update[MaxNumberOfLevels];

  register struct skiplistnode *p, *q;

  CHECKLAST(l);

  /* to make debugging easier */

  for (k = 0; k < MaxNumberOfLevels; ++k)

    update[k] = NULL;

  p = l->header;

  k = m = l->level;

  do {

    while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)

      p = q;

    update[k] = p;

  } while (--k >= 0);

  if (l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) {

    while (q && ((*l->cmp)(q->key, key) == 0)

           && (q->value != value)) {

      int i;

      for (i = 0; i <= l->level; ++i) {

        if (update[i]->forward[i] == q)

          update[i] = q;

      }

      q = q->forward[0];

    }

  }

  if (q && (*l->cmp)(q->key, key) == 0) {

    if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)

        || (q->value == value)) {

/*

 * found node to delete

 */

#ifdef SKIPLIST_0TIMER_DEBUG

      q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;

#endif

      /*

       * If we are deleting the last element of the list,

       * update the list's "last" pointer.

       */

      if (l->last == q) {

        if (update[0] == l->header)

          l->last = NULL;

        else

          l->last = update[0];

      }

      for (k = 0; k <= m && (p = update[k])->forward[k] == q;

           k++) {

        p->forward[k] = q->forward[k];

      }

      --(l->level_stats[k - 1]);

#ifdef SKIPLIST_DEBUG

      zlog_debug("%s: decremented level_stats @%p:%d, now %d",

           __func__, l, k - 1, l->level_stats[k - 1]);

#endif

      if (l->del)

        (*l->del)(q->value);

      XFREE(MTYPE_SKIP_LIST_NODE, q);

      while (l->header->forward[m] == NULL && m > 0)

        m--;

      l->level = m;

      CHECKLAST(l);

      --(l->count);

      return 0;

    }

  }

  CHECKLAST(l);

  return -1;

}

/*

 * Obtain first value matching "key". Unless SKIPLIST_FLAG_ALLOW_DUPLICATES

 * is set, this will also be the only value matching "key".

 *

 * Also set a cursor for use with skiplist_next_value.

 */

int skiplist_first_value(register struct skiplist *l, /* in */

       register const void *key,    /* in */

       void **valuePointer,       /* out */

       void **cursor)         /* out */

{

  register int k;

  register struct skiplistnode *p, *q;

  p = l->header;

  k = l->level;

  do {

    while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)

      p = q;

  } while (--k >= 0);

  if (!q || (*l->cmp)(q->key, key))

    return -1;

  if (valuePointer)

    *valuePointer = q->value;

  if (cursor)

    *cursor = q;

  return 0;

}

int skiplist_search(register struct skiplist *l, register void *key,

        void **valuePointer)

{

  return skiplist_first_value(l, key, valuePointer, NULL);

}

/*

 * Caller supplies key and value of an existing item in the list.

 * Function returns the value of the next list item that has the

 * same key (useful when SKIPLIST_FLAG_ALLOW_DUPLICATES is set).

 *

 * Returns 0 on success. If the caller-supplied key and value

 * do not correspond to a list element, or if they specify the

 * last element with the given key, -1 is returned.

 */

int skiplist_next_value(register struct skiplist *l, /* in */

      register const void *key,   /* in */

      void **valuePointer,   /* in/out */

      void **cursor)         /* in/out */

{

  register int k;

  register struct skiplistnode *p, *q;

  CHECKLAST(l);

  if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)) {

    return -1;

  }

  if (!cursor || !*cursor) {

    p = l->header;

    k = l->level;

    /*

     * Find matching key

     */

    do {

      while (q = p->forward[k],

             q && (*l->cmp)(q->key, key) < 0)

        p = q;

    } while (--k >= 0);

    /*

     * Find matching value

     */

    while (q && ((*l->cmp)(q->key, key) == 0)

           && (q->value != *valuePointer)) {

      q = q->forward[0];

    }

    if (!q || ((*l->cmp)(q->key, key) != 0)

        || (q->value != *valuePointer)) {

      /*

       * No matching value

       */

      CHECKLAST(l);

      return -1;

    }

  } else {

    q = (struct skiplistnode *)*cursor;

  }

  /*

   * Advance cursor

   */

  q = q->forward[0];

  /*

   * If we reached end-of-list or if the key is no longer the same,

   * then return error

   */

  if (!q || ((*l->cmp)(q->key, key) != 0))

    return -1;

  *valuePointer = q->value;

  if (cursor)

    *cursor = q;

  CHECKLAST(l);

  return 0;

}

int skiplist_first(register struct skiplist *l, void **keyPointer,

       void **valuePointer)

{

  register struct skiplistnode *p;

  CHECKLAST(l);

  p = l->header->forward[0];

  if (!p)

    return -1;

  if (keyPointer)

    *keyPointer = p->key;

  if (valuePointer)

    *valuePointer = p->value;

  CHECKLAST(l);

  return 0;

}

int skiplist_last(register struct skiplist *l, void **keyPointer,

      void **valuePointer)

{

  CHECKLAST(l);

  if (l->last) {

    if (keyPointer)

      *keyPointer = l->last->key;

    if (valuePointer)

      *valuePointer = l->last->value;

    return 0;

  }

  return -1;

}

/*

 * true = empty

 */

int skiplist_empty(register struct skiplist *l)

{

  CHECKLAST(l);

  if (l->last)

    return 0;

  return 1;

}

/*

 * Use this to walk the list. Caller sets *cursor to NULL to obtain

 * first element. Return value of 0 indicates valid cursor/element

 * returned, otherwise NULL cursor arg or EOL.

 */

int skiplist_next(register struct skiplist *l, /* in */

      void **keyPointer,     /* out */

      void **valuePointer,   /* out */

      void **cursor)         /* in/out */

{

  struct skiplistnode *p;

  if (!cursor)

    return -1;

  CHECKLAST(l);

  if (!*cursor) {

    p = l->header->forward[0];

  } else {

    p = *cursor;

    p = p->forward[0];

  }

  *cursor = p;

  if (!p)

    return -1;

  if (keyPointer)

    *keyPointer = p->key;

  if (valuePointer)

    *valuePointer = p->value;

  CHECKLAST(l);

  return 0;

}

int skiplist_delete_first(register struct skiplist *l)

{

  register int k;

  register struct skiplistnode *p, *q;

  int nodelevel = 0;

  CHECKLAST(l);

  p = l->header;

  q = l->header->forward[0];

  if (!q)

    return -1;

  for (k = l->level; k >= 0; --k) {

    if (p->forward[k] == q) {

      p->forward[k] = q->forward[k];

      if ((k == l->level) && (p->forward[k] == NULL)

          && (l->level > 0))

        --(l->level);

      if (!nodelevel)

        nodelevel = k;

    }

  }

#ifdef SKIPLIST_0TIMER_DEBUG

  q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;

#endif

  /*

   * If we are deleting the last element of the list,

   * update the list's "last" pointer.

   */

  if (l->last == q) {

    l->last = NULL;

  }

  --(l->level_stats[nodelevel]);

#ifdef SKIPLIST_DEBUG

  zlog_debug("%s: decremented level_stats @%p:%d, now %d", __func__, l,

       nodelevel, l->level_stats[nodelevel]);

#endif

  if (l->del)

    (*l->del)(q->value);

  XFREE(MTYPE_SKIP_LIST_NODE, q);

  CHECKLAST(l);

  --(l->count);

  return 0;

}

void skiplist_debug(struct vty *vty, struct skiplist *l)

{

  int i;

  if (!l)

    return;

  vty_out(vty, "Skiplist %p has max level %d\n", l, l->level);

  for (i = l->level; i >= 0; --i)

    vty_out(vty, "  @%d: %d\n", i, l->level_stats[i]);

}

static void *scramble(int i)

{

  uintptr_t result;

  result = (unsigned)(i & 0xff) << 24;

  result |= (unsigned)i >> 8;

  return (void *)result;

}

#define sampleSize 65536

void skiplist_test(struct vty *vty)

{

  struct skiplist *l;

  register int i, k;

  void *keys[sampleSize];

  void *v = NULL;

  zlog_debug("%s: entry", __func__);

  l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);

  zlog_debug("%s: skiplist_new returned %p", __func__, l);

  for (i = 0; i < 4; i++) {

    for (k = 0; k < sampleSize; k++) {

      if (!(k % 1000)) {

        zlog_debug("%s: (%d:%d)", __func__, i, k);

      }

      // keys[k] = (void *)random();

      keys[k] = scramble(k);

      if (skiplist_insert(l, keys[k], keys[k]))

        zlog_debug("error in insert #%d,#%d", i, k);

    }

    zlog_debug("%s: inserts done", __func__);

    for (k = 0; k < sampleSize; k++) {

      if (!(k % 1000))

        zlog_debug("[%d:%d]", i, k);

      if (skiplist_search(l, keys[k], &v))

        zlog_debug("error in search #%d,#%d", i, k);

      if (v != keys[k])

        zlog_debug("search returned wrong value");

    }

    for (k = 0; k < sampleSize; k++) {

      if (!(k % 1000))

        zlog_debug("<%d:%d>", i, k);

      if (skiplist_delete(l, keys[k], keys[k]))

        zlog_debug("error in delete");

      keys[k] = scramble(k ^ 0xf0f0f0f0);

      if (skiplist_insert(l, keys[k], keys[k]))

        zlog_debug("error in insert #%d,#%d", i, k);

    }

    for (k = 0; k < sampleSize; k++) {

      if (!(k % 1000))

        zlog_debug("{%d:%d}", i, k);

      if (skiplist_delete_first(l))

        zlog_debug("error in delete_first");

    }

  }

  skiplist_free(l);

}