Skiplist implementation intended for the IDL compound indexes feature. Signed-off-by: Esteban Rodriguez Betancourt <esteb...@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
diff --git a/lib/automake.mk b/lib/automake.mk index 7b829d0..5e08b44 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -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 \ diff --git a/lib/skiplist.c b/lib/skiplist.c new file mode 100644 index 0000000..fcf24f6 --- /dev/null +++ b/lib/skiplist.c @@ -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); +} diff --git a/lib/skiplist.h b/lib/skiplist.h new file mode 100644 index 0000000..12006f8 --- /dev/null +++ b/lib/skiplist.h @@ -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_ */ diff --git a/tests/.gitignore b/tests/.gitignore index f4540a3..ed017c1 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -38,6 +38,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 aed032b..b4d0150 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -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 \ diff --git a/tests/library.at b/tests/library.at index e1bac92..d0e1053 100644 --- a/tests/library.at +++ b/tests/library.at @@ -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 diff --git a/tests/test-skiplist.c b/tests/test-skiplist.c new file mode 100644 index 0000000..36d9b8c --- /dev/null +++ b/tests/test-skiplist.c @@ -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); -- 1.9.1 _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev