Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2430 → Rev 2431

/branches/rcu/kernel/test/timeout/timeoutbench1.def
0,0 → 1,6
{
"timeoutbench1",
"Timeout structures benchmark test",
&test_timeoutbench1,
true
},
/branches/rcu/kernel/test/timeout/timeoutbench1.c
0,0 → 1,817
/*
* 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/avl.h>
#include <adt/extavl.h>
#include <adt/extavlrel.h>
#include <debug.h>
#include <arch/types.h>
#include <arch/cycle.h>
#include <arch/asm.h>
#include <panic.h>
#include <mm/slab.h>
 
/*
* Node count must be more then 1000!
*/
#define NODE_COUNT 1000000
#define GEN_NUM 275604541
#define OPERATION_COUNT 100000000
#define TEST_COUNT 3
 
static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};
 
/*
* Wrapper tree data structures.
*/
static avltree_t avltree;
static extavltree_t extavltree;
static extavlreltree_t extavlreltree;
 
/*
* Slab cache variables.
*/
static slab_cache_t *avl_slab;
static slab_cache_t *extavl_slab;
static slab_cache_t *extavlrel_slab;
 
/*
* Head of free nodes' list:
*/
static avltree_node_t *avl_ffn = NULL;
static extavltree_node_t *extavl_ffn = NULL;
static extavlreltree_node_t *extavlrel_ffn = NULL;
 
 
static void keys_prepare(int node_count, int type)
{
unsigned int i;
uint16_t s;
avltree_node_t *a = avl_ffn;
extavltree_node_t *b = extavl_ffn;
extavlreltree_node_t *c = extavlrel_ffn;
switch (type) {
case 0:
s = (uint16_t) get_cycle();
for (i = 0; i < node_count; i++) {
a->key = s;
b->key = s;
c->key = s;
s += GEN_NUM;
a = a->par;
b = b->par;
c = c->par;
}
break;
case 1:
for (i = 1; i <= node_count; i++) {
a->key = i;
b->key = i;
c->key = i;
a = a->par;
b = b->par;
c = c->par;
}
break;
case 2:
for (i = node_count; i > 0; i--) {
a->key = i;
b->key = i;
c->key = i;
a = a->par;
b = b->par;
c = c->par;
}
break;
}
}
 
 
static bool alloc_nodes(int node_count)
{
int i;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
avl_ffn = NULL;
extavl_ffn = NULL;
extavlrel_ffn = NULL;
 
for (i = 0; i < node_count; i++) {
a = (avltree_node_t *) slab_alloc(avl_slab,0);
if (!a) {
printf("Not enough memory to allocate test arrays.");
return false;
}
b = (extavltree_node_t *) slab_alloc(extavl_slab,0);
if (!b) {
printf("Not enough memory to allocate test arrays.");
return false;
}
c = (extavlreltree_node_t *) slab_alloc(extavlrel_slab,0);
if (!c) {
printf("Not enough memory to allocate test arrays.");
return false;
}
a->par = avl_ffn;
b->par = extavl_ffn;
c->par = extavlrel_ffn;
avl_ffn = a;
extavl_ffn = b;
extavlrel_ffn = c;
}
return true;
}
 
static void free_nodes(int node_count)
{
int i;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
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);
panic("Some nodes have been lost!");
}
avl_ffn = avl_ffn->par;
extavl_ffn = extavl_ffn->par;
extavlrel_ffn = extavlrel_ffn->par;
slab_free(avl_slab,a);
slab_free(extavl_slab,b);
slab_free(extavlrel_slab,c);
}
}
 
static avltree_node_t *alloc_avltree_node(void)
{
avltree_node_t *node;
 
node = avl_ffn;
avl_ffn = avl_ffn->par;
 
return node;
}
 
static extavltree_node_t *alloc_extavltree_node(void)
{
extavltree_node_t *node;
 
node = extavl_ffn;
 
extavl_ffn = extavl_ffn->par;
 
return node;
}
 
