commit 5f5bc133f3d6f2cd3bcab9b859bfc3e2459afdf0
parent c0a3c9c6f1e67d3f77da298454e52919767ff776
Author: vaplv <vaplv@free.fr>
Date: Sun, 6 Apr 2014 15:43:16 +0200
Change the hash table API
Diffstat:
4 files changed, 75 insertions(+), 53 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -61,6 +61,8 @@ set(RSYS_FILES_INC_COMMON
binary_heap.h
clock_time.h
dynamic_array.h
+ dynamic_array_char.h
+ dynamic_array_u64.h
free_list.h
hash.h
hash_table.h
diff --git a/src/dynamic_array_u64.h b/src/dynamic_array_u64.h
@@ -0,0 +1,11 @@
+#ifndef DYNAMIC_ARRRAY_U64_H
+#define DYNAMIC_ARRRAY_U64_H
+
+#include "dynamic_array.h"
+
+#define DARRAY_NAME u64
+#define DARRAY_DATA uint64_t
+#include "dynamic_array.h"
+
+#endif /* DYNAMIC_ARRRAY_U64_H */
+
diff --git a/src/hash_table.h b/src/hash_table.h
@@ -18,6 +18,9 @@
* - HTABLE_NAME: prefix of the hash table functions & types;
* - HTABLE_DATA: type of the data registered into the hash table;
* - HTABLE_KEY: type of the key indexing the hash table data;
+ * - HTABLE_KEY_FUNCTOR_HASH: hash functor on HTABLE_KEY. If not defined, use
+ * the default function that hashes the bytes of HTABLE_KEY;
+ * - HTABLE_KEY_FUNCTOR_EQ: equality functor on 2 HTABLE_KEY;
* - HTABLE_<DATA|KEY>_FUNCTOR_INIT: init functor on HTABLE_<DATA|KEY>. If not
* defined, no specific treatment is performed on the created data;
* - HTABLE_<DATA|KEY>_FUNCTOR_COPY: copy functor on HTABLE_<DATA|KEY>. If not
@@ -129,6 +132,31 @@ HTABLE_FUNC__(key_functor_cp_and_release__)(HTABLE_KEY* dst, HTABLE_KEY* src)
HTABLE_FUNC__(key_functor_cp_and_release__)
#endif
+#ifndef HTABLE_KEY_FUNCTOR_HASH
+static INLINE size_t
+HTABLE_FUNC__(key_functor_hash__)(HTABLE_KEY const* key)
+{
+#ifdef ARCH_32BITS
+ return (size_t)hash_fnv32(key, sizeof(HTABLE_KEY));
+#elif defined(ARCH_64BITS)
+ return (size_t)hash_fnv64(key, sizeof(HTABLE_KEY));
+#else
+ #error "Unexpected architecture"
+#endif
+}
+#define HTABLE_KEY_FUNCTOR_HASH HTABLE_FUNC__(key_functor_hash__)
+#endif
+
+#ifndef HTABLE_KEY_FUNCTOR_EQ
+static INLINE char
+HTABLE_FUNC__(key_functor_eq__)(HTABLE_KEY const* a, HTABLE_KEY const* b)
+{
+ ASSERT(a && b);
+ return *a == *b;
+}
+#define HTABLE_KEY_FUNCTOR_EQ HTABLE_FUNC__(key_functor_eq__)
+#endif
+
/*******************************************************************************
* Pair functor
******************************************************************************/
@@ -187,10 +215,6 @@ 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;
};
@@ -217,46 +241,30 @@ HTABLE_FUNC__(find_slot__)(const struct HTABLE__* htbl, HTABLE_KEY const* key)
pairs = HTABLE_DATA_FUNC__(cdata_get)(&htbl->table);
used_pairs = darray_char_cdata_get(&htbl->table_slot_is_used);
- /* slot = hash % size */
- slot = htbl->hash(key) & (HTABLE_DATA_FUNC__(size_get)(&htbl->table) - 1);
+ slot = /* slot = hash % size */
+ HTABLE_KEY_FUNCTOR_HASH(key)
+ & (HTABLE_DATA_FUNC__(size_get)(&htbl->table) - 1);
- while(used_pairs[slot] && !htbl->eq_key(key, &pairs[slot].key)) {
+ while(used_pairs[slot] && !HTABLE_KEY_FUNCTOR_EQ(key, &pairs[slot].key)) {
/* slot = (slot + 1) % size */
slot = (slot + 1) & (HTABLE_DATA_FUNC__(size_get)(&htbl->table) - 1);
}
return slot;
}
-static INLINE size_t
-HTABLE_FUNC__(hash__)(HTABLE_KEY const* key)
-{
-#ifdef ARCH_32BITS
- return (size_t)hash_fnv32(key, sizeof(HTABLE_KEY));
-#elif defined(ARCH_64BITS)
- return (size_t)hash_fnv64(key, sizeof(HTABLE_KEY));
-#else
- #error "Unexpected architecture"
-#endif
-}
-
/*******************************************************************************
* Hash table API
******************************************************************************/
static INLINE void
HTABLE_FUNC__(init)
- (struct HTABLE__* htbl,
- /* May be NULL <=> use default allocator */
+ ( /* May be NULL <=> use default allocator */
struct mem_allocator* allocator,
- /* May be NULL <=> use default hash function */
- size_t (*hash)(HTABLE_KEY const*),
- char (*eq_key)(HTABLE_KEY const*, HTABLE_KEY const*))
+ struct HTABLE__* htbl)
{
- ASSERT( htbl && eq_key );
+ ASSERT(htbl);
HTABLE_DATA_FUNC__(init)(allocator, &htbl->table);
darray_char_init(allocator, &htbl->table_slot_is_used);
htbl->table_size_in_use = 0;
- htbl->hash = hash ? hash : HTABLE_FUNC__(hash__);
- htbl->eq_key = eq_key;
htbl->allocator = allocator ? allocator : &mem_default_allocator;
}
@@ -336,10 +344,11 @@ HTABLE_FUNC__(reserve)(struct HTABLE__* htbl, const size_t size_submitted)
if(!old_used_pairs[islot])
continue;
- islot_new = htbl->hash(&old_pairs[islot].key) & (size - 1);
+ islot_new = HTABLE_KEY_FUNCTOR_HASH(&old_pairs[islot].key) & (size - 1);
while(new_used_pairs[islot_new]) {
- ASSERT /* There is at most 1 entry for a given key */
- (!htbl->eq_key(&new_pairs[islot_new].key, &old_pairs[islot].key ));
+ /* There is at most 1 entry for a given key */
+ ASSERT(!HTABLE_KEY_FUNCTOR_EQ
+ (&new_pairs[islot_new].key, &old_pairs[islot].key ));
islot_new = (islot_new + 1) & (size - 1); /* (islot_new + 1) % size */
}
@@ -429,7 +438,7 @@ HTABLE_FUNC__(erase)(struct HTABLE__* htbl, HTABLE_KEY const* key)
for(j = (i + 1) & (tbl_size - 1); /* <=> j = (i+1) % size */
used_pairs[j];
j = (j + 1) & (tbl_size - 1) ) { /* <=> j = (j+1) % size */
- const size_t k = htbl->hash(&pairs[j].key) & (tbl_size- 1);
+ const size_t k = HTABLE_KEY_FUNCTOR_HASH(&pairs[j].key) & (tbl_size- 1);
if(i <= j ? (i < k && k <= j) : (i < k || k <= j))
continue;
@@ -550,16 +559,18 @@ HTABLE_FUNC__(iterator_data_get)(const struct HTABLE_ITERATOR__* it)
return &HTABLE_DATA_FUNC__(data_get)(&it->hash_table->table)[it->slot].data;
}
-#undef HTABLE_DATA
+#undef HTABLE_KEY
#undef HTABLE_KEY_FUNCTOR_COPY
#undef HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE
+#undef HTABLE_KEY_FUNCTOR_EQ
+#undef HTABLE_KEY_FUNCTOR_HASH
#undef HTABLE_KEY_FUNCTOR_INIT
#undef HTABLE_KEY_FUNCTOR_RELEASE
+#undef HTABLE_DATA
#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__
#undef HTABLE_PAIR__
diff --git a/src/test_hash_table.c b/src/test_hash_table.c
@@ -9,12 +9,6 @@
#define HTABLE_NAME int_float
#include "hash_table.h"
-static INLINE char
-eq_int(const int* a, const int* b)
-{
- return *a == *b;
-}
-
static void
test_htbl_int_float(void)
{
@@ -23,12 +17,12 @@ test_htbl_int_float(void)
int i;
const int n = 678;
- htable_int_float_init(&htbl, NULL, NULL, eq_int);
+ htable_int_float_init(NULL, &htbl);
htable_int_float_release(&htbl);
mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator);
- htable_int_float_init(&htbl, &allocator_proxy, NULL, eq_int);
+ htable_int_float_init(&allocator_proxy, &htbl);
htable_int_float_reserve(&htbl, 30);
FOR_EACH(i, 0, n) {
@@ -66,15 +60,6 @@ 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)
{
@@ -87,6 +72,17 @@ hash_str(const struct str* a)
return hash_fnv32(str_cget(a), str_len(a));
}
+#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
+#define HTABLE_KEY_FUNCTOR_EQ eq_str
+#define HTABLE_KEY_FUNCTOR_HASH hash_str
+#include "hash_table.h"
+
static void
test_htbl_str_int(void)
{
@@ -145,7 +141,7 @@ test_htbl_str_int(void)
str_init(&allocator_proxy, &tmp);
- htable_str_int_init(&htbl, &allocator_proxy, hash_str, eq_str);
+ htable_str_int_init(&allocator_proxy, &htbl);
CHECK(htable_str_int_is_empty(&htbl), 1);
str_set(&tmp, "empty");
CHECK(htable_str_int_find(&htbl, &tmp), NULL);
@@ -231,7 +227,7 @@ test_htbl_str_int(void)
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_init(&allocator_proxy, &htbl);
htable_str_int_reserve(&htbl, 3);
str_set(&tmp, "Zero"), i = 0;
CHECK(htable_str_int_set(&htbl, &tmp, &i), 0);
@@ -271,6 +267,8 @@ test_htbl_str_int(void)
#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
+#define HTABLE_KEY_FUNCTOR_EQ eq_str
+#define HTABLE_KEY_FUNCTOR_HASH hash_str
#define HTABLE_DATA_FUNCTOR_INIT darray_char_init
#define HTABLE_DATA_FUNCTOR_RELEASE darray_char_release
#define HTABLE_DATA_FUNCTOR_COPY darray_char_copy
@@ -350,7 +348,7 @@ ANGVBA BS QRZBAF EHA NZBX VA BHE PVGVRF.",
const size_t nerase = 3;
mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator);
- htable_str_darray_init(&htbl, &allocator_proxy, hash_str, eq_str);
+ htable_str_darray_init(&allocator_proxy, &htbl);
darray_char_init(&allocator_proxy, &darray);
str_init(&allocator_proxy, &tmp);
