HelenOSHelenOS-docHelenOS-historic

Català-Valencià – Catalan中文 – Chinese (Simplified)中文 – Chinese (Traditional)Česky – CzechDansk – DanishNederlands – DutchEnglish – EnglishSuomi – FinnishFrançais – FrenchDeutsch – Germanעברית – Hebrewहिंदी – HindiMagyar – HungarianBahasa Indonesia – IndonesianItaliano – Italian日本語 – Japanese한국어 – KoreanМакедонски – Macedonianमराठी – MarathiNorsk – NorwegianPolski – PolishPortuguês – PortuguesePortuguês – Portuguese (Brazil)Русский – RussianSlovenčina – SlovakSlovenščina – SlovenianEspañol – SpanishSvenska – SwedishTürkçe – TurkishУкраїнська – UkrainianOëzbekcha – Uzbek

Compare Revisions

• This comparison shows the changes necessary to convert path

  → /branches/rcu/kernel/test @ 2456

  → /branches/rcu/kernel/test/ @ 2461

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

Ignore whitespace Rev 2456 → 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);

/branches/rcu/kernel/test/test.c
60,6 → 60,7
#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,6 → 72,7
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);

/branches/rcu/kernel/test/favltree/favltree1.def
0,0 → 1,6
{
"favltree1",
"Test Fast Avl tree operations",
&test_favltree1,
true
},

/branches/rcu/kernel/test/favltree/favltree1.c
0,0 → 1,289
/*
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <test.h>
#include <print.h>
#include <adt/favl.h>
#include <debug.h>
#define NODE_COUNT 100
/*
* wrapper structure with a pointer to favl tree root
*/
static favltree_t favltree;
/*
* favl tree nodes in array for faster allocating
*/
static favltree_node_t favltree_nodes[NODE_COUNT];
/*
* head of free nodes' list:
*/
static favltree_node_t *first_free_node = NULL;
static int test_tree_balance(favltree_node_t *node);
static favltree_node_t *test_tree_parents(favltree_node_t *node);
static void print_tree_structure_flat (favltree_node_t *node, int level);
static favltree_node_t *alloc_favltree_node(void);
static favltree_node_t *test_tree_parents(favltree_node_t *node)
{
favltree_node_t *tmp;
if (!node) return NULL;
if (node->lft) {
tmp = test_tree_parents(node->lft);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->lft);
}
}
if (node->rgt) {
tmp = test_tree_parents(node->rgt);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->rgt);
}
}
return node->par;
}
int test_tree_balance(favltree_node_t *node)
{
int h1, h2, diff;
if (!node) return 0;
h1 = test_tree_balance(node->lft);
h2 = test_tree_balance(node->rgt);
diff = h2 - h1;
if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
printf("Bad balance\n");
}
return h1 > h2 ? h1 + 1 : h2 + 1;
}
/**
* Prints the structure of node, which is level levels from the top of the tree.
*/
static void print_tree_structure_flat (favltree_node_t *node, int level)
{
/* You can set the maximum level as high as you like.
Most of the time, you'll want to debug code using small trees,
so that a large level indicates a loop, which is a bug. */
if (level > 16)
{
printf ("[...]");
return;
}
if (node == NULL)
return;
printf ("%d[%d]", node->key,node->balance);
if (node->lft != NULL || node->rgt != NULL)
{
printf("(");
print_tree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
printf(",");
print_tree_structure_flat (node->rgt, level + 1);
}
printf(")");
}
}
//****************************************************************
static void alloc_favltree_node_prepare(void)
{
int i;
for (i = 0; i < NODE_COUNT - 1; i++) {
favltree_nodes[i].par = &(favltree_nodes[i+1]);
}
/*
* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
*/
// First tree node and same key
favltree_nodes[0].key = 60;
favltree_nodes[1].key = 60;
favltree_nodes[2].key = 60;
//LL rotation
favltree_nodes[3].key = 50;
favltree_nodes[4].key = 40;
favltree_nodes[5].key = 30;
//LR rotation
favltree_nodes[6].key = 20;
favltree_nodes[7].key = 20;
favltree_nodes[8].key = 25;
favltree_nodes[9].key = 25;
//LL rotation in lower floor
favltree_nodes[10].key = 35;
//RR rotation
favltree_nodes[11].key = 70;
favltree_nodes[12].key = 80;
//RL rotation
favltree_nodes[13].key = 90;
favltree_nodes[14].key = 85;
//Insert 0 key
favltree_nodes[15].key = 0;
favltree_nodes[16].key = 0;
//Insert reverse
favltree_nodes[17].key = 600;
favltree_nodes[18].key = 500;
favltree_nodes[19].key = 400;
favltree_nodes[20].key = 300;
for (i = 21; i < NODE_COUNT; i++)
favltree_nodes[i].key = i * 3;
favltree_nodes[i].par = NULL;
first_free_node = &(favltree_nodes[0]);
}
static favltree_node_t *alloc_favltree_node(void)
{
favltree_node_t *node;
node = first_free_node;
first_free_node = first_free_node->par;
return node;
}
//****************************************************************
static void test_tree_insert(favltree_t *tree, unsigned int node_count, int quiet)
{
unsigned int i;
favltree_node_t *newnode;
/*
* Initialize tree before using.
*/
favltree_create(tree);
if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
for (i = 0; i < node_count; i++) {
newnode = alloc_favltree_node();
//if (!quiet) printf("[[[%d]]]\n",newnode->key);
favltree_insert(tree, newnode);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
if (!quiet) printf("Inserting was finished\n");
}
static void test_tree_delete(favltree_t *tree, int node_count, int node_position, bool quiet)
{
favltree_node_t *delnode;
unsigned int i;
//aktualni pocet tiku:
if (!quiet) printf("Deleting tree...\n");
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\nDelete root nodes\n");
while(tree->root != NULL) {
delnode = tree->root;
favltree_delete(tree,delnode);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
break;
case 1:
if (!quiet) printf("\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
favltree_delete(tree,&(favltree_nodes[i]));
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
break;
}
if (!quiet) printf("Deletion was finished\n");
}
static void timeout_tree(favltree_t *tree, int node_count, bool quiet)
{
int i = 0;
if (!quiet) printf("\nTimeout tree ...\n");
while(tree->root != NULL) {
i++;
favltree_delete_min(tree);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");
if (!quiet) printf("Timeout tree finished\n");
}
char * test_favltree1(bool quiet)
{
alloc_favltree_node_prepare();
test_tree_insert(&favltree, NODE_COUNT, quiet);
test_tree_delete(&favltree, NODE_COUNT, 0, quiet);
alloc_favltree_node_prepare();
test_tree_insert(&favltree, NODE_COUNT, quiet);
test_tree_delete(&favltree, NODE_COUNT, 1, quiet);
alloc_favltree_node_prepare();
test_tree_insert(&favltree, NODE_COUNT, quiet);
timeout_tree(&favltree, NODE_COUNT, quiet);
return NULL;
}