Edit

kc3-lang/kc3/libc3/skiplist.c.in

Branch :

  • libc3/skiplist.c.in 
  • /* c3
 * Copyright 2022 kmx.io <contact@kmx.io>
 *
 * Permission is hereby granted to use this software granted
 * the above copyright notice and this permission paragraph
 * are included in all copies and substantial portions of this
 * software.
 *
 * THIS SOFTWARE IS PROVIDED "AS-IS" WITHOUT ANY GUARANTEE OF
 * PURPOSE AND PERFORMANCE. IN NO EVENT WHATSOEVER SHALL THE
 * AUTHOR BE CONSIDERED LIABLE FOR THE USE AND PERFORMANCE OF
 * THIS SOFTWARE.
 */
#include <assert.h>
#include <stdlib.h>
#include <strings.h>
#include "_NAME$.h"
#include "skiplist_node___NAME$.h"
#include "skiplist___NAME$.h"

/*
  Random height
  -------------

  ∀ U ∈ ℕ : 1 < U
  ∀ n ∈ ℕ*
  ∀ r ∈ ℕ : r ≤ n
  ∀ random : ℕ* ⟶ ℕ
             random(n) ∈ [0..n-1]
             ∀ i ∈ [0..n-1], P(random(n) = i) = n⁻¹               (i)
  Qᵣ := random(Uⁿ) < Uⁿ⁻ʳ

  (i) ⇒        P(random(n) < v) = ∑ᵢ₌₀ᵛ⁻¹ P(random(n) = i)
      ⇒        P(random(n) < v) = v . n⁻¹                        (ii)

      ⇒    P(random(Uⁿ) < Uⁿ⁻ʳ) = Uⁿ⁻ʳ . (Uⁿ)⁻¹
      ⇔                   P(Qᵣ) = U⁻ʳ                           (iii)

  P(Qₙ) = P(random(Uⁿ) < U⁰)
        = P(random(Uⁿ) < 1)
        = P(random(Uⁿ) = 0)
        = U⁻ⁿ

  R := maxᵣ(Qᵣ)
     = maxᵣ(random(Uⁿ) < Uⁿ⁻ʳ)
     = maxᵣ(random(Uⁿ) + 1 ≤ Uⁿ⁻ʳ)
     = maxᵣ(logᵤ(random(Uⁿ) + 1) ≤ n - r)
     = maxᵣ(⌈logᵤ(random(Uⁿ) + 1)⌉ ≤ n - r)
     = maxᵣ(r ≤ n - ⌈logᵤ(random(Uⁿ) + 1)⌉)
     = n - ⌈logᵤ(random(Uⁿ) + 1)⌉                                (iv)

                       0 ≤ random(Uⁿ) < Uⁿ
   ⇔                   1 ≤ random(Uⁿ)+1 ≤ Uⁿ
   ⇔        logᵤ(1) ≤ logᵤ(random(Uⁿ)+1) ≤ logᵤ(Uⁿ)
   ⇔             0 ≤ ⌈logᵤ(random(Uⁿ)+1)⌉ ≤ n
   ⇔           -n ≤ -⌈logᵤ(random(Uⁿ)+1)⌉ ≤ 0
   ⇔         0 ≤ n - ⌈logᵤ(random(Uⁿ)+1)⌉ ≤ n
   ⇔                      0 ≤ R ≤ n                               (v)
*/

void
skiplist_clean___NAME$ (s_skiplist___NAME$ *skiplist)
{
  s_skiplist_node___NAME$ *node;
  assert(skiplist);
  assert(skiplist->head);
  while ((node = SKIPLIST_NODE_NEXT___NAME$(skiplist->head, 0)))
    skiplist_remove___NAME$(skiplist, node->_NAME$);
  skiplist_node_delete___NAME$(skiplist->head);
}

void
skiplist_delete___NAME$ (s_skiplist___NAME$ *skiplist)
{
  assert(skiplist);
  skiplist_clean___NAME$(skiplist);
  free(skiplist);
}

s_skiplist_node___NAME$ *
skiplist_find___NAME$ (s_skiplist___NAME$ *skiplist, _TYPE$ _NAME$)
{
  s_skiplist_node___NAME$ *node = skiplist->head;
  u8 level = node->height;
  while (level--) {
    s_skiplist_node___NAME$ *n = node;
    s8 c = -1;
    while (n && (c = skiplist->compare(_NAME$, n->_NAME$)) > 0)
      n = SKIPLIST_NODE_NEXT___NAME$(n, level);
    if (c == 0)
      return n;
  }
  return NULL;
}

