lib: skiplist implementation

Skiplist implementation intended for use in the IDL compound indexes
feature.

Signed-off-by: Esteban Rodriguez Betancourt <estebarb@hpe.com>
Co-authored-by: Lance Richardson <lrichard@redhat.com>
Signed-off-by: Lance Richardson <lrichard@redhat.com>
Signed-off-by: Ben Pfaff <blp@ovn.org>

7 files changed, 537 insertions, 0 deletions

diff --git a/lib/automake.mk b/lib/automake.mk
index bd56f434b..2415f4cd6 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -230,6 +230,8 @@ lib_libopenvswitch_la_SOURCES = \
 	lib/shash.c \
 	lib/simap.c \
 	lib/simap.h \
+	lib/skiplist.c \
+	lib/skiplist.h \
 	lib/smap.c \
 	lib/smap.h \
 	lib/socket-util.c \
diff --git a/lib/skiplist.c b/lib/skiplist.c
new file mode 100644
index 000000000..2cea6d8df
--- /dev/null
+++ b/lib/skiplist.c
@@ -0,0 +1,261 @@
+/* Copyright (C) 2016 Hewlett Packard Enterprise Development LP
+ * All Rights Reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may
+ * not use this file except in compliance with the License. You may obtain
+ * a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+/* Skiplist implementation based on:
+ * "Skip List: A Probabilistic Alternative to Balanced Trees",
+ * by William Pugh. */
+
+#include <config.h>
+#include <stdio.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "skiplist.h"
+#include "random.h"
+#include "util.h"
+
+/*
+ * A maximum height level of 32 should be more than sufficient for
+ * anticipated use cases, delivering good expected performance with
+ * up to 2**32 list nodes. Changes to this limit will also require
+ * changes in skiplist_determine_level().
+ */
+#define SKIPLIST_MAX_LEVELS 32
+
+/* Skiplist node container */
+struct skiplist_node {
+    const void *data;                 /* Pointer to saved data. */
+    int height;                       /* Height of this node. */
+    struct skiplist_node *forward[];  /* Links to the next nodes. */
+};
+
+/* Skiplist container */
+struct skiplist {
+    struct skiplist_node *header; /* Pointer to head node (not first
+                                   * data node). */
+    skiplist_comparator *cmp;     /* Pointer to the skiplist's comparison
+                                   * function. */
+    void *cfg;                    /* Pointer to optional comparison
+                                   * configuration, used by the comparator. */
+    int level;                    /* Maximum level currently in use. */
+    uint32_t size;                /* Current number of nodes in skiplist. */
+};
+
+/* Create a new skiplist_node with given level and data. */
+static struct skiplist_node *
+skiplist_create_node(int level, const void *object)
+{
+    struct skiplist_node *new_node;
+    size_t alloc_size = sizeof *new_node +
+                        (level + 1) * sizeof new_node->forward[0];
+
+    new_node = xmalloc(alloc_size);
+    new_node->data = object;
+    new_node->height = level;
+    memset(new_node->forward, 0,
+           (level + 1) * sizeof new_node->forward[0]);
+
+    return new_node;
+}
+
+/*
+ * Create a new skiplist, configured with given data comparison function
+ * and configuration.
+ */
+struct skiplist *
+skiplist_create(skiplist_comparator object_comparator, void *configuration)
+{
+    random_init();
+    struct skiplist *sl;
+
+    sl = xmalloc(sizeof (struct skiplist));
+    sl->cfg = configuration;
+    sl->size = 0;
+    sl->level = 0;
+    sl->cmp = object_comparator;
+    sl->header = skiplist_create_node(SKIPLIST_MAX_LEVELS, NULL);
+
+    return sl;
+}
+
+/*
+ * Move the cursor forward to the first node with associated data greater than
+ * or equal to "value".
+ */
+static struct skiplist_node *
+skiplist_forward_to_(struct skiplist *sl, const void *value,
+                     struct skiplist_node **update)
+{
+    struct skiplist_node *x = sl->header;
+    int i;
+
+    /* Loop invariant: x < value */
+    for (i = sl->level; i >= 0; i--) {
+        while (x->forward[i] &&
+               sl->cmp(x->forward[i]->data, value, sl->cfg) < 0) {
+            x = x->forward[i];
+        }
+        /* x < value <= x->forward[1] */
+        if (update) {
+            update[i] = x;
+        }
+    }
+    /* x < value <= x->forward[1] */
+    x = x->forward[0];
+    return x;
+}
+
+struct skiplist_node *
+skiplist_forward_to(struct skiplist *sl, const void *value)
+{
+    return skiplist_forward_to_(sl, value, NULL);
+}
+
+/* Find the first exact match of value in the skiplist. */
+struct skiplist_node *
+skiplist_find(struct skiplist *sl, const void *value)
+{
+    struct skiplist_node *x = skiplist_forward_to(sl, value);
+
+    return x && sl->cmp(x->data, value, sl->cfg) == 0 ? x : NULL;
+}
+
+/*
+ * Determine the level for a skiplist node by choosing a level N with
+ * probability P(N) = 1/(2**(N+1)) in the range 0..32, with  the returned
+ * level clamped at the current skiplist height plus 1.
+ */
+static int
+skiplist_determine_level(struct skiplist *sl)
+{
+    int lvl;
+
+    lvl = clz32(random_uint32());
+
+    return MIN(lvl, sl->level + 1);
+}
+
+/* Insert data into a skiplist. */
+void
+skiplist_insert(struct skiplist *list, const void *value)
+{
+    struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1];
+    struct skiplist_node *x = skiplist_forward_to_(list, value, update);
+    int i, lvl;
+
+    if (x && list->cmp(x->data, value, list->cfg) == 0) {
+        x->data = value;
+    } else {
+        lvl = skiplist_determine_level(list);
+        if (lvl > list->level) {
+            for (i = list->level + 1; i <= lvl; i++) {
+                update[i] = list->header;
+            }
+            list->level = lvl;
+        }
+        x = skiplist_create_node(lvl, value);
+        for (i = 0; i <= lvl; i++) {
+            x->forward[i] = update[i]->forward[i];
+            update[i]->forward[i] = x;
+        }
+        list->size++;
+    }
+}
+
+/* Remove first node with associated data equal to "value" from skiplist. */
+void *
+skiplist_delete(struct skiplist *list, const void *value)
+{
+    struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1];
+    struct skiplist_node *x;
+    void *data = NULL;
+    int i;
+
+    x = skiplist_forward_to_(list, value, update);
+
+    if (x && list->cmp(x->data, value, list->cfg) == 0) {
+        for (i = 0; i <= list->level; i++) {
+            if (!update[i]->forward[i] ||
+                list->cmp(update[i]->forward[i]->data, value,
+                          list->cfg) != 0) {
+                break;
+            }
+            update[i]->forward[i] = x->forward[i];
+        }
+        data = CONST_CAST(void *, x->data);
+
+        free(x);
+
+        while (list->level > 0 && !list->header->forward[list->level]) {
+            list->level--;
+        }
+        list->size--;
+    }
+    return data;
+}
+
+/* Get the associated data value stored in a skiplist node. */
+void *
+skiplist_get_data(struct skiplist_node *node)
+{
+    return node ? CONST_CAST(void *, node->data) : NULL;
+}
+
+/* Get the number of items in a skiplist. */
+uint32_t
+skiplist_get_size(struct skiplist *sl)
+{
+    return sl->size;
+}
+
+/* Get the first node in a skiplist.  */
+struct skiplist_node *
+skiplist_first(struct skiplist *sl)
+{
+    return sl->header->forward[0];
+}
+
+/* Get a node's successor in a skiplist. */
+struct skiplist_node *
+skiplist_next(struct skiplist_node *node)
+{
+    return node ? node->forward[0] : NULL;
+}
+
+/*
+ * Destroy a skiplist and free all nodes in the list.  If the "data_destroy"
+ * function pointer is non-NULL, it will be called for each node as it is
+ * removed to allow any needed cleanups to be performed on the associated
+ * data.
+ */
+void
+skiplist_destroy(struct skiplist *sl, void (*data_destroy)(void *))
+{
+    struct skiplist_node *node, *next;
+
+    next = node = sl->header;
+    while (next != NULL) {
+        next = node->forward[0];
+        if (data_destroy) {
+            data_destroy(CONST_CAST(void *, node->data));
+        }
+        free(node);
+        node = next;
+    }
+    free(sl);
+}
diff --git a/lib/skiplist.h b/lib/skiplist.h
new file mode 100644
index 000000000..80aeecba0
--- /dev/null
+++ b/lib/skiplist.h
@@ -0,0 +1,49 @@
+/* Copyright (C) 2016 Hewlett Packard Enterprise Development LP
+ * All Rights Reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may
+ * not use this file except in compliance with the License. You may obtain
+ * a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+#ifndef LIB_SKIPLIST_H_
+#define LIB_SKIPLIST_H_
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+typedef int (skiplist_comparator)(const void *a, const void *b,
+                                  const void *conf);
+
+struct skiplist_node;
+
+struct skiplist;
+
+#define SKIPLIST_FOR_EACH (SKIPLIST_NODE, SKIPLIST) \
+    for (SKIPLIST_NODE = skiplist_first(SKIPLIST); \
+         SKIPLIST_NODE; \
+         SKIPLIST_NODE = skiplist_next(SKIPLIST_NODE))
+
+struct skiplist *skiplist_create(skiplist_comparator *object_comparator,
+                                 void *configuration);
+void skiplist_insert(struct skiplist *sl, const void *object);
+void *skiplist_delete(struct skiplist *sl, const void *object);
+struct skiplist_node *skiplist_find(struct skiplist *sl, const void *value);
+void *skiplist_get_data(struct skiplist_node *node);
+uint32_t skiplist_get_size(struct skiplist *sl);
+struct skiplist_node *skiplist_forward_to(struct skiplist *sl,
+                                          const void *value);
+struct skiplist_node *skiplist_first(struct skiplist *sl);
+struct skiplist_node *skiplist_next(struct skiplist_node *node);
+void skiplist_destroy(struct skiplist *sl, void (*func)(void *));
+
+#endif /* LIB_SKIPLIST_H_ */
diff --git a/tests/.gitignore b/tests/.gitignore
index 7b91dff3d..294e6fb6d 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -39,6 +39,7 @@
 /test-rstp
 /test-sflow
 /test-sha1
