Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2420 → 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[];
 
/branches/rcu/kernel/generic/include/cpu.h
40,11 → 40,14
#include <proc/scheduler.h>
#include <arch/cpu.h>
#include <arch/context.h>
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE
#include <adt/extavl.h>
#if defined CONFIG_TIMEOUT_AVL_TREE
#include <adt/avl.h>
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
#include <adt/extavl.h>
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
#include <adt/extavlrel.h>
#endif
 
 
#define CPU_STACK_SIZE STACK_SIZE
 
/** CPU structure.
/branches/rcu/kernel/generic/include/adt/avl.h
120,10 → 120,11
node->balance = 0;
}
 
avltree_node_t *avltree_find_min(avltree_t *t);
avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
void avltree_insert(avltree_t *t, avltree_node_t *newnode);
void avltree_delete(avltree_t *t, avltree_node_t *node);
avltree_node_t *avltree_delete_min(avltree_t *t);
bool avltree_delete_min(avltree_t *t);
 
#endif
 
/branches/rcu/kernel/generic/include/adt/extavlrel.h
1,5 → 1,5
/*
* Copyright (C) 2006 Vojtech Mencl
* Copyright (C) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
94,7 → 94,6
};
 
/** Relative key Extended AVL tree structure (ExtAvlrel). */
#ifdef AVLTREE_TEST
struct extavlreltree
{
/*
114,7 → 113,7
*
* @param t Extended AVL tree structure.
*/
void extavlreltree_create (extavlreltree_t *t)
static inline void extavlreltree_create (extavlreltree_t *t)
{
t->root = NULL;
 
126,7 → 125,7
*
* @param node Node which is initialized.
*/
void extavlreltree_node_initialize(extavlreltree_node_t *node)
static inline void extavlreltree_node_initialize(extavlreltree_node_t *node)
{
node->lft = NULL;
node->rgt = NULL;
/branches/rcu/kernel/generic/src/time/timeout.c
59,7 → 59,7
avltree_create(&CPU->timeout_active_tree);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
extavltree_create(&CPU->timeout_active_tree);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
extavlreltree_create(&CPU->timeout_active_tree);
#else
list_initialize(&CPU->timeout_active_head);
/branches/rcu/kernel/generic/src/time/clock.c
123,8 → 123,7
}
}
 
#if defined CONFIG_TIMEOUT_AVL_TREE || \
defined CONFIG_TIMEOUT_EXTAVL_TREE
#if defined CONFIG_TIMEOUT_AVL_TREE
 
/** Clock routine
*
141,11 → 140,98
count_t missed_clock_ticks = CPU->missed_clock_ticks;
uint64_t *i = &(CPU->timeout_active_tree.base);
uint64_t absolute_clock_ticks = *i + missed_clock_ticks;
#if defined CONFIG TIMEOUT_AVL_TREE
avltree_node_t *expnode;
 
/*
* To avoid lock ordering problems,
* run all expired timeouts as you visit them.
*/
 
for (; *i <= absolute_clock_ticks; (*i)++) {
/*
* Basetime is encreased by missed clock ticks + 1 !!
*/
clock_update_counters();
spinlock_lock(&CPU->timeoutlock);
/*
* Check whether first timeout (with the smallest key in the tree) time out. If so perform
* callback function and try next timeout (more timeouts can have same timeout).
*/
while ((expnode = avltree_find_min(&CPU->timeout_active_tree)) != NULL) {
h = avltree_get_instance(expnode,timeout_t,node);
spinlock_lock(&h->lock);
if (expnode->key != *i) {
spinlock_unlock(&h->lock);
break;
}
/*
* Delete minimal key from the tree and repair tree structure in
* logarithmic time.
*/
avltree_delete_min(&CPU->timeout_active_tree);
 
f = h->handler;
arg = h->arg;
timeout_reinitialize(h);
spinlock_unlock(&h->lock);
spinlock_unlock(&CPU->timeoutlock);
 
f(arg);
 
spinlock_lock(&CPU->timeoutlock);
}
spinlock_unlock(&CPU->timeoutlock);
}
 
CPU->missed_clock_ticks = 0;
 
/*
* Do CPU usage accounting and find out whether to preempt THREAD.
*/
if (THREAD) {
uint64_t ticks;
spinlock_lock(&CPU->lock);
CPU->needs_relink += 1 + missed_clock_ticks;
spinlock_unlock(&CPU->lock);
spinlock_lock(&THREAD->lock);
if ((ticks = THREAD->ticks)) {
if (ticks >= 1 + missed_clock_ticks)
THREAD->ticks -= 1 + missed_clock_ticks;
else
THREAD->ticks = 0;
}
spinlock_unlock(&THREAD->lock);
if (!ticks && !PREEMPTION_DISABLED) {
scheduler();
}
}
}
 
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
 
