103 lines
4.0 KiB
C
103 lines
4.0 KiB
C
/**************************************************************************/
|
|
/* */
|
|
/* OCaml */
|
|
/* */
|
|
/* Xavier Leroy, projet Cambium, INRIA Paris */
|
|
/* */
|
|
/* Copyright 2020 Institut National de Recherche en Informatique et */
|
|
/* en Automatique. */
|
|
/* */
|
|
/* All rights reserved. This file is distributed under the terms of */
|
|
/* the GNU Lesser General Public License version 2.1, with the */
|
|
/* special exception on linking described in the file LICENSE. */
|
|
/* */
|
|
/**************************************************************************/
|
|
|
|
/* A dictionary data structure implemented as skip lists */
|
|
|
|
/* Keys and associated data are natural-width integers (type [uintnat]).
|
|
Pointers can be used too, modulo conversion to [uintnat]. */
|
|
|
|
#ifndef CAML_SKIPLIST_H
|
|
#define CAML_SKIPLIST_H
|
|
|
|
#ifdef CAML_INTERNALS
|
|
|
|
#include "config.h"
|
|
|
|
#define NUM_LEVELS 17
|
|
|
|
/* The head of a skip list */
|
|
|
|
struct skiplist {
|
|
struct skipcell * forward[NUM_LEVELS]; /* forward chaining */
|
|
int level; /* max level used */
|
|
};
|
|
|
|
/* The cells of a skip list */
|
|
|
|
struct skipcell {
|
|
uintnat key;
|
|
uintnat data;
|
|
#if (__STDC_VERSION__ >= 199901L)
|
|
struct skipcell * forward[]; /* variable-length array */
|
|
#else
|
|
struct skipcell * forward[1]; /* variable-length array */
|
|
#endif
|
|
};
|
|
|
|
/* Initialize a skip list, statically */
|
|
#define SKIPLIST_STATIC_INITIALIZER { {0, }, 0 }
|
|
|
|
/* Initialize a skip list, dynamically */
|
|
extern void caml_skiplist_init(struct skiplist * sk);
|
|
|
|
/* Search a skip list.
|
|
If [key] is found, store associated data in [*data] and return 1.
|
|
If [key] is not found, return 0 and leave [*data] unchanged. */
|
|
extern int caml_skiplist_find(struct skiplist * sk, uintnat key,
|
|
/*out*/ uintnat * data);
|
|
|
|
/* Search the entry of the skip list that has the largest key less than
|
|
or equal to [k].
|
|
If such an entry exists, store its key in [*key], the associated data in
|
|
[*data], and return 1.
|
|
If no such entry exists (all keys in the skip list are strictly greater
|
|
than [k]), return 0 and leave [*key] and [*data] unchanged. */
|
|
extern int caml_skiplist_find_below(struct skiplist * sk, uintnat k,
|
|
/*out*/ uintnat * key,
|
|
/*out*/ uintnat * data);
|
|
|
|
/* Insertion in a skip list.
|
|
If [key] was already there, change the associated data and return 1.
|
|
If [key] was not there, insert new [key, data] binding and return 0. */
|
|
extern int caml_skiplist_insert(struct skiplist * sk,
|
|
uintnat key, uintnat data);
|
|
|
|
/* Deletion in a skip list.
|
|
If [key] was there, remove it and return 1.
|
|
If [key] was not there, leave the skip list unchanged and return 0. */
|
|
extern int caml_skiplist_remove(struct skiplist * sk, uintnat key);
|
|
|
|
/* Empty an already initialized skip list. */
|
|
extern void caml_skiplist_empty(struct skiplist * sk);
|
|
|
|
/* Iterate over a skip list, in increasing order of keys.
|
|
[var] designates the current element.
|
|
[action] can refer to [var->key] and [var->data].
|
|
[action] can safely remove the current element, i.e. call
|
|
[caml_skiplist_remove] on [var->key]. The traversal will
|
|
continue with the skiplist element following the removed element.
|
|
Other operations performed over the skiplist during its traversal have
|
|
unspecified effects on the traversal. */
|
|
|
|
#define FOREACH_SKIPLIST_ELEMENT(var,sk,action) \
|
|
{ struct skipcell * var, * caml__next; \
|
|
for (var = (sk)->forward[0]; var != NULL; var = caml__next) \
|
|
{ caml__next = (var)->forward[0]; action; } \
|
|
}
|
|
|
|
#endif
|
|
|
|
#endif
|