Compare commits
No commits in common. "gburd/splay-list" and "main" have entirely different histories.
gburd/spla
...
main
5 changed files with 1369 additions and 1878 deletions
3
.gitignore
vendored
3
.gitignore
vendored
|
@ -5,9 +5,6 @@ tests/test
|
||||||
examples/mls.c
|
examples/mls.c
|
||||||
examples/mls
|
examples/mls
|
||||||
examples/mls.o
|
examples/mls.o
|
||||||
examples/ex2_sl.c
|
|
||||||
examples/ex2_sl
|
|
||||||
examples/ex2_sl.o
|
|
||||||
/mxe
|
/mxe
|
||||||
.cache
|
.cache
|
||||||
hints.txt
|
hints.txt
|
||||||
|
|
8
Makefile
8
Makefile
|
@ -14,7 +14,7 @@ TEST_FLAGS = -Itests/
|
||||||
|
|
||||||
TESTS = tests/test
|
TESTS = tests/test
|
||||||
TEST_OBJS = tests/test.o tests/munit.o
|
TEST_OBJS = tests/test.o tests/munit.o
|
||||||
EXAMPLES = examples/ex1 examples/ex2
|
EXAMPLES = examples/ex1.c
|
||||||
|
|
||||||
.PHONY: all shared static clean test examples mls
|
.PHONY: all shared static clean test examples mls
|
||||||
|
|
||||||
|
@ -64,15 +64,9 @@ examples/%.o: examples/%.c
|
||||||
examples/mls.c: examples/ex1.c
|
examples/mls.c: examples/ex1.c
|
||||||
$(CC) $(CFLAGS) -C -E examples/ex1.c | sed -e '1,7d' -e '/^# [0-9]* "/d' | clang-format > examples/mls.c
|
$(CC) $(CFLAGS) -C -E examples/ex1.c | sed -e '1,7d' -e '/^# [0-9]* "/d' | clang-format > examples/mls.c
|
||||||
|
|
||||||
examples/ex2_sl.c: examples/ex2.c
|
|
||||||
$(CC) $(CFLAGS) -C -E examples/ex2.c | sed -e '1,7d' -e '/^# [0-9]* "/d' | clang-format > examples/ex2_sl.c
|
|
||||||
|
|
||||||
examples/mls: examples/mls.o $(STATIC_LIB)
|
examples/mls: examples/mls.o $(STATIC_LIB)
|
||||||
$(CC) $^ -o $@ $(CFLAGS) $(TEST_FLAGS) -lm -pthread
|
$(CC) $^ -o $@ $(CFLAGS) $(TEST_FLAGS) -lm -pthread
|
||||||
|
|
||||||
examples/ex2_sl: examples/ex2_sl.o $(STATIC_LIB)
|
|
||||||
$(CC) $^ -o $@ $(CFLAGS) $(TEST_FLAGS) -lm -pthread
|
|
||||||
|
|
||||||
#dot:
|
#dot:
|
||||||
# ./examples/mls
|
# ./examples/mls
|
||||||
# dot -Tpdf /tmp/ex1.dot -o /tmp/ex1.pdf >/dev/null 2>&1
|
# dot -Tpdf /tmp/ex1.dot -o /tmp/ex1.pdf >/dev/null 2>&1
|
||||||
|
|
315
examples/ex1.c
315
examples/ex1.c
|
@ -5,6 +5,12 @@
|
||||||
// ---------------------------------------------------------------------------
|
// ---------------------------------------------------------------------------
|
||||||
#define DEBUG
|
#define DEBUG
|
||||||
#define SKIPLIST_DIAGNOSTIC
|
#define SKIPLIST_DIAGNOSTIC
|
||||||
|
/* Setting SKIPLIST_MAX_HEIGHT will do two things:
|
||||||
|
* 1) limit our max height across all instances of this data structure.
|
||||||
|
* 2) remove a heap allocation on frequently used paths, insert/remove/etc.
|
||||||
|
* so, use it when you need it.
|
||||||
|
*/
|
||||||
|
#define SKIPLIST_MAX_HEIGHT 12
|
||||||
|
|
||||||
// Include our monolithic ADT, the Skiplist!
|
// Include our monolithic ADT, the Skiplist!
|
||||||
// ---------------------------------------------------------------------------
|
// ---------------------------------------------------------------------------
|
||||||
|
@ -14,8 +20,8 @@
|
||||||
// ---------------------------------------------------------------------------
|
// ---------------------------------------------------------------------------
|
||||||
#define TEST_ARRAY_SIZE 10
|
#define TEST_ARRAY_SIZE 10
|
||||||
#define VALIDATE
|
#define VALIDATE
|
||||||
// define SNAPSHOTS
|
//define SNAPSHOTS
|
||||||
// define TODO_RESTORE_SNAPSHOTS
|
//define TODO_RESTORE_SNAPSHOTS
|
||||||
#define STABLE_SEED
|
#define STABLE_SEED
|
||||||
#define DOT
|
#define DOT
|
||||||
|
|
||||||
|
@ -68,10 +74,7 @@ SKIPLIST_DECL(
|
||||||
return 0;
|
return 0;
|
||||||
},
|
},
|
||||||
/* free entry: node */
|
/* free entry: node */
|
||||||
{
|
{ free(node->value); },
|
||||||
free(node->value);
|
|
||||||
node->value = NULL;
|
|
||||||
},
|
|
||||||
/* update entry: rc, node, value */
|
/* update entry: rc, node, value */
|
||||||
{
|
{
|
||||||
char *numeral = (char *)value;
|
char *numeral = (char *)value;
|
||||||
|
@ -175,7 +178,7 @@ SKIPLIST_DECL_VALIDATE(ex, api_, entries)
|
||||||
*/
|
*/
|
||||||
SKIPLIST_DECL_DOT(ex, api_, entries)
|
SKIPLIST_DECL_DOT(ex, api_, entries)
|
||||||
|
|
||||||
static void
|
void
|
||||||
sprintf_ex_node(ex_node_t *node, char *buf)
|
sprintf_ex_node(ex_node_t *node, char *buf)
|
||||||
{
|
{
|
||||||
sprintf(buf, "%d:%s", node->key, node->value);
|
sprintf(buf, "%d:%s", node->key, node->value);
|
||||||
|
@ -183,8 +186,51 @@ sprintf_ex_node(ex_node_t *node, char *buf)
|
||||||
|
|
||||||
// Function for this demo application.
|
// Function for this demo application.
|
||||||
// ---------------------------------------------------------------------------
|
// ---------------------------------------------------------------------------
|
||||||
|
int __xorshift32_state = 0;
|
||||||
|
|
||||||
|
// Xorshift algorithm for PRNG
|
||||||
|
uint32_t
|
||||||
|
xorshift32()
|
||||||
|
{
|
||||||
|
uint32_t x = __xorshift32_state;
|
||||||
|
if (x == 0)
|
||||||
|
x = 123456789;
|
||||||
|
x ^= x << 13;
|
||||||
|
x ^= x >> 17;
|
||||||
|
x ^= x << 5;
|
||||||
|
__xorshift32_state = x;
|
||||||
|
return x;
|
||||||
|
}
|
||||||
|
|
||||||
|
void
|
||||||
|
xorshift32_seed()
|
||||||
|
{
|
||||||
|
// Seed the PRNG
|
||||||
|
#ifdef STABLE_SEED
|
||||||
|
__xorshift32_state = 8675309;
|
||||||
|
#else
|
||||||
|
__xorshift32_state = (unsigned int)time(NULL) ^ getpid();
|
||||||
|
#endif
|
||||||
|
}
|
||||||
|
|
||||||
|
static char *
|
||||||
|
to_lower(char *str)
|
||||||
|
{
|
||||||
|
char *p = str;
|
||||||
|
for (; *p; ++p)
|
||||||
|
*p = (char)(*p >= 'A' && *p <= 'Z' ? *p | 0x60 : *p);
|
||||||
|
return str;
|
||||||
|
}
|
||||||
|
|
||||||
|
static char *
|
||||||
|
to_upper(char *str)
|
||||||
|
{
|
||||||
|
char *p = str;
|
||||||
|
for (; *p; ++p)
|
||||||
|
*p = (char)(*p >= 'a' && *p <= 'z' ? *p & ~0x20 : *p);
|
||||||
|
return str;
|
||||||
|
}
|
||||||
|
|
||||||
/* convert a number into the Roman numeral equivalent, allocates a string caller must free */
|
|
||||||
static char *
|
static char *
|
||||||
int_to_roman_numeral(int num)
|
int_to_roman_numeral(int num)
|
||||||
{
|
{
|
||||||
|
@ -217,11 +263,18 @@ int_to_roman_numeral(int num)
|
||||||
return res;
|
return res;
|
||||||
}
|
}
|
||||||
|
|
||||||
/* calculate the floor of the log base 2 of a number m (⌊log2(m)⌋) */
|
void
|
||||||
static int
|
shuffle(int *array, size_t n)
|
||||||
floor_log2(unsigned int m)
|
|
||||||
{
|
{
|
||||||
return (int)floor(log(m) / log(2));
|
if (n > 1) {
|
||||||
|
size_t i;
|
||||||
|
for (i = n - 1; i > 0; i--) {
|
||||||
|
size_t j = (unsigned int)(xorshift32() % (i + 1)); /* NOLINT(*-msc50-cpp) */
|
||||||
|
int t = array[j];
|
||||||
|
array[j] = array[i];
|
||||||
|
array[i] = t;
|
||||||
|
}
|
||||||
|
}
|
||||||
}
|
}
|
||||||
|
|
||||||
#ifdef TODO_RESTORE_SNAPSHOTS
|
#ifdef TODO_RESTORE_SNAPSHOTS
|
||||||
|
@ -233,25 +286,17 @@ typedef struct {
|
||||||
#endif
|
#endif
|
||||||
|
|
||||||
// ---------------------------------------------------------------------------
|
// ---------------------------------------------------------------------------
|
||||||
|
|
||||||
/* The head node's height is always 1 more than the tallest node, that location
|
|
||||||
is where we store the total hits, or "m". */
|
|
||||||
#define splay_list_m(m) list->slh_head->entries.sle_levels[list->slh_head->entries.sle_height].hits
|
|
||||||
|
|
||||||
int
|
int
|
||||||
main()
|
main()
|
||||||
{
|
{
|
||||||
int rc;
|
int rc;
|
||||||
char *numeral;
|
|
||||||
#ifdef DOT
|
|
||||||
char msg[1024];
|
|
||||||
memset(msg, 0, 1024);
|
|
||||||
#endif
|
|
||||||
#ifdef TODO_RESTORE_SNAPSHOTS
|
#ifdef TODO_RESTORE_SNAPSHOTS
|
||||||
size_t n_snaps = 0;
|
size_t n_snaps = 0;
|
||||||
snap_info_t snaps[TEST_ARRAY_SIZE * 2 + 1];
|
snap_info_t snaps[TEST_ARRAY_SIZE * 2 + 1];
|
||||||
#endif
|
#endif
|
||||||
|
|
||||||
|
xorshift32_seed();
|
||||||
|
|
||||||
#ifdef DOT
|
#ifdef DOT
|
||||||
of = fopen("/tmp/ex1.dot", "w");
|
of = fopen("/tmp/ex1.dot", "w");
|
||||||
if (!of) {
|
if (!of) {
|
||||||
|
@ -265,117 +310,167 @@ main()
|
||||||
if (list == NULL)
|
if (list == NULL)
|
||||||
return ENOMEM;
|
return ENOMEM;
|
||||||
|
|
||||||
rc = api_skip_init_ex(list);
|
/* We set the max height here to 12, it's negative so that
|
||||||
|
the PRNG is seeded with this value as a testing trick for
|
||||||
|
predictable random sequences. */
|
||||||
|
rc = api_skip_init_ex(list, -12);
|
||||||
if (rc)
|
if (rc)
|
||||||
return rc;
|
return rc;
|
||||||
|
|
||||||
/* Set the PRNG state to a known constant for reproducible generation, easing debugging. */
|
|
||||||
list->slh_prng_state = 12;
|
|
||||||
#ifdef SNAPSHOTS
|
|
||||||
api_skip_snapshots_init_ex(list);
|
api_skip_snapshots_init_ex(list);
|
||||||
#endif
|
|
||||||
#ifdef DOT
|
#ifdef DOT
|
||||||
api_skip_dot_ex(of, list, gen++, "init", sprintf_ex_node);
|
api_skip_dot_ex(of, list, gen++, "init", sprintf_ex_node);
|
||||||
#endif
|
#endif
|
||||||
|
if (api_skip_get_ex(list, 0) != NULL)
|
||||||
|
perror("found a non-existent item!");
|
||||||
|
api_skip_del_ex(list, 0);
|
||||||
|
CHECK;
|
||||||
|
|
||||||
/* This example mirrors the example given in the paper about splay-lists
|
/* Insert TEST_ARRAY_SIZE key/value pairs into the list. */
|
||||||
to test implementation against research. */
|
int i, j;
|
||||||
|
char *numeral;
|
||||||
|
#ifdef DOT
|
||||||
|
char msg[1024];
|
||||||
|
memset(msg, 0, 1024);
|
||||||
|
#endif
|
||||||
|
int amt = TEST_ARRAY_SIZE, asz = (amt * 2) + 1;
|
||||||
|
int array[(TEST_ARRAY_SIZE * 2) + 1];
|
||||||
|
for (j = 0, i = -amt; i <= amt; i++, j++)
|
||||||
|
array[j] = i;
|
||||||
|
shuffle(array, asz);
|
||||||
|
|
||||||
for (int i = 1; i < 8; i++) {
|
for (i = 0; i < asz; i++) {
|
||||||
numeral = int_to_roman_numeral(i);
|
#ifdef SNAPSHOTS
|
||||||
if ((rc = api_skip_put_ex(list, i, numeral)))
|
api_skip_snapshot_ex(list);
|
||||||
perror("put failed");
|
#elif defined(TODO_RESTORE_SNAPSHOTS)
|
||||||
|
/* Snapshot the first iteration, and then every 5th after that. */
|
||||||
|
if (i % 5 == 0) {
|
||||||
|
snaps[i].length = api_skip_length_ex(list);
|
||||||
|
snaps[i].key = array[i];
|
||||||
|
snaps[i].snap_id = api_skip_snapshot_ex(list);
|
||||||
|
n_snaps++;
|
||||||
|
CHECK;
|
||||||
|
}
|
||||||
|
#endif
|
||||||
|
numeral = to_lower(int_to_roman_numeral(array[i]));
|
||||||
|
rc = api_skip_put_ex(list, array[i], numeral);
|
||||||
|
CHECK;
|
||||||
#ifdef DOT
|
#ifdef DOT
|
||||||
sprintf(msg, "put key: %d value: %s", i, numeral);
|
sprintf(msg, "put key: %d value: %s", i, numeral);
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
||||||
#endif
|
#endif
|
||||||
|
char *v = api_skip_get_ex(list, array[i]);
|
||||||
|
CHECK;
|
||||||
|
char *upper_numeral = calloc(1, strlen(v) + 1);
|
||||||
|
strncpy(upper_numeral, v, strlen(v));
|
||||||
|
assert(strncmp(v, upper_numeral, strlen(upper_numeral)) == 0);
|
||||||
|
to_upper(upper_numeral);
|
||||||
|
api_skip_set_ex(list, array[i], upper_numeral);
|
||||||
|
CHECK;
|
||||||
}
|
}
|
||||||
|
numeral = int_to_roman_numeral(-1);
|
||||||
|
api_skip_dup_ex(list, -1, numeral);
|
||||||
CHECK;
|
CHECK;
|
||||||
|
|
||||||
/* Now we're going to poke around the internals a bit to set things up.
|
|
||||||
This first time around we're going to build the list by hand, later
|
|
||||||
we'll ensure that we can build this shape using only API calls. */
|
|
||||||
|
|
||||||
ex_node_t *head = list->slh_head;
|
|
||||||
ex_node_t *tail = list->slh_tail;
|
|
||||||
ex_node_t *node_1 = head->entries.sle_levels[0].next;
|
|
||||||
ex_node_t *node_2 = node_1->entries.sle_levels[0].next;
|
|
||||||
ex_node_t *node_3 = node_2->entries.sle_levels[0].next;
|
|
||||||
ex_node_t *node_4 = node_3->entries.sle_levels[0].next;
|
|
||||||
ex_node_t *node_5 = node_4->entries.sle_levels[0].next;
|
|
||||||
ex_node_t *node_6 = node_5->entries.sle_levels[0].next;
|
|
||||||
|
|
||||||
// Head/Tail-nodes are height 3, ...
|
|
||||||
head->entries.sle_height = tail->entries.sle_height = 3;
|
|
||||||
|
|
||||||
// Head-node
|
|
||||||
head->entries.sle_levels[3].hits = 10;
|
|
||||||
head->entries.sle_levels[2].hits = 5;
|
|
||||||
head->entries.sle_levels[1].hits = 1;
|
|
||||||
head->entries.sle_levels[0].hits = 1;
|
|
||||||
head->entries.sle_levels[1].next = node_2;
|
|
||||||
head->entries.sle_levels[2].next = node_6;
|
|
||||||
head->entries.sle_levels[3].next = tail;
|
|
||||||
|
|
||||||
// Tail-node
|
|
||||||
tail->entries.sle_levels[3].hits = 0;
|
|
||||||
tail->entries.sle_levels[2].hits = 0;
|
|
||||||
tail->entries.sle_levels[1].hits = 0;
|
|
||||||
tail->entries.sle_levels[0].hits = 1;
|
|
||||||
tail->entries.sle_levels[1].next = tail;
|
|
||||||
tail->entries.sle_levels[2].next = tail;
|
|
||||||
tail->entries.sle_levels[3].next = tail;
|
|
||||||
|
|
||||||
// First node has key "1", height "0", hits(0) = 1
|
|
||||||
node_1->entries.sle_height = 0;
|
|
||||||
node_1->entries.sle_levels[0].hits = 1;
|
|
||||||
|
|
||||||
// Second node has key "2", height "1", hits(0) = 1, hits(1) = 0
|
|
||||||
node_2->entries.sle_height = 1;
|
|
||||||
node_2->entries.sle_levels[0].hits = 1;
|
|
||||||
node_2->entries.sle_levels[1].hits = 0;
|
|
||||||
node_2->entries.sle_levels[1].next = node_3;
|
|
||||||
|
|
||||||
// Third node has key "3", height "1", hits(0) = 1, hits(1) = 2
|
|
||||||
node_3->entries.sle_height = 1;
|
|
||||||
node_3->entries.sle_levels[0].hits = 1;
|
|
||||||
node_3->entries.sle_levels[1].hits = 2;
|
|
||||||
node_3->entries.sle_levels[1].next = node_6;
|
|
||||||
|
|
||||||
// Fourth node has key "4", height "0", hits(0) = 1
|
|
||||||
node_4->entries.sle_height = 0;
|
|
||||||
node_4->entries.sle_levels[0].hits = 1;
|
|
||||||
|
|
||||||
// Fifth node has key "5", height "0", hits(0) = 1
|
|
||||||
node_5->entries.sle_height = 0;
|
|
||||||
node_5->entries.sle_levels[0].hits = 1;
|
|
||||||
|
|
||||||
// Sixth node has key "6", height "2", hits(0) = 5, hits(1) = 0, hits(2) = 0
|
|
||||||
node_6->entries.sle_height = 2;
|
|
||||||
node_6->entries.sle_levels[0].hits = 5;
|
|
||||||
node_6->entries.sle_levels[1].hits = 0;
|
|
||||||
node_6->entries.sle_levels[2].hits = 0;
|
|
||||||
node_6->entries.sle_levels[1].next = tail;
|
|
||||||
node_6->entries.sle_levels[2].next = tail;
|
|
||||||
|
|
||||||
CHECK;
|
|
||||||
|
|
||||||
#ifdef DOT
|
#ifdef DOT
|
||||||
sprintf(msg, "manually adjusted");
|
sprintf(msg, "put dup key: %d value: %s", i, numeral);
|
||||||
|
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
||||||
|
#endif
|
||||||
|
numeral = int_to_roman_numeral(1);
|
||||||
|
api_skip_dup_ex(list, 1, numeral);
|
||||||
|
CHECK;
|
||||||
|
#ifdef DOT
|
||||||
|
sprintf(msg, "put dup key: %d value: %s", i, numeral);
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
||||||
#endif
|
#endif
|
||||||
|
|
||||||
printf("m = %ld; ", splay_list_m(list));
|
api_skip_del_ex(list, 0);
|
||||||
printf("(⌊log2(m)⌋) = %d\n", floor_log2(splay_list_m(list)));
|
CHECK;
|
||||||
|
if (api_skip_get_ex(list, 0) != NULL)
|
||||||
if (!(rc = api_skip_contains_ex(list, 5)))
|
perror("found a deleted item!");
|
||||||
perror("missing element 5");
|
api_skip_del_ex(list, 0);
|
||||||
|
CHECK;
|
||||||
|
if (api_skip_get_ex(list, 0) != NULL)
|
||||||
|
perror("found a deleted item!");
|
||||||
|
int key = TEST_ARRAY_SIZE + 1;
|
||||||
|
api_skip_del_ex(list, key);
|
||||||
|
CHECK;
|
||||||
|
key = -(TEST_ARRAY_SIZE)-1;
|
||||||
|
api_skip_del_ex(list, key);
|
||||||
|
CHECK;
|
||||||
|
|
||||||
#ifdef DOT
|
#ifdef DOT
|
||||||
sprintf(msg, "contains(5)");
|
sprintf(msg, "deleted key: %d, value: %s", 0, numeral);
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
||||||
#endif
|
#endif
|
||||||
|
|
||||||
|
numeral = int_to_roman_numeral(-(TEST_ARRAY_SIZE));
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_GTE, -(TEST_ARRAY_SIZE)-1)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(-2);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_GTE, -2)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(1);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_GTE, 0)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(2);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_GTE, 2)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
assert(api_skip_pos_ex(list, SKIP_GTE, (TEST_ARRAY_SIZE + 1)) == NULL);
|
||||||
|
|
||||||
|
numeral = int_to_roman_numeral(-(TEST_ARRAY_SIZE));
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_GT, -(TEST_ARRAY_SIZE)-1)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(-1);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_GT, -2)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(1);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_GT, 0)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(2);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_GT, 1)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
assert(api_skip_pos_ex(list, SKIP_GT, TEST_ARRAY_SIZE) == NULL);
|
||||||
|
|
||||||
|
assert(api_skip_pos_ex(list, SKIP_LT, -(TEST_ARRAY_SIZE)) == NULL);
|
||||||
|
numeral = int_to_roman_numeral(-2);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_LT, -1)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(-1);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_LT, 0)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(1);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_LT, 2)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(TEST_ARRAY_SIZE);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_LT, (TEST_ARRAY_SIZE + 1))->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
|
||||||
|
assert(api_skip_pos_ex(list, SKIP_LTE, -(TEST_ARRAY_SIZE)-1) == NULL);
|
||||||
|
numeral = int_to_roman_numeral(-2);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_LTE, -2)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(-1);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_LTE, 0)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(2);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_LTE, 2)->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
numeral = int_to_roman_numeral(TEST_ARRAY_SIZE);
|
||||||
|
assert(strcmp(api_skip_pos_ex(list, SKIP_LTE, (TEST_ARRAY_SIZE + 1))->value, numeral) == 0);
|
||||||
|
free(numeral);
|
||||||
|
|
||||||
|
#ifdef TODO_RESTORE_SNAPSHOTS
|
||||||
|
// Walk backward by 2 and test snapshot restore.
|
||||||
|
for (i = n_snaps; i > 0; i -= 2) {
|
||||||
|
api_skip_restore_snapshot_ex(list, snaps[i].snap_id);
|
||||||
|
CHECK;
|
||||||
|
assert(api_skip_length_ex(list) == snaps[i].length);
|
||||||
|
numeral = int_to_roman_numeral(snaps[i].key);
|
||||||
|
assert(strncmp(api_skip_get_ex(list, snaps[i].key), numeral, strlen(numeral)) == 0);
|
||||||
|
free(numeral);
|
||||||
|
}
|
||||||
|
api_skip_release_snapshots_ex(list);
|
||||||
|
#endif
|
||||||
|
|
||||||
#ifdef DOT
|
#ifdef DOT
|
||||||
api_skip_dot_end_ex(of, gen);
|
api_skip_dot_end_ex(of, gen);
|
||||||
fclose(of);
|
fclose(of);
|
||||||
|
|
516
examples/ex2.c
516
examples/ex2.c
|
@ -1,516 +0,0 @@
|
||||||
#pragma GCC push_options
|
|
||||||
#pragma GCC optimize("O0")
|
|
||||||
|
|
||||||
// OPTIONS to set before including sl.h
|
|
||||||
// ---------------------------------------------------------------------------
|
|
||||||
#define DEBUG
|
|
||||||
#define SKIPLIST_DIAGNOSTIC
|
|
||||||
|
|
||||||
// Include our monolithic ADT, the Skiplist!
|
|
||||||
// ---------------------------------------------------------------------------
|
|
||||||
#include "../include/sl.h"
|
|
||||||
|
|
||||||
// Local demo application OPTIONS:
|
|
||||||
// ---------------------------------------------------------------------------
|
|
||||||
#define TEST_ARRAY_SIZE 10
|
|
||||||
#define VALIDATE
|
|
||||||
// define SNAPSHOTS
|
|
||||||
// define TODO_RESTORE_SNAPSHOTS
|
|
||||||
// define STABLE_SEED
|
|
||||||
#define DOT
|
|
||||||
|
|
||||||
#ifdef DOT
|
|
||||||
size_t gen = 0;
|
|
||||||
FILE *of = 0;
|
|
||||||
#endif
|
|
||||||
|
|
||||||
// ---------------------------------------------------------------------------
|
|
||||||
#ifdef VALIDATE
|
|
||||||
#define CHECK __skip_integrity_check_ex(list, 0)
|
|
||||||
#else
|
|
||||||
#define CHECK ((void)0)
|
|
||||||
#endif
|
|
||||||
|
|
||||||
/*
|
|
||||||
* SKIPLIST EXAMPLE:
|
|
||||||
*
|
|
||||||
* This example creates an "ex" Skiplist where keys are integers, values are
|
|
||||||
* strings containing the roman numeral for the key allocated on the heap.
|
|
||||||
*/
|
|
||||||
|
|
||||||
/*
|
|
||||||
* To start, you must create a type node that will contain the
|
|
||||||
* fields you'd like to maintain in your Skiplist. In this case
|
|
||||||
* we map int -> char [] on the heap, but what you put here is up
|
|
||||||
* to you. You don't even need a "key", just a way to compare one
|
|
||||||
* node against another, logic you'll provide in SKIP_DECL as a
|
|
||||||
* block below.
|
|
||||||
*/
|
|
||||||
struct ex_node {
|
|
||||||
int key;
|
|
||||||
char *value;
|
|
||||||
SKIPLIST_ENTRY(ex) entries;
|
|
||||||
};
|
|
||||||
|
|
||||||
/*
|
|
||||||
* Generate all the access functions for our type of Skiplist.
|
|
||||||
*/
|
|
||||||
SKIPLIST_DECL(
|
|
||||||
ex, api_, entries,
|
|
||||||
/* compare entries: list, a, b, aux */
|
|
||||||
{
|
|
||||||
(void)list;
|
|
||||||
(void)aux;
|
|
||||||
if (a->key < b->key)
|
|
||||||
return -1;
|
|
||||||
if (a->key > b->key)
|
|
||||||
return 1;
|
|
||||||
return 0;
|
|
||||||
},
|
|
||||||
/* free entry: node */
|
|
||||||
{
|
|
||||||
free(node->value);
|
|
||||||
node->value = NULL;
|
|
||||||
},
|
|
||||||
/* update entry: rc, node, value */
|
|
||||||
{
|
|
||||||
char *numeral = (char *)value;
|
|
||||||
if (node->value)
|
|
||||||
free(node->value);
|
|
||||||
node->value = numeral;
|
|
||||||
},
|
|
||||||
/* archive an entry: rc, src, dest */
|
|
||||||
{
|
|
||||||
dest->key = src->key;
|
|
||||||
char *nv = calloc(strlen(src->value) + 1, sizeof(char));
|
|
||||||
if (nv == NULL)
|
|
||||||
rc = ENOMEM;
|
|
||||||
else {
|
|
||||||
strncpy(nv, src->value, strlen(src->value));
|
|
||||||
dest->value = nv;
|
|
||||||
}
|
|
||||||
},
|
|
||||||
/* size in bytes of the content stored in an entry: bytes */
|
|
||||||
{ bytes = strlen(node->value) + 1; })
|
|
||||||
|
|
||||||
/*
|
|
||||||
* Skiplists are ordered, we need a way to compare entries.
|
|
||||||
* Let's create a function with four arguments:
|
|
||||||
* - a reference to the Skiplist, `slist`
|
|
||||||
* - the two nodes to compare, `a` and `b`
|
|
||||||
* - and `aux`, which you can use to pass into this function
|
|
||||||
* any additional information required to compare objects.
|
|
||||||
* `aux` is passed from the value in the Skiplist, you can
|
|
||||||
* modify that value at any time to suit your needs.
|
|
||||||
*
|
|
||||||
* Your function should result in a return statement:
|
|
||||||
* a < b : return -1
|
|
||||||
* a == b : return 0
|
|
||||||
* a > b : return 1
|
|
||||||
*
|
|
||||||
* This result provides the ordering within the Skiplist. Sometimes
|
|
||||||
* your function will not be used when comparing nodes. This will
|
|
||||||
* happen when `a` or `b` are references to the head or tail of the
|
|
||||||
* list or when `a == b`. In those cases the comparison function
|
|
||||||
* returns before using the code in your block, don't panic. :)
|
|
||||||
int
|
|
||||||
__ex_key_compare(ex_t *list, ex_node_t *a, ex_node_t *b, void *aux)
|
|
||||||
{
|
|
||||||
(void)list;
|
|
||||||
(void)aux;
|
|
||||||
if (a->key < b->key)
|
|
||||||
return -1;
|
|
||||||
if (a->key > b->key)
|
|
||||||
return 1;
|
|
||||||
return 0;
|
|
||||||
}
|
|
||||||
*/
|
|
||||||
|
|
||||||
/*
|
|
||||||
* Optional: Getters and Setters
|
|
||||||
* - get, put, dup(put), del, etc. functions
|
|
||||||
*
|
|
||||||
* It can be useful to have simple get/put-style API, but to
|
|
||||||
* do that you'll have to supply some blocks of code used to
|
|
||||||
* extract data from within your nodes.
|
|
||||||
*/
|
|
||||||
SKIPLIST_DECL_ACCESS(
|
|
||||||
ex, api_, key, int, value, char *,
|
|
||||||
/* query blk */ { query.key = key; },
|
|
||||||
/* return blk */ { return node->value; })
|
|
||||||
|
|
||||||
/*
|
|
||||||
* Optional: Snapshots
|
|
||||||
*
|
|
||||||
* Enable functions that enable returning to an earlier point in
|
|
||||||
* time when a snapshot was created.
|
|
||||||
*/
|
|
||||||
SKIPLIST_DECL_SNAPSHOTS(ex, api_, entries)
|
|
||||||
|
|
||||||
/*
|
|
||||||
* Optional: Archive to/from bytes
|
|
||||||
*
|
|
||||||
* Enable functions that can write/read the content of your Skiplist
|
|
||||||
* out/in to/from an array of bytes.
|
|
||||||
*/
|
|
||||||
// TODO SKIPLIST_DECL_ARCHIVE(ex, api_, entries)
|
|
||||||
|
|
||||||
/*
|
|
||||||
* Optional: As Hashtable
|
|
||||||
*
|
|
||||||
* Turn your Skiplist into a hash table.
|
|
||||||
*/
|
|
||||||
// TODO SKIPLIST_DECL_HASHTABLE(ex, api_, entries, snaps)
|
|
||||||
|
|
||||||
/*
|
|
||||||
* Optional: Check Skiplists at runtime
|
|
||||||
*
|
|
||||||
* Create a functions that validate the integrity of a Skiplist.
|
|
||||||
*/
|
|
||||||
SKIPLIST_DECL_VALIDATE(ex, api_, entries)
|
|
||||||
|
|
||||||
/* Optional: Visualize your Skiplist using DOT/Graphviz in PDF
|
|
||||||
*
|
|
||||||
* Create the functions used to annotate a visualization of a Skiplist.
|
|
||||||
*/
|
|
||||||
SKIPLIST_DECL_DOT(ex, api_, entries)
|
|
||||||
|
|
||||||
static void
|
|
||||||
sprintf_ex_node(ex_node_t *node, char *buf)
|
|
||||||
{
|
|
||||||
sprintf(buf, "%d:%s", node->key, node->value);
|
|
||||||
}
|
|
||||||
|
|
||||||
// Function for this demo application.
|
|
||||||
// ---------------------------------------------------------------------------
|
|
||||||
int __xorshift32_state = 0;
|
|
||||||
|
|
||||||
// Xorshift algorithm for PRNG
|
|
||||||
static uint32_t
|
|
||||||
xorshift32()
|
|
||||||
{
|
|
||||||
uint32_t x = __xorshift32_state;
|
|
||||||
if (x == 0)
|
|
||||||
x = 123456789;
|
|
||||||
x ^= x << 13;
|
|
||||||
x ^= x >> 17;
|
|
||||||
x ^= x << 5;
|
|
||||||
__xorshift32_state = x;
|
|
||||||
return x;
|
|
||||||
}
|
|
||||||
|
|
||||||
static void
|
|
||||||
xorshift32_seed()
|
|
||||||
{
|
|
||||||
// Seed the PRNG
|
|
||||||
#ifdef STABLE_SEED
|
|
||||||
__xorshift32_state = 8675309;
|
|
||||||
#else
|
|
||||||
__xorshift32_state = (unsigned int)time(NULL) ^ getpid();
|
|
||||||
#endif
|
|
||||||
}
|
|
||||||
|
|
||||||
/* convert upper case characters to lower case */
|
|
||||||
static char *
|
|
||||||
to_lower(char *str)
|
|
||||||
{
|
|
||||||
char *p = str;
|
|
||||||
for (; *p; ++p)
|
|
||||||
*p = (char)(*p >= 'A' && *p <= 'Z' ? *p | 0x60 : *p);
|
|
||||||
return str;
|
|
||||||
}
|
|
||||||
|
|
||||||
/* convert lower case characters to upper case */
|
|
||||||
static char *
|
|
||||||
to_upper(char *str)
|
|
||||||
{
|
|
||||||
char *p = str;
|
|
||||||
for (; *p; ++p)
|
|
||||||
*p = (char)(*p >= 'a' && *p <= 'z' ? *p & ~0x20 : *p);
|
|
||||||
return str;
|
|
||||||
}
|
|
||||||
|
|
||||||
/* convert a number into the Roman numeral equivalent, allocates a string caller must free */
|
|
||||||
static char *
|
|
||||||
int_to_roman_numeral(int num)
|
|
||||||
{
|
|
||||||
int del[] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; // Key value in Roman counting
|
|
||||||
char *sym[] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" }; // Symbols for key values
|
|
||||||
// The maximum length of the Roman numeral representation for the maximum signed 64-bit integer would be approximately 19 * 3 = 57 characters, assuming
|
|
||||||
// every digit is represented by its Roman numeral equivalent up to 3 repetitions. Therefore, 64 should be more than enough.
|
|
||||||
char *res = (char *)calloc(4096, sizeof(char));
|
|
||||||
int i = 0;
|
|
||||||
if (num < 0) {
|
|
||||||
res[0] = '-';
|
|
||||||
i++;
|
|
||||||
num = -num;
|
|
||||||
}
|
|
||||||
if (num == 0) {
|
|
||||||
res[0] = '0';
|
|
||||||
return res;
|
|
||||||
}
|
|
||||||
if (num > 10000) {
|
|
||||||
sprintf(res, "The person you were looking for is not here, their mailbox is full, good bye.");
|
|
||||||
return res;
|
|
||||||
}
|
|
||||||
while (num) { // while input number is not zero
|
|
||||||
while (num / del[i]) { // while a number contains the largest key value possible
|
|
||||||
strcat(res, sym[i]); // append the symbol for this key value to res string
|
|
||||||
num -= del[i]; // subtract the key value from number
|
|
||||||
}
|
|
||||||
i++; // proceed to the next key value
|
|
||||||
}
|
|
||||||
return res;
|
|
||||||
}
|
|
||||||
|
|
||||||
/* shuffle an array of length n */
|
|
||||||
static void
|
|
||||||
shuffle(int *array, size_t n)
|
|
||||||
{
|
|
||||||
if (n > 1) {
|
|
||||||
size_t i;
|
|
||||||
for (i = n - 1; i > 0; i--) {
|
|
||||||
size_t j = (unsigned int)(xorshift32() % (i + 1)); /* NOLINT(*-msc50-cpp) */
|
|
||||||
int t = array[j];
|
|
||||||
array[j] = array[i];
|
|
||||||
array[i] = t;
|
|
||||||
}
|
|
||||||
}
|
|
||||||
}
|
|
||||||
|
|
||||||
#ifdef TODO_RESTORE_SNAPSHOTS
|
|
||||||
typedef struct {
|
|
||||||
size_t length;
|
|
||||||
size_t key;
|
|
||||||
size_t snap_id;
|
|
||||||
} snap_info_t;
|
|
||||||
#endif
|
|
||||||
|
|
||||||
// ---------------------------------------------------------------------------
|
|
||||||
int
|
|
||||||
main()
|
|
||||||
{
|
|
||||||
int rc;
|
|
||||||
#ifdef TODO_RESTORE_SNAPSHOTS
|
|
||||||
size_t n_snaps = 0;
|
|
||||||
snap_info_t snaps[TEST_ARRAY_SIZE * 2 + 1];
|
|
||||||
#endif
|
|
||||||
|
|
||||||
xorshift32_seed();
|
|
||||||
|
|
||||||
#ifdef DOT
|
|
||||||
of = fopen("/tmp/ex2.dot", "w");
|
|
||||||
if (!of) {
|
|
||||||
perror("Failed to open file /tmp/ex2.dot");
|
|
||||||
return 1;
|
|
||||||
}
|
|
||||||
#endif
|
|
||||||
|
|
||||||
/* Allocate and initialize a Skiplist. */
|
|
||||||
ex_t *list = (ex_t *)malloc(sizeof(ex_t));
|
|
||||||
if (list == NULL)
|
|
||||||
return ENOMEM;
|
|
||||||
|
|
||||||
rc = api_skip_init_ex(list);
|
|
||||||
if (rc)
|
|
||||||
return rc;
|
|
||||||
|
|
||||||
/* Set the PRNG state to a known constant for reproducible generation, easing debugging. */
|
|
||||||
#ifdef STABLE_SEED
|
|
||||||
list->slh_prng_state = 12;
|
|
||||||
#endif
|
|
||||||
#ifdef SNAPSHOTS
|
|
||||||
api_skip_snapshots_init_ex(list);
|
|
||||||
#endif
|
|
||||||
#ifdef DOT
|
|
||||||
api_skip_dot_ex(of, list, gen++, "init", sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
if (api_skip_get_ex(list, 0) != NULL)
|
|
||||||
perror("found a non-existent item!");
|
|
||||||
api_skip_del_ex(list, 0);
|
|
||||||
CHECK;
|
|
||||||
|
|
||||||
/* Insert TEST_ARRAY_SIZE key/value pairs into the list. */
|
|
||||||
int i, j;
|
|
||||||
char *numeral;
|
|
||||||
#ifdef DOT
|
|
||||||
char msg[1024];
|
|
||||||
memset(msg, 0, 1024);
|
|
||||||
#endif
|
|
||||||
int amt = TEST_ARRAY_SIZE, asz = (amt * 2) + 1;
|
|
||||||
int array[(TEST_ARRAY_SIZE * 2) + 1];
|
|
||||||
for (j = 0, i = -amt; i <= amt; i++, j++)
|
|
||||||
array[j] = i;
|
|
||||||
shuffle(array, asz);
|
|
||||||
|
|
||||||
for (i = 0; i < asz; i++) {
|
|
||||||
#ifdef SNAPSHOTS
|
|
||||||
api_skip_snapshot_ex(list);
|
|
||||||
#elif defined(TODO_RESTORE_SNAPSHOTS)
|
|
||||||
/* Snapshot the first iteration, and then every 5th after that. */
|
|
||||||
if (i % 5 == 0) {
|
|
||||||
snaps[i].length = api_skip_length_ex(list);
|
|
||||||
snaps[i].key = array[i];
|
|
||||||
snaps[i].snap_id = api_skip_snapshot_ex(list);
|
|
||||||
n_snaps++;
|
|
||||||
CHECK;
|
|
||||||
}
|
|
||||||
#endif
|
|
||||||
numeral = to_lower(int_to_roman_numeral(array[i]));
|
|
||||||
rc = api_skip_put_ex(list, array[i], numeral);
|
|
||||||
CHECK;
|
|
||||||
#ifdef DOT
|
|
||||||
sprintf(msg, "put key: %d value: %s", array[i], numeral);
|
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
char *v = api_skip_get_ex(list, array[i]);
|
|
||||||
#ifdef DOT
|
|
||||||
sprintf(msg, "get key: %d", array[i]);
|
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
CHECK;
|
|
||||||
char *upper_numeral = calloc(1, strlen(v) + 1);
|
|
||||||
strncpy(upper_numeral, v, strlen(v));
|
|
||||||
assert(strncmp(v, upper_numeral, strlen(upper_numeral)) == 0);
|
|
||||||
to_upper(upper_numeral);
|
|
||||||
api_skip_set_ex(list, array[i], upper_numeral);
|
|
||||||
#ifdef DOT
|
|
||||||
sprintf(msg, "set key: %d value: %s", array[i], upper_numeral);
|
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
CHECK;
|
|
||||||
|
|
||||||
for (size_t j = 0, k = api_skip_length_ex(list); j < k; j++) {
|
|
||||||
int n = xorshift32() % api_skip_length_ex(list);
|
|
||||||
api_skip_contains_ex(list, array[n]);
|
|
||||||
CHECK;
|
|
||||||
}
|
|
||||||
#if 0
|
|
||||||
sprintf(msg, "locate all the keys!!!");
|
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
}
|
|
||||||
numeral = int_to_roman_numeral(-1);
|
|
||||||
api_skip_dup_ex(list, -1, numeral);
|
|
||||||
CHECK;
|
|
||||||
#ifdef DOT
|
|
||||||
sprintf(msg, "put dup key: %d value: %s", -1, numeral);
|
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
numeral = int_to_roman_numeral(1);
|
|
||||||
api_skip_dup_ex(list, 1, numeral);
|
|
||||||
CHECK;
|
|
||||||
#ifdef DOT
|
|
||||||
sprintf(msg, "put dup key: %d value: %s", 1, numeral);
|
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
|
|
||||||
api_skip_del_ex(list, 0);
|
|
||||||
CHECK;
|
|
||||||
#ifdef DOT
|
|
||||||
sprintf(msg, "deleted key: %d, value: %s", 0, numeral);
|
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
if (api_skip_get_ex(list, 0) != NULL)
|
|
||||||
perror("found a deleted item!");
|
|
||||||
api_skip_del_ex(list, 0);
|
|
||||||
CHECK;
|
|
||||||
if (api_skip_get_ex(list, 0) != NULL)
|
|
||||||
perror("found a deleted item!");
|
|
||||||
int key = TEST_ARRAY_SIZE + 1;
|
|
||||||
api_skip_del_ex(list, key);
|
|
||||||
CHECK;
|
|
||||||
key = -(TEST_ARRAY_SIZE)-1;
|
|
||||||
api_skip_del_ex(list, key);
|
|
||||||
CHECK;
|
|
||||||
|
|
||||||
numeral = int_to_roman_numeral(-(TEST_ARRAY_SIZE));
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_GTE, -(TEST_ARRAY_SIZE)-1)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(-2);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_GTE, -2)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(1);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_GTE, 0)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(2);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_GTE, 2)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
assert(api_skip_pos_ex(list, SKIP_GTE, (TEST_ARRAY_SIZE + 1)) == NULL);
|
|
||||||
|
|
||||||
numeral = int_to_roman_numeral(-(TEST_ARRAY_SIZE));
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_GT, -(TEST_ARRAY_SIZE)-1)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(-1);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_GT, -2)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(1);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_GT, 0)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(2);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_GT, 1)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
assert(api_skip_pos_ex(list, SKIP_GT, TEST_ARRAY_SIZE) == NULL);
|
|
||||||
|
|
||||||
assert(api_skip_pos_ex(list, SKIP_LT, -(TEST_ARRAY_SIZE)) == NULL);
|
|
||||||
numeral = int_to_roman_numeral(-2);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_LT, -1)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(-1);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_LT, 0)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(1);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_LT, 2)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(TEST_ARRAY_SIZE);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_LT, (TEST_ARRAY_SIZE + 1))->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
|
|
||||||
assert(api_skip_pos_ex(list, SKIP_LTE, -(TEST_ARRAY_SIZE)-1) == NULL);
|
|
||||||
numeral = int_to_roman_numeral(-2);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_LTE, -2)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(-1);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_LTE, 0)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(2);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_LTE, 2)->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
numeral = int_to_roman_numeral(TEST_ARRAY_SIZE);
|
|
||||||
assert(strcmp(api_skip_pos_ex(list, SKIP_LTE, (TEST_ARRAY_SIZE + 1))->value, numeral) == 0);
|
|
||||||
free(numeral);
|
|
||||||
|
|
||||||
#ifdef TODO_RESTORE_SNAPSHOTS
|
|
||||||
// Walk backward by 2 and test snapshot restore.
|
|
||||||
for (i = n_snaps; i > 0; i -= 2) {
|
|
||||||
api_skip_restore_snapshot_ex(list, snaps[i].snap_id);
|
|
||||||
CHECK;
|
|
||||||
assert(api_skip_length_ex(list) == snaps[i].length);
|
|
||||||
numeral = int_to_roman_numeral(snaps[i].key);
|
|
||||||
assert(strncmp(api_skip_get_ex(list, snaps[i].key), numeral, strlen(numeral)) == 0);
|
|
||||||
free(numeral);
|
|
||||||
}
|
|
||||||
api_skip_release_snapshots_ex(list);
|
|
||||||
#endif
|
|
||||||
|
|
||||||
for (size_t i = 0; i < 1000000; i++) {
|
|
||||||
for (size_t j = 0, k = api_skip_length_ex(list); j < k; j++) {
|
|
||||||
int n = xorshift32() % api_skip_length_ex(list);
|
|
||||||
api_skip_contains_ex(list, array[n]);
|
|
||||||
CHECK;
|
|
||||||
}
|
|
||||||
}
|
|
||||||
#ifdef DOT
|
|
||||||
sprintf(msg, "lots-o-contains later...");
|
|
||||||
api_skip_dot_ex(of, list, gen++, msg, sprintf_ex_node);
|
|
||||||
#endif
|
|
||||||
|
|
||||||
#ifdef DOT
|
|
||||||
api_skip_dot_end_ex(of, gen);
|
|
||||||
fclose(of);
|
|
||||||
#endif
|
|
||||||
api_skip_free_ex(list);
|
|
||||||
free(list);
|
|
||||||
return rc;
|
|
||||||
}
|
|
||||||
#pragma GCC pop_options
|
|
435
include/sl.h
435
include/sl.h
|
@ -53,22 +53,20 @@
|
||||||
#define _SKIPLIST_H_
|
#define _SKIPLIST_H_
|
||||||
|
|
||||||
/*
|
/*
|
||||||
* This file defines a skip-list data structure written in C. Implemented as
|
* This file defines a skiplist data structure written in C. Implemented as
|
||||||
* using macros this code provides a way to essentially "template" (as in C++)
|
* using macros this code provides a way to essentially "template" (as in C++)
|
||||||
* and emit code with types and functions specific to your use case. You can
|
* and emit code with types and functions specific to your use case. You can
|
||||||
* apply these macros multiple times safely, once for each list type you need.
|
* apply these macros multiple times safely in your code, once for each
|
||||||
|
* application.
|
||||||
*
|
*
|
||||||
* A skip-list is a sorted list with O(log(n)) on average for most operations.
|
* A skiplist is a sorted list with O(log(n)) on average for most operations.
|
||||||
* It is a probabilistic datastructure, meaning that it does not guarantee
|
* It is a probabilistic datastructure, meaning that it does not guarantee
|
||||||
* O(log(n)), but it has been shown to approximate it over time. This
|
* O(log(n)) it approximates it over time. This implementation improves the
|
||||||
* implementation includes the re-balancing techniques that improve on that
|
* probability by integrating the splay list algorithm for rebalancing trading
|
||||||
* approximation using an adaptive technique called "splay-list". It is similar
|
* off a bit of computational overhead and code complexity for a nearly always
|
||||||
* to a standard skip-list, with the key distinction that the height of each
|
* optimal, or "perfect" skiplist.
|
||||||
* element adapts dynamically to its access rate: popular elements increase in
|
|
||||||
* height, whereas rarely-accessed elements decrease in height. See below for
|
|
||||||
* the link to the research behind this adaptive technique.
|
|
||||||
*
|
*
|
||||||
* Conceptually, at a high level, a skip-list is arranged as follows:
|
* Conceptually, a skiplist is arranged as follows:
|
||||||
*
|
*
|
||||||
* <head> ----------> [2] --------------------------------------------------> [9] ---------->
|
* <head> ----------> [2] --------------------------------------------------> [9] ---------->
|
||||||
* <head> ----------> [2] ------------------------------------[7] ----------> [9] ---------->
|
* <head> ----------> [2] ------------------------------------[7] ----------> [9] ---------->
|
||||||
|
@ -81,22 +79,22 @@
|
||||||
* diagram). This allows for the algorithm to move down the list faster than
|
* diagram). This allows for the algorithm to move down the list faster than
|
||||||
* having to visit every element.
|
* having to visit every element.
|
||||||
*
|
*
|
||||||
* A skip-list can be thought of as a stack of linked lists. At the very bottom
|
* Conceptually, the skiplist can be thought of as a stack of linked lists. At
|
||||||
* is a linked list with every element, and each layer above corresponds to a
|
* the very bottom is the full linked list with every element, and each layer
|
||||||
* linked list containing a random subset of the elements from the layer
|
* above corresponds to a linked list containing a random subset of the elements
|
||||||
* immediately below it. The probability distribution that determines this
|
* from the layer immediately below it. The probability distribution that
|
||||||
* random subset can be customized, but typically a layer will contain half the
|
* determines this random subset can be customized, but typically a layer will
|
||||||
* nodes from the layer below.
|
* contain half the nodes from the layer below.
|
||||||
*
|
*
|
||||||
* This implementation maintains a doubly-linked list at the bottom layer to
|
* This implementation maintains a doubly-linked list at the bottom layer to
|
||||||
* support efficient iteration in either direction. There is also a guard node
|
* support efficient iteration in either direction. There is also a guard
|
||||||
* at the tail rather than simply pointing to NULL.
|
* node at the tail rather than simply pointing to NULL.
|
||||||
*
|
*
|
||||||
* <head> <-> [1] <-> [2] <-> [3] <-> [4] <-> [5] <-> [6] <-> [7] <-> <tail>
|
* <head> <-> [1] <-> [2] <-> [3] <-> [4] <-> [5] <-> [6] <-> [7] <-> <tail>
|
||||||
*
|
*
|
||||||
* Safety:
|
* Safety:
|
||||||
*
|
*
|
||||||
* The ordered skip-list relies on a well-behaved comparison
|
* The ordered skiplist relies on a well-behaved comparison
|
||||||
* function. Specifically, given some ordering function f(a, b), it must satisfy
|
* function. Specifically, given some ordering function f(a, b), it must satisfy
|
||||||
* the following properties:
|
* the following properties:
|
||||||
*
|
*
|
||||||
|
@ -201,14 +199,14 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
*/
|
*/
|
||||||
|
|
||||||
#ifndef SKIPLIST_MAX_HEIGHT
|
#ifndef SKIPLIST_MAX_HEIGHT
|
||||||
#define SKIPLIST_MAX_HEIGHT 64
|
#define SKIPLIST_MAX_HEIGHT 1
|
||||||
#endif
|
#endif
|
||||||
|
|
||||||
/*
|
/*
|
||||||
* Every Skiplist node has to have an additional section of data used to manage
|
* Every Skiplist node has to hvae an additional section of data used to manage
|
||||||
* nodes in the list. The rest of the datastructure is defined by the use case.
|
* nodes in the list. The rest of the datastructure is defined by the use case.
|
||||||
* This housekeeping portion is the SKIPLIST_ENTRY, see below. It maintains the
|
* This housekeeping portion is the SKIPLIST_ENTRY, see below. It maintains the
|
||||||
* array of forward pointers to nodes and has a height, this height is a
|
* array of forward pointers to nodes and has a height, this height is a a
|
||||||
* zero-based count of levels, so a height of `0` means one (1) level and a
|
* zero-based count of levels, so a height of `0` means one (1) level and a
|
||||||
* height of `4` means five (5) forward pointers (levels) in the node, [0-4).
|
* height of `4` means five (5) forward pointers (levels) in the node, [0-4).
|
||||||
*/
|
*/
|
||||||
|
@ -219,7 +217,6 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
struct decl##_node *sle_prev; \
|
struct decl##_node *sle_prev; \
|
||||||
struct __skiplist_##decl##_level { \
|
struct __skiplist_##decl##_level { \
|
||||||
struct decl##_node *next; \
|
struct decl##_node *next; \
|
||||||
size_t hits; \
|
|
||||||
} *sle_levels; \
|
} *sle_levels; \
|
||||||
}
|
}
|
||||||
|
|
||||||
|
@ -231,25 +228,16 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
for (iter = (list)->slh_length, (elm) = (list)->slh_tail; ((elm) = (elm)->field.sle_prev) != (list)->slh_head; iter--)
|
for (iter = (list)->slh_length, (elm) = (list)->slh_tail; ((elm) = (elm)->field.sle_prev) != (list)->slh_head; iter--)
|
||||||
|
|
||||||
/* Iterate over the next pointers in a node from bottom to top (B2T) or top to bottom (T2B). */
|
/* Iterate over the next pointers in a node from bottom to top (B2T) or top to bottom (T2B). */
|
||||||
#define __SKIP_ALL_ENTRIES_T2B(field, elm) for (size_t lvl = slist->slh_head->field.sle_height - 1; lvl != (size_t)-1; lvl--)
|
#define __SKIP_ALL_ENTRIES_T2B(field, elm) for (size_t lvl = slist->slh_max_height; lvl != (size_t)-1; lvl--)
|
||||||
#define __SKIP_ENTRIES_T2B(field, elm) for (size_t lvl = elm->field.sle_height; lvl != (size_t)-1; lvl--)
|
#define __SKIP_ENTRIES_T2B(field, elm) for (size_t lvl = elm->field.sle_height; lvl != (size_t)-1; lvl--)
|
||||||
#define __SKIP_ENTRIES_T2B_FROM(field, elm, off) for (size_t lvl = off; lvl != (size_t)-1; lvl--)
|
#define __SKIP_ENTRIES_T2B_FROM(field, elm, off) for (size_t lvl = off; lvl != (size_t)-1; lvl--)
|
||||||
#define __SKIP_IS_LAST_ENTRY_T2B() if (lvl == 0)
|
#define __SKIP_IS_LAST_ENTRY_T2B() if (lvl == 0)
|
||||||
|
|
||||||
#define __SKIP_ALL_ENTRIES_B2T(field, elm) for (size_t lvl = 0; lvl < slist->slh_head->field.sle_height - 1; lvl++)
|
#define __SKIP_ALL_ENTRIES_B2T(field, elm) for (size_t lvl = 0; lvl < slist->slh_max_height; lvl++)
|
||||||
#define __SKIP_ENTRIES_B2T(field, elm) for (size_t lvl = 0; lvl <= elm->field.sle_height; lvl++)
|
#define __SKIP_ENTRIES_B2T(field, elm) for (size_t lvl = 0; lvl <= elm->field.sle_height; lvl++)
|
||||||
#define __SKIP_ENTRIES_B2T_FROM(field, elm, off) for (size_t lvl = off; lvl <= elm->field.sle_height; lvl++)
|
#define __SKIP_ENTRIES_B2T_FROM(field, elm, off) for (size_t lvl = off; lvl <= elm->field.sle_height; lvl++)
|
||||||
#define __SKIP_IS_LAST_ENTRY_B2T() if (lvl + 1 == elm->field.sle_height)
|
#define __SKIP_IS_LAST_ENTRY_B2T() if (lvl + 1 == elm->field.sle_height)
|
||||||
|
|
||||||
/* Iterate over the left (v) subtree or right (u) subtree or "CHu" and "CHv". */
|
|
||||||
#define __SKIP_SUBTREE_CHv(decl, field, list, path, nth) \
|
|
||||||
for (decl##_node_t *elm = path[nth].node; elm->field.sle_levels[path[nth].in].next == path[nth].node; elm = elm->field.sle_prev)
|
|
||||||
#define __SKIP_SUBTREE_CHu(decl, field, list, path, nth) \
|
|
||||||
for (decl##_node_t *elm = path[nth].node; elm != path[nth].node->field.sle_levels[0].next; elm = elm->field.sle_levels[0].next)
|
|
||||||
/* Iterate over a subtree starting at provided path element, u = path.in */
|
|
||||||
#define __SKIP_SUBTREE_CHux(decl, field, list, node, level) \
|
|
||||||
for (decl##_node_t *elm = node->field.sle_levels[level].next->field.sle_prev; elm != node->field.sle_prev; elm = elm->field.sle_prev)
|
|
||||||
|
|
||||||
/*
|
/*
|
||||||
* Skiplist declarations and access methods.
|
* Skiplist declarations and access methods.
|
||||||
*/
|
*/
|
||||||
|
@ -266,7 +254,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
\
|
\
|
||||||
/* Skiplist structure */ \
|
/* Skiplist structure */ \
|
||||||
struct decl { \
|
struct decl { \
|
||||||
size_t slh_length; \
|
size_t slh_length, slh_max_height; \
|
||||||
void *slh_aux; \
|
void *slh_aux; \
|
||||||
int slh_prng_state; \
|
int slh_prng_state; \
|
||||||
decl##_node_t *slh_head; \
|
decl##_node_t *slh_head; \
|
||||||
|
@ -291,8 +279,6 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
\
|
\
|
||||||
typedef struct __skiplist_path_##decl { \
|
typedef struct __skiplist_path_##decl { \
|
||||||
decl##_node_t *node; /* node traversed in the act of location */ \
|
decl##_node_t *node; /* node traversed in the act of location */ \
|
||||||
size_t in; /* level at which the node was intersected */ \
|
|
||||||
size_t pu; /* see "partial sums trick" */ \
|
|
||||||
} __skiplist_path_##decl##_t; \
|
} __skiplist_path_##decl##_t; \
|
||||||
\
|
\
|
||||||
/* Xorshift algorithm for PRNG */ \
|
/* Xorshift algorithm for PRNG */ \
|
||||||
|
@ -416,12 +402,12 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
* \
|
* \
|
||||||
* Allocates a new node on the heap and sets default values. \
|
* Allocates a new node on the heap and sets default values. \
|
||||||
*/ \
|
*/ \
|
||||||
int prefix##skip_alloc_node_##decl(decl##_node_t **node) \
|
int prefix##skip_alloc_node_##decl(decl##_t *slist, decl##_node_t **node) \
|
||||||
{ \
|
{ \
|
||||||
decl##_node_t *n; \
|
decl##_node_t *n; \
|
||||||
/* Calculate the size of the struct sle within decl##_node_t, multiply \
|
/* Calculate the size of the struct sle within decl##_node_t, multiply \
|
||||||
by array size. (16/24 bytes on 32/64 bit systems) */ \
|
by array size. (16/24 bytes on 32/64 bit systems) */ \
|
||||||
size_t sle_arr_sz = sizeof(struct __skiplist_##decl##_level) * SKIPLIST_MAX_HEIGHT; \
|
size_t sle_arr_sz = sizeof(struct __skiplist_##decl##_level) * slist->slh_max_height; \
|
||||||
n = (decl##_node_t *)calloc(1, sizeof(decl##_node_t) + sle_arr_sz); \
|
n = (decl##_node_t *)calloc(1, sizeof(decl##_node_t) + sle_arr_sz); \
|
||||||
if (n == NULL) \
|
if (n == NULL) \
|
||||||
return ENOMEM; \
|
return ENOMEM; \
|
||||||
|
@ -434,15 +420,16 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
/** \
|
/** \
|
||||||
* -- skip_init_ \
|
* -- skip_init_ \
|
||||||
* \
|
* \
|
||||||
* Initializes a Skiplist to the default values, this must be \
|
* Initializes a Skiplist to the deafault values, this must be called \
|
||||||
* called before using the list. \
|
* before using the list. \
|
||||||
*/ \
|
*/ \
|
||||||
int prefix##skip_init_##decl(decl##_t *slist) \
|
int prefix##skip_init_##decl(decl##_t *slist, int max) \
|
||||||
{ \
|
{ \
|
||||||
int rc = 0; \
|
int rc = 0; \
|
||||||
size_t i; \
|
size_t i; \
|
||||||
\
|
\
|
||||||
slist->slh_length = 0; \
|
slist->slh_length = 0; \
|
||||||
|
slist->slh_max_height = SKIPLIST_MAX_HEIGHT == 1 ? (size_t)(max < 0 ? -max : max) : SKIPLIST_MAX_HEIGHT; \
|
||||||
slist->slh_snap.cur_era = 0; \
|
slist->slh_snap.cur_era = 0; \
|
||||||
slist->slh_snap.pres_era = 0; \
|
slist->slh_snap.pres_era = 0; \
|
||||||
slist->slh_snap.pres = 0; \
|
slist->slh_snap.pres = 0; \
|
||||||
|
@ -451,24 +438,31 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
slist->slh_fns.archive_entry = __skip_archive_entry_fn_##decl; \
|
slist->slh_fns.archive_entry = __skip_archive_entry_fn_##decl; \
|
||||||
slist->slh_fns.sizeof_entry = __skip_sizeof_entry_fn_##decl; \
|
slist->slh_fns.sizeof_entry = __skip_sizeof_entry_fn_##decl; \
|
||||||
slist->slh_fns.compare_entries = __skip_compare_entries_fn_##decl; \
|
slist->slh_fns.compare_entries = __skip_compare_entries_fn_##decl; \
|
||||||
rc = prefix##skip_alloc_node_##decl(&slist->slh_head); \
|
rc = prefix##skip_alloc_node_##decl(slist, &slist->slh_head); \
|
||||||
if (rc) \
|
if (rc) \
|
||||||
goto fail; \
|
goto fail; \
|
||||||
rc = prefix##skip_alloc_node_##decl(&slist->slh_tail); \
|
rc = prefix##skip_alloc_node_##decl(slist, &slist->slh_tail); \
|
||||||
if (rc) \
|
if (rc) \
|
||||||
goto fail; \
|
goto fail; \
|
||||||
\
|
\
|
||||||
/* Initial height at head is 0 (meaning 0 sub-lists), all next point to tail */ \
|
/* Initial height is 0 (meaning 1 level), all next point to tail */ \
|
||||||
slist->slh_head->field.sle_height = 1; \
|
slist->slh_head->field.sle_height = 0; \
|
||||||
for (i = 0; i < slist->slh_head->entries.sle_height + 1; i++) \
|
for (i = 0; i < slist->slh_max_height; i++) \
|
||||||
slist->slh_head->field.sle_levels[i].next = slist->slh_tail; \
|
slist->slh_head->field.sle_levels[i].next = slist->slh_tail; \
|
||||||
slist->slh_head->field.sle_prev = NULL; \
|
slist->slh_head->field.sle_prev = NULL; \
|
||||||
\
|
\
|
||||||
/* Initial height at tail is also 0 and all next point to tail */ \
|
/* Initial height is 0 (meaning 1 level), all next point to tail */ \
|
||||||
slist->slh_tail->field.sle_height = slist->slh_head->field.sle_height; \
|
slist->slh_tail->field.sle_height = slist->slh_head->field.sle_height; \
|
||||||
for (i = 0; i < slist->slh_head->entries.sle_height + 1; i++) \
|
for (i = 0; i < slist->slh_max_height; i++) \
|
||||||
slist->slh_tail->field.sle_levels[i].next = NULL; \
|
slist->slh_tail->field.sle_levels[i].next = NULL; \
|
||||||
slist->slh_tail->field.sle_prev = slist->slh_head; \
|
slist->slh_tail->field.sle_prev = slist->slh_head; \
|
||||||
|
\
|
||||||
|
/* NOTE: Here's a testing aid, simply set `max` to a negative number to \
|
||||||
|
* seed the PRNG in a predictable way and have reproducible random numbers. \
|
||||||
|
*/ \
|
||||||
|
if (max < 0) \
|
||||||
|
slist->slh_prng_state = -max; \
|
||||||
|
else \
|
||||||
slist->slh_prng_state = ((unsigned int)time(NULL) ^ getpid()); \
|
slist->slh_prng_state = ((unsigned int)time(NULL) ^ getpid()); \
|
||||||
fail:; \
|
fail:; \
|
||||||
return rc; \
|
return rc; \
|
||||||
|
@ -527,8 +521,6 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
*/ \
|
*/ \
|
||||||
decl##_node_t *prefix##skip_tail_##decl(decl##_t *slist) \
|
decl##_node_t *prefix##skip_tail_##decl(decl##_t *slist) \
|
||||||
{ \
|
{ \
|
||||||
if (slist == NULL) \
|
|
||||||
return NULL; \
|
|
||||||
return slist->slh_tail->field.sle_prev == slist->slh_head->field.sle_levels[0].next ? NULL : slist->slh_tail->field.sle_prev; \
|
return slist->slh_tail->field.sle_prev == slist->slh_head->field.sle_levels[0].next ? NULL : slist->slh_tail->field.sle_prev; \
|
||||||
} \
|
} \
|
||||||
\
|
\
|
||||||
|
@ -612,174 +604,36 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
return nodes; \
|
return nodes; \
|
||||||
} \
|
} \
|
||||||
\
|
\
|
||||||
/** \
|
|
||||||
* -- __skip_adjust_hit_counts_ TODO \
|
|
||||||
* \
|
|
||||||
* On delete we check the hit counts across all nodes and next[] pointers \
|
|
||||||
* and find the smallest counter then subtract that + 1 from all hit \
|
|
||||||
* counters. \
|
|
||||||
* \
|
|
||||||
*/ \
|
|
||||||
static void __skip_adjust_hit_counts_##decl(decl##_t *slist) \
|
|
||||||
{ \
|
|
||||||
((void)slist); \
|
|
||||||
} \
|
|
||||||
\
|
|
||||||
/** \
|
|
||||||
* -- __skip_rebalance_ \
|
|
||||||
* \
|
|
||||||
* Restore balance to our list by adjusting heights and forward pointers \
|
|
||||||
* according to the algorithm put forth in "The Splay-List: A \
|
|
||||||
* Distribution-Adaptive Concurrent Skip-List". \
|
|
||||||
* \
|
|
||||||
*/ \
|
|
||||||
static void __skip_rebalance_##decl(decl##_t *slist, size_t len, __skiplist_path_##decl##_t path[]) \
|
|
||||||
{ \
|
|
||||||
size_t i, lvl, u_hits, hits_CHu = 0, hits_CHv = 0, delta_height; \
|
|
||||||
size_t k_threshold, m_total_hits, expected_height; \
|
|
||||||
double asc_cond, dsc_cond; \
|
|
||||||
__skiplist_path_##decl##_t *p, path_u, path_v; \
|
|
||||||
decl##_node_t *node; \
|
|
||||||
\
|
|
||||||
/* Total hits, `k`, across all nodes. */ \
|
|
||||||
m_total_hits = slist->slh_head->field.sle_levels[slist->slh_head->field.sle_height].hits; \
|
|
||||||
\
|
|
||||||
/* Should we adjust the height? */ \
|
|
||||||
if (m_total_hits > 0) { \
|
|
||||||
expected_height = floor(log(m_total_hits) / log(2)); \
|
|
||||||
if (expected_height > slist->slh_head->field.sle_height && expected_height < SKIPLIST_MAX_HEIGHT - 1) { \
|
|
||||||
slist->slh_head->field.sle_height++; \
|
|
||||||
slist->slh_head->field.sle_levels[slist->slh_head->field.sle_height].next = slist->slh_tail; \
|
|
||||||
slist->slh_head->field.sle_levels[slist->slh_head->field.sle_height].hits = \
|
|
||||||
slist->slh_head->field.sle_levels[slist->slh_head->field.sle_height - 1].hits; \
|
|
||||||
slist->slh_head->field.sle_levels[slist->slh_head->field.sle_height - 1].hits = 0; \
|
|
||||||
slist->slh_tail->field.sle_height = slist->slh_head->field.sle_height; \
|
|
||||||
} \
|
|
||||||
} \
|
|
||||||
\
|
|
||||||
/* Height of the head node, should be equal to floor(log(m_total_hits)). */ \
|
|
||||||
k_threshold = slist->slh_head->field.sle_height; \
|
|
||||||
\
|
|
||||||
/* Moving backwards along the path... \
|
|
||||||
* - path[0] contains a match, if there was one \
|
|
||||||
* - path[1..len] will be the nodes traversed along the way \
|
|
||||||
* - path[len] is where the locate() terminated, just before path[0] \
|
|
||||||
* if there was a match \
|
|
||||||
*/ \
|
|
||||||
p = &path[0]; \
|
|
||||||
for (i = 0; i < len; i++, p++) { \
|
|
||||||
hits_CHu = hits_CHv = 0; \
|
|
||||||
path_u = *p; \
|
|
||||||
if (path_u.node == slist->slh_head || path_u.node == slist->slh_tail) \
|
|
||||||
continue; \
|
|
||||||
path_v = *(p + 1); \
|
|
||||||
\
|
|
||||||
/* Evaluate the subtree 'u'. */ \
|
|
||||||
__SKIP_SUBTREE_CHux(decl, field, slist, path_u.node, path_u.in) \
|
|
||||||
{ \
|
|
||||||
hits_CHu += elm->field.sle_levels[0].hits; \
|
|
||||||
} \
|
|
||||||
/* Evaluate the subtree 'v' at the same level. */ \
|
|
||||||
__SKIP_SUBTREE_CHux(decl, field, slist, (*(p + 1)).node->field.sle_levels[path_u.in].next, path_u.in) \
|
|
||||||
{ \
|
|
||||||
hits_CHv += elm->field.sle_levels[0].hits; \
|
|
||||||
} \
|
|
||||||
\
|
|
||||||
/* (a) Check the decent condition: \
|
|
||||||
* u_hits <= m_total_hits / (2 ^ (k_threshold - height of node)) \
|
|
||||||
* When met we: \
|
|
||||||
* 1) go backwards along path from where we are until head \
|
|
||||||
* 2) adjust any forward pointers, then... \
|
|
||||||
* 3) adjust hits, and... \
|
|
||||||
* 4) lower the path[i]'s node height by 1 \
|
|
||||||
*/ \
|
|
||||||
delta_height = k_threshold - path_u.node->field.sle_height; \
|
|
||||||
dsc_cond = m_total_hits / pow(2.0, delta_height); \
|
|
||||||
u_hits = hits_CHu + hits_CHv; \
|
|
||||||
if (u_hits <= dsc_cond && path_u.node->field.sle_height > 0) { \
|
|
||||||
lvl = path_u.node->field.sle_height; \
|
|
||||||
/* 1) go backwards along path from where we are until head */ \
|
|
||||||
node = path_u.node; \
|
|
||||||
do { \
|
|
||||||
node = node->field.sle_prev; \
|
|
||||||
/* 2) adjust forward pointers */ \
|
|
||||||
if (node->field.sle_height >= lvl && node->field.sle_levels[lvl].next == path_u.node) { \
|
|
||||||
node->field.sle_levels[lvl].next = path_u.node->field.sle_levels[lvl].next; \
|
|
||||||
/* 3) adjust hits */ \
|
|
||||||
node->field.sle_levels[lvl].hits += 1; \
|
|
||||||
break; \
|
|
||||||
} \
|
|
||||||
} while (node != slist->slh_head); \
|
|
||||||
/* 4) reduce height by one */ \
|
|
||||||
path_u.node->field.sle_height--; \
|
|
||||||
} \
|
|
||||||
/* (b) Check the ascent condition: \
|
|
||||||
* path[i].pu + node_hits > hits total / (2 ^ (height of head - height of node - 1)) \
|
|
||||||
* When met we: \
|
|
||||||
* 1) check the ascent condition, then iff true ... \
|
|
||||||
* 2) add a level, and ... \
|
|
||||||
* 3) set its hits to the prev node at intersection height \
|
|
||||||
* 4) set prev node hits to 0 and forward to this new level \
|
|
||||||
*/ \
|
|
||||||
/* 1) check ascent condition */ \
|
|
||||||
asc_cond = m_total_hits / pow(2.0, delta_height - 1); \
|
|
||||||
if (path_u.pu > asc_cond && path_u.node->entries.sle_height < 64 - 1) { \
|
|
||||||
if (path_u.node->field.sle_height + 1 > path_v.node->field.sle_height) { \
|
|
||||||
continue; \
|
|
||||||
} \
|
|
||||||
lvl = ++path_u.node->field.sle_height; \
|
|
||||||
/* Don't adjust hits when the previous node on the path is the head. */ \
|
|
||||||
if (path_v.node != slist->slh_head) { \
|
|
||||||
path_u.node->field.sle_levels[lvl].hits = path_v.node->entries.sle_levels[lvl].hits; \
|
|
||||||
path_v.node->field.sle_levels[lvl].hits = 0; \
|
|
||||||
} \
|
|
||||||
path_u.node->field.sle_levels[lvl].next = path_v.node->field.sle_levels[lvl].next; \
|
|
||||||
path_v.node->field.sle_levels[lvl].next = path_u.node; \
|
|
||||||
} \
|
|
||||||
} \
|
|
||||||
} \
|
|
||||||
\
|
|
||||||
/** \
|
/** \
|
||||||
* -- __skip_locate_ \
|
* -- __skip_locate_ \
|
||||||
* \
|
* \
|
||||||
* Locates a node that matches another node updating `path` and then \
|
* Locates a node that matches another node updating `path` and then \
|
||||||
* returning the length of that path + 1 to the node and the matching \
|
* returning the length of that path + 1 to the node and the matching \
|
||||||
* node in path[0], or NULL at path[0] where there wasn't a match. \
|
* node in path[0], or NULL at path[0] where there wasn't a match. \
|
||||||
* sizeof(path) should be `slist->slh_head->field.sle_height + 1` \
|
* sizeof(path) should be `slist->slh_max_height + 1` \
|
||||||
*/ \
|
*/ \
|
||||||
static size_t __skip_locate_##decl(decl##_t *slist, decl##_node_t *n, __skiplist_path_##decl##_t path[]) \
|
static size_t __skip_locate_##decl(decl##_t *slist, decl##_node_t *n, __skiplist_path_##decl##_t path[]) \
|
||||||
{ \
|
{ \
|
||||||
unsigned int i; \
|
unsigned int i; \
|
||||||
size_t len = 0; \
|
size_t len = 0; \
|
||||||
decl##_node_t *elm; \
|
decl##_node_t *elm = slist->slh_head; \
|
||||||
__skiplist_path_##decl##_t *cur; \
|
|
||||||
\
|
\
|
||||||
if (slist == NULL || n == NULL) \
|
if (slist == NULL || n == NULL) \
|
||||||
return 0; \
|
return 0; \
|
||||||
\
|
\
|
||||||
elm = slist->slh_head; \
|
|
||||||
\
|
|
||||||
/* Find the node that matches `node` or NULL. */ \
|
/* Find the node that matches `node` or NULL. */ \
|
||||||
i = slist->slh_head->field.sle_height - 1; \
|
i = slist->slh_head->field.sle_height; \
|
||||||
do { \
|
do { \
|
||||||
cur = &path[i + 1]; \
|
while (elm != slist->slh_tail && elm->field.sle_levels[i].next && \
|
||||||
cur->pu = 0; \
|
__skip_compare_nodes_##decl(slist, elm->field.sle_levels[i].next, n, slist->slh_aux) < 0) { \
|
||||||
while (elm != slist->slh_tail && __skip_compare_nodes_##decl(slist, elm->field.sle_levels[i].next, n, slist->slh_aux) < 0) { \
|
|
||||||
cur->in = i; \
|
|
||||||
elm = elm->field.sle_levels[i].next; \
|
elm = elm->field.sle_levels[i].next; \
|
||||||
} \
|
} \
|
||||||
cur->node = elm; \
|
path[i + 1].node = elm; \
|
||||||
cur->node->field.sle_levels[cur->in].hits += i ? 1 : 0; \
|
|
||||||
cur->pu += cur->node->field.sle_levels[0].hits; \
|
|
||||||
len++; \
|
len++; \
|
||||||
} while (i--); \
|
} while (i--); \
|
||||||
elm = elm->field.sle_levels[0].next; \
|
elm = elm->field.sle_levels[0].next; \
|
||||||
if (__skip_compare_nodes_##decl(slist, elm, n, slist->slh_aux) == 0) { \
|
if (__skip_compare_nodes_##decl(slist, elm, n, slist->slh_aux) == 0) { \
|
||||||
path[0].node = elm; \
|
path[0].node = elm; \
|
||||||
path[0].node->field.sle_levels[0].hits++; \
|
|
||||||
cur->pu += path[0].node->field.sle_levels[0].hits; \
|
|
||||||
slist->slh_head->field.sle_levels[slist->slh_head->field.sle_height].hits++; \
|
|
||||||
__skip_rebalance_##decl(slist, len, path); \
|
|
||||||
} \
|
} \
|
||||||
return len; \
|
return len; \
|
||||||
} \
|
} \
|
||||||
|
@ -795,14 +649,24 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
{ \
|
{ \
|
||||||
static __skiplist_path_##decl##_t apath[SKIPLIST_MAX_HEIGHT + 1]; \
|
static __skiplist_path_##decl##_t apath[SKIPLIST_MAX_HEIGHT + 1]; \
|
||||||
int rc = 0; \
|
int rc = 0; \
|
||||||
size_t i, len, loc = 0, current_height, new_height; \
|
size_t i, len, loc = 0, cur_height, new_height; \
|
||||||
decl##_node_t *node; \
|
decl##_node_t *node; \
|
||||||
__skiplist_path_##decl##_t *path = apath; \
|
__skiplist_path_##decl##_t *path = apath; \
|
||||||
\
|
\
|
||||||
if (slist == NULL || new == NULL) \
|
if (slist == NULL || new == NULL) \
|
||||||
return ENOENT; \
|
return ENOENT; \
|
||||||
\
|
\
|
||||||
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * SKIPLIST_MAX_HEIGHT + 1); \
|
/* Allocate a buffer, or use a static one. */ \
|
||||||
|
if (SKIPLIST_MAX_HEIGHT == 1) { \
|
||||||
|
path = malloc(sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
|
if (path == NULL) \
|
||||||
|
return ENOMEM; \
|
||||||
|
} \
|
||||||
|
/* First element in path should be NULL, reset should start pointing at tail. */ \
|
||||||
|
path[0].node = NULL; \
|
||||||
|
for (i = 1; i < slist->slh_max_height + 1; i++) { \
|
||||||
|
path[i].node = slist->slh_tail; \
|
||||||
|
} \
|
||||||
\
|
\
|
||||||
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
||||||
len = __skip_locate_##decl(slist, new, path); \
|
len = __skip_locate_##decl(slist, new, path); \
|
||||||
|
@ -812,12 +676,12 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
/* Don't insert, duplicate if flag not set. */ \
|
/* Don't insert, duplicate if flag not set. */ \
|
||||||
return -1; \
|
return -1; \
|
||||||
} \
|
} \
|
||||||
current_height = slist->slh_head->field.sle_height - 1; \
|
/* Coin toss to determine level of this new node [0, max) */ \
|
||||||
/* Coin toss to determine level of this new node [0, current max height) */ \
|
cur_height = slist->slh_head->field.sle_height; \
|
||||||
new_height = __skip_toss_##decl(slist, current_height); \
|
new_height = __skip_toss_##decl(slist, slist->slh_max_height - 1); \
|
||||||
new->field.sle_height = new_height; \
|
new->field.sle_height = new_height; \
|
||||||
/* Trim the path to at most the new height for the new node. */ \
|
/* Trim the path to at most the new height for the new node. */ \
|
||||||
for (i = current_height + 1; i <= new_height; i++) { \
|
for (i = cur_height + 1; i <= new_height; i++) { \
|
||||||
path[i + 1].node = slist->slh_tail; \
|
path[i + 1].node = slist->slh_tail; \
|
||||||
} \
|
} \
|
||||||
/* Ensure all next[] point to tail. */ \
|
/* Ensure all next[] point to tail. */ \
|
||||||
|
@ -838,19 +702,29 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
new->field.sle_levels[i].next = slist->slh_tail; \
|
new->field.sle_levels[i].next = slist->slh_tail; \
|
||||||
} \
|
} \
|
||||||
} \
|
} \
|
||||||
/* Adjust the previous pointers in the nodes. */ \
|
/* Ensure all slh_head->next[] above loc point to tail. */ \
|
||||||
|
if (path[1].node == slist->slh_head) { \
|
||||||
|
__SKIP_ENTRIES_B2T_FROM(field, slist->slh_head, loc + 1) \
|
||||||
|
{ \
|
||||||
|
slist->slh_head->field.sle_levels[lvl].next = slist->slh_tail; \
|
||||||
|
} \
|
||||||
|
} \
|
||||||
|
/* Adujust the previous pointers in the nodes. */ \
|
||||||
new->field.sle_prev = path[1].node; \
|
new->field.sle_prev = path[1].node; \
|
||||||
new->field.sle_levels[0].next->field.sle_prev = new; \
|
new->field.sle_levels[0].next->field.sle_prev = new; \
|
||||||
/* Account for insert at tail. */ \
|
/* Account for insert at tail. */ \
|
||||||
if (new->field.sle_levels[0].next == slist->slh_tail) \
|
if (new->field.sle_levels[0].next == slist->slh_tail) \
|
||||||
slist->slh_tail->field.sle_prev = new; \
|
slist->slh_tail->field.sle_prev = new; \
|
||||||
|
/* Adjust the head/tail boundary node heights if necessary. */ \
|
||||||
|
if (new_height > cur_height) { \
|
||||||
|
slist->slh_head->field.sle_height = new_height; \
|
||||||
|
slist->slh_tail->field.sle_height = new_height; \
|
||||||
|
} \
|
||||||
/* Record the era for this node to enable snapshots. */ \
|
/* Record the era for this node to enable snapshots. */ \
|
||||||
if (slist->slh_snap.pres_era > 0) { \
|
if (slist->slh_snap.pres_era > 0) { \
|
||||||
/* Increase the list's era/age and record it. */ \
|
/* Increase the the list's era/age and record it. */ \
|
||||||
new->field.sle_era = slist->slh_snap.cur_era++; \
|
new->field.sle_era = slist->slh_snap.cur_era++; \
|
||||||
} \
|
} \
|
||||||
/* Set hits for re-balancing to 1 when newborn. */ \
|
|
||||||
new->field.sle_levels[new_height].hits = 1; \
|
|
||||||
/* Increase our list length (aka. size, count, etc.) by one. */ \
|
/* Increase our list length (aka. size, count, etc.) by one. */ \
|
||||||
slist->slh_length++; \
|
slist->slh_length++; \
|
||||||
\
|
\
|
||||||
|
@ -893,11 +767,18 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
decl##_node_t *node = NULL; \
|
decl##_node_t *node = NULL; \
|
||||||
__skiplist_path_##decl##_t *path = apath; \
|
__skiplist_path_##decl##_t *path = apath; \
|
||||||
\
|
\
|
||||||
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * SKIPLIST_MAX_HEIGHT + 1); \
|
/* Allocate a buffer, or use a static one. */ \
|
||||||
|
if (SKIPLIST_MAX_HEIGHT == 1) { \
|
||||||
|
path = malloc(sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
|
if (path == NULL) \
|
||||||
|
goto done; \
|
||||||
|
} \
|
||||||
|
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
\
|
\
|
||||||
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
||||||
__skip_locate_##decl(slist, query, path); \
|
__skip_locate_##decl(slist, query, path); \
|
||||||
node = path[0].node; \
|
node = path[0].node; \
|
||||||
|
done:; \
|
||||||
if (SKIPLIST_MAX_HEIGHT == 1) \
|
if (SKIPLIST_MAX_HEIGHT == 1) \
|
||||||
free(path); \
|
free(path); \
|
||||||
\
|
\
|
||||||
|
@ -918,7 +799,13 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
decl##_node_t *node; \
|
decl##_node_t *node; \
|
||||||
__skiplist_path_##decl##_t *path = apath; \
|
__skiplist_path_##decl##_t *path = apath; \
|
||||||
\
|
\
|
||||||
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * SKIPLIST_MAX_HEIGHT + 1); \
|
/* Allocate a buffer, or use a static one. */ \
|
||||||
|
if (SKIPLIST_MAX_HEIGHT == 1) { \
|
||||||
|
path = malloc(sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
|
if (path == NULL) \
|
||||||
|
goto done; \
|
||||||
|
} \
|
||||||
|
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
\
|
\
|
||||||
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
||||||
__skip_locate_##decl(slist, query, path); \
|
__skip_locate_##decl(slist, query, path); \
|
||||||
|
@ -927,6 +814,8 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
node = node->field.sle_levels[0].next; \
|
node = node->field.sle_levels[0].next; \
|
||||||
cmp = __skip_compare_nodes_##decl(slist, node, query, slist->slh_aux); \
|
cmp = __skip_compare_nodes_##decl(slist, node, query, slist->slh_aux); \
|
||||||
} while (cmp < 0); \
|
} while (cmp < 0); \
|
||||||
|
\
|
||||||
|
done:; \
|
||||||
if (SKIPLIST_MAX_HEIGHT == 1) \
|
if (SKIPLIST_MAX_HEIGHT == 1) \
|
||||||
free(path); \
|
free(path); \
|
||||||
\
|
\
|
||||||
|
@ -937,7 +826,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
* -- skip_position_gt_ \
|
* -- skip_position_gt_ \
|
||||||
* \
|
* \
|
||||||
* Position and return a cursor at the first node that is greater than \
|
* Position and return a cursor at the first node that is greater than \
|
||||||
* the provided node `n`. If the largest key is less than the key in `n` \
|
* the provided node `n`. If the largestkey is less than the key in `n` \
|
||||||
* return NULL. \
|
* return NULL. \
|
||||||
*/ \
|
*/ \
|
||||||
decl##_node_t *prefix##skip_position_gt_##decl(decl##_t *slist, decl##_node_t *query) \
|
decl##_node_t *prefix##skip_position_gt_##decl(decl##_t *slist, decl##_node_t *query) \
|
||||||
|
@ -947,7 +836,13 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
decl##_node_t *node; \
|
decl##_node_t *node; \
|
||||||
__skiplist_path_##decl##_t *path = apath; \
|
__skiplist_path_##decl##_t *path = apath; \
|
||||||
\
|
\
|
||||||
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * SKIPLIST_MAX_HEIGHT + 1); \
|
/* Allocate a buffer, or use a static one. */ \
|
||||||
|
if (SKIPLIST_MAX_HEIGHT == 1) { \
|
||||||
|
path = malloc(sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
|
if (path == NULL) \
|
||||||
|
goto done; \
|
||||||
|
} \
|
||||||
|
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
\
|
\
|
||||||
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
||||||
__skip_locate_##decl(slist, query, path); \
|
__skip_locate_##decl(slist, query, path); \
|
||||||
|
@ -958,6 +853,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
node = node->field.sle_levels[0].next; \
|
node = node->field.sle_levels[0].next; \
|
||||||
cmp = __skip_compare_nodes_##decl(slist, node, query, slist->slh_aux); \
|
cmp = __skip_compare_nodes_##decl(slist, node, query, slist->slh_aux); \
|
||||||
} while (cmp <= 0 && node != slist->slh_tail); \
|
} while (cmp <= 0 && node != slist->slh_tail); \
|
||||||
|
\
|
||||||
done:; \
|
done:; \
|
||||||
if (SKIPLIST_MAX_HEIGHT == 1) \
|
if (SKIPLIST_MAX_HEIGHT == 1) \
|
||||||
free(path); \
|
free(path); \
|
||||||
|
@ -978,7 +874,13 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
decl##_node_t *node; \
|
decl##_node_t *node; \
|
||||||
__skiplist_path_##decl##_t *path = apath; \
|
__skiplist_path_##decl##_t *path = apath; \
|
||||||
\
|
\
|
||||||
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * SKIPLIST_MAX_HEIGHT + 1); \
|
/* Allocate a buffer, or use a static one. */ \
|
||||||
|
if (SKIPLIST_MAX_HEIGHT == 1) { \
|
||||||
|
path = malloc(sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
|
if (path == NULL) \
|
||||||
|
goto done; \
|
||||||
|
} \
|
||||||
|
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
\
|
\
|
||||||
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
||||||
__skip_locate_##decl(slist, query, path); \
|
__skip_locate_##decl(slist, query, path); \
|
||||||
|
@ -986,6 +888,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
if (node) \
|
if (node) \
|
||||||
goto done; \
|
goto done; \
|
||||||
node = path[1].node; \
|
node = path[1].node; \
|
||||||
|
\
|
||||||
done:; \
|
done:; \
|
||||||
if (SKIPLIST_MAX_HEIGHT == 1) \
|
if (SKIPLIST_MAX_HEIGHT == 1) \
|
||||||
free(path); \
|
free(path); \
|
||||||
|
@ -1005,11 +908,19 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
decl##_node_t *node; \
|
decl##_node_t *node; \
|
||||||
__skiplist_path_##decl##_t *path = apath; \
|
__skiplist_path_##decl##_t *path = apath; \
|
||||||
\
|
\
|
||||||
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * SKIPLIST_MAX_HEIGHT + 1); \
|
/* Allocate a buffer, or use a static one. */ \
|
||||||
|
if (SKIPLIST_MAX_HEIGHT == 1) { \
|
||||||
|
path = malloc(sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
|
if (path == NULL) \
|
||||||
|
goto done; \
|
||||||
|
} \
|
||||||
|
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
\
|
\
|
||||||
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
|
||||||
__skip_locate_##decl(slist, query, path); \
|
__skip_locate_##decl(slist, query, path); \
|
||||||
node = path[1].node; \
|
node = path[1].node; \
|
||||||
|
\
|
||||||
|
done:; \
|
||||||
if (SKIPLIST_MAX_HEIGHT == 1) \
|
if (SKIPLIST_MAX_HEIGHT == 1) \
|
||||||
free(path); \
|
free(path); \
|
||||||
\
|
\
|
||||||
|
@ -1065,7 +976,13 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
if (slist == NULL) \
|
if (slist == NULL) \
|
||||||
return -1; \
|
return -1; \
|
||||||
\
|
\
|
||||||
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * SKIPLIST_MAX_HEIGHT + 1); \
|
/* Allocate a buffer, or use a static one. */ \
|
||||||
|
if (SKIPLIST_MAX_HEIGHT == 1) { \
|
||||||
|
path = malloc(sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
|
if (path == NULL) \
|
||||||
|
return ENOMEM; \
|
||||||
|
} \
|
||||||
|
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
\
|
\
|
||||||
__skip_locate_##decl(slist, query, path); \
|
__skip_locate_##decl(slist, query, path); \
|
||||||
node = path[0].node; \
|
node = path[0].node; \
|
||||||
|
@ -1085,7 +1002,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
if (np > 0) \
|
if (np > 0) \
|
||||||
return np; \
|
return np; \
|
||||||
\
|
\
|
||||||
/* Increase the list's era/age. */ \
|
/* Increase the the list's era/age. */ \
|
||||||
slist->slh_snap.cur_era++; \
|
slist->slh_snap.cur_era++; \
|
||||||
} \
|
} \
|
||||||
\
|
\
|
||||||
|
@ -1112,7 +1029,13 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
if (slist->slh_length == 0) \
|
if (slist->slh_length == 0) \
|
||||||
return 0; \
|
return 0; \
|
||||||
\
|
\
|
||||||
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * SKIPLIST_MAX_HEIGHT + 1); \
|
/* Allocate a buffer */ \
|
||||||
|
if (SKIPLIST_MAX_HEIGHT == 1) { \
|
||||||
|
path = malloc(sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
|
if (path == NULL) \
|
||||||
|
return ENOMEM; \
|
||||||
|
} \
|
||||||
|
memset(path, 0, sizeof(__skiplist_path_##decl##_t) * slist->slh_max_height + 1); \
|
||||||
\
|
\
|
||||||
/* Attempt to locate the node in the list. */ \
|
/* Attempt to locate the node in the list. */ \
|
||||||
len = __skip_locate_##decl(slist, query, path); \
|
len = __skip_locate_##decl(slist, query, path); \
|
||||||
|
@ -1127,7 +1050,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
if (np > 0) \
|
if (np > 0) \
|
||||||
return np; \
|
return np; \
|
||||||
\
|
\
|
||||||
/* Increase the list's era/age. */ \
|
/* Increase the the list's era/age. */ \
|
||||||
slist->slh_snap.cur_era++; \
|
slist->slh_snap.cur_era++; \
|
||||||
} \
|
} \
|
||||||
/* We found it, set the next->prev to the node->prev keeping in mind \
|
/* We found it, set the next->prev to the node->prev keeping in mind \
|
||||||
|
@ -1140,8 +1063,8 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
break; \
|
break; \
|
||||||
/* ... adjust the next pointer at that level. */ \
|
/* ... adjust the next pointer at that level. */ \
|
||||||
path[i + 1].node->field.sle_levels[i].next = node->field.sle_levels[i].next; \
|
path[i + 1].node->field.sle_levels[i].next = node->field.sle_levels[i].next; \
|
||||||
/* Adjust the height such that we're only pointing at the tail once at \
|
/* Adjust the height so we're only pointing at the tail once at \
|
||||||
the top that way we don't waste steps later when searching. */ \
|
the top so we don't waste steps later when searching. */ \
|
||||||
if (path[i + 1].node->field.sle_levels[i].next == slist->slh_tail) { \
|
if (path[i + 1].node->field.sle_levels[i].next == slist->slh_tail) { \
|
||||||
height = path[i + 1].node->field.sle_height; \
|
height = path[i + 1].node->field.sle_height; \
|
||||||
path[i + 1].node->field.sle_height = height - 1; \
|
path[i + 1].node->field.sle_height = height - 1; \
|
||||||
|
@ -1156,16 +1079,15 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
free(path); \
|
free(path); \
|
||||||
\
|
\
|
||||||
slist->slh_fns.free_entry(node); \
|
slist->slh_fns.free_entry(node); \
|
||||||
free(node); \
|
|
||||||
\
|
\
|
||||||
/* Reduce the height of the head/tail nodes. */ \
|
/* Reduce the height of the head node. */ \
|
||||||
for (i = 0; slist->slh_head->field.sle_levels[i].next != slist->slh_tail && i < SKIPLIST_MAX_HEIGHT; i++) \
|
i = 0; \
|
||||||
; \
|
while (slist->slh_head->field.sle_levels[i].next != slist->slh_tail && i < slist->slh_head->field.sle_height) \
|
||||||
slist->slh_head->field.sle_levels[i].hits = slist->slh_head->field.sle_levels[slist->slh_head->field.sle_height].hits; \
|
i++; \
|
||||||
slist->slh_head->field.sle_height = slist->slh_tail->field.sle_height = i; \
|
slist->slh_head->field.sle_height = i; \
|
||||||
|
slist->slh_tail->field.sle_height = i; \
|
||||||
\
|
\
|
||||||
slist->slh_length--; \
|
slist->slh_length--; \
|
||||||
__skip_adjust_hit_counts_##decl(slist); \
|
|
||||||
} \
|
} \
|
||||||
return 0; \
|
return 0; \
|
||||||
} \
|
} \
|
||||||
|
@ -1268,8 +1190,8 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
return 0; \
|
return 0; \
|
||||||
\
|
\
|
||||||
/* (a) alloc, ... */ \
|
/* (a) alloc, ... */ \
|
||||||
size_t sle_arr_sz = sizeof(struct __skiplist_##decl##_level) * slist->slh_head->field.sle_height - 1; \
|
size_t sle_arr_sz = sizeof(struct __skiplist_##decl##_level) * slist->slh_max_height; \
|
||||||
rc = prefix##skip_alloc_node_##decl(&dest); \
|
rc = prefix##skip_alloc_node_##decl(slist, &dest); \
|
||||||
if (rc) \
|
if (rc) \
|
||||||
return rc; \
|
return rc; \
|
||||||
\
|
\
|
||||||
|
@ -1503,29 +1425,21 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
return n_err; \
|
return n_err; \
|
||||||
} \
|
} \
|
||||||
\
|
\
|
||||||
if (slist->slh_head->field.sle_height > SKIPLIST_MAX_HEIGHT) { \
|
if (slist->slh_max_height < 1) { \
|
||||||
__skip_integrity_failure_##decl("skiplist head height > SKIPLIST_MAX_HEIGHT\n"); \
|
__skip_integrity_failure_##decl("skiplist max level must be 1 at minimum\n"); \
|
||||||
n_err++; \
|
n_err++; \
|
||||||
if (flags) \
|
if (flags) \
|
||||||
return n_err; \
|
return n_err; \
|
||||||
} \
|
} \
|
||||||
\
|
\
|
||||||
if (slist->slh_tail->field.sle_height > SKIPLIST_MAX_HEIGHT) { \
|
if (slist->slh_head->field.sle_height >= slist->slh_max_height) { \
|
||||||
__skip_integrity_failure_##decl("skiplist tail height > SKIPLIST_MAX_HEIGHT\n"); \
|
/* level is 0-based, max of 12 means level cannot be > 11 */ \
|
||||||
|
__skip_integrity_failure_##decl("skiplist level %lu in header was >= max %lu\n", slist->slh_head->field.sle_height, slist->slh_max_height); \
|
||||||
n_err++; \
|
n_err++; \
|
||||||
if (flags) \
|
if (flags) \
|
||||||
return n_err; \
|
return n_err; \
|
||||||
} \
|
} \
|
||||||
\
|
\
|
||||||
if (slist->slh_head->field.sle_height != slist->slh_tail->field.sle_height) { \
|
|
||||||
__skip_integrity_failure_##decl("skiplist head & tail height are not equal\n"); \
|
|
||||||
n_err++; \
|
|
||||||
if (flags) \
|
|
||||||
return n_err; \
|
|
||||||
} \
|
|
||||||
\
|
|
||||||
/* TODO: slh_head->field.sle_height should == log(m) where m is the sum of all hits on all nodes */ \
|
|
||||||
\
|
|
||||||
if (SKIPLIST_MAX_HEIGHT < 1) { \
|
if (SKIPLIST_MAX_HEIGHT < 1) { \
|
||||||
__skip_integrity_failure_##decl("SKIPLIST_MAX_HEIGHT cannot be less than 1\n"); \
|
__skip_integrity_failure_##decl("SKIPLIST_MAX_HEIGHT cannot be less than 1\n"); \
|
||||||
n_err++; \
|
n_err++; \
|
||||||
|
@ -1533,6 +1447,14 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
return n_err; \
|
return n_err; \
|
||||||
} \
|
} \
|
||||||
\
|
\
|
||||||
|
if (SKIPLIST_MAX_HEIGHT > 1 && slist->slh_max_height > SKIPLIST_MAX_HEIGHT) { \
|
||||||
|
__skip_integrity_failure_##decl("slist->slh_max_height %lu cannot be greater than SKIPLIST_MAX_HEIGHT %lu\n", slist->slh_max_height, \
|
||||||
|
(size_t)SKIPLIST_MAX_HEIGHT); \
|
||||||
|
n_err++; \
|
||||||
|
if (flags) \
|
||||||
|
return n_err; \
|
||||||
|
} \
|
||||||
|
\
|
||||||
node = slist->slh_head; \
|
node = slist->slh_head; \
|
||||||
__SKIP_ENTRIES_B2T(field, node) \
|
__SKIP_ENTRIES_B2T(field, node) \
|
||||||
{ \
|
{ \
|
||||||
|
@ -1581,9 +1503,8 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
{ \
|
{ \
|
||||||
this = &node->field; \
|
this = &node->field; \
|
||||||
\
|
\
|
||||||
if (this->sle_height > slist->slh_head->field.sle_height) { \
|
if (this->sle_height >= slist->slh_max_height) { \
|
||||||
__skip_integrity_failure_##decl("the %lu node's [%p] height %lu is > head %lu\n", nth, (void *)node, this->sle_height, \
|
__skip_integrity_failure_##decl("the %lu node's [%p] height %lu is >= max %lu\n", nth, (void *)node, this->sle_height, slist->slh_max_height); \
|
||||||
slist->slh_head->field.sle_height); \
|
|
||||||
n_err++; \
|
n_err++; \
|
||||||
if (flags) \
|
if (flags) \
|
||||||
return n_err; \
|
return n_err; \
|
||||||
|
@ -1758,7 +1679,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
{ \
|
{ \
|
||||||
int rc; \
|
int rc; \
|
||||||
decl##_node_t *node; \
|
decl##_node_t *node; \
|
||||||
rc = prefix##skip_alloc_node_##decl(&node); \
|
rc = prefix##skip_alloc_node_##decl(slist, &node); \
|
||||||
if (rc) \
|
if (rc) \
|
||||||
return rc; \
|
return rc; \
|
||||||
node->key = key; \
|
node->key = key; \
|
||||||
|
@ -1779,7 +1700,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
{ \
|
{ \
|
||||||
int rc; \
|
int rc; \
|
||||||
decl##_node_t *node; \
|
decl##_node_t *node; \
|
||||||
rc = prefix##skip_alloc_node_##decl(&node); \
|
rc = prefix##skip_alloc_node_##decl(slist, &node); \
|
||||||
if (rc) \
|
if (rc) \
|
||||||
return rc; \
|
return rc; \
|
||||||
node->key = key; \
|
node->key = key; \
|
||||||
|
@ -1855,6 +1776,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
static void __skip_dot_node_##decl(FILE *os, decl##_t *slist, decl##_node_t *node, size_t nsg, skip_sprintf_node_##decl##_t fn) \
|
static void __skip_dot_node_##decl(FILE *os, decl##_t *slist, decl##_node_t *node, size_t nsg, skip_sprintf_node_##decl##_t fn) \
|
||||||
{ \
|
{ \
|
||||||
char buf[2048]; \
|
char buf[2048]; \
|
||||||
|
size_t width; \
|
||||||
decl##_node_t *next; \
|
decl##_node_t *next; \
|
||||||
\
|
\
|
||||||
__skip_dot_write_node_##decl(os, nsg, node); \
|
__skip_dot_write_node_##decl(os, nsg, node); \
|
||||||
|
@ -1863,9 +1785,8 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
__SKIP_ENTRIES_T2B(field, node) \
|
__SKIP_ENTRIES_T2B(field, node) \
|
||||||
{ \
|
{ \
|
||||||
next = (node->field.sle_levels[lvl].next == slist->slh_tail) ? NULL : node->field.sle_levels[lvl].next; \
|
next = (node->field.sle_levels[lvl].next == slist->slh_tail) ? NULL : node->field.sle_levels[lvl].next; \
|
||||||
(void)__skip_dot_width_##decl; \
|
width = __skip_dot_width_##decl(slist, node, next ? next : slist->slh_tail); \
|
||||||
/* size_t width = __skip_dot_width_##decl(slist, node, next ? next : slist->slh_tail); */ \
|
fprintf(os, " { <w%lu> %lu | <f%lu> ", lvl, width, lvl); \
|
||||||
fprintf(os, " { <w%lu> %lu | <f%lu> ", lvl, node->field.sle_levels[lvl].hits, lvl); \
|
|
||||||
if (next) \
|
if (next) \
|
||||||
fprintf(os, "%p } |", (void *)next); \
|
fprintf(os, "%p } |", (void *)next); \
|
||||||
else \
|
else \
|
||||||
|
@ -1874,7 +1795,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
} \
|
} \
|
||||||
if (fn) { \
|
if (fn) { \
|
||||||
fn(node, buf); \
|
fn(node, buf); \
|
||||||
fprintf(os, " <f0> \u219F %lu \u226B %s \"\n", node->field.sle_height, buf); \
|
fprintf(os, " <f0> \u219F %lu \u226B %s \"\n", node->field.sle_height + 1, buf); \
|
||||||
} else { \
|
} else { \
|
||||||
fprintf(os, " <f0> \u219F %lu \"\n", node->field.sle_height); \
|
fprintf(os, " <f0> \u219F %lu \"\n", node->field.sle_height); \
|
||||||
} \
|
} \
|
||||||
|
@ -1939,15 +1860,15 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
int prefix##skip_dot_##decl(FILE *os, decl##_t *slist, size_t nsg, char *msg, skip_sprintf_node_##decl##_t fn) \
|
int prefix##skip_dot_##decl(FILE *os, decl##_t *slist, size_t nsg, char *msg, skip_sprintf_node_##decl##_t fn) \
|
||||||
{ \
|
{ \
|
||||||
int letitgo = 0; \
|
int letitgo = 0; \
|
||||||
size_t i; \
|
size_t width, i; \
|
||||||
decl##_node_t *node, *next; \
|
decl##_node_t *node, *next; \
|
||||||
\
|
\
|
||||||
if (slist == NULL || fn == NULL) \
|
if (slist == NULL || fn == NULL) \
|
||||||
return nsg; \
|
return nsg; \
|
||||||
/*if (__skip_integrity_check_##decl(slist, 1) != 0) { \
|
if (__skip_integrity_check_##decl(slist, 1) != 0) { \
|
||||||
perror("Skiplist failed integrity checks, impossible to diagram."); \
|
perror("Skiplist failed integrity checks, impossible to diagram."); \
|
||||||
return -1; \
|
return -1; \
|
||||||
}*/ \
|
} \
|
||||||
if (nsg == 0) { \
|
if (nsg == 0) { \
|
||||||
fprintf(os, "digraph Skiplist {\n"); \
|
fprintf(os, "digraph Skiplist {\n"); \
|
||||||
fprintf(os, "label = \"Skiplist.\"\n"); \
|
fprintf(os, "label = \"Skiplist.\"\n"); \
|
||||||
|
@ -1957,9 +1878,9 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
} \
|
} \
|
||||||
fprintf(os, "subgraph cluster%lu {\n", nsg); \
|
fprintf(os, "subgraph cluster%lu {\n", nsg); \
|
||||||
fprintf(os, "style=dashed\n"); \
|
fprintf(os, "style=dashed\n"); \
|
||||||
fprintf(os, "label=\"Skiplist [%lu]", nsg); \
|
fprintf(os, "label=\"Skiplist iteration %lu", nsg); \
|
||||||
if (msg) \
|
if (msg) \
|
||||||
fprintf(os, " %s", msg); \
|
fprintf(os, ", %s", msg); \
|
||||||
fprintf(os, "\"\n\n"); \
|
fprintf(os, "\"\n\n"); \
|
||||||
fprintf(os, "\"HeadNode%lu\" [\n", nsg); \
|
fprintf(os, "\"HeadNode%lu\" [\n", nsg); \
|
||||||
fprintf(os, "label = \""); \
|
fprintf(os, "label = \""); \
|
||||||
|
@ -1973,8 +1894,8 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
__SKIP_ENTRIES_T2B(field, node) \
|
__SKIP_ENTRIES_T2B(field, node) \
|
||||||
{ \
|
{ \
|
||||||
next = (node->field.sle_levels[lvl].next == slist->slh_tail) ? NULL : node->field.sle_levels[lvl].next; \
|
next = (node->field.sle_levels[lvl].next == slist->slh_tail) ? NULL : node->field.sle_levels[lvl].next; \
|
||||||
/* size_t width = __skip_dot_width_##decl(slist, node, next ? next : slist->slh_tail); */ \
|
width = __skip_dot_width_##decl(slist, node, next ? next : slist->slh_tail); \
|
||||||
fprintf(os, "{ %lu | <f%lu> ", node->field.sle_levels[lvl].hits, lvl); \
|
fprintf(os, "{ %lu | <f%lu> ", width, lvl); \
|
||||||
if (next) \
|
if (next) \
|
||||||
fprintf(os, "%p }", (void *)next); \
|
fprintf(os, "%p }", (void *)next); \
|
||||||
else \
|
else \
|
||||||
|
@ -2018,7 +1939,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
|
||||||
} \
|
} \
|
||||||
fflush(os); \
|
fflush(os); \
|
||||||
\
|
\
|
||||||
/* The tail, sentinel node */ \
|
/* The tail, sentinal node */ \
|
||||||
if (letitgo) { \
|
if (letitgo) { \
|
||||||
__skip_dot_write_node_##decl(os, nsg, NULL); \
|
__skip_dot_write_node_##decl(os, nsg, NULL); \
|
||||||
fprintf(os, " [label = \""); \
|
fprintf(os, " [label = \""); \
|
||||||
|
|
Loading…
Reference in a new issue