@@ -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 \
new file mode 100644
@@ -0,0 +1,286 @@
+/* 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 implementationn 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"
+
+/*
+ * The primary usage of the skiplists are the compound indexes
+ * at the IDL.
+ * For that use case 32 height levels is more than enough as
+ * it could indexes a table with 4.294.967.296 rows.
+ * In case that a new use case require more than that then this
+ * number can be changed, but also the way in which the random
+ * numbers are generated must be changed.
+ */
+#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. */
+};
+
+/*
+ * Creates 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;
+}
+
+/*
+ * skiplist_create returns 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;
+}
+
+/*
+ * Moves the cursor forward, to the first data equal or greater than 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;
+}
+
+/*
+ * Determines the level for a skiplist node. Computes 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);
+}
+
+/*
+ * Inserts data into 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++;
+ }
+}
+
+/*
+ * Removes first occurrence of data 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;
+}
+
+/*
+ * Returns the value stored in the skiplist node
+ */
+void *
+skiplist_get_data(struct skiplist_node *node)
+{
+ return node ? CONST_CAST(void *, node->data) : NULL;
+}
+
+/*
+ * Returns the count of items in the skiplist
+ */
+uint32_t
+skiplist_get_size(struct skiplist *sl)
+{
+ return sl->size;
+}
+
+/*
+ * Returns the first element in the skiplist
+ */
+struct skiplist_node *
+skiplist_first(struct skiplist *sl)
+{
+ return sl->header->forward[0];
+}
+
+/*
+ * Given a skiplist node, returns a pointer to the next skiplist node.
+ */
+struct skiplist_node *
+skiplist_next(struct skiplist_node *node)
+{
+ return node ? node->forward[0] : NULL;
+}
+
+/*
+ * Destroys the skiplist, and frees all skiplist nodes.
+ * If the "data_destroy" function pointer is non-NULL, it will be called
+ * for each node as it is deleted to allow any needed cleanups to be
+ * performed on the associated node 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);
+}
new file mode 100644
@@ -0,0 +1,51 @@
+/* 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>
+
+/*
+ * Skiplist key comparison function.
+ */
+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_ */
@@ -39,6 +39,7 @@
/test-rstp
/test-sflow
/test-sha1
+/test-skiplist
/test-stp
/test-strtok_r
/test-timeval
@@ -183,6 +183,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
@@ -343,6 +344,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 \
@@ -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
new file mode 100644
@@ -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);