Add prettydump and prettyprint to examples

Also replaced skip_next(), skip_prev(), skip_key(), skip_val() and
skip_setval() with the SkipNode struct.

5 files changed, 133 insertions, 82 deletions

diff --git a/examples/dump.c b/examples/dump.c
index 747191e..d7424e8 100644
--- a/examples/dump.c
+++ b/examples/dump.c
@@ -1,6 +1,7 @@
 #include <fcntl.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 #include <unistd.h>
 
 #include "skip.h"
@@ -8,20 +9,20 @@
 #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.
+ * never define _SkipNode or SkipList but use given functions instead.
  */
 
-struct SkipNode {
+struct _SkipNode {
 	SkipKey key;
 	SkipVal val;
 #ifdef SKIP_DOUBLY
-	SkipNode *bwd;
+	struct _SkipNode *bwd;
 #endif /* SKIP_DOUBLY */
-	SkipNode *fwd[];
+	struct _SkipNode *fwd[];
 };
 
 struct SkipList {
-	SkipNode *hdr;
+	struct _SkipNode *hdr;
 	size_t siz;
 	int lvl;
 };
@@ -42,22 +43,79 @@ setrand(void)
 static void
 skip_dump(SkipList *list)
 {
-	SkipNode *node;
+	struct _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));
+			printf("%d[%d]->", node->key, node->val);
 		puts("NULL");
 	}
 }
 
+/*  ----------                     ------   --------
+ *  | Header |-------------------->| 40 |-->| NULL |
+ *  ----------                     ------   --------
+ *  ----------   ------            ------   --------
+ *  | Header |-->| 32 |----------->| 40 |-->| NULL |
+ *  ----------   ------            ------   --------
+ *  ----------   ------   ------   ------   --------
+ *  | Header |-->| 32 |-->| 33 |-->| 40 |-->| NULL |
+ *  ----------   ------   ------   ------   --------
+ */
+
+static void
+skip_prettydump(SkipList *list)
+{
+	struct _SkipNode *node, **nodes, **lvlnodes;
+	size_t j;
+	int i;
+
+	nodes = calloc(list->siz, sizeof(struct _SkipNode *));
+	lvlnodes = calloc(list->siz, sizeof(struct _SkipNode *));
+	for (node = list->hdr->fwd[0], i = 0; node; node = node->fwd[0], i++)
+		nodes[i] = node;
+
+	for (i = list->lvl - 1; i >= 0; i--) {
+		memset(lvlnodes, 0, list->siz * sizeof(struct _SkipNode *));
+		printf("----------   ");
+		j = 0;
+		for (node = list->hdr->fwd[i]; node; node = node->fwd[i]) {
+			for (; nodes[j]->key < node->key; j++)
+				printf("         ");
+			printf("------   ");
+			lvlnodes[j] = node;
+			j++;
+		}
+		for (; j < list->siz; j++)
+			printf("         ");
+		printf("--------\n| Header |--");
+		for (j = 0; j < list->siz; j++) {
+			if (lvlnodes[j])
+				printf(">| %02d |--", lvlnodes[j]->key);
+			else
+				printf("---------");
+		}
+		printf(">| NULL |\n----------   ");
+		for (j = 0; j < list->siz; j++) {
+			if (lvlnodes[j])
+				printf("------   ");
+			else
+				printf("         ");
+		}
+		printf("--------\n");
+	}
+
+	free(nodes);
+	free(lvlnodes);
+}
+
 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 key[] = { 32, 47, 36, 51, 13, 62, 43, 39 };
+	const SkipVal val[] = { 14, 10, 11, 29, 22, 18, 16, 38 };
 	SkipList *list;
 	size_t i;
 
@@ -69,15 +127,14 @@ main(void)
 	}
 
 	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_dump(list); */
+	skip_prettydump(list);
 	skip_destroy(list);
 
 	return 0;
diff --git a/examples/example.c b/examples/example.c
index ed1ed2b..8fb42dc 100644
--- a/examples/example.c
+++ b/examples/example.c
@@ -11,8 +11,8 @@ 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));
+	for (node = skip_first(list); node; node = node->next)
+		printf("%d[%d]->", node->key, node->val);
 	puts("NULL");
 }
 
@@ -23,16 +23,34 @@ 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));
+	for (node = skip_last(list); node; node = node->prev)
+		printf("<-%d[%d]", node->key, node->val);
 	fputc('\n', stdout);
 }
 #endif /* SKIP_DOUBLY */
 
