diff options
| -rw-r--r-- | pjlib/build/Makefile | 4 | ||||
| -rw-r--r-- | pjlib/src/pj/hash.c | 6 | ||||
| -rw-r--r-- | pjlib/src/pjlib-test/hash_test.c | 162 | ||||
| -rw-r--r-- | pjlib/src/pjlib-test/test.c | 4 | ||||
| -rw-r--r-- | pjlib/src/pjlib-test/test.h | 2 |
5 files changed, 173 insertions, 5 deletions
diff --git a/pjlib/build/Makefile b/pjlib/build/Makefile index 4d747e10..c3819f34 100644 --- a/pjlib/build/Makefile +++ b/pjlib/build/Makefile @@ -33,8 +33,8 @@ export PJLIB_CFLAGS += $(_CFLAGS) # export TEST_SRCDIR = ../src/pjlib-test export TEST_OBJS += activesock.o atomic.o echo_clt.o errno.o exception.o \ - fifobuf.o file.o ioq_perf.o ioq_udp.o ioq_unreg.o \ - ioq_tcp.o \ + fifobuf.o file.o hash_test.o ioq_perf.o ioq_udp.o \ + ioq_unreg.o ioq_tcp.o \ list.o mutex.o os.o pool.o pool_perf.o rand.o rbtree.o \ select.o sleep.o sock.o sock_perf.o \ string.o test.o thread.o timer.o timestamp.o \ diff --git a/pjlib/src/pj/hash.c b/pjlib/src/pj/hash.c index ffebeea4..fb1fdcac 100644 --- a/pjlib/src/pj/hash.c +++ b/pjlib/src/pj/hash.c @@ -276,7 +276,7 @@ PJ_DEF(pj_hash_iterator_t*) pj_hash_first( pj_hash_table_t *ht, it->index = 0; it->entry = NULL; - for (; it->index < ht->rows; ++it->index) { + for (; it->index <= ht->rows; ++it->index) { it->entry = ht->table[it->index]; if (it->entry) { break; @@ -294,7 +294,7 @@ PJ_DEF(pj_hash_iterator_t*) pj_hash_next( pj_hash_table_t *ht, return it; } - for (++it->index; it->index < ht->rows; ++it->index) { + for (++it->index; it->index <= ht->rows; ++it->index) { it->entry = ht->table[it->index]; if (it->entry) { break; @@ -319,7 +319,7 @@ void pj_hash_dump_collision( pj_hash_table_t *ht ) char line[120]; int len, totlen = 0; - for (i=0; i<ht->rows; ++i) { + for (i=0; i<=ht->rows; ++i) { unsigned count = 0; pj_hash_entry *entry = ht->table[i]; while (entry) { diff --git a/pjlib/src/pjlib-test/hash_test.c b/pjlib/src/pjlib-test/hash_test.c new file mode 100644 index 00000000..336f71c3 --- /dev/null +++ b/pjlib/src/pjlib-test/hash_test.c @@ -0,0 +1,162 @@ +/* $Id:$ */ +/* + * Copyright (C)2003-2008 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 <pj/hash.h> +#include <pj/rand.h> +#include <pj/log.h> +#include <pj/pool.h> +#include "test.h" + +#if INCLUDE_HASH_TEST + +#define HASH_COUNT 31 + +static int hash_test_with_key(pj_pool_t *pool, unsigned char key) +{ + pj_hash_table_t *ht; + unsigned value = 0x12345; + pj_hash_iterator_t it_buf, *it; + unsigned *entry; + + ht = pj_hash_create(pool, HASH_COUNT); + if (!ht) + return -10; + + pj_hash_set(pool, ht, &key, sizeof(key), 0, &value); + + entry = (unsigned*) pj_hash_get(ht, &key, sizeof(key), NULL); + if (!entry) + return -20; + + if (*entry != value) + return -30; + + if (pj_hash_count(ht) != 1) + return -30; + + it = pj_hash_first(ht, &it_buf); + if (it == NULL) + return -40; + + entry = (unsigned*) pj_hash_this(ht, it); + if (!entry) + return -50; + + if (*entry != value) + return -60; + + it = pj_hash_next(ht, it); + if (it != NULL) + return -70; + + /* Erase item */ + + pj_hash_set(NULL, ht, &key, sizeof(key), 0, NULL); + + if (pj_hash_get(ht, &key, sizeof(key), NULL) != NULL) + return -80; + + if (pj_hash_count(ht) != 0) + return -90; + + it = pj_hash_first(ht, &it_buf); + if (it != NULL) + return -100; + + return 0; +} + + +static int hash_collision_test(pj_pool_t *pool) +{ + enum { + COUNT = HASH_COUNT * 4 + }; + pj_hash_table_t *ht; + pj_hash_iterator_t it_buf, *it; + unsigned char *values; + unsigned i; + + ht = pj_hash_create(pool, HASH_COUNT); + if (!ht) + return -200; + + values = (unsigned char*) pj_pool_alloc(pool, COUNT); + + for (i=0; i<COUNT; ++i) { + values[i] = (unsigned char)i; + pj_hash_set(pool, ht, &i, sizeof(i), 0, &values[i]); + } + + if (pj_hash_count(ht) != COUNT) + return -210; + + for (i=0; i<COUNT; ++i) { + unsigned char *entry; + entry = (unsigned char*) pj_hash_get(ht, &i, sizeof(i), NULL); + if (!entry) + return -220; + if (*entry != values[i]) + return -230; + } + + i = 0; + it = pj_hash_first(ht, &it_buf); + while (it) { + ++i; + it = pj_hash_next(ht, it); + } + + if (i != COUNT) + return -240; + + return 0; +} + + +/* + * Hash table test. + */ +int hash_test(void) +{ + pj_pool_t *pool = pj_pool_create(mem, "hash", 512, 512, NULL); + int rc; + unsigned i; + + /* Test to fill in each row in the table */ + for (i=0; i<=HASH_COUNT; ++i) { + rc = hash_test_with_key(pool, (unsigned char)i); + if (rc != 0) { + pj_pool_release(pool); + return rc; + } + } + + /* Collision test */ + rc = hash_collision_test(pool); + if (rc != 0) { + pj_pool_release(pool); + return rc; + } + + pj_pool_release(pool); + return 0; +} + +#endif /* INCLUDE_HASH_TEST */ + diff --git a/pjlib/src/pjlib-test/test.c b/pjlib/src/pjlib-test/test.c index 62450457..37118ee4 100644 --- a/pjlib/src/pjlib-test/test.c +++ b/pjlib/src/pjlib-test/test.c @@ -102,6 +102,10 @@ int test_inner(void) DO_TEST( rbtree_test() ); #endif +#if INCLUDE_HASH_TEST + DO_TEST( hash_test() ); +#endif + #if INCLUDE_TIMESTAMP_TEST DO_TEST( timestamp_test() ); #endif diff --git a/pjlib/src/pjlib-test/test.h b/pjlib/src/pjlib-test/test.h index c2eeb08c..41503d76 100644 --- a/pjlib/src/pjlib-test/test.h +++ b/pjlib/src/pjlib-test/test.h @@ -36,6 +36,7 @@ #define INCLUDE_EXCEPTION_TEST GROUP_LIBC #define INCLUDE_RAND_TEST GROUP_LIBC #define INCLUDE_LIST_TEST GROUP_DATA_STRUCTURE +#define INCLUDE_HASH_TEST GROUP_DATA_STRUCTURE #define INCLUDE_POOL_TEST GROUP_LIBC #define INCLUDE_POOL_PERF_TEST GROUP_LIBC #define INCLUDE_STRING_TEST GROUP_DATA_STRUCTURE @@ -74,6 +75,7 @@ extern int timestamp_test(void); extern int exception_test(void); extern int rand_test(void); extern int list_test(void); +extern int hash_test(void); extern int pool_test(void); extern int pool_perf_test(void); extern int string_test(void); |