/** Clock routine
*
* Clock routine executed from clock interrupt handler
* (assuming interrupts_disable()'d). Runs expired timeouts
* and preemptive scheduling.
*
*/
void clock(void)
{
timeout_t *h;
timeout_handler_t f;
void *arg;
count_t missed_clock_ticks = CPU->missed_clock_ticks;
uint64_t *i = &(CPU->timeout_active_tree.base);
uint64_t absolute_clock_ticks = *i + missed_clock_ticks;
extavltree_node_t *expnode;
#endif
 
/*
* To avoid lock ordering problems,
176,11 → 262,7
* Delete first node in the list and repair tree structure in
* constant time.
*/
#if defined CONFIG TIMEOUT_AVL_TREE
avltree_delete_min(&CPU->timeout_active_tree);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
extavltree_delete_min(&CPU->timeout_active_tree);
#endif
 
f = h->handler;
arg = h->arg;
233,7 → 315,7
*/
void clock(void)
{
extavltree_node_t *expnode;
extavlreltree_node_t *expnode;
timeout_t *h;
timeout_handler_t f;
void *arg;
253,7 → 335,7
* next timeout (more timeouts can have same timeout).
*/
while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) {
h = list_get_instance(l, timeout_t, link);
h = extavlreltree_get_instance(expnode,timeout_t,node);
spinlock_lock(&h->lock);
if (expnode->key != 0) {
expnode->key--;
265,7 → 347,7
* Delete first node in the list and repair tree structure in
* constant time. Be careful of expnode's key, it must be 0!
*/
extavltree_delete_min(&CPU->timeout_active_tree);
extavlreltree_delete_min(&CPU->timeout_active_tree);
f = h->handler;
arg = h->arg;
/branches/rcu/kernel/generic/src/adt/avl.c
1,5 → 1,5
/*
* Copyright (c) 2006 Vojtech Mencl
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
61,7 → 61,7
* @param t AVL tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @return Pointer to node or NULL if there is no such key.
*/
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
{
84,6 → 84,30
}
 
 
/** Find node with smallest key in AVL tree.
*
* @param t AVL tree.
*
* @return Pointer to node or NULL if there is no node in the tree.
*/
avltree_node_t *avltree_find_min(avltree_t *t)
{
avltree_node_t *p = t->root;
/*
* Check whether tree is empty.
*/
if (!p) return NULL;
/*
* Iteratively descend to the leftmost leaf in the tree.
*/
while (p->lft != NULL)
p = p->lft;
return p;
}
 
/** Insert new node into AVL tree.
*
* @param t AVL tree.
114,7 → 138,7
dpc = &t->root;
gpa = NULL;
top = t->root;
while (par = *dpc) {
while ((par = (*dpc)) != NULL) {
if (par->balance != 0) {
top = par;
}
670,7 → 694,7
*
* @param t AVL tree structure.
*/
avltree_node_t *avltree_delete_min(avltree_t *t)
bool avltree_delete_min(avltree_t *t)
{
avltree_node_t *node;
uint64_t key;
/branches/rcu/kernel/generic/src/adt/extavl.c
63,7 → 63,7
* @param t Extended AVL tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @return Pointer to node or NULL if there is no such key.
*/
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key)
{
/branches/rcu/kernel/generic/src/adt/extavlrel.c
60,7 → 60,7
 
 
/* Returns height of tree -1 */
#define extavlreltree_tree_height(node) ((node) == NULL) ? (-1) : max(((node)->lft_height),((node)->rgt_height))
#define extavlreltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
 
/** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree.
*
67,9 → 67,9
* @param t ExtAVLrel tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @return Pointer to node or NULL if there is no such key.
*/
extavlreltree_node_t *extavlreltree_search(extavlreltree_t t, uint64_t key)
extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key)
{
extavlreltree_node_t *cur;
uint64_t sum, s;
492,7 → 492,7
extavlreltree_node_t *gpa;
int8_t dir;
int8_t dir2=0;
uint64_t key;
uint64_t key=0;
int16_t balance;
/*
* Condition var - if true then all rgt_sums in the way down to root must be repaired in condition
700,7 → 700,7
if (gpa->par->lft == gpa) {
gpapar = &(gpa->par->lft);
dir2 = AVLTREE_LEFT;
repair_rgt_sum = falsi;
repair_rgt_sum = false;
} else {
gpapar = &(gpa->par->rgt);
dir2 = AVLTREE_RIGHT;
/branches/rcu/kernel/Makefile
255,7 → 255,10
test/tasklet/tasklet1.c \
test/thread/thread1.c \
test/sysinfo/sysinfo1.c \
test/extavltree/extavltree1.c
test/avltree/avltree1.c \
test/extavltree/extavltree1.c \
test/extavlreltree/extavlreltree1.c \
test/timeout/timeout1.c
endif
 
## Experimental features