+/test-skiplist
 /test-stp
 /test-strtok_r
 /test-timeval
diff --git a/tests/automake.mk b/tests/automake.mk
index 53c468614..3399c781d 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -187,6 +187,7 @@ valgrind_wrappers = \
 	tests/valgrind/ovsdb-tool \
 	tests/valgrind/ovstest \
 	tests/valgrind/test-ovsdb \
+	tests/valgrind/test-skiplist \
 	tests/valgrind/test-strtok_r \
 	tests/valgrind/test-type-props
 
@@ -347,6 +348,7 @@ tests_ovstest_SOURCES = \
 	tests/test-rstp.c \
 	tests/test-sflow.c \
 	tests/test-sha1.c \
+	tests/test-skiplist.c \
 	tests/test-stp.c \
 	tests/test-unixctl.c \
 	tests/test-util.c \
diff --git a/tests/library.at b/tests/library.at
index e3d32bece..6073abfbd 100644
--- a/tests/library.at
+++ b/tests/library.at
@@ -57,6 +57,17 @@ AT_CHECK([ovstest test-sha1], [0], [.........
 ])
 AT_CLEANUP
 
+AT_SETUP([test skiplist])
+AT_KEYWORDS([skiplist])
+AT_CHECK([ovstest test-skiplist], [0], [skiplist insert
+skiplist delete
+skiplist find
+skiplist forward_to
+skiplist random
+
+])
+AT_CLEANUP
+
 AT_SETUP([type properties])
 AT_CHECK([test-type-props])
 AT_CLEANUP
