Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2460 → Rev 2461

/branches/rcu/kernel/test/timeout/timeoutbench1.c
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);