/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 |