+static void
+skip_prettyprint(SkipList *list)
+{
+	SkipNode *node;
+	size_t i;
+
+	printf("%*s\n", 32, "str");
+	for (i = 0; i < skip_size(list); i++)
+		printf("------   ");
+	printf("--------\n");
+	for (node = skip_first(list); node; node = node->next)
+		printf("| %02d |-->", node->key);
+	printf("| NULL |\n");
+	for (i = 0; i < skip_size(list); i++)
+		printf("------   ");
+	printf("--------\n");
+}
+
 int
 main(void)
 {
-	const SkipKey key[] = { 32, 47, 36, 51, 0, 62, 43, 39 };
+	const SkipKey key[] = { 32, 47, 36, 51, 12, 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 };
@@ -60,6 +78,7 @@ main(void)
 #ifdef SKIP_DOUBLY
 	skip_printbw(list);
 #endif /* SKIP_DOUBLY */
+	skip_prettyprint(list);
 	fputc('\n', stdout);
 
 	for (i = 0; i < LENGTH(delkey); i++) {
@@ -74,6 +93,7 @@ main(void)
 #ifdef SKIP_DOUBLY
 	skip_printbw(list);
 #endif /* SKIP_DOUBLY */
+	skip_prettyprint(list);
 	fputc('\n', stdout);
 
 	for (i = 0; i < LENGTH(searchkey); i++) {
@@ -82,7 +102,7 @@ main(void)
 			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));
+			       searchkey[i], node->val);
 	}
 
 	skip_destroy(list);
diff --git a/examples/range.c b/examples/range.c
index 858052c..36e5217 100644
--- a/examples/range.c
+++ b/examples/range.c
@@ -11,9 +11,9 @@ skip_delrange_slow(SkipList *list, SkipKey from, SkipKey to)
 	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));
+	for (n = 0; node && node->key < to; n++) {
+		next = node->next;
+		skip_delete(list, node->key);
 		node = next;
 	}
 
@@ -25,8 +25,8 @@ 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));
+	for (node = skip_first(list); node; node = node->next)
+		printf("%d[%d]->", node->key, node->val);
 	puts("NULL");
 }
 
@@ -65,13 +65,13 @@ main(void)
 
 	/* 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));
+	printf("node with key ~= 37: %d[%d]\n", node->key, node->val);
 #ifdef SKIP_DOUBLY
-	node = skip_prev(node);
-	printf("prev: %d[%d]\n", skip_key(node), skip_val(node));
+	node = node->prev;
+	printf("prev: %d[%d]\n", node->key, node->val);
 #endif
-	printf("set val %d to node with key %d\n", 42, skip_key(node));
-	skip_setval(node, 42);
+	printf("set val %d to node with key %d\n", 42, node->val);
+	node->val = 42;
 	skip_print(list);
 
 	skip_destroy(list);
diff --git a/skip.c b/skip.c
index 79763b2..1197fd1 100644
--- a/skip.c
+++ b/skip.c
@@ -7,17 +7,17 @@
 #define MAXLVL    32
 #define THRESHOLD RAND_MAX * 0.25
 
-struct SkipNode {
+struct _SkipNode {
 	SkipKey key;
 	SkipVal val;
 #ifdef SKIP_DOUBLY
-	SkipNode *bwd;
+	struct _SkipNode *bwd;
 #endif /* SKIP_DOUBLY */
-	SkipNode *fwd[];
+	struct _SkipNode *fwd[];
 };
 
 struct SkipList {
-	SkipNode *hdr;
+	struct _SkipNode *hdr;
 	size_t siz;
 	int lvl;
 };
@@ -31,8 +31,8 @@ skip_create(void)
 	if (list == NULL)
 		return NULL;
 
-	list->lvl = 1;
 	list->siz = 0;
