[ovs-dev] [PATCH v6 2/4] lib: skiplist implementation

Lance Richardson lrichard at redhat.com
Sat Jul 1 18:26:02 UTC 2017


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

Signed-off-by: Esteban Rodriguez Betancourt <estebarb at hpe.com>
Co-authored-by: Lance Richardson <lrichard at redhat.com>
Signed-off-by: Lance Richardson <lrichard at redhat.com>
---
 v6: - Coding style edits.
 v5: - Changed skiplist_node and skiplist structs to use smaller integer
       types than 64-bit as appropriate.
     - Removed free_func member from struct skiplist, as suggested in v4
       review.
     - Fixed max_levels at 32 as suggested in v4 review.
     - Changed skiplist_determine_levels() to use clz32(random_uint32()) for
       node height distribution. Also changed function to ensure that the
       maximum node height is increased by no more than one level, this
       is suggested in the original Pugh paper and seems to have been intended
       here according to comments.
     - Verified node distribution as expected (1M node list has about 500K
       level 0 nodes, 250K level 1 nodes, 125K level 2 nodes, etc.)
     - Coding style fixes (with checkpatch.py assistance).

 lib/automake.mk       |   2 +
 lib/skiplist.c        | 261 ++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/skiplist.h        |  48 ++++++++++
 tests/.gitignore      |   1 +
 tests/automake.mk     |   2 +
 tests/library.at      |  11 +++
 tests/test-skiplist.c | 212 ++++++++++++++++++++++++++++++++++++++++
 7 files changed, 537 insertions(+)
 create mode 100644 lib/skiplist.c
 create mode 100644 lib/skiplist.h
 create mode 100644 tests/test-skiplist.c

diff --git a/lib/automake.mk b/lib/automake.mk
index 54a1032..ec03a0c 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -229,6 +229,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 0000000..89be9b1
--- /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
+ * probabilty 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] = { NULL };
+    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] = { NULL };
+    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 0000000..e3c7fe0
--- /dev/null
+++ b/lib/skiplist.h
@@ -0,0 +1,48 @@
+/* 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 7b91dff..294e6fb 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 3118bbc..e929f3f 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -185,6 +185,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
 
@@ -345,6 +346,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 e3d32be..6073abf 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 0000000..ff51a37
--- /dev/null
+++ b/tests/test-skiplist.c
@@ -0,0 +1,212 @@
+/* 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 <assert.h>
+#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);
+        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 */
+    assert(a == *(int *)skiplist_get_data(skiplist_find(sl, &a)));
+    assert(b == *(int *)skiplist_get_data(skiplist_find(sl, &b)));
+    assert(c == *(int *)skiplist_get_data(skiplist_find(sl, &c)));
+
+    /* Delete b*/
+    skiplist_delete(sl, &b);
+
+    /* Check that the items doesn't exists */
+    assert(a == *(int *)skiplist_get_data(skiplist_find(sl, &a)));
+    assert(NULL == skiplist_get_data(skiplist_find(sl, &b)));
+    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));
+        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;
+    assert(a == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    x = 2;
+    assert(b == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    x = 5;
+    assert(c == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    x = 8;
+    assert(d == *(int *)skiplist_get_data(skiplist_forward_to(sl, &x)));
+
+    x = 15;
+    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);
-- 
2.9.4



More information about the dev mailing list