True init

10 files changed, 572 insertions, 301 deletions

diff --git a/README.md b/README.md
index b602669..8d145b5 100644
--- a/README.md
+++ b/README.md
@@ -1,15 +1,9 @@
-skiplist.c
-==========
-A C99 implementation of [skiplists](https://wikipedia.org/wiki/Skip_list)
+Skip
+====
+A C99 implementation of [skip lists](https://wikipedia.org/wiki/Skip_list)
 
 Usage
 -----
-Change Key and Val type in skiplist.h according to your key/val types and
-that's it.
-
-Notes
------
-sl_create() and sl_search() return NULL on error.
-sl_insert() and sl_remove() return -1 on error.
-Only the .val field of a Node could be modified manually otherwise use
-provided functions.
+Define `SKIP_DOUBLY` to use doubly skip lists instead of singly skip lists.
+Change `SkipKey` and `SkipVal` types in skip.h according to your key/val types,
+include skip.c and skip.h to your project, that's it.
diff --git a/example.c b/example.c
deleted file mode 100644
index 70980a0..0000000
--- a/example.c
+++ /dev/null
@@ -1,108 +0,0 @@
-#include <fcntl.h>
-#include <stdio.h>
-#include <unistd.h>
-
-#include "skiplist.h"
-
-#define LENGTH(X) (sizeof(X) / sizeof(X[0]))
-
-static unsigned int
-getseed(void)
-{
-	unsigned int seed;
-	int fd;
-
-	if ((fd = open("/dev/urandom", O_RDONLY)) < 0)
-		return 0;
-	if (read(fd, &seed, sizeof(seed)) < 0)
-		return 0;
-	if (close(fd) < 0)
-		return 0;
-
-	return seed;
-}
-
-static void
-sl_printlvl(SkipList *list, size_t lvl)
-{
-	Node *np;
-
-	if (list == NULL)
-		return;
-
-	for (np = list->header->fwd[lvl]; np; np = np->fwd[lvl])
-		printf("%d[%d]->", np->key, np->val);
-	puts("NULL");
-
-}
-
-static void
-sl_printall(SkipList *list)
-{
-	unsigned int i;
-
-	if (list == NULL)
-		return;
-
-	for (i = list->lvl; (int)i >= 0; i--) {
-		printf("lvl %u: ", i);
-		sl_printlvl(list, i);
-	}
-}
-
-int
-main(void)
-{
-	const Key key[] = { 32, 47, 36, 51, 0, 62, 43, 39 };
-	const Val val[] = { 14, 10, 11, 29, 2, 18, 16, 38 };
-	const Key delkey[] = { 43, 62, 31, 32, 66 };
-	const Key searchkey[] = { 32, 51, 8, 0, 100 };
-	SkipList *list;
-	Node *np;
-	size_t i;
-
-	list = sl_create(10, getseed());
-	if (list == NULL) {
-		perror(NULL);
-		return 1;
-	}
-
-	for (i = 0; i < LENGTH(key); i++) {
-		printf("insert key %d with val %d\n", key[i], val[i]);
-		if (sl_insert(list, key[i], val[i]) < 0) {
-			perror(NULL);
-			return 1;
-		}
-	}
-
-	sl_printlvl(list, 0);
-	fputc('\n', stdout);
-
-	sl_printall(list);
-	fputc('\n', stdout);
-
-	for (i = 0; i < LENGTH(delkey); i++) {
-		if (sl_remove(list, delkey[i]) < 0)
-			/* not found or malloc failed */
-			printf("key %d is not in the list\n", delkey[i]);
-		else
-			printf("key %d has been deleted\n", delkey[i]);
-	}
-
-	sl_printlvl(list, 0);
-	fputc('\n', stdout);
-
-	for (i = 0; i < LENGTH(searchkey); i++) {
-		np = sl_search(list, searchkey[i]);
-		if (np == NULL)
-			printf("key %d is not in the list\n", searchkey[i]);
-		else
-			printf("key %d found with val = %d\n",
-			       searchkey[i], np->val);
-
-	}
-
-	sl_destroy(list);
-
-	return 0;
-}
diff --git a/examples/Makefile b/examples/Makefile
new file mode 100644
index 0000000..9abba2b
--- /dev/null
+++ b/examples/Makefile
@@ -0,0 +1,20 @@
+TOP       = ..
+SKIP      = ${TOP}/skip.c
+EXAMPLES  = example dump range
+DOUBLY    = -DSKIP_DOUBLY
+CFLAGS   += -std=c99 -pedantic -I${TOP} ${DOUBLY}
+
+all: ${EXAMPLES}
+
+${EXAMPLES}:
+	${CC} $@.c ${SKIP} ${CFLAGS} -o $@
+
+run: all
+	@-./example
+	@-./dump
+	@-./range
+
+clean:
+	rm -f ${EXAMPLES}
+
+.PHONY: all run clean
diff --git a/examples/dump.c b/examples/dump.c
new file mode 100644
index 0000000..747191e
--- /dev/null
+++ b/examples/dump.c
@@ -0,0 +1,84 @@
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "skip.h"
+
+#define LENGTH(X) (sizeof(X) / sizeof(X[0]))
+
+/* This is just to show a dump of a skiplists with all its levels. One should
+ * never define SkipNode or SkipList but use given functions instead.
+ */
+
+struct SkipNode {
+	SkipKey key;
+	SkipVal val;
+#ifdef SKIP_DOUBLY
+	SkipNode *bwd;
+#endif /* SKIP_DOUBLY */
+	SkipNode *fwd[];
+};
+
+struct SkipList {
+	SkipNode *hdr;
+	size_t siz;
+	int lvl;
+};
+
+static void
+setrand(void)
+{
+	unsigned int seed;
+	int fd;
+
+	if ((fd = open("/dev/urandom", O_RDONLY)) < 0)
+		return;
+	read(fd, &seed, sizeof(seed));
+	close(fd);
+	srand(seed);
+}
+
+static void
+skip_dump(SkipList *list)
+{
+	SkipNode *node;
+	int i;
+
+	for (i = list->lvl - 1; i >= 0; i--) {
+		printf("lvl %u: ", i);
+		for (node = list->hdr->fwd[i]; node; node = node->fwd[i])
+			printf("%d[%d]->", skip_key(node), skip_val(node));
+		puts("NULL");
+	}
+}
+
+int
+main(void)
+{
+	const SkipKey key[] = { 32, 47, 36, 51, 0, 62, 43, 39 };
+	const SkipVal val[] = { 14, 10, 11, 29, 2, 18, 16, 38 };
+	SkipList *list;
+	size_t i;
+
+	setrand();
+	list = skip_create();
+	if (list == NULL) {
+		perror(NULL);
+		return 1;
+	}
+
+	for (i = 0; i < LENGTH(key); i++) {
+		printf("insert key %d with val %d\n", key[i], val[i]);
+		if (skip_insert(list, key[i], val[i]) == NULL) {
+			perror(NULL);
+			return 1;
+		}
+	}
+
+	fputc('\n', stdout);
+	skip_dump(list);
+	skip_destroy(list);
+
+	return 0;
+}
diff --git a/examples/example.c b/examples/example.c
new file mode 100644
index 0000000..ed1ed2b
--- /dev/null
+++ b/examples/example.c
@@ -0,0 +1,91 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "skip.h"
+
+#define LENGTH(X) (sizeof(X) / sizeof(X[0]))
+
+static void
+skip_print(SkipList *list)
+{
+	SkipNode *node;
+
+	for (node = skip_first(list); node; node = skip_next(node))
+		printf("%d[%d]->", skip_key(node), skip_val(node));
+	puts("NULL");
+}
+
+#ifdef SKIP_DOUBLY
+static void
+skip_printbw(SkipList *list)
+{
+	SkipNode *node;
+
+	printf("NULL");
+	for (node = skip_last(list); node; node = skip_prev(node))
+		printf("<-%d[%d]", skip_key(node), skip_val(node));
+	fputc('\n', stdout);
+}
+#endif /* SKIP_DOUBLY */
+
+int
+main(void)
+{
+	const SkipKey key[] = { 32, 47, 36, 51, 0, 62, 43, 39 };
+	const SkipVal val[] = { 14, 10, 11, 29, 2, 18, 16, 38 };
+	const SkipKey delkey[] = { 43, 62, 31, 32, 66 };
+	const SkipKey searchkey[] = { 32, 51, 8, 0, 100 };
+	SkipList *list;
+	SkipNode *node;
+	size_t i;
+
+	srand(time(NULL));
+	list = skip_create();
+	if (list == NULL) {
+		perror(NULL);
+		return 1;
+	}
+
+	for (i = 0; i < LENGTH(key); i++) {
+		printf("insert key %d with val %d\n", key[i], val[i]);
+		if (skip_insert(list, key[i], val[i]) == NULL) {
+			perror(NULL);
+			return 1;
+		}
+	}
+
+	printf("\nskip list of size %zu:\n", skip_size(list));
+	skip_print(list);
+#ifdef SKIP_DOUBLY
+	skip_printbw(list);
+#endif /* SKIP_DOUBLY */
+	fputc('\n', stdout);
+
+	for (i = 0; i < LENGTH(delkey); i++) {
+		if (skip_delete(list, delkey[i]))
+			printf("deleted node with key %d\n", delkey[i]);
+		else
+			printf("no node with key %d in the list\n", delkey[i]);
+	}
+
+	printf("\nskip list of size %zu:\n", skip_size(list));
+	skip_print(list);
+#ifdef SKIP_DOUBLY
+	skip_printbw(list);
+#endif /* SKIP_DOUBLY */
+	fputc('\n', stdout);
+
+	for (i = 0; i < LENGTH(searchkey); i++) {
+		node = skip_search(list, searchkey[i]);
+		if (node == NULL)
+			printf("key %d is not in the list\n", searchkey[i]);
+		else
+			printf("key %d found with val = %d\n",
+			       searchkey[i], skip_val(node));
+	}
+
+	skip_destroy(list);
+
+	return 0;
+}
diff --git a/examples/range.c b/examples/range.c
new file mode 100644
index 0000000..858052c
--- /dev/null
+++ b/examples/range.c
@@ -0,0 +1,80 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "skip.h"
+
+static size_t
+skip_delrange_slow(SkipList *list, SkipKey from, SkipKey to)
+{
+	SkipNode *node, *next;
+	size_t n;
+
+	node = skip_approx(list, from);
+	for (n = 0; node && skip_key(node) < to; n++) {
+		next = skip_next(node);
+		skip_delete(list, skip_key(node));
+		node = next;
+	}
+
+	return n;
+}
+
+static void
+skip_print(SkipList *list)
+{
+	SkipNode *node;
+
+	for (node = skip_first(list); node; node = skip_next(node))
+		printf("%d[%d]->", skip_key(node), skip_val(node));
+	puts("NULL");
+}
+
+int
+main(void)
+{
+	SkipList *list;
+	SkipNode *node;
+	size_t rv;
+	int i;
+
+	srand(time(NULL));
+	list = skip_create();
+	if (list == NULL) {
+		perror(NULL);
+		return 1;
+	}
+
+	for (i = 0; i < 100; i++) {
+		if (skip_insert(list, i, i) == NULL) {
+			perror(NULL);
+			return 1;
+		}
+	}
+
+	puts("list:");
+	skip_print(list);
+	fputc('\n', stdout);
+
+	printf("delete node with key from %d to %d\n", 32, 58);
+	rv = skip_delrange(list, 32, 58);
+	/* rv = skip_delrange_slow(list, 32, 58); */
+	printf("removed %zu nodes\nupdated list:\n", rv);
+	skip_print(list);
+	fputc('\n', stdout);
+
+	/* Normally we should null check all of this */
+	node = skip_approx(list, 37);
+	printf("node with key ~= 37: %d[%d]\n", skip_key(node), skip_val(node));
+#ifdef SKIP_DOUBLY
+	node = skip_prev(node);
+	printf("prev: %d[%d]\n", skip_key(node), skip_val(node));
+#endif
+	printf("set val %d to node with key %d\n", 42, skip_key(node));
+	skip_setval(node, 42);
+	skip_print(list);
+
+	skip_destroy(list);
+
+	return 0;
+}
diff --git a/skip.c b/skip.c
new file mode 100644
index 0000000..79763b2
--- /dev/null
+++ b/skip.c
@@ -0,0 +1,251 @@
+/* Copyright © 2023 Ratakor. ISC License */
+
+#include <stdlib.h>
+
+#include "skip.h"
+
+#define MAXLVL    32
+#define THRESHOLD RAND_MAX * 0.25
+
+struct SkipNode {
+	SkipKey key;
+	SkipVal val;
+#ifdef SKIP_DOUBLY
+	SkipNode *bwd;
+#endif /* SKIP_DOUBLY */
+	SkipNode *fwd[];
+};
+
+struct SkipList {
+	SkipNode *hdr;
+	size_t siz;
+	int lvl;
+};
+
+SkipList *
+skip_create(void)
+{
+	SkipList *list;
+
+	list = malloc(sizeof(*list));
+	if (list == NULL)
+		return NULL;
+
+	list->lvl = 1;
+	list->siz = 0;
+	list->hdr = calloc(1, sizeof(SkipNode) + MAXLVL * sizeof(SkipNode *));
+	if (list->hdr == NULL) {
+		free(list);
+		return NULL;
+	}
+
+	return list;
+}
+
+void
+skip_destroy(SkipList *list)
+{
+	SkipNode *node, *next;
+
+	for (node = list->hdr; node; node = next) {
+		next = node->fwd[0];
+		free(node);
+	}
+	free(list);
+}
+
+SkipNode *
+skip_insert(SkipList *list, SkipKey key, SkipVal val)
+{
+	SkipNode *update[MAXLVL], *node = list->hdr;
+	int lvl, i;
+
+	for (i = list->lvl - 1; i >= 0; i--) {
+		while (node->fwd[i] && node->fwd[i]->key < key)
+			node = node->fwd[i];
+		update[i] = node;
+	}
+
+	node = node->fwd[0];
+	if (node && node->key == key) {
+		node->val = val;
+		return node;
+	}
+
+	for (lvl = 1; rand() < THRESHOLD; lvl++);
+	if (lvl > list->lvl) {
+		if (lvl > MAXLVL)
+			lvl = MAXLVL;
+		for (i = list->lvl; i < lvl; i++)
+			update[i] = list->hdr;
+		list->lvl = lvl;
+	}
+
+	node = malloc(sizeof(*node) + (size_t)lvl * sizeof(SkipNode *));
+	if (node == NULL)
+		return NULL;
+	node->key = key;
+	node->val = val;
+
+	for (i = 0; i < lvl; i++) {
+		node->fwd[i] = update[i]->fwd[i];
+		update[i]->fwd[i] = node;
+	}
+
+#ifdef SKIP_DOUBLY
+	node->bwd = (update[0] == list->hdr) ? NULL : update[0];
+
+	if (node->fwd[0])
+		node->fwd[0]->bwd = node;
+	else
+		list->hdr->bwd = node;
+#endif /* SKIP_DOUBLY */
+
+	list->siz++;
+
+	return node;
+}
+
+static inline void
+skip_delnode(SkipList *list, SkipNode *node, SkipNode **update)
+{
+	int i;
+
+	for (i = 0; i < list->lvl; i++) {
+		if (update[i]->fwd[i] != node)
+			break;
+		update[i]->fwd[i] = node->fwd[i];
+	}
+
+#ifdef SKIP_DOUBLY
+	if (node->fwd[0])
+		node->fwd[0]->bwd = node->bwd;
+	else
+		list->hdr->bwd = node->bwd;
+#endif /* SKIP_DOUBLY */
+
+	while (list->lvl > 1 && list->hdr->fwd[list->lvl - 1] == NULL)
+		list->lvl--;
+	list->siz--;
+	free(node);
+}
+
+bool
+skip_delete(SkipList *list, SkipKey key)
+{
+	SkipNode *update[MAXLVL], *node = list->hdr;
+	int i;
+
+	for (i = list->lvl - 1; i >= 0; i--) {
+		while (node->fwd[i] && node->fwd[i]->key < key)
+			node = node->fwd[i];
+		update[i] = node;
+	}
+
+	node = node->fwd[0];
+	if (node && node->key == key) {
+		skip_delnode(list, node, update);
+		return true;
+	}
+
+	return false;
+}
+
+size_t
+skip_delrange(SkipList *list, SkipKey from, SkipKey to)
+{
+	SkipNode *update[MAXLVL], *node = list->hdr, *next;
+	size_t n;
+	int i;
+
+	for (i = list->lvl - 1; i >= 0; i--) {
+		while (node->fwd[i] && node->fwd[i]->key < from)
+			node = node->fwd[i];
+		update[i] = node;
+	}
+
+	node = node->fwd[0];
+	for (n = 0; node && node->key < to; n++) {
+		next = node->fwd[0];
+		skip_delnode(list, node, update);
+		node = next;
+	}
+
+	return n;
+}
+
+SkipNode *
+skip_search(SkipList *list, SkipKey key)
+{
+	SkipNode *node;
+
+	node = skip_approx(list, key);
+	if (node && node->key == key)
+		return node;
+
+	return NULL;
+}
+
+SkipNode *
+skip_approx(SkipList *list, SkipKey key)
+{
+	SkipNode *node = list->hdr;
+	int i;
+
+	for (i = list->lvl - 1; i >= 0; i--) {
+		while (node->fwd[i] && node->fwd[i]->key < key)
+			node = node->fwd[i];
+	}
+
+	return node->fwd[0];
+}
+
+size_t
+skip_size(SkipList *list)
+{
+	return list->siz;
+}
+
+SkipNode *
+skip_first(SkipList *list)
+{
+	return list->hdr->fwd[0];
+}
+
+SkipNode *
+skip_next(SkipNode *node)
+{
+	return node->fwd[0];
+}
+
+#ifdef SKIP_DOUBLY
+SkipNode *
+skip_last(SkipList *list)
+{
+	return list->hdr->bwd;
+}
+
+SkipNode *
+skip_prev(SkipNode *node)
+{
+	return node->bwd;
+}
+#endif /* SKIP_DOUBLY */
+
+SkipKey
+skip_key(SkipNode *node)
+{
+	return node->key;
+}
+
+SkipVal
+skip_val(SkipNode *node)
+{
+	return node->val;
+}
+
+void
+skip_setval(SkipNode *node, SkipVal val)
+{
+	node->val = val;
+}
diff --git a/skip.h b/skip.h
new file mode 100644
index 0000000..ae71209
--- /dev/null
+++ b/skip.h
@@ -0,0 +1,40 @@
+/* Copyright © 2023 Ratakor. ISC License */
+
+#ifndef SKIP_H
+#define SKIP_H
+
+#include <sys/types.h>
+#include <stdbool.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+typedef int SkipKey;
+typedef int SkipVal;
+typedef struct SkipNode SkipNode;
+typedef struct SkipList SkipList;
+
+SkipList *skip_create(void);
+void skip_destroy(SkipList *list);
+SkipNode *skip_insert(SkipList *list, SkipKey key, SkipVal val);
+bool skip_delete(SkipList *list, SkipKey key);
+size_t skip_delrange(SkipList *list, SkipKey from, SkipKey to);
+SkipNode *skip_search(SkipList *list, SkipKey key);
+SkipNode *skip_approx(SkipList *list, SkipKey key);
+size_t skip_size(SkipList *list);
+SkipNode *skip_first(SkipList *list);
+SkipNode *skip_next(SkipNode *node);
+#ifdef SKIP_DOUBLY
+SkipNode *skip_last(SkipList *list);
+SkipNode *skip_prev(SkipNode *node);
+#endif /* SKIP_DOUBLY */
+SkipKey skip_key(SkipNode *node);
+SkipVal skip_val(SkipNode *node);
+void skip_setval(SkipNode *node, SkipVal val);
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* SKIP_H */
diff --git a/skiplist.c b/skiplist.c
deleted file mode 100644
index bd711db..0000000
--- a/skiplist.c
+++ /dev/null
@@ -1,145 +0,0 @@
-/* Copyright © 2023 Ratakor. See LICENSE file for license details. */
-
-#include <stdlib.h>
-
-#include "skiplist.h"
-
-SkipList *
-sl_create(unsigned int maxlvl, unsigned int seed)
-{
-	SkipList *list;
-
-	list = malloc(sizeof(*list));
-	if (list == NULL)
-		return NULL;
-
-	list->maxlvl = maxlvl;
-	list->lvl = 0;
-	list->header = calloc(1, sizeof(Node) + (maxlvl + 1) * sizeof(Node *));
-	if (list->header == NULL) {
-		free(list);
-		return NULL;
-	}
-
-	srand(seed);
-
-	return list;
-}
-
-void
-sl_destroy(SkipList *list)
-{
-	Node *np, *next;
-
-	if (list == NULL)
-		return;
-
-	for (np = list->header; np; np = next) {
-		next = np->fwd[0];
-		free(np);
-	}
-	free(list);
-}
-
-int
-sl_insert(SkipList *list, Key key, Val val)
-{
-	Node **update, *np = list->header;
-	unsigned int lvl, i;
-
-	update = malloc((list->maxlvl + 1) * sizeof(Node *));
-	if (update == NULL)
-		return -1;
-
-	for (i = list->lvl; (int)i >= 0; i--) {
-		while (np->fwd[i] && np->fwd[i]->key < key)
-			np = np->fwd[i];
-		update[i] = np;
-	}
-
-	np = np->fwd[0];
-	if (np && np->key == key) {
-		np->val = val;
-		free(update);
-		return 0;
-	}
-
-	for (lvl = 0; lvl < list->maxlvl && rand() < RAND_MAX / 2; lvl++);
-
-	if (lvl > list->lvl) {
-		for (i = list->lvl + 1; i < lvl + 1; i++)
-			update[i] = list->header;
-		list->lvl = lvl;
-	}
-
-	np = malloc(sizeof(*np) + (lvl + 1) * sizeof(Node *));
-	if (np == NULL) {
-		free(update);
-		return -1;
-	}
-	np->key = key;
-	np->val = val;
-
-	for (i = 0; i < lvl + 1; i++) {
-		np->fwd[i] = update[i]->fwd[i];
-		update[i]->fwd[i] = np;
-	}
-
-	free(update);
-
-	return 0;
-}
-
-int
-sl_remove(SkipList *list, Key key)
-{
-	Node **update, *np = list->header;
-	unsigned int i;
-
-	update = malloc((list->maxlvl + 1) * sizeof(Node *));
-	if (update == NULL)
-		return -1;
-
-	for (i = list->lvl; (int)i >= 0; i--) {
-		while (np->fwd[i] && np->fwd[i]->key < key)
-			np = np->fwd[i];
-		update[i] = np;
-	}
-
-	np = np->fwd[0];
-	if (np == NULL || np->key != key) {
-		free(update);
-		return -1;
-	}
-
-	for (i = 0; i < list->lvl + 1; i++) {
-		if (update[i]->fwd[i] != np)
-			break;
-		update[i]->fwd[i] = np->fwd[i];
-	}
-
-	free(np);
-	free(update);
-
-	while (list->lvl > 0 && list->header->fwd[list->lvl] == NULL)
-		list->lvl--;
-
-	return 0;
-}
-
-Node *
-sl_search(SkipList *list, Key key)
-{
-	Node *np = list->header;
-	unsigned int i;
-
-	for (i = list->lvl; (int)i >= 0; i--) {
-		while (np->fwd[i] && np->fwd[i]->key < key)
-			np = np->fwd[i];
-	}
-
-	if (np->fwd[0] && np->fwd[0]->key == key)
-		return np->fwd[0];
-
-	return NULL;
-}
diff --git a/skiplist.h b/skiplist.h
deleted file mode 100644
index da2385f..0000000
--- a/skiplist.h
+++ /dev/null
@@ -1,36 +0,0 @@
-/* Copyright © 2023 Ratakor. See LICENSE file for license details. */
-
-#ifndef SKIPLIST_H
-#define SKIPLIST_H
-
-#ifdef __cplusplus
-extern "C" {
-#endif /* __cplusplus */
-
-typedef int Key;
-typedef int Val;
-
-typedef struct Node Node;
-struct Node {
-	Key key;
-	Val val;
-	Node *fwd[];
-};
-
-typedef struct {
-	unsigned int maxlvl;
-	unsigned int lvl;
-	Node *header;
-} SkipList;
-
-SkipList *sl_create(unsigned int maxlvl, unsigned int seed);
-void sl_destroy(SkipList *list);
-int sl_insert(SkipList *list, Key key, Val val);
-int sl_remove(SkipList *list, Key key);
-Node *sl_search(SkipList *list, Key key);
-
-#ifdef __cplusplus
-}
-#endif /* __cplusplus */
-
-#endif /* SKIPLIST_H */