/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[]; |