static void skiplist_height_table_init___NAME$ (s_skiplist___NAME$ *skiplist, f64 spacing)
{
  sw *height_table;
  u8 h;
  f64 w = spacing;
  f64 end = w;
  height_table = SKIPLIST_HEIGHT_TABLE___NAME$(skiplist);
  for (h = 0; h < skiplist->max_height; h++) {
    w *= spacing;
    end += w;
    height_table[h] = end;
  }
}

s_skiplist___NAME$ *
skiplist_init___NAME$ (s_skiplist___NAME$ *skiplist, u8 max_height, f64 spacing)
{
  assert(skiplist);
  skiplist->head = skiplist_node_new___NAME$(NULL, max_height);
  skiplist->compare = _NAME$_compare;
  skiplist->length = 0;
  skiplist->max_height = max_height;
  skiplist_height_table_init___NAME$(skiplist, spacing);
  return skiplist;
}

s_skiplist_node___NAME$ *
skiplist_insert___NAME$ (s_skiplist___NAME$ *skiplist, _TYPE$ _NAME$)
{
  s_skiplist_node___NAME$ *pred = skiplist_pred___NAME$(skiplist, _NAME$);
  s_skiplist_node___NAME$ *next = SKIPLIST_NODE_NEXT___NAME$(pred, 0);
  uw height;
  s_skiplist_node___NAME$ *node;
  next = SKIPLIST_NODE_NEXT___NAME$(next, 0);
  if (next && skiplist->compare(_NAME$, next->_NAME$) == 0)
    return next;
  height = skiplist_random_height___NAME$(skiplist);
  node = skiplist_node_new___NAME$(_NAME$, height);
  skiplist_node_insert___NAME$(node, pred);
  skiplist->length++;
  skiplist_node_delete___NAME$(pred);
  return node;
}

s_skiplist___NAME$ *
skiplist_new___NAME$ (u8 max_height, f64 spacing)
{
  s_skiplist___NAME$ *skiplist = malloc(SKIPLIST_SIZE___NAME$(max_height));
  if (skiplist)
    skiplist_init___NAME$(skiplist, max_height, spacing);
  return skiplist;
}

s_skiplist_node___NAME$ *
skiplist_pred___NAME$ (s_skiplist___NAME$ *skiplist, _TYPE$ _NAME$)
{
  int level = skiplist->max_height;
  s_skiplist_node___NAME$ *pred =
    skiplist_node_new___NAME$(NULL, skiplist->max_height);
  s_skiplist_node___NAME$ *node = skiplist->head;
  assert(pred);
  while (level--) {
    s_skiplist_node___NAME$ *n = node;
    while (n && skiplist->compare(_NAME$, n->_NAME$) > 0) {
      node = n;
      n = SKIPLIST_NODE_NEXT___NAME$(node, level);
    }
    SKIPLIST_NODE_NEXT___NAME$(pred, level) = node;
  }
  return pred;
}

u8
skiplist_random_height___NAME$ (s_skiplist___NAME$ *skiplist)
{
  const sw *height_table = SKIPLIST_HEIGHT_TABLE___NAME$(skiplist);
  sw max = height_table[skiplist->max_height - 1];

  sw k = random() % max;
  sw i;
  for (i = 0; k > height_table[i]; i++)
    ;
  return skiplist->max_height - i;
}

e_bool
skiplist_remove___NAME$ (s_skiplist___NAME$ *skiplist, _TYPE$ _NAME$)
{
  uw level;
  s_skiplist_node___NAME$ *pred;
  s_skiplist_node___NAME$ *next;
  pred = skiplist_pred___NAME$(skiplist, _NAME$);
  assert(pred);
  next = SKIPLIST_NODE_NEXT___NAME$(pred, 0);
  assert(next);
  next = SKIPLIST_NODE_NEXT___NAME$(next, 0);
  if (!next || skiplist->compare(_NAME$, next->_NAME$) != 0) {
    skiplist_node_delete___NAME$(pred);
    return false;
  }
  for (level = 0; level < next->height; level++) {
    s_skiplist_node___NAME$ *p =
      SKIPLIST_NODE_NEXT___NAME$(pred, level);
    SKIPLIST_NODE_NEXT___NAME$(p, level) =
      SKIPLIST_NODE_NEXT___NAME$(next, level);
  }
  skiplist->length--;
  skiplist_node_delete___NAME$(pred);
  skiplist_node_delete___NAME$(next);
  return true;
}