static extavlreltree_node_t *alloc_extavlreltree_node(void)
{
extavlreltree_node_t *node;
 
node = extavlrel_ffn;
extavlrel_ffn = extavlrel_ffn->par;
 
return node;
}
 
static void free_avltree_node(avltree_node_t *node)
{
node->par = avl_ffn;
avl_ffn = node;
}
 
static void free_extavltree_node(extavltree_node_t *node)
{
node->par = extavl_ffn;
extavl_ffn = node;
}
 
static void free_extavlreltree_node(extavlreltree_node_t *node)
{
node->par = extavlrel_ffn;
extavlrel_ffn = node;
}
 
/** Insert keys of ascending sequence and delete tree deleting root nodes.
*/
static void test1(void)
{
ipl_t ipl;
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
printf("INSERT nodes with keys of ascending sequence.\n");
printf("Nodes:\t\t");
for (ii = 0; ii < TEST_COUNT; ii++) {
printf("%20u",node_count[ii]);
keys_prepare(node_count[ii],1);
 
/*
* AVL INSERT
*/
ipl = interrupts_disable();
s[0][ii] = get_cycle();
avltree_create(&avltree);
for (i = 0; i < node_count[ii]; i++) {
avltree_insert(&avltree,alloc_avltree_node());
}
f[0][ii] = get_cycle();
interrupts_restore(ipl);
/*
* AVL DELETE
*/
ipl = interrupts_disable();
ds[0][ii] = get_cycle();
while ((a = avltree.root) != NULL) {
avltree_delete(&avltree,a);
free_avltree_node(a);
}
df[0][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVL INSERT
*/
ipl = interrupts_disable();
s[1][ii] = get_cycle();
extavltree_create(&extavltree);
for (i = 0; i < node_count[ii]; i++) {
extavltree_insert(&extavltree,alloc_extavltree_node());
}
f[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVL DELETE
*/
ipl = interrupts_disable();
ds[1][ii] = get_cycle();
while ((b = extavltree.root) != NULL) {
extavltree_delete(&extavltree,b);
free_extavltree_node(b);
}
df[1][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVLrel INSERT
*/
ipl = interrupts_disable();
s[2][ii] = get_cycle();
extavlreltree_create(&extavlreltree);
for (i = 0; i < node_count[ii]; i++) {
extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
}
f[2][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel DELETE
*/
ipl = interrupts_disable();
ds[2][ii] = get_cycle();
while ((c = extavlreltree.root) != NULL) {
extavlreltree_delete(&extavlreltree,c);
free_extavlreltree_node(c);
}
df[2][ii] = get_cycle();
interrupts_restore(ipl);
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[0][ii]-s[0][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[1][ii]-s[1][ii]);
printf("\nExtAVLrel\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[2][ii]-s[2][ii]);
printf("\n\n");
 
printf("DELETE tree deleting root nodes\n");
printf("Nodes:\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20u",node_count[ii]);
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[0][ii]-ds[0][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[1][ii]-ds[1][ii]);
printf("\nExtAVLrel\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[2][ii]-ds[2][ii]);
printf("\n\n");
}
 
 
/** Insert keys of ascending sequence and delete tree with delete_min functions.
*/
static void test2(void)
{
ipl_t ipl;
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
 
 
printf("INSERT nodes with keys of descending sequence.\n");
printf("Nodes:\t\t");
for (ii = 0; ii < TEST_COUNT; ii++) {
printf("%20u",node_count[ii]);
keys_prepare(node_count[ii],2);
/*
* AVL INSERT
*/
ipl = interrupts_disable();
s[0][ii] = get_cycle();
avltree_create(&avltree);
for (i = 0; i < node_count[ii]; i++) {
avltree_insert(&avltree,alloc_avltree_node());
}
f[0][ii] = get_cycle();
interrupts_restore(ipl);
/*
* AVL DELETE
*/
ipl = interrupts_disable();
ds[0][ii] = get_cycle();
while (avltree.root != NULL) {
a = avltree_find_min(&avltree);
avltree_delete_min(&avltree);
free_avltree_node(a);
}
df[0][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVL INSERT
*/
ipl = interrupts_disable();
s[1][ii] = get_cycle();
extavltree_create(&extavltree);
for (i = 0; i < node_count[ii]; i++) {
extavltree_insert(&extavltree,alloc_extavltree_node());
}
f[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVL DELETE
*/
ipl = interrupts_disable();
ds[1][ii] = get_cycle();
while (extavltree.root != NULL) {
b = extavltree.head.next;
extavltree_delete_min(&extavltree);
free_extavltree_node(b);
}
df[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel INSERT
*/
ipl = interrupts_disable();
s[2][ii] = get_cycle();
extavlreltree_create(&extavlreltree);
for (i = 0; i < node_count[ii]; i++) {
extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
}
f[2][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel DELETE
*/
ipl = interrupts_disable();
ds[2][ii] = get_cycle();
while (extavlreltree.root != NULL) {
c = extavlreltree.head.next;
extavlreltree_delete_min(&extavlreltree);
free_extavlreltree_node(c);
}
df[2][ii] = get_cycle();
interrupts_restore(ipl);
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[0][ii]-s[0][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[1][ii]-s[1][ii]);
printf("\nExtAVLrel\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[2][ii]-s[2][ii]);
printf("\n\n");
 
printf("DELETE tree deleting nodes with minimal key\n");
printf("Nodes:\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20u",node_count[ii]);
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[0][ii]-ds[0][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[1][ii]-ds[1][ii]);
printf("\nExtAVLrel\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[2][ii]-ds[2][ii]);
printf("\n\n");
}
 
 
/** Insert keys of random sequence and delete tree with delete_min functions.
*/
static void test3(void)
{
ipl_t ipl;
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
 
printf("INSERT nodes with keys of random sequence 1-65536.\n");
printf("Nodes:\t\t");
for (ii = 0; ii < TEST_COUNT; ii++) {
printf("%20u",node_count[ii]);
keys_prepare(node_count[ii],0);
/*
* AVL INSERT
*/
ipl = interrupts_disable();
s[0][ii] = get_cycle();
avltree_create(&avltree);
for (i = 0; i < node_count[ii]; i++) {
avltree_insert(&avltree,alloc_avltree_node());
}
f[0][ii] = get_cycle();
interrupts_restore(ipl);
/*
* AVL DELETE
*/
ipl = interrupts_disable();
ds[0][ii] = get_cycle();
while (avltree.root != NULL) {
a = avltree_find_min(&avltree);
avltree_delete_min(&avltree);
free_avltree_node(a);
}
df[0][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVL INSERT
*/
ipl = interrupts_disable();
s[1][ii] = get_cycle();
extavltree_create(&extavltree);
for (i = 0; i < node_count[ii]; i++) {
extavltree_insert(&extavltree,alloc_extavltree_node());
}
f[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVL DELETE
*/
ipl = interrupts_disable();
ds[1][ii] = get_cycle();
while (extavltree.root != NULL) {
b = extavltree.head.next;
extavltree_delete_min(&extavltree);
free_extavltree_node(b);
}
df[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel INSERT
*/
ipl = interrupts_disable();
s[2][ii] = get_cycle();
extavlreltree_create(&extavlreltree);
for (i = 0; i < node_count[ii]; i++) {
extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
}
f[2][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel DELETE
*/
ipl = interrupts_disable();
ds[2][ii] = get_cycle();
while (extavlreltree.root != NULL) {
c = extavlreltree.head.next;
extavlreltree_delete_min(&extavlreltree);
free_extavlreltree_node(c);
}
df[2][ii] = get_cycle();
interrupts_restore(ipl);
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[0][ii]-s[0][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[1][ii]-s[1][ii]);
printf("\nExtAVLrel\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[2][ii]-s[2][ii]);
printf("\n\n");
 
printf("DELETE tree deleting nodes with minimal key\n");
printf("Nodes:\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20u",node_count[ii]);
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[0][ii]-ds[0][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[1][ii]-ds[1][ii]);
printf("\nExtAVLrel\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[2][ii]-ds[2][ii]);
printf("\n\n");
}
 
 
/** Simulating timeout mechanismus with insert and delete_min operations.
*/
static void test4(void)
{
ipl_t ipl;
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
uint64_t r;
uint16_t rr;
unsigned int mn,nc;
 
printf("Simulating timeout mechanismus with %d insert or delete_min operations\n",OPERATION_COUNT);
printf("Maximum nodes:\t");
for (ii = 0; ii < TEST_COUNT; ii++) {
printf("%20u",node_count[ii]);
r = (uint64_t) get_cycle();
mn = node_count[ii];
/*
* AVL
*/
rr = r;
nc = 0;
ipl = interrupts_disable();
s[0][ii] = get_cycle();
avltree_create(&avltree);
for (i = 0; i < OPERATION_COUNT; i++) {
if (((rr % mn) <= nc) && nc) {
/*
* Delete min.
*/
a = avltree_find_min(&avltree);
avltree_delete_min(&avltree);
free_avltree_node(a);
nc--;
} else {
/*
* Insert.
*/
a = alloc_avltree_node();
a->key = rr;
avltree_insert(&avltree,a);
nc++;
}
rr += GEN_NUM;
}
/*
* Delete rest tree.
*/
while (avltree.root != NULL) {
a = avltree_find_min(&avltree);
avltree_delete_min(&avltree);
free_avltree_node(a);
}
f[0][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVL
*/
rr = r;
nc = 0;
ipl = interrupts_disable();
s[1][ii] = get_cycle();
extavltree_create(&extavltree);
for (i = 0; i < OPERATION_COUNT; i++) {
if (((rr % mn) <= nc) && nc) {
/*
* Delete min.
*/
b = extavltree.head.next;
extavltree_delete_min(&extavltree);
free_extavltree_node(b);
nc--;
} else {
/*
* Insert.
*/
b = alloc_extavltree_node();
b->key = rr;
extavltree_insert(&extavltree,b);
nc++;
}
rr += GEN_NUM;
}
/*
* Delete rest tree.
*/
while (extavltree.root != NULL) {
b = extavltree.head.next;
extavltree_delete_min(&extavltree);
free_extavltree_node(b);
}
 
f[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel
*/
rr = r;
nc = 0;
ipl = interrupts_disable();
s[2][ii] = get_cycle();
extavlreltree_create(&extavlreltree);
for (i = 0; i < OPERATION_COUNT; i++) {
if (((rr % mn) <= nc) && nc) {
/*
* Delete min.
*/
c = extavlreltree.head.next;
//if (ii == 2 && !(i % 100)) printf("DEL key %llu, nc: %u, op: %u\n",c->key,nc,i);
extavlreltree_delete_min(&extavlreltree);
free_extavlreltree_node(c);
nc--;
} else {
/*
* Insert.
*/
c = alloc_extavlreltree_node();
c->key = rr;
//if (ii == 2 && !(i % 100)) printf("INS key %llu, nc: %u, op: %u\n",c->key,nc,i);
extavlreltree_insert(&extavlreltree,c);
nc++;
}
rr += GEN_NUM;
}
/*
* Delete rest tree.
*/
while (extavlreltree.root != NULL) {
c = extavlreltree.head.next;
extavlreltree_delete_min(&extavlreltree);
free_extavlreltree_node(c);
}
 
f[2][ii] = get_cycle();
interrupts_restore(ipl);
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[0][ii]-s[0][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[1][ii]-s[1][ii]);
printf("\nExtAVLrel\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[2][ii]-s[2][ii]);
printf("\n\n");
}
 
 
char * test_timeoutbench1(bool quiet)
{
printf("\n\tBenchmark test of timeout data structures: AVL, ExtAVL and ExtAVLrel.\n"
"Run test more than once for eliminating possible distortion due to caching!\n\n");
 
avl_slab = slab_cache_create("avl_slab",sizeof(avltree_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);
 
if (!alloc_nodes(NODE_COUNT))
return NULL;
 
/*
* Disable interrupts,
* store initial cycle count,
* do test,
* store finish cycle count,
* enable interrupts,
* show results
*/
 
test1();
test2();
test3();
test4();
 
/*
* Deallocate arrays.
*/
free_nodes(NODE_COUNT);
return NULL;
}
/branches/rcu/kernel/test/test.c
63,6 → 63,7
#include <extavltree/extavltree1.def>
#include <extavlreltree/extavlreltree1.def>
#include <timeout/timeout1.def>
#include <timeout/timeoutbench1.def>
{NULL, NULL, NULL}
};
 
/branches/rcu/kernel/test/avltree/avltree1.c
31,9 → 31,7
#include <adt/avl.h>
#include <debug.h>
 
#include <panic.h>
 
 
#define NODE_COUNT 100
 
/*
162,12 → 160,14
//RL rotation
avltree_nodes[13].key = 90;
avltree_nodes[14].key = 85;
avltree_nodes[15].key = 100;
avltree_nodes[16].key = 200;
avltree_nodes[17].key = 300;
avltree_nodes[18].key = 400;
avltree_nodes[19].key = 500;
avltree_nodes[20].key = 600;
//Insert 0 key
avltree_nodes[15].key = 0;
avltree_nodes[16].key = 0;
//Insert reverse
avltree_nodes[17].key = 600;
avltree_nodes[18].key = 500;
avltree_nodes[19].key = 400;
avltree_nodes[20].key = 300;
 
for (i = 21; i < NODE_COUNT; i++)
avltree_nodes[i].key = i * 3;
/branches/rcu/kernel/test/test.h
75,6 → 75,7
extern char * test_extavltree1(bool quiet);
extern char * test_extavlreltree1(bool quiet);
extern char * test_timeout1(bool quiet);
extern char * test_timeoutbench1(bool quiet);
 
extern test_t tests[];
 
/branches/rcu/kernel/generic/src/time/timeout.c
1,5 → 1,6
/*
* Copyright (C) 2001-2004 Jakub Jermar
* Copyright (C) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
/branches/rcu/kernel/generic/src/adt/extavl.c
163,7 → 163,7
newnode->par = cur;
gpa = cur;
while (gpa != &t->head && gpa->key == cur->key)
while ((gpa != &t->head) && (gpa->key == cur->key))
gpa = gpa->prev;
newnode->next = gpa->next;
newnode->prev = gpa;
403,7 → 403,7
}
if (&t->head != node->prev && node->prev->key == node->key) {
if ((&t->head != node->prev) && (node->prev->key == node->key)) {
/*
* Deleted node has at least one node node with the same key which is closest previous
* neighbor in the list, copy node atributes into previous node and end.
747,6 → 747,11
expnode->par->lft = NULL;
expnode->par->lft_height = 0;
}
} else if (expnode->next == &t->head) {
/*
* Special case of deleting last node with key equal 0.
*/
t->root = NULL;
}
 
/*
/branches/rcu/kernel/generic/src/adt/extavlrel.c
1017,6 → 1017,11
expnode->par->lft_height = 0;
}
nextnode->key += expnode->key;
} else {
/*
* Delete last node in tree.
*/
t->root = NULL;
}
 
/*
/branches/rcu/kernel/Makefile
258,7 → 258,8
test/avltree/avltree1.c \
test/extavltree/extavltree1.c \
test/extavlreltree/extavlreltree1.c \
test/timeout/timeout1.c
test/timeout/timeout1.c \
test/timeout/timeoutbench1.c
endif
 
## Experimental features