commit 42666630355d4fd027a1ffef71656527e05a301a
parent 3549e9d1e6d9cba04ed58e098ff2f733b03688a2
Author: vaplv <vaplv@free.fr>
Date: Sun, 6 Apr 2014 00:35:43 +0200
Test and fix the init/copy/release hash table functors
Diffstat:
4 files changed, 296 insertions(+), 49 deletions(-)
diff --git a/src/hash.h b/src/hash.h
@@ -1,7 +1,7 @@
#ifndef HASH_H
#define HASH_H
-#include "hash.h"
+#include "rsys.h"
/* 32-bits Fowler/Noll/Vo hash function */
static INLINE uint32_t
@@ -28,7 +28,7 @@ hash_fnv64(const void* data, const size_t len)
{
const uint64_t FNV64_PRIME =
(uint64_t)(((uint64_t)1<<40) + ((uint64_t)1<<8) + 0xB3);
- const uint64_t OFFSET64_BASIS = 14695981039346656037u;
+ const uint64_t OFFSET64_BASIS = (uint64_t)14695981039346656037u;
const char* octets = (const char*)data;
uint64_t hash = OFFSET64_BASIS;
size_t i;
diff --git a/src/hash_table.h b/src/hash_table.h
@@ -49,7 +49,7 @@
#define HTABLE__ CONCAT(htable_, HTABLE_NAME)
#define HTABLE_PAIR__ CONCAT(CONCAT(HTABLE__, _), pair)
-#define HTABLE_ITERATOR__ CONCAT(HTABLE, iterator)
+#define HTABLE_ITERATOR__ CONCAT(CONCAT(HTABLE__, _), iterator)
#define HTABLE_FUNC__(Func) \
CONCAT(CONCAT(CONCAT(CONCAT(htable, _), HTABLE_NAME), _), Func)
@@ -59,30 +59,6 @@ struct HTABLE_PAIR__ {
HTABLE_KEY key;
};
-#define DARRAY_NAME CONCAT(HTABLE_NAME, __)
-#define DARRAY_DATA struct HTABLE_PAIR__
-#include "dynamic_array.h"
-
-#define HTABLE_DATA__ CONCAT(CONCAT(darray_, HTABLE_NAME), __)
-#define HTABLE_DATA_FUNC__(Func) CONCAT(CONCAT(HTABLE_DATA__, _), Func)
-
-struct HTABLE__ {
- struct HTABLE_DATA__ table;
- struct darray_char table_slot_is_used;
- size_t table_size_in_use;
-
- size_t (*hash)(HTABLE_KEY const*);
- char (*eq_key)(HTABLE_KEY const*, HTABLE_KEY const*);
-
- struct mem_allocator* allocator;
-};
-
-struct HTABLE_ITERATOR__ {
- struct HTABLE__* hash_table;
- size_t slot;
- size_t entries_scanned;
-};
-
/*******************************************************************************
* Internal default functions
******************************************************************************/
@@ -154,6 +130,77 @@ HTABLE_FUNC__(key_functor_cp_and_release__)(HTABLE_KEY* dst, HTABLE_KEY* src)
#endif
/*******************************************************************************
+ * Pair functor
+ ******************************************************************************/
+static INLINE void
+HTABLE_FUNC__(pair_init__)
+ (struct mem_allocator* allocator, struct HTABLE_PAIR__* pair)
+{
+ HTABLE_KEY_FUNCTOR_INIT(allocator, &pair->key);
+ HTABLE_DATA_FUNCTOR_INIT(allocator, &pair->data);
+}
+
+static INLINE void
+HTABLE_FUNC__(pair_release__)(struct HTABLE_PAIR__* pair)
+{
+ HTABLE_KEY_FUNCTOR_RELEASE(&pair->key);
+ HTABLE_DATA_FUNCTOR_RELEASE(&pair->data);
+}
+
+static INLINE int
+HTABLE_FUNC__(pair_copy__)
+ (struct HTABLE_PAIR__* dst, struct HTABLE_PAIR__ const* src)
+{
+ int res = 0;
+ if((res = HTABLE_KEY_FUNCTOR_COPY(&dst->key, &src->key)))
+ return res;
+ res = HTABLE_DATA_FUNCTOR_COPY(&dst->data, &src->data);
+ return res;
+}
+
+static INLINE int
+HTABLE_FUNC__(pair_copy_and_release__)
+ (struct HTABLE_PAIR__* dst, struct HTABLE_PAIR__* src)
+{
+ int res = 0;
+ if((res = HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE(&dst->key, &src->key)))
+ return res;
+ res = HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE(&dst->data, &src->data);
+ return res;
+}
+
+/*******************************************************************************
+ * Data types
+ ******************************************************************************/
+#define DARRAY_NAME CONCAT(HTABLE_NAME, __)
+#define DARRAY_DATA struct HTABLE_PAIR__
+#define DARRAY_FUNCTOR_INIT HTABLE_FUNC__(pair_init__)
+#define DARRAY_FUNCTOR_RELEASE HTABLE_FUNC__(pair_release__)
+#define DARRAY_FUNCTOR_COPY HTABLE_FUNC__(pair_copy__)
+#define DARRAY_FUNCTOR_COPY_AND_RELEASE HTABLE_FUNC__(pair_copy_and_release__)
+#include "dynamic_array.h"
+
+#define HTABLE_DATA__ CONCAT(CONCAT(darray_, HTABLE_NAME), __)
+#define HTABLE_DATA_FUNC__(Func) CONCAT(CONCAT(HTABLE_DATA__, _), Func)
+
+struct HTABLE__ {
+ struct HTABLE_DATA__ table;
+ struct darray_char table_slot_is_used;
+ size_t table_size_in_use;
+
+ size_t (*hash)(HTABLE_KEY const*);
+ char (*eq_key)(HTABLE_KEY const*, HTABLE_KEY const*);
+
+ struct mem_allocator* allocator;
+};
+
+struct HTABLE_ITERATOR__ {
+ struct HTABLE__* hash_table;
+ size_t slot;
+ size_t entries_scanned;
+};
+
+/*******************************************************************************
* Internal helper functions
******************************************************************************/
static INLINE size_t
@@ -229,9 +276,9 @@ HTABLE_FUNC__(clear)(struct HTABLE__* htbl)
darray_char_data_get(&htbl->table_slot_is_used)[islot] = 0;
pair = HTABLE_DATA_FUNC__(data_get)(&htbl->table) + islot;
- HTABLE_KEY_FUNCTOR_RELEASE(&pair->key);
- HTABLE_DATA_FUNCTOR_RELEASE(&pair->data);
+ HTABLE_FUNC__(pair_release__)(pair);
}
+ htbl->table_size_in_use = 0;
}
static INLINE void
@@ -293,12 +340,9 @@ HTABLE_FUNC__(reserve)(struct HTABLE__* htbl, const size_t size_submitted)
islot_new = (islot_new + 1) & (size - 1); /* (islot_new + 1) % size */
}
- HTABLE_KEY_FUNCTOR_INIT(htbl->allocator, &new_pairs[islot_new].key);
- HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE
- (&new_pairs[islot_new].key, &old_pairs[islot].key);
- HTABLE_DATA_FUNCTOR_INIT(htbl->allocator, &new_pairs[islot_new].data);
- HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE
- (&new_pairs[islot_new].data, &old_pairs[islot].data);
+ HTABLE_FUNC__(pair_init__)(htbl->allocator, &new_pairs[islot_new]);
+ HTABLE_FUNC__(pair_copy_and_release__)
+ (&new_pairs[islot_new], &old_pairs[islot]);
new_used_pairs[islot_new] = 1;
++in_use;
@@ -346,9 +390,8 @@ HTABLE_FUNC__(set)
if(darray_char_cdata_get(&htbl->table_slot_is_used)[i]) {
HTABLE_DATA_FUNCTOR_COPY(&pair->data, data);
} else {
- HTABLE_KEY_FUNCTOR_INIT(htbl->allocator, &pair->key);
+ HTABLE_FUNC__(pair_init__)(htbl->allocator, pair);
HTABLE_KEY_FUNCTOR_COPY(&pair->key, key);
- HTABLE_DATA_FUNCTOR_INIT(htbl->allocator, &pair->data);
HTABLE_DATA_FUNCTOR_COPY(&pair->data, data);
darray_char_data_get(&htbl->table_slot_is_used)[i] = 1;
@@ -376,9 +419,8 @@ HTABLE_FUNC__(erase)(struct HTABLE__* htbl, HTABLE_KEY const* key)
return 0; /* No entry */
/* Remove the entry */
+ HTABLE_FUNC__(pair_release__)(&pairs[i]);
used_pairs[i] = 0;
- HTABLE_KEY_FUNCTOR_RELEASE(&pairs[i].key);
- HTABLE_DATA_FUNCTOR_RELEASE(&pairs[i].data);
--htbl->table_size_in_use;
for(j = (i + 1) & (tbl_size - 1); /* <=> j = (i+1) % size */
@@ -389,8 +431,8 @@ HTABLE_FUNC__(erase)(struct HTABLE__* htbl, HTABLE_KEY const* key)
if(i <= j ? (i < k && k <= j) : (i < k || k <= j))
continue;
- HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE(&pairs[i].key, &pairs[j].key);
- HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE(&pairs[i].data, &pairs[j].data);
+ HTABLE_FUNC__(pair_init__)(htbl->allocator, &pairs[i]);
+ HTABLE_FUNC__(pair_copy_and_release__)(&pairs[i], &pairs[j]);
used_pairs[i] = 1;
used_pairs[j] = 0;
i = j;
@@ -504,10 +546,14 @@ HTABLE_FUNC__(iterator_data_get)(const struct HTABLE_ITERATOR__* it)
}
#undef HTABLE_DATA
-#undef HTABLE_FUNCTOR_COPY
-#undef HTABLE_FUNCTOR_COPY_AND_RELEASE
-#undef HTABLE_FUNCTOR_INIT
-#undef HTABLE_FUNCTOR_RELEASE
+#undef HTABLE_KEY_FUNCTOR_COPY
+#undef HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE
+#undef HTABLE_KEY_FUNCTOR_INIT
+#undef HTABLE_KEY_FUNCTOR_RELEASE
+#undef HTABLE_DATA_FUNCTOR_COPY
+#undef HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE
+#undef HTABLE_DATA_FUNCTOR_INIT
+#undef HTABLE_DATA_FUNCTOR_RELEASE
#undef HTABLE_KEY
#undef HTABLE_NAME
#undef HTABLE__
diff --git a/src/str.h b/src/str.h
@@ -34,7 +34,7 @@ str_release(struct str* str)
}
static INLINE size_t
-str_len(struct str* str)
+str_len(const struct str* str)
{
ASSERT(str);
return str->len;
diff --git a/src/test_hash_table.c b/src/test_hash_table.c
@@ -1,4 +1,6 @@
+#include "hash.h"
#include "hash_table.h"
+#include "str.h"
#include <string.h>
#define HTABLE_KEY int
@@ -7,13 +9,13 @@
#include "hash_table.h"
static INLINE char
-eq_int( const int* a, const int* b )
+eq_int(const int* a, const int* b)
{
return *a == *b;
}
static void
-test_htbl_int_float( void )
+test_htbl_int_float(void)
{
struct mem_allocator allocator_proxy;
struct htable_int_float htbl;
@@ -33,7 +35,7 @@ test_htbl_int_float( void )
CHECK(htable_int_float_set(&htbl, &i, &f), 0);
}
- FOR_EACH( i, 0, n ) {
+ FOR_EACH(i, 0, n) {
float* p = htable_int_float_find(&htbl, &i);
NCHECK(p, NULL);
CHECK(*p, (float) i);
@@ -63,11 +65,210 @@ test_htbl_int_float( void )
mem_shutdown_proxy_allocator(&allocator_proxy);
}
+#define HTABLE_KEY struct str
+#define HTABLE_DATA int
+#define HTABLE_NAME str_int
+#define HTABLE_KEY_FUNCTOR_INIT str_init
+#define HTABLE_KEY_FUNCTOR_RELEASE str_release
+#define HTABLE_KEY_FUNCTOR_COPY str_copy
+#define HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE str_copy_and_release
+#include "hash_table.h"
+
+static INLINE char
+eq_str(const struct str* a, const struct str* b)
+{
+ return !strcmp(str_cget(a), str_cget(b));
+}
+
+static INLINE size_t
+hash_str(const struct str* a)
+{
+ return hash_fnv32(str_cget(a), str_len(a));
+}
+
+static void
+test_htbl_str_int(void)
+{
+ struct mem_allocator allocator_proxy;
+ struct htable_str_int htbl;
+ struct htable_str_int_iterator it0;
+ struct htable_str_int_iterator it1;
+ const char* str[] = {
+ "analyse", "analysis", "analyst", "analytic", "analytical", "analytically",
+ "analyze", "approach", "approachable", "area", "assess", "assessable",
+ "assessment", "assume", "assumed", "assuming", "assumption",
+ "authoritative", "authoritatively", "authority", "availability",
+ "available", "beneficial", "beneficiary", "benefit", "blinker", "concept",
+ "conception", "conceptual", "conceptualize", "conceptually", "consist",
+ "consistency", "consistent", "consistently", "constituency", "constituent",
+ "constitute", "constitution", "constitutional", "constitutionally",
+ "constitutive", "context", "contextual", "contextualization",
+ "contextualize", "contextually", "contract", "contractor", "create",
+ "creation", "creative", "creatively", "creativity", "creator", "data",
+ "definable", "define", "definition", "derivation", "derivative", "derive",
+ "disestablish", "disestablishment", "dissimilar", "dissimilarity",
+ "distribute", "distribution", "distributional", "distributive",
+ "distributor", "economic", "economical", "economically", "economics",
+ "economist", "economy", "environment", "environmental", "environmentalism",
+ "environmentalist", "environmentally", "establish", "established",
+ "establishment", "estimate", "estimation", "evidence", "evident",
+ "evidential", "evidently", "export", "exporter", "factor", "finance",
+ "financial", "financially", "financier", "financing", "formula"
+ };
+ char str_found[sizeof(str) / sizeof(const char*)];
+ const int str_size = (int)(sizeof(str) / sizeof(const char*));
+ int array[32];
+ const int array_size = (int)(sizeof(array) / sizeof(int));
+ struct str tmp;
+ int i = 0;
+ int * data = NULL;
+ STATIC_ASSERT
+ (sizeof(str)/sizeof(const char*) >= sizeof(array)/sizeof(int),
+ Unexpected_array_size);
+
+ mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator);
+
+ FOR_EACH(i, 0, (int)array_size) {
+ /* Compute a str id that is not already registered into array */
+ int j = rand() % str_size;
+ for(;;) {
+ int k;
+ FOR_EACH(k, 0, i) {
+ if(array[k] == j) break;
+ }
+ if(k >= i) break;
+ j = j + 1 % str_size;
+ }
+ array[i] = j;
+ }
+
+ str_init(&allocator_proxy, &tmp);
+
+ htable_str_int_init(&htbl, &allocator_proxy, hash_str, eq_str);
+ CHECK(htable_str_int_is_empty(&htbl), 1);
+ str_set(&tmp, "empty");
+ CHECK(htable_str_int_find(&htbl, &tmp), NULL);
+ CHECK(htable_str_int_size_get(&htbl), 0);
+ i = 0;
+ str_set(&tmp, str[i]);
+ CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
+ CHECK(htable_str_int_is_empty(&htbl), 0);
+ CHECK(htable_str_int_size_get(&htbl), 1);
+
+ FOR_EACH(i, 1, str_size) {
+ str_set(&tmp, str[i]);
+ CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
+ }
+ CHECK(htable_str_int_size_get(&htbl), (size_t)str_size);
+
+ str_set(&tmp, "Terra icognita");
+ CHECK(htable_str_int_find(&htbl, &tmp), NULL);
+ FOR_EACH(i, 0, 64) {
+ int j = rand() % str_size;
+ str_set(&tmp, str[j]);
+ data = htable_str_int_find(&htbl, &tmp);
+ NCHECK(data, NULL);
+ CHECK(*data, (int)j);
+ }
+
+ str_set(&tmp, "Terra icognita");
+ CHECK(htable_str_int_erase(&htbl, &tmp), 0);
+ FOR_EACH(i, 0, array_size) {
+ str_set(&tmp, str[array[i]]);
+ CHECK(htable_str_int_erase(&htbl, &tmp), 1);
+ }
+ FOR_EACH(i, 0, array_size) {
+ str_set(&tmp, str[array[i]]);
+ CHECK(htable_str_int_find(&htbl, &tmp), 0);
+ }
+ CHECK(htable_str_int_size_get(&htbl), (size_t)(str_size - array_size));
+ FOR_EACH(i, 0, str_size) {
+ int j = 0;
+ FOR_EACH(j, 0, array_size) {
+ if(array[j] == i)
+ break;
+ }
+ if(j >= array_size) {
+ str_set(&tmp, str[i]);
+ data = htable_str_int_find(&htbl, &tmp);
+ NCHECK(data, NULL);
+ CHECK(*data, (int)i);
+ }
+ }
+ FOR_EACH(i, 0, array_size) {
+ str_set(&tmp, str[array[i]]);
+ CHECK(htable_str_int_set(&htbl, &tmp, array + i), 0);
+ }
+ CHECK(htable_str_int_size_get(&htbl), (size_t)str_size);
+ CHECK(htable_str_int_is_empty(&htbl), 0);
+
+ htable_str_int_begin(&htbl, &it0);
+ htable_str_int_end(&htbl, &it1);
+ CHECK(htable_str_int_iterator_eq(&it0, &it0), 1);
+ CHECK(htable_str_int_iterator_eq(&it0, &it1), 0);
+ memset(str_found, 0, sizeof(str_found));
+ while(!htable_str_int_iterator_eq(&it0, &it1) ) {
+ data = htable_str_int_iterator_data_get(&it0);
+ CHECK
+ (*htable_str_int_find(&htbl, htable_str_int_iterator_key_get(&it0) ),
+ *data);
+ CHECK(str_found[*data], 0);
+ str_found[*data] = 1;
+ htable_str_int_iterator_next(&it0);
+ }
+
+ FOR_EACH(i, 0, str_size) {
+ CHECK(str_found[i], 1);
+ }
+
+ htable_str_int_clear(&htbl);
+ htable_str_int_begin(&htbl, &it0);
+ htable_str_int_end(&htbl, &it1);
+ CHECK(htable_str_int_iterator_eq(&it0, &it1), 1);
+
+ CHECK(htable_str_int_is_empty(&htbl), 1);
+ CHECK(htable_str_int_size_get(&htbl), 0);
+ htable_str_int_release(&htbl);
+
+ htable_str_int_init(&htbl, &allocator_proxy, hash_str, eq_str);
+ htable_str_int_reserve(&htbl, 3);
+ str_set(&tmp, "Zero"), i = 0;
+ CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
+ str_set(&tmp, "One"), i = 1;
+ CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
+ str_set(&tmp, "Two"), i = 2;
+ CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
+ str_set(&tmp, "Three"), i = 3;
+ CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
+ str_set(&tmp, "Four"), i = 4;
+ CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
+ CHECK(htable_str_int_size_get(&htbl), 5);
+ str_set(&tmp, "Zero"), i = 'a';
+ CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
+ CHECK(htable_str_int_size_get(&htbl), 5);
+
+ data = htable_str_int_find(&htbl, &tmp);
+ NCHECK(data, NULL);
+ CHECK(*data, 'a');
+ htable_str_int_release(&htbl);
+
+ str_release(&tmp);
+
+ if(MEM_ALLOCATED_SIZE(&allocator_proxy) ) {
+ char dump[512];
+ MEM_DUMP(&allocator_proxy, dump, sizeof(dump) / sizeof(char));
+ fprintf(stderr, "error: %s\n", dump);
+ FATAL("Memory leaks\n");
+ }
+ mem_shutdown_proxy_allocator(&allocator_proxy);
+}
+
int
main(int argc, char** argv)
{
(void)argc, (void)argv;
test_htbl_int_float();
+ test_htbl_str_int();
return 0;
}