+	list->lvl = 1;
 	list->hdr = calloc(1, sizeof(SkipNode) + MAXLVL * sizeof(SkipNode *));
 	if (list->hdr == NULL) {
 		free(list);
@@ -45,7 +45,7 @@ skip_create(void)
 void
 skip_destroy(SkipList *list)
 {
-	SkipNode *node, *next;
+	struct _SkipNode *node, *next;
 
 	for (node = list->hdr; node; node = next) {
 		next = node->fwd[0];
@@ -57,7 +57,7 @@ skip_destroy(SkipList *list)
 SkipNode *
 skip_insert(SkipList *list, SkipKey key, SkipVal val)
 {
-	SkipNode *update[MAXLVL], *node = list->hdr;
+	struct _SkipNode *update[MAXLVL], *node = list->hdr;
 	int lvl, i;
 
 	for (i = list->lvl - 1; i >= 0; i--) {
@@ -69,7 +69,7 @@ skip_insert(SkipList *list, SkipKey key, SkipVal val)
 	node = node->fwd[0];
 	if (node && node->key == key) {
 		node->val = val;
-		return node;
+		return (SkipNode *)node;
 	}
 
 	for (lvl = 1; rand() < THRESHOLD; lvl++);
@@ -103,11 +103,11 @@ skip_insert(SkipList *list, SkipKey key, SkipVal val)
 
 	list->siz++;
 
-	return node;
+	return (SkipNode *)node;
 }
 
 static inline void
-skip_delnode(SkipList *list, SkipNode *node, SkipNode **update)
+skip_delnode(SkipList *list, struct _SkipNode *node, struct _SkipNode **update)
 {
 	int i;
 
@@ -133,7 +133,7 @@ skip_delnode(SkipList *list, SkipNode *node, SkipNode **update)
 bool
 skip_delete(SkipList *list, SkipKey key)
 {
-	SkipNode *update[MAXLVL], *node = list->hdr;
+	struct _SkipNode *update[MAXLVL], *node = list->hdr;
 	int i;
 
 	for (i = list->lvl - 1; i >= 0; i--) {
@@ -154,7 +154,7 @@ skip_delete(SkipList *list, SkipKey key)
 size_t
 skip_delrange(SkipList *list, SkipKey from, SkipKey to)
 {
-	SkipNode *update[MAXLVL], *node = list->hdr, *next;
+	struct _SkipNode *update[MAXLVL], *node = list->hdr, *next;
 	size_t n;
 	int i;
 
@@ -177,11 +177,11 @@ skip_delrange(SkipList *list, SkipKey from, SkipKey to)
 SkipNode *
 skip_search(SkipList *list, SkipKey key)
 {
-	SkipNode *node;
+	struct _SkipNode *node;
 
-	node = skip_approx(list, key);
+	node = (struct _SkipNode *)skip_approx(list, key);
 	if (node && node->key == key)
-		return node;
+		return (SkipNode *)node;
 
 	return NULL;
 }
@@ -189,7 +189,7 @@ skip_search(SkipList *list, SkipKey key)
 SkipNode *
 skip_approx(SkipList *list, SkipKey key)
 {
-	SkipNode *node = list->hdr;
+	struct _SkipNode *node = list->hdr;
 	int i;
 
 	for (i = list->lvl - 1; i >= 0; i--) {
@@ -197,7 +197,7 @@ skip_approx(SkipList *list, SkipKey key)
 			node = node->fwd[i];
 	}
 
-	return node->fwd[0];
+	return (SkipNode *)node->fwd[0];
 }
 
 size_t
@@ -209,43 +209,13 @@ skip_size(SkipList *list)
 SkipNode *
 skip_first(SkipList *list)
 {
-	return list->hdr->fwd[0];
-}
-
-SkipNode *
-skip_next(SkipNode *node)
-{
-	return node->fwd[0];
+	return (SkipNode *)list->hdr->fwd[0];
 }
 
 #ifdef SKIP_DOUBLY
 SkipNode *
 skip_last(SkipList *list)
 {
-	return list->hdr->bwd;
-}
-
-SkipNode *
-skip_prev(SkipNode *node)
-{
-	return node->bwd;
+	return (SkipNode *)list->hdr->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
index ae71209..133090e 100644
--- a/skip.h
+++ b/skip.h
@@ -15,6 +15,15 @@ typedef int SkipVal;
 typedef struct SkipNode SkipNode;
 typedef struct SkipList SkipList;
 
+struct SkipNode {
+	const SkipKey key;
+	SkipVal val;
+#ifdef SKIP_DOUBLY
+	SkipNode *const prev;
+#endif /* SKIP_DOUBLY */
+	SkipNode *const next;
+};
+
 SkipList *skip_create(void);
 void skip_destroy(SkipList *list);
 SkipNode *skip_insert(SkipList *list, SkipKey key, SkipVal val);
@@ -24,14 +33,9 @@ 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
 }