Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2461 → Rev 2456

/branches/rcu/kernel/test/favltree/favltree1.def
File deleted
/branches/rcu/kernel/test/favltree/favltree1.c
File deleted
/branches/rcu/kernel/test/timeout/timeoutbench1.c
29,7 → 29,6
#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>
53,7 → 52,6
* Wrapper tree data structures.
*/
static avltree_t avltree;
static favltree_t favltree;
static extavltree_t extavltree;
static extavlreltree_t extavlreltree;
 
61,7 → 59,6
* 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;
 
69,7 → 66,6
* 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;
 
79,9 → 75,8
unsigned int i;
uint16_t s;
avltree_node_t *a = avl_ffn;
favltree_node_t *b = favl_ffn;
extavltree_node_t *c = extavl_ffn;
extavlreltree_node_t *d = extavlrel_ffn;
extavltree_node_t *b = extavl_ffn;
extavlreltree_node_t *c = extavlrel_ffn;
switch (type) {
case 0:
90,12 → 85,10
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:
103,11 → 96,9
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:
115,11 → 106,9
a->key = i;
b->key = i;
c->key = i;
d->key = i;
a = a->par;
b = b->par;
c = c->par;
d = d->par;
c = c->par;
}
break;
}
132,10 → 121,8
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;
 
155,19 → 142,12
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;
}
178,26 → 158,21
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;
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);
if (!a || !b || !c) {
printf("Deleted nodes: %d, node count: %d, a: %p, b: %p,c: %p ",i,node_count,a,b,c);
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);
}
}
 
211,16 → 186,6
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;
248,12 → 213,6
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;
270,13 → 229,12
*/
static void test1(void)
{
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][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");
353,37 → 311,11
}
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]);
400,9 → 332,6
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]);
417,13 → 346,12
*/
static void test2(void)
{
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][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");
502,39 → 430,11
}
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]);
551,9 → 451,6
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]);
568,13 → 465,12
*/
static void test3(void)
{
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][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");
653,38 → 549,11
}
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]);
701,9 → 570,6
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]);
718,12 → 584,11
*/
static void test4(void)
{
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t s[3][TEST_COUNT],f[3][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;
777,45 → 642,6
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;
899,9 → 725,6
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]);
919,7 → 742,6
 
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);
 
/branches/rcu/kernel/test/test.c
60,7 → 60,6
#include <tasklet/tasklet1.def>
#include <synch/rcu1.def>
#include <avltree/avltree1.def>
#include <favltree/favltree1.def>
#include <extavltree/extavltree1.def>
#include <extavlreltree/extavlreltree1.def>
#include <timeout/timeout1.def>
/branches/rcu/kernel/test/test.h
72,7 → 72,6
extern char * test_tasklet1(bool quiet);
extern char * test_rcu1(bool quiet);
extern char * test_avltree1(bool quiet);
extern char * test_favltree1(bool quiet);
extern char * test_extavltree1(bool quiet);
extern char * test_extavlreltree1(bool quiet);
extern char * test_timeout1(bool quiet);