Init

5 files changed, 317 insertions, 0 deletions

diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..f1c9616
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,13 @@
+Copyright © 2023, Ratakor <ratakor@disroot.org>
+
+Permission to use, copy, modify, and/or distribute this software for any
+purpose with or without fee is hereby granted, provided that the above
+copyright notice and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
+OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+PERFORMANCE OF THIS SOFTWARE.
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..b602669
--- /dev/null
+++ b/README.md
@@ -0,0 +1,15 @@
+skiplist.c
+==========
+A C99 implementation of [skiplists](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.
diff --git a/example.c b/example.c
new file mode 100644
index 0000000..70980a0
--- /dev/null
+++ b/example.c
@@ -0,0 +1,108 @@
+#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/skiplist.c b/skiplist.c
new file mode 100644
index 0000000..bd711db
--- /dev/null
+++ b/skiplist.c
@@ -0,0 +1,145 @@
+/* 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
new file mode 100644
index 0000000..da2385f
--- /dev/null
+++ b/skiplist.h
@@ -0,0 +1,36 @@
+/* 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 */