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; |
} |