29,6 → 29,7 |
#include <test.h> |
#include <print.h> |
#include <adt/avl.h> |
#include <adt/favl.h> |
#include <adt/extavl.h> |
#include <adt/extavlrel.h> |
#include <debug.h> |
52,6 → 53,7 |
* Wrapper tree data structures. |
*/ |
static avltree_t avltree; |
static favltree_t favltree; |
static extavltree_t extavltree; |
static extavlreltree_t extavlreltree; |
|
59,6 → 61,7 |
* Slab cache variables. |
*/ |
static slab_cache_t *avl_slab; |
static slab_cache_t *favl_slab; |
static slab_cache_t *extavl_slab; |
static slab_cache_t *extavlrel_slab; |
|
66,6 → 69,7 |
* Head of free nodes' list: |
*/ |
static avltree_node_t *avl_ffn = NULL; |
static favltree_node_t *favl_ffn = NULL; |
static extavltree_node_t *extavl_ffn = NULL; |
static extavlreltree_node_t *extavlrel_ffn = NULL; |
|
75,8 → 79,9 |
unsigned int i; |
uint16_t s; |
avltree_node_t *a = avl_ffn; |
extavltree_node_t *b = extavl_ffn; |
extavlreltree_node_t *c = extavlrel_ffn; |
favltree_node_t *b = favl_ffn; |
extavltree_node_t *c = extavl_ffn; |
extavlreltree_node_t *d = extavlrel_ffn; |
|
switch (type) { |
case 0: |
85,10 → 90,12 |
a->key = s; |
b->key = s; |
c->key = s; |
d->key = s; |
s += GEN_NUM; |
a = a->par; |
b = b->par; |
c = c->par; |
d = d->par; |
} |
break; |
case 1: |
96,9 → 103,11 |
a->key = i; |
b->key = i; |
c->key = i; |
d->key = i; |
a = a->par; |
b = b->par; |
c = c->par; |
d = d->par; |
} |
break; |
case 2: |
106,9 → 115,11 |
a->key = i; |
b->key = i; |
c->key = i; |
d->key = i; |
a = a->par; |
b = b->par; |
c = c->par; |
c = c->par; |
d = d->par; |
} |
break; |
} |
121,8 → 132,10 |
avltree_node_t *a; |
extavltree_node_t *b; |
extavlreltree_node_t *c; |
favltree_node_t *d; |
|
avl_ffn = NULL; |
favl_ffn = NULL; |
extavl_ffn = NULL; |
extavlrel_ffn = NULL; |
|
142,12 → 155,19 |
printf("Not enough memory to allocate test arrays."); |
return false; |
} |
d = (favltree_node_t *) slab_alloc(favl_slab,0); |
if (!d) { |
printf("Not enough memory to allocate test arrays."); |
return false; |
} |
a->par = avl_ffn; |
b->par = extavl_ffn; |
c->par = extavlrel_ffn; |
d->par = favl_ffn; |
avl_ffn = a; |
extavl_ffn = b; |
extavlrel_ffn = c; |
favl_ffn = d; |
} |
return true; |
} |
158,21 → 178,26 |
avltree_node_t *a; |
extavltree_node_t *b; |
extavlreltree_node_t *c; |
favltree_node_t *d; |
|
for (i = 0; i < node_count; i++) { |
a = avl_ffn; |
b = extavl_ffn; |
c = extavlrel_ffn; |
if (!a || !b || !c) { |
printf("Deleted nodes: %d, node count: %d, a: %p, b: %p,c: %p ",i,node_count,a,b,c); |
d = favl_ffn; |
if (!a || !b || !c || !d) { |
printf("Deleted nodes: %d, node count: %d, a: %p, b: %p, c: %p, d: %p\n", |
i,node_count,a,b,c,d); |
panic("Some nodes have been lost!"); |
} |
avl_ffn = avl_ffn->par; |
extavl_ffn = extavl_ffn->par; |
extavlrel_ffn = extavlrel_ffn->par; |
favl_ffn = favl_ffn->par; |
slab_free(avl_slab,a); |
slab_free(extavl_slab,b); |
slab_free(extavlrel_slab,c); |
slab_free(favl_slab,d); |
} |
} |
|
186,6 → 211,16 |
return node; |
} |
|
static favltree_node_t *alloc_favltree_node(void) |
{ |
favltree_node_t *node; |
|
node = favl_ffn; |
favl_ffn = favl_ffn->par; |
|
return node; |
} |
|
static extavltree_node_t *alloc_extavltree_node(void) |
{ |
extavltree_node_t *node; |
213,6 → 248,12 |
avl_ffn = node; |
} |
|
static void free_favltree_node(favltree_node_t *node) |
{ |
node->par = favl_ffn; |
favl_ffn = node; |
} |
|
static void free_extavltree_node(extavltree_node_t *node) |
{ |
node->par = extavl_ffn; |
229,12 → 270,13 |
*/ |
static void test1(void) |
{ |
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT]; |
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT]; |
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
unsigned int i,ii; |
avltree_node_t *a; |
extavltree_node_t *b; |
extavlreltree_node_t *c; |
favltree_node_t *d; |
|
|
printf("INSERT nodes with keys of ascending sequence.\n"); |
311,11 → 353,37 |
} |
|
df[2][ii] = get_cycle(); |
|
/* |
* FAVL INSERT |
*/ |
s[3][ii] = get_cycle(); |
|
favltree_create(&favltree); |
for (i = 0; i < node_count[ii]; i++) { |
favltree_insert(&favltree,alloc_favltree_node()); |
} |
|
f[3][ii] = get_cycle(); |
/* |
* FAVL DELETE |
*/ |
ds[3][ii] = get_cycle(); |
|
while ((d = favltree.root) != NULL) { |
favltree_delete(&favltree,d); |
free_favltree_node(d); |
} |
|
df[3][ii] = get_cycle(); |
} |
printf("\n----------------------------------------------------------------------------"); |
printf("\nAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[0][ii]-s[0][ii]); |
printf("\nFAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[3][ii]-s[3][ii]); |
printf("\nExtAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[1][ii]-s[1][ii]); |
332,6 → 400,9 |
printf("\nAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[0][ii]-ds[0][ii]); |
printf("\nAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[3][ii]-ds[3][ii]); |
printf("\nExtAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[1][ii]-ds[1][ii]); |
346,12 → 417,13 |
*/ |
static void test2(void) |
{ |
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT]; |
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT]; |
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
unsigned int i,ii; |
avltree_node_t *a; |
extavltree_node_t *b; |
extavlreltree_node_t *c; |
favltree_node_t *d; |
|
|
printf("INSERT nodes with keys of descending sequence.\n"); |
430,11 → 502,39 |
} |
|
df[2][ii] = get_cycle(); |
|
/* |
* FAVL INSERT |
*/ |
s[3][ii] = get_cycle(); |
|
favltree_create(&favltree); |
for (i = 0; i < node_count[ii]; i++) { |
favltree_insert(&favltree,alloc_favltree_node()); |
} |
|
f[3][ii] = get_cycle(); |
/* |
* AVL DELETE |
*/ |
ds[3][ii] = get_cycle(); |
|
while (favltree.root != NULL) { |
d = favltree_find_min(&favltree); |
favltree_delete_min(&favltree); |
free_favltree_node(d); |
} |
|
df[3][ii] = get_cycle(); |
|
} |
printf("\n----------------------------------------------------------------------------"); |
printf("\nAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[0][ii]-s[0][ii]); |
printf("\nFAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[3][ii]-s[3][ii]); |
printf("\nExtAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[1][ii]-s[1][ii]); |
451,6 → 551,9 |
printf("\nAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[0][ii]-ds[0][ii]); |
printf("\nFAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[3][ii]-ds[3][ii]); |
printf("\nExtAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[1][ii]-ds[1][ii]); |
465,12 → 568,13 |
*/ |
static void test3(void) |
{ |
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT]; |
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT]; |
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT]; |
unsigned int i,ii; |
avltree_node_t *a; |
extavltree_node_t *b; |
extavlreltree_node_t *c; |
favltree_node_t *d; |
|
|
printf("INSERT nodes with keys of random sequence 1-65536.\n"); |
549,11 → 653,38 |
} |
|
df[2][ii] = get_cycle(); |
|
/* |
* FAVL INSERT |
*/ |
s[3][ii] = get_cycle(); |
|
favltree_create(&favltree); |
for (i = 0; i < node_count[ii]; i++) { |
favltree_insert(&favltree,alloc_favltree_node()); |
} |
|
f[3][ii] = get_cycle(); |
/* |
* AVL DELETE |
*/ |
ds[3][ii] = get_cycle(); |
|
while (favltree.root != NULL) { |
d = favltree_find_min(&favltree); |
favltree_delete_min(&favltree); |
free_favltree_node(d); |
} |
|
df[3][ii] = get_cycle(); |
} |
printf("\n----------------------------------------------------------------------------"); |
printf("\nAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[0][ii]-s[0][ii]); |
printf("\nFAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[3][ii]-s[3][ii]); |
printf("\nExtAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[1][ii]-s[1][ii]); |
570,6 → 701,9 |
printf("\nAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[0][ii]-ds[0][ii]); |
printf("\nFAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[3][ii]-ds[3][ii]); |
printf("\nExtAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",df[1][ii]-ds[1][ii]); |
584,11 → 718,12 |
*/ |
static void test4(void) |
{ |
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT]; |
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT]; |
unsigned int i,ii; |
avltree_node_t *a; |
extavltree_node_t *b; |
extavlreltree_node_t *c; |
favltree_node_t *d; |
uint64_t r; |
uint16_t rr; |
unsigned int mn,nc; |
642,6 → 777,45 |
f[0][ii] = get_cycle(); |
|
/* |
* FAVL |
*/ |
rr = r; |
nc = 0; |
s[3][ii] = get_cycle(); |
|
avltree_create(&avltree); |
for (i = 0; i < OPERATION_COUNT; i++) { |
if (((rr % mn) <= nc) && nc) { |
/* |
* Delete min. |
*/ |
d = favltree_find_min(&favltree); |
favltree_delete_min(&favltree); |
free_favltree_node(d); |
nc--; |
} else { |
/* |
* Insert. |
*/ |
d = alloc_favltree_node(); |
d->key = rr; |
favltree_insert(&favltree,d); |
nc++; |
} |
rr += GEN_NUM; |
} |
/* |
* Delete rest tree. |
*/ |
while (favltree.root != NULL) { |
d = favltree_find_min(&favltree); |
favltree_delete_min(&favltree); |
free_favltree_node(d); |
} |
|
f[3][ii] = get_cycle(); |
|
/* |
* ExtAVL |
*/ |
rr = r; |
725,6 → 899,9 |
printf("\nAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[0][ii]-s[0][ii]); |
printf("\nFAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[3][ii]-s[3][ii]); |
printf("\nExtAVL\t\t"); |
for (ii = 0; ii < TEST_COUNT; ii++) |
printf("%20llu",f[1][ii]-s[1][ii]); |
742,6 → 919,7 |
|
|
avl_slab = slab_cache_create("avl_slab",sizeof(avltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
favl_slab = slab_cache_create("favl_slab",sizeof(favltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
extavl_slab = slab_cache_create("extavl_slab",sizeof(extavltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
extavlrel_slab = slab_cache_create("extavlrel_slab",sizeof(extavlreltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
|