diff options
Diffstat (limited to 'pjlib/src/pjlib-test/rbtree.c')
-rw-r--r-- | pjlib/src/pjlib-test/rbtree.c | 334 |
1 files changed, 167 insertions, 167 deletions
diff --git a/pjlib/src/pjlib-test/rbtree.c b/pjlib/src/pjlib-test/rbtree.c index 588e58a7..dc10218d 100644 --- a/pjlib/src/pjlib-test/rbtree.c +++ b/pjlib/src/pjlib-test/rbtree.c @@ -1,167 +1,167 @@ -/* $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 */
-
-
+/* $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 */ + + |