@@ -220,6 +220,8 @@ lib_libopenvswitch_la_SOURCES = \
lib/shash.h \
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,313 @@
+/* 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 */
+ uint64_t 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 max_levels; /* Max levels of the skiplist. */
+ int64_t size; /* Current size of the skiplist. */
+ int64_t level; /* Max number of levels used in this skiplist */
+ void (*free_func) (void *); /* Function that free the value's memory */
+};
+
+static int skiplist_determine_level(struct skiplist *sl);
+
+static struct skiplist_node *skiplist_create_node(int, const void *);
+
+static struct skiplist_node *skiplist_forward_to_(struct skiplist *sl,
+ const void *value,
+ struct skiplist_node
+ **update);
+
+/*
+ * skiplist_create returns a new skiplist, configured with given max_levels,
+ * data comparer and configuration.
+ * Sets a probability of 0.5 (RAND_MAX / 2).
+ */
+struct skiplist *
+skiplist_create(int max_levels, skiplist_comparator object_comparator,
+ void *configuration)
+{
+ random_init();
+ struct skiplist *sl;
+
+ sl = xmalloc(sizeof (struct skiplist));
+ sl->cfg = configuration;
+ sl->max_levels = max_levels < SKIPLIST_MAX_LEVELS ?
+ max_levels : SKIPLIST_MAX_LEVELS;
+ sl->size = 0;
+ sl->level = 0;
+ sl->cmp = object_comparator;
+ sl->header = skiplist_create_node(sl->max_levels, NULL);
+ sl->free_func = NULL;
+
+ return sl;
+}
+
+/*
+ * Set a custom function that free the value's memory when
+ * destroying the skiplist.
+ */
+void
+skiplist_set_free_func(struct skiplist *sl, void (*func) (void *))
+{
+ sl->free_func = func;
+}
+
+/*
+ * Determines the correspondent level for a skiplist node.
+ * Guarantees that the returned integer is less or equal
+ * to the current height of the skiplist plus 1.
+ */
+static int
+skiplist_determine_level(struct skiplist *sl)
+{
+ int lvl = 0;
+ uint32_t random_value = random_uint32();
+
+ while ((random_value & 1) && lvl < sl->max_levels) {
+ random_value >>= 1;
+ lvl++;
+ }
+ return lvl;
+}
+
+/*
+ * Creates a new skiplist_node with given levels and data.
+ */
+static struct skiplist_node *
+skiplist_create_node(int levels, const void *object)
+{
+ struct skiplist_node *new_node = xmalloc(sizeof (struct skiplist_node) +
+ (levels +
+ 1) *
+ sizeof (struct skiplist_node *));
+ new_node->data = object;
+ new_node->height = levels;
+ memset(new_node->forward, 0,
+ (levels + 1) * sizeof (struct skiplist_node *));
+ return new_node;
+}
+
+/*
+ * 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;
+}
+
+/*
+ * Moves the cursor forward, to the first data equal or greater than value.
+ */
+struct skiplist_node *
+skiplist_forward_to(struct skiplist *sl, const void *value)
+{
+ return skiplist_forward_to_(sl, value, NULL);
+}
+
+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;
+}
+
+/*
+ * Inserts data into skiplist.
+ */
+void
+skiplist_insert(struct skiplist *list, const void *value)
+{
+ struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1] = { NULL };
+ int i, lvl;
+ struct skiplist_node *x = skiplist_forward_to_(list, value, update);
+
+ 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 ocurrence of data from skiplist.
+ */
+void *
+skiplist_delete(struct skiplist *list, const void *value)
+{
+ struct skiplist_node *update[SKIPLIST_MAX_LEVELS + 1] = { NULL };
+ void *data = NULL;
+ int i;
+ struct skiplist_node *x = list->header;
+
+ 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
+ */
+int64_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 the skiplist nodes.
+ * If a free function was defined (with skiplist_set_free_func)
+ * this frees the stored data with that function, otherwise the
+ * data is not freed.
+ */
+void
+skiplist_destroy(struct skiplist *sl)
+{
+ struct skiplist_node *node, *next;
+
+ next = node = sl->header;
+ while (next != NULL) {
+ next = node->forward[0];
+ if (sl->free_func) {
+ sl->free_func(CONST_CAST(void *, node->data));
+ }
+ free(node);
+ node = next;
+ }
+ free(sl);
+}
new file mode 100644
@@ -0,0 +1,54 @@
+/* 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 comparison function. Allows to store sorted data.
+ */
+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(int max_levels,
+ skiplist_comparator* object_comparator,
+ void *configuration);
+void skiplist_set_free_func(struct skiplist *sl, void (*func) (void *));
+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);
+int64_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);
+
+#endif /* LIB_SKIPLIST_H_ */
@@ -38,6 +38,7 @@
/test-rstp
/test-sflow
/test-sha1
+/test-skiplist
/test-stp
/test-strtok_r
/test-timeval
@@ -185,6 +185,7 @@ valgrind_wrappers = \
tests/valgrind/test-reconnect \
tests/valgrind/test-rstp \
tests/valgrind/test-sha1 \
+ tests/valgrind/test-skiplist \
tests/valgrind/test-stp \
tests/valgrind/test-type-props \
tests/valgrind/test-unix-socket \
@@ -332,6 +333,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 \
@@ -51,6 +51,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([test type properties])
AT_CHECK([test-type-props])
AT_CLEANUP
new file mode 100644
@@ -0,0 +1,210 @@
+/* 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(14, test_skiplist_cmp, NULL);
+ skiplist_set_free_func(sl, free);
+ int i;
+ int *integer;
+ /* Insert a million rows */
+ for(i = 0; i < 1000000; i++){
+ integer = malloc(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);
+}
+
+static void test_skiplist_delete(void)
+{
+ struct skiplist *sl = skiplist_create(3, 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);
+}
+
+static void test_skiplist_find(void)
+{
+ struct skiplist *sl = skiplist_create(14, test_skiplist_cmp, NULL);
+ skiplist_set_free_func(sl, free);
+
+ int i;
+ int *integer;
+ /* Insert a many rows */
+ for(i = 0; i < 1000000; i++){
+ integer = malloc(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);
+}
+
+static void test_skiplist_forward_to(void)
+{
+ struct skiplist *sl = skiplist_create(3, 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);
+}
+
+static void
+test_skiplist_random(void)
+{
+ int j;
+ for(j=1; j<64; j++) {
+ struct skiplist *sl = skiplist_create(j, test_skiplist_cmp, NULL);
+ int total_numbers = 50;
+ int expected_count = 0;
+ int *numbers = malloc(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);
+ 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);
Skiplist implementation intended for the IDL compound indexes feature. Signed-off-by: Esteban Rodriguez Betancourt <estebarb@hpe.com> --- lib/automake.mk | 2 + lib/skiplist.c | 313 ++++++++++++++++++++++++++++++++++++++++++++++++++ lib/skiplist.h | 54 +++++++++ tests/.gitignore | 1 + tests/automake.mk | 2 + tests/library.at | 11 ++ tests/test-skiplist.c | 210 +++++++++++++++++++++++++++++++++ 7 files changed, 593 insertions(+) create mode 100644 lib/skiplist.c create mode 100644 lib/skiplist.h create mode 100644 tests/test-skiplist.c