diff --git a/tests/test-skiplist.c b/tests/test-skiplist.c
new file mode 100644
index 000000000..943d447fa
--- /dev/null
+++ b/tests/test-skiplist.c
@@ -0,0 +1,211 @@
+/* Copyright (C) 2016 Hewlett Packard Enterprise Development LP
+ * All Rights Reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may
+ * not use this file except in compliance with the License. You may obtain
+ * a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+/* A non-exhaustive test for some of the functions and macros declared in
+ * skiplist.h. */
+
+#include <config.h>
+#undef NDEBUG
+#include <stdio.h>
+#include <string.h>
+#include "ovstest.h"
+#include "skiplist.h"
+#include "random.h"
+#include "util.h"
+
+static void
+test_skiplist_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED);
+
+static int test_skiplist_cmp(const void *a, const void *b, const void *conf);
+
+static void test_skiplist_insert(void);
+static void test_skiplist_delete(void);
+static void test_skiplist_find(void);
+static void test_skiplist_forward_to(void);
+static void test_skiplist_random(void);
+
+static int
+test_skiplist_cmp(const void *a, const void *b,
+                  const void *conf OVS_UNUSED)
+{
+    const int *n = (const int *)a;
+    const int *m = (const int *)b;
+    return (*n > *m) - (*n < *m);
+}
+
+static void
+test_skiplist_insert(void)
+{
+    struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL);
+    int i;
+    int *integer;
+
+    /* Insert a million rows */
+    for (i = 0; i < 1000000; i++) {
+        integer = xmalloc(sizeof(int));
+        *integer = i;
+        skiplist_insert(sl, integer);
+    }
+
+    /* Check that the skiplist maintains the list sorted */
+    struct skiplist_node *node = skiplist_first(sl);
+
+    for (i = 0; i < 1000000; i++) {
+        integer = (int *)skiplist_get_data(node);
+        ovs_assert(i == *integer);
+        node = skiplist_next(node);
+    }
+
+    skiplist_destroy(sl, free);
+}
+
+static void
+test_skiplist_delete(void)
+{
+    struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL);
+    int a, b, c;
+    a = 1;
+    b = 2;
+    c = 3;
+    /* Insert rows */
+    skiplist_insert(sl, &a);
+    skiplist_insert(sl, &c);
+    skiplist_insert(sl, &b);
+
+    /* Check that the items exists */
+    ovs_assert(a == *(int *)skiplist_get_data(skiplist_find(sl, &a)));
+    ovs_assert(b == *(int *)skiplist_get_data(skiplist_find(sl, &b)));
+    ovs_assert(c == *(int *)skiplist_get_data(skiplist_find(sl, &c)));
+
+    /* Delete b*/
+    skiplist_delete(sl, &b);
+
+    /* Check that the items doesn't exists */
+    ovs_assert(a == *(int *)skiplist_get_data(skiplist_find(sl, &a)));
+    ovs_assert(NULL == skiplist_get_data(skiplist_find(sl, &b)));
+    ovs_assert(c == *(int *)skiplist_get_data(skiplist_find(sl, &c)));
+
+    skiplist_destroy(sl, NULL);
+}
+
+static void
+test_skiplist_find(void)
+{
+    struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL);
+
+    int i;
+    int *integer;
+    /* Insert a many rows */
+    for (i = 0; i < 1000000; i++) {
+        integer = xmalloc(sizeof(int));
+        *integer = i;
+        skiplist_insert(sl, integer);
+    }
+
+    /* Seek all the items */
+    for (i = 0; i < 1000000; i++) {
+        integer = (int *)skiplist_get_data(skiplist_find(sl, &i));
+        ovs_assert(i == *integer);
+    }
+
+    skiplist_destroy(sl, free);
+}
+
+static void
+test_skiplist_forward_to(void)
+{
+    struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL);
+    int a, b, c, d, x;
+    a = 1;
+    b = 3;
+    c = 7;
+    d = 10;
+    /* Insert rows */
+    skiplist_insert(sl, &a);
+    skiplist_insert(sl, &c);
+    skiplist_insert(sl, &b);
+    skiplist_insert(sl, &d);
+
+    /* Check that forward_to returns the expected value */
+    x = a;
+    ovs_assert(a == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    x = 2;
+    ovs_assert(b == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    x = 5;
+    ovs_assert(c == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    x = 8;
+    ovs_assert(d == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    x = 15;
+    ovs_assert(NULL == (int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    /* Destroy skiplist */
+    skiplist_destroy(sl, NULL);
+}
+
+static void
+test_skiplist_random(void)
+{
+    struct skiplist *sl = skiplist_create(test_skiplist_cmp, NULL);
+    int total_numbers = 50;
+    int expected_count = 0;
+    int *numbers = xmalloc(sizeof(int) * total_numbers);
+    int i, op, element;
+    for (i = 0; i < total_numbers; i++) {
+        numbers[i] = i;
+    }
+    random_init();
+    for (i = 0; i < total_numbers * 1000; i++) {
+        op = random_uint32() % 2;
+        element = random_range(total_numbers);
+        if (op == 0) {
+            if (!skiplist_find(sl, &numbers[element])) {
+                expected_count++;
+            }
+            skiplist_insert(sl, &numbers[element]);
+        } else {
+            if (skiplist_find(sl, &numbers[element])) {
+                expected_count--;
+            }
+            skiplist_delete(sl, &numbers[element]);
+        }
+        ovs_assert(expected_count == skiplist_get_size(sl));
+    }
+
+    skiplist_destroy(sl, NULL);
+    free(numbers);
+}
+
+static void
+test_skiplist_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
+{
+    printf("skiplist insert\n");
+    test_skiplist_insert();
+    printf("skiplist delete\n");
+    test_skiplist_delete();
+    printf("skiplist find\n");
+    test_skiplist_find();
+    printf("skiplist forward_to\n");
+    test_skiplist_forward_to();
+    printf("skiplist random\n");
+    test_skiplist_random();
+    printf("\n");
+}
+
+OVSTEST_REGISTER("test-skiplist", test_skiplist_main);