Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2416 → Rev 2421

/branches/rcu/kernel/test/extavltree/extavltree1.c
57,7 → 57,7
static extavltree_node_t *exttree_test_parents(extavltree_node_t *node);
static void print_exttree_structure_flat (extavltree_node_t *node, int level);
static bool exttree_test_link(int node_count);
static void print_exttree_link(int node_count);
static void print_exttree_link(void);
static extavltree_node_t *alloc_extavltree_node(void);
 
 
124,7 → 124,7
test_link = false;
}
}
if (node_count && i != node_count) {
if (i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
134,7 → 134,7
test_link = false;
}
}
if (node_count && i != node_count) {
if (i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
180,7 → 180,7
/** Prints list of nodes
*
*/
static void print_exttree_link(int node_count)
static void print_exttree_link(void)
{
extavltree_node_t *node;
printf("\n");
260,7 → 260,7
*/
extavltree_create(tree);
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_extavltree_node();
269,7 → 269,7
extavltree_insert(tree, newnode);
if (!quiet) {
if (!exttree_test_link(i+1)) {
print_exttree_link(i+1);
print_exttree_link();
printf("\n");
}
exttree_test_parents(tree->root);
310,14 → 310,14
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\n\nDelete root nodes\n");
i = node_count;
if (!quiet) printf("\nDelete root nodes\n");
i = node_count - 1;
while(tree->root != NULL) {
delnode = tree->root;
extavltree_delete(tree,delnode);
if (!quiet) {
if (!exttree_test_link(i)) {
print_exttree_link(i);
print_exttree_link();
printf("\n");
}
exttree_test_parents(tree->root);
328,12 → 328,12
break;
case 1:
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
if (!quiet) printf("\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
extavltree_delete(tree,&(extavltree_nodes[i]));
if (!quiet) {
if (!exttree_test_link(i+1)) {
print_exttree_link(i+1);
if (!exttree_test_link(node_count-i-1)) {
print_exttree_link();
printf("\n");
}
exttree_test_parents(tree->root);
349,15 → 349,15
 
static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)
{
int i = node_count;
int i = node_count - 1;
if (!quiet) printf("Timeout tree ...\n");
if (!quiet) printf("\nTimeout tree ...\n");
while(tree->head.next != &(tree->head)) {
extavltree_delete_min(tree);
if (!quiet) {
if (!exttree_test_link(i)) {
print_exttree_link(i);
print_exttree_link();
printf("\n");
}
exttree_test_parents(tree->root);
366,7 → 366,7
i--;
}
 
if (!quiet && (i != 0)) printf("Bad node count. Some nodes have been lost!");
if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
 
if (!quiet) printf("Timeout tree finished\n");
}
/branches/rcu/kernel/test/extavlreltree/extavlreltree1.c
28,7 → 28,7
 
#include <test.h>
#include <print.h>
#include <adt/extavlreltree.h>
#include <adt/extavlrel.h>
#include <debug.h>
 
#include <panic.h>
53,17 → 53,17
 
 
 
static int extreltree_test_height(extrelavltree_node_t *node,bool timeout);
static extavlreltree_node_t *extreltree_test_parents(extavlireltree_node_t *node);
static int extreltree_test_height(extavlreltree_node_t *node,bool timeout);
static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node);
static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level);
static bool extreltree_test_link(int node_count);
static void print_extreltree_link(int node_count);
static bool extreltree_test_link(extavlreltree_t *tree, int node_count);
static void print_extreltree_link(extavlreltree_t *tree);
static extavlreltree_node_t *alloc_extavlreltree_node(void);
 
 
 
//vraci hloubku stromu
static int extreltree_test_height(extavltree_node_t *node,bool timeout)
static int extreltree_test_height(extavlreltree_node_t *node,bool timeout)
{
int h1, h2;
 
90,7 → 90,7
*/
static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node)
{
extavltree_node_t *tmp;
extavlreltree_node_t *tmp;
if (!node) return NULL;
 
112,21 → 112,21
/** Checks list of nodes
*
*/
static bool extreltree_test_link(int node_count)
static bool extreltree_test_link(extavlreltree_t *tree, int node_count)
{
extavltree_node_t *node;
extavlreltree_node_t *node;
int i;
bool test_link = true;
 
for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next)
for (i = 0,node = tree->head.next; node != &(tree->head); i++,node = node->next)
;
if (node_count && i != node_count) {
if (i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev)
for (i = 0,node = tree->head.prev; node != &(tree->head); i++,node = node->prev)
;
if (node_count && i != node_count) {
if (i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
145,18 → 145,17
return sum + node->key;
}
 
static int extreltree_test_maxsum(extavlreltree_node_t *node)
static int extreltree_test_rgtsum(extavlreltree_node_t *node)
{
int rs, ls;
if (!node) return 0;
rs = extreltree_test_maxsum(node->rgt);
ls = extreltree_test_maxsum(node->lft);
rs = extreltree_test_rgtsum(node->rgt);
ls = extreltree_test_rgtsum(node->lft);
 
if (rs != node->rgt_max_key) {
printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_max_key,rs,node->key,node);
getchar();
if (rs != node->rgt_sum) {
printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_sum,rs,node->key,node);
}
return rs + ls + node->key;
}
181,19 → 180,19
for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++)
;
 
printf ("%d[%d,%d]", node->key,node->rgt_max_key,i);
printf ("%d[%d,%d]", node->key,node->rgt_sum,i);
if (node->lft != NULL || node->rgt != NULL)
{
putchar ('(');
printf ("(");
 
print_extreltree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
putchar (',');
printf(",");
print_extreltree_structure_flat (node->rgt, level + 1);
}
 
putchar (')');
printf(")");
}
}
 
200,20 → 199,20
/** Prints list of nodes
*
*/
static void print_extreltree_link(int node_count)
static void print_extreltree_link(extavlreltree_t *tree)
{
extavltree_node_t *node;
extavlreltree_node_t *node;
printf("\n");
for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
for (node = tree->head.next; node != &(tree->head); node = node->next) {
printf(" %d,",node->key);
}
for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {
for (node = tree->head.prev; node != &(tree->head); node = node->prev) {
printf(" %d,",node->key);
}
}
 
//****************************************************************
static void alloc_extavltree_node_prepare(void)
static void alloc_extavlreltree_node_prepare(void)
{
int i;
 
280,7 → 279,7
*/
extavlreltree_create(tree);
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_extavlreltree_node();
288,8 → 287,8
extavlreltree_insert(tree, newnode);
if (!quiet) {
if (!extreltree_test_link(i+1)) {
print_extreltree_link(i+1);
if (!extreltree_test_link(tree,i+1)) {
print_extreltree_link(tree);
printf("\n");
}
extreltree_test_parents(tree->root);
311,14 → 310,14
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\n\nDelete root nodes\n");
i = node_count;
if (!quiet) printf("\nDelete root nodes\n");
i = node_count - 1;
while(tree->root != NULL) {
delnode = tree->root;
extavlreltree_delete(tree,delnode);
if (!quiet) {
if (!extreltree_test_link(i)) {
print_extreltree_link(i);
if (!extreltree_test_link(tree,i)) {
print_extreltree_link(tree);
printf("\n");
}
extreltree_test_parents(tree->root);
330,12 → 329,12
break;
case 1:
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
if (!quiet) printf("\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
extavlreltree_delete(tree,&(extavlreltree_nodes[i]));
if (!quiet) {
if (!extreltree_test_link(i+1)) {
print_extreltree_link(i+1);
if (!extreltree_test_link(tree,node_count-i-1)) {
print_extreltree_link(tree);
printf("\n");
}
extreltree_test_parents(tree->root);
352,15 → 351,15
 
static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet)
{
int i = node_count;
int i = node_count - 1;
if (!quiet) printf("Timeout tree ...\n");
if (!quiet) printf("\nTimeout tree ...\n");
while(tree->head.next != &(tree->head)) {
extavlreltree_delete_min(tree);
if (!quiet) {
if (!extreltree_test_link(i)) {
print_extreltree_link(i);
if (!extreltree_test_link(tree,i)) {
print_extreltree_link(tree);
printf("\n");
}
extreltree_test_parents(tree->root);
370,7 → 369,7
i--;
}
 
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");
if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
 
if (!quiet) printf("Timeout tree finished\n");
}
/branches/rcu/kernel/test/timeout/timeout1.def
0,0 → 1,6
{
"timeout1",
"Timeout test",
&test_timeout1,
true
},
/branches/rcu/kernel/test/timeout/timeout1.c
0,0 → 1,97
/*
* Copyright (c) 2005 Jakub Vana
* Copyright (c) 2005 Jakub Jermar
* 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 <print.h>
#include <debug.h>
 
#include <test.h>
#include <atomic.h>
#include <proc/thread.h>
 
#include <arch.h>
 
#define THREADS 5
#define RUN_TIME 10
 
static atomic_t finish;
static atomic_t threads_finished;
static atomic_t run_time;
static bool sh_quiet;
 
static void timeouttest(void *data)
{
unsigned int tmp;
thread_detach(THREAD);
 
while (atomic_get(&finish)) {
tmp = atomic_get(&run_time) + 10000;
if (!sh_quiet)
printf("%llu sleeps %u mikrosec\n", THREAD->tid, tmp);
atomic_set(&run_time, tmp + 10000);
thread_usleep(atomic_get(&run_time));
if (atomic_get(&run_time) > 300000)
atomic_set(&run_time,10000);
}
atomic_inc(&threads_finished);
}
 
char * test_timeout1(bool quiet)
{
unsigned int i, total = 0;
sh_quiet = quiet;
atomic_set(&finish, 1);
atomic_set(&threads_finished, 0);
atomic_set(&run_time, 10000);
 
for (i = 0; i < THREADS; i++) {
thread_t *t;
if (!(t = thread_create(timeouttest, NULL, TASK, 0, "timeouttest", false))) {
if (!quiet)
printf("Could not create thread %d\n", i);
break;
}
thread_ready(t);
total++;
}
if (!quiet)
printf("Running threads for %d seconds...\n",RUN_TIME);
thread_sleep(RUN_TIME);
atomic_set(&finish, 0);
while (atomic_get(&threads_finished) < total) {
if (!quiet)
printf("Threads left: %d\n", total - atomic_get(&threads_finished));
thread_sleep(1);
}
return NULL;
}
/branches/rcu/kernel/test/test.c
62,6 → 62,7
#include <avltree/avltree1.def>
#include <extavltree/extavltree1.def>
#include <extavlreltree/extavlreltree1.def>
#include <timeout/timeout1.def>
{NULL, NULL, NULL}
};
 
/branches/rcu/kernel/test/avltree/avltree1.c
54,7 → 54,7
 
 
static int test_tree_balance(avltree_node_t *node);
static avltree_node_t *tree_test_parents(avltree_node_t *node);
static avltree_node_t *test_tree_parents(avltree_node_t *node);
static void print_tree_structure_flat (avltree_node_t *node, int level);
static avltree_node_t *alloc_avltree_node(void);
 
98,7 → 98,7
/**
* Prints the structure of node, which is level levels from the top of the tree.
*/
static void print_tree_structure_flat (const avltree_node_t *node, int level)
static void print_tree_structure_flat (avltree_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,
115,16 → 115,16
printf ("%d[%d]", node->key,node->balance);
if (node->lft != NULL || node->rgt != NULL)
{
putchar ('(');
printf("(");
 
print_tree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
putchar (',');
printf(",");
print_tree_structure_flat (node->rgt, level + 1);
}
 
putchar (')');
printf(")");
}
}
 
135,7 → 135,7
int i;
 
for (i = 0; i < NODE_COUNT - 1; i++) {
avltree_nodes[i].n = &(avltree_nodes[i+1]);
avltree_nodes[i].par = &(avltree_nodes[i+1]);
}
/*
* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
172,7 → 172,7
for (i = 21; i < NODE_COUNT; i++)
avltree_nodes[i].key = i * 3;
avltree_nodes[i].n = NULL;
avltree_nodes[i].par = NULL;
first_free_node = &(avltree_nodes[0]);
}
 
181,7 → 181,7
avltree_node_t *node;
 
node = first_free_node;
first_free_node = first_free_node->n;
first_free_node = first_free_node->par;
 
return node;
}
197,7 → 197,7
*/
avltree_create(tree);
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_avltree_node();
213,26 → 213,7
if (!quiet) printf("Inserting was finished\n");
}
 
/*
static avltree_node_t *tree_random_delete_node(avltree_t *tree, int node_count, int r, bool quiet)
{
avltree_node_t *delnode;
int i;
 
for (i = 0,delnode = tree->head.n; i < (r-1); i++)
delnode = delnode->n;
if (delnode == &tree->head) {
if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
return NULL;
}
 
avltree_delete(tree, delnode);
 
return delnode;
}
*/
 
static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)
{
avltree_node_t *delnode;
243,7 → 224,7
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\n\nDelete root nodes\n");
if (!quiet) printf("\nDelete root nodes\n");
while(tree->root != NULL) {
delnode = tree->root;
avltree_delete(tree,delnode);
255,7 → 236,7
break;
case 1:
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
if (!quiet) printf("\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
avltree_delete(tree,&(avltree_nodes[i]));
if (!quiet) {
274,9 → 255,9
{
int i = 0;
if (!quiet) printf("Timeout tree ...\n");
if (!quiet) printf("\nTimeout tree ...\n");
while(tree->head.n != &(tree->head)) {
while(tree->root != NULL) {
i++;
avltree_delete_min(tree);
if (!quiet) {
285,62 → 266,24
}
}
 
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");
 
if (!quiet) printf("Timeout tree finished\n");
}
 
/*
void timeout_tree_run(avltree_t *tree, int operation_count, int verbal)
{
int i;
avltree_node_t *node;
int r;
int count;
//inicializace stromu:
avltree_create(tree);
for(i = 0, count = 0; i < operation_count; i++) {
if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
node = tree_random_delete_node(tree,(r % tree->count));
//printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
node->n = first_free_node;
first_free_node = node;
} else {
node = tree->head.n;
avltree_delete_min(tree);
//printf("TIMEOUT key: %d, address: %p\n",node->key,node);
node->n = first_free_node;
first_free_node = node;
}
} else {
node = alloc_avltree_node_random();
//printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
avltree_insert(tree, node);
}
//test_tree_height(tree->root,1);
//tree_test_parents(tree->root);
//print_tree_link(tree->count);
//print_tree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
}
}
*/
 
char * test_avltree1(bool quiet)
{
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
test_tree_delete(&tree, NODE_COUNT, 0, quiet);
test_tree_insert(&avltree, NODE_COUNT, quiet);
test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
 
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
test_tree_delete(&tree, NODE_COUNT, 1, quiet);
test_tree_insert(&avltree, NODE_COUNT, quiet);
test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
 
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
timeout_tree(&tree, NODE_COUNT, quiet);
test_tree_insert(&avltree, NODE_COUNT, quiet);
timeout_tree(&avltree, NODE_COUNT, quiet);
 
return NULL;
}
/branches/rcu/kernel/test/test.h
74,6 → 74,7
extern char * test_avltree1(bool quiet);
extern char * test_extavltree1(bool quiet);
extern char * test_extavlreltree1(bool quiet);
extern char * test_timeout1(bool quiet);
 
extern test_t tests[];