/* $Id$ */ | |
/* | |
* Copyright (C)2003-2006 Benny Prijono <benny@prijono.org> | |
* | |
* This program is free software; you can redistribute it and/or modify | |
* it under the terms of the GNU General Public License as published by | |
* the Free Software Foundation; either version 2 of the License, or | |
* (at your option) any later version. | |
* | |
* This program is distributed in the hope that it will be useful, | |
* but WITHOUT ANY WARRANTY; without even the implied warranty of | |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
* GNU General Public License for more details. | |
* | |
* You should have received a copy of the GNU General Public License | |
* along with this program; if not, write to the Free Software | |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
*/ | |
#include "test.h" | |
#if INCLUDE_RBTREE_TEST | |
#include <pjlib.h> | |
#define LOOP 32 | |
#define MIN_COUNT 64 | |
#define MAX_COUNT (LOOP * MIN_COUNT) | |
#define STRSIZE 16 | |
#define THIS_FILE "rbtree_test" | |
typedef struct node_key | |
{ | |
pj_uint32_t hash; | |
char str[STRSIZE]; | |
} node_key; | |
static int compare_node(const node_key *k1, const node_key *k2) | |
{ | |
if (k1->hash == k2->hash) { | |
return strcmp(k1->str, k2->str); | |
} else { | |
return k1->hash < k2->hash ? -1 : 1; | |
} | |
} | |
void randomize_string(char *str, int len) | |
{ | |
int i; | |
for (i=0; i<len-1; ++i) | |
str[i] = (char)('a' + pj_rand() % 26); | |
str[len-1] = '\0'; | |
} | |
static int test(void) | |
{ | |
pj_rbtree rb; | |
node_key *key; | |
pj_rbtree_node *node; | |
pj_pool_t *pool; | |
int err=0; | |
int count = MIN_COUNT; | |
int i; | |
unsigned size; | |
pj_rbtree_init(&rb, (pj_rbtree_comp*)&compare_node); | |
size = MAX_COUNT*(sizeof(*key)+PJ_RBTREE_NODE_SIZE) + | |
PJ_RBTREE_SIZE + PJ_POOL_SIZE; | |
pool = pj_pool_create( mem, "pool", size, 0, NULL); | |
if (!pool) { | |
PJ_LOG(3,("test", "...error: creating pool of %u bytes", size)); | |
return -10; | |
} | |
key = (node_key *)pj_pool_alloc(pool, MAX_COUNT*sizeof(*key)); | |
if (!key) | |
return -20; | |
node = (pj_rbtree_node*)pj_pool_alloc(pool, MAX_COUNT*sizeof(*node)); | |
if (!node) | |
return -30; | |
for (i=0; i<LOOP; ++i) { | |
int j; | |
pj_rbtree_node *prev, *it; | |
pj_timestamp t1, t2, t_setup, t_insert, t_search, t_erase; | |
pj_assert(rb.size == 0); | |
t_setup.u32.lo = t_insert.u32.lo = t_search.u32.lo = t_erase.u32.lo = 0; | |
for (j=0; j<count; j++) { | |
randomize_string(key[j].str, STRSIZE); | |
pj_get_timestamp(&t1); | |
node[j].key = &key[j]; | |
node[j].user_data = key[j].str; | |
key[j].hash = pj_hash_calc(0, key[j].str, PJ_HASH_KEY_STRING); | |
pj_get_timestamp(&t2); | |
t_setup.u32.lo += (t2.u32.lo - t1.u32.lo); | |
pj_get_timestamp(&t1); | |
pj_rbtree_insert(&rb, &node[j]); | |
pj_get_timestamp(&t2); | |
t_insert.u32.lo += (t2.u32.lo - t1.u32.lo); | |
} | |
pj_assert(rb.size == (unsigned)count); | |
// Iterate key, make sure they're sorted. | |
prev = NULL; | |
it = pj_rbtree_first(&rb); | |
while (it) { | |
if (prev) { | |
if (compare_node((node_key*)prev->key,(node_key*)it->key)>=0) { | |
++err; | |
PJ_LOG(3, (THIS_FILE, "Error: %s >= %s", | |
(char*)prev->user_data, (char*)it->user_data)); | |
} | |
} | |
prev = it; | |
it = pj_rbtree_next(&rb, it); | |
} | |
// Search. | |
for (j=0; j<count; j++) { | |
pj_get_timestamp(&t1); | |
it = pj_rbtree_find(&rb, &key[j]); | |
pj_get_timestamp(&t2); | |
t_search.u32.lo += (t2.u32.lo - t1.u32.lo); | |
pj_assert(it != NULL); | |
if (it == NULL) | |
++err; | |
} | |
// Erase node. | |
for (j=0; j<count; j++) { | |
pj_get_timestamp(&t1); | |
it = pj_rbtree_erase(&rb, &node[j]); | |
pj_get_timestamp(&t2); | |
t_erase.u32.lo += (t2.u32.lo - t1.u32.lo); | |
} | |
PJ_LOG(4, (THIS_FILE, | |
"...count:%d, setup:%d, insert:%d, search:%d, erase:%d", | |
count, | |
t_setup.u32.lo / count, t_insert.u32.lo / count, | |
t_search.u32.lo / count, t_erase.u32.lo / count)); | |
count = 2 * count; | |
if (count > MAX_COUNT) | |
break; | |
} | |
pj_pool_release(pool); | |
return err; | |
} | |
int rbtree_test() | |
{ | |
return test(); | |
} | |
#endif /* INCLUDE_RBTREE_TEST */ | |