/* $Id: rbtree.c 974 2007-02-19 01:13:53Z bennylp $ *//*  * Copyright (C)2003-2007 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 */