commit 3549e9d1e6d9cba04ed58e098ff2f733b03688a2
parent 25e61caedcce78bbbc1f0be6d52115f2d932b2c8
Author: vaplv <vaplv@free.fr>
Date: Sat, 5 Apr 2014 23:19:10 +0200
Add support of specific init/copy/release hash table functors
Diffstat:
2 files changed, 144 insertions(+), 46 deletions(-)
diff --git a/src/dynamic_array.h b/src/dynamic_array.h
@@ -73,9 +73,9 @@ DARRAY_FUNC__(functor_cp__)(DARRAY_DATA* dst, DARRAY_DATA const* src)
static FINLINE int
DARRAY_FUNC__(functor_cp_and_release__)(DARRAY_DATA* dst, DARRAY_DATA* src)
{
- DARRAY_FUNCTOR_COPY(dst, src);
+ const int res = DARRAY_FUNCTOR_COPY(dst, src);
DARRAY_FUNCTOR_RELEASE(src);
- return 0;
+ return res;
}
#define DARRAY_FUNCTOR_COPY_AND_RELEASE DARRAY_FUNC__(functor_cp_and_release__)
#endif
diff --git a/src/hash_table.h b/src/hash_table.h
@@ -18,15 +18,15 @@
* - 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;
- * TODO
- * - HTABLE_FUNCTOR_INIT: init functor on HTABLE_DATA. If not defined, no
- * specific treatment is performed on the created data;
- * - HTABLE_FUNCTOR_COPY: copy functor on HTABLE_DATA. If not defined a
- * bitwise copy is used instead;
- * - HTABLE_FUNCTOR_RELEASE: release functor on HTABLE_DATA. If not defined
- * nothing is done on the release of an element;
- * - HTABLE_FUNCTOR_COPY_AND_RELEASE: Copy and release of a HTABLE_DATA. If
- * not defined the copy and the release functors is used.
+ * - 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
+ * defined a bitwise copy is used instead;
+ * - HTABLE_<DATA|KEY>_FUNCTOR_RELEASE: release functor on HTABLE_<DATA|KEY>.
+ * If not defined nothing is done on the release of an element;
+ * - HTABLE_<DATA|KEY>_FUNCTOR_COPY_AND_RELEASE: Copy and release of a
+ * HTABLE_<DATA|KEY>. If not defined the copy and the release functors is
+ * used.
*
* The name of the generated types are:
* struct htable_<HTABLE_NAME>[_pair|_iterator]
@@ -49,13 +49,12 @@
#define HTABLE__ CONCAT(htable_, HTABLE_NAME)
#define HTABLE_PAIR__ CONCAT(CONCAT(HTABLE__, _), pair)
-#define HTABLE_INTERATOR__ CONCAT(HTABLE, iterator)
+#define HTABLE_ITERATOR__ CONCAT(HTABLE, iterator)
#define HTABLE_FUNC__(Func) \
CONCAT(CONCAT(CONCAT(CONCAT(htable, _), HTABLE_NAME), _), Func)
/* Internal data structure */
-struct HTABLE_PAIR__
-{
+struct HTABLE_PAIR__ {
HTABLE_DATA data;
HTABLE_KEY key;
};
@@ -67,8 +66,7 @@ struct HTABLE_PAIR__
#define HTABLE_DATA__ CONCAT(CONCAT(darray_, HTABLE_NAME), __)
#define HTABLE_DATA_FUNC__(Func) CONCAT(CONCAT(HTABLE_DATA__, _), Func)
-struct HTABLE__
-{
+struct HTABLE__ {
struct HTABLE_DATA__ table;
struct darray_char table_slot_is_used;
size_t table_size_in_use;
@@ -79,14 +77,83 @@ struct HTABLE__
struct mem_allocator* allocator;
};
-struct HTABLE_INTERATOR__
-{
+struct HTABLE_ITERATOR__ {
struct HTABLE__* hash_table;
size_t slot;
size_t entries_scanned;
};
/*******************************************************************************
+ * Internal default functions
+ ******************************************************************************/
+#ifndef HTABLE_DATA_FUNCTOR_INIT
+static FINLINE void
+HTABLE_FUNC__(data_functor_init__)
+ (struct mem_allocator* alloc, HTABLE_DATA* data)
+{ ASSERT(data); (void)alloc, (void)data; }
+#define HTABLE_DATA_FUNCTOR_INIT HTABLE_FUNC__(data_functor_init__)
+#endif
+
+#ifndef HTABLE_KEY_FUNCTOR_INIT
+static FINLINE void
+HTABLE_FUNC__(key_functor_init__)(struct mem_allocator* alloc, HTABLE_KEY* key)
+{ ASSERT(key); (void)alloc, (void)key; }
+#define HTABLE_KEY_FUNCTOR_INIT HTABLE_FUNC__(key_functor_init__)
+#endif
+
+#ifndef HTABLE_DATA_FUNCTOR_RELEASE
+static FINLINE void
+HTABLE_FUNC__(data_functor_release__)(HTABLE_DATA* data)
+{ ASSERT(data); (void)data; }
+#define HTABLE_DATA_FUNCTOR_RELEASE HTABLE_FUNC__(data_functor_release__)
+#endif
+
+#ifndef HTABLE_KEY_FUNCTOR_RELEASE
+static FINLINE void
+HTABLE_FUNC__(key_functor_release__)(HTABLE_KEY* key)
+{ ASSERT(key); (void)key; }
+#define HTABLE_KEY_FUNCTOR_RELEASE HTABLE_FUNC__(key_functor_release__)
+#endif
+
+#ifndef HTABLE_DATA_FUNCTOR_COPY
+static FINLINE int
+HTABLE_FUNC__(data_functor_cp__)(HTABLE_DATA* dst, HTABLE_DATA const* src)
+{ ASSERT(dst && src); *dst = *src; return 0; }
+#define HTABLE_DATA_FUNCTOR_COPY HTABLE_FUNC__(data_functor_cp__)
+#endif
+
+#ifndef HTABLE_KEY_FUNCTOR_COPY
+static FINLINE int
+HTABLE_FUNC__(key_functor_cp__)(HTABLE_KEY* dst, HTABLE_KEY const* src)
+{ ASSERT(dst && src); *dst = *src; return 0; }
+#define HTABLE_KEY_FUNCTOR_COPY HTABLE_FUNC__(key_functor_cp__)
+#endif
+
+#ifndef HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE
+static FINLINE int
+HTABLE_FUNC__(data_functor_cp_and_release__)(HTABLE_DATA* dst, HTABLE_DATA* src)
+{
+ const int res = HTABLE_DATA_FUNCTOR_COPY(dst, src);
+ HTABLE_DATA_FUNCTOR_RELEASE(src);
+ return res;
+}
+#define HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE \
+ HTABLE_FUNC__(data_functor_cp_and_release__)
+#endif
+
+#ifndef HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE
+static FINLINE int
+HTABLE_FUNC__(key_functor_cp_and_release__)(HTABLE_KEY* dst, HTABLE_KEY* src)
+{
+ const int res = HTABLE_KEY_FUNCTOR_COPY(dst, src);
+ HTABLE_KEY_FUNCTOR_RELEASE(src);
+ return res;
+}
+#define HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE \
+ HTABLE_FUNC__(key_functor_cp_and_release__)
+#endif
+
+/*******************************************************************************
* Internal helper functions
******************************************************************************/
static INLINE size_t
@@ -147,21 +214,33 @@ HTABLE_FUNC__(init)
}
static INLINE void
-HTABLE_FUNC__(release)(struct HTABLE__* htbl)
+HTABLE_FUNC__(clear)(struct HTABLE__* htbl)
{
+ size_t islot = 0, in_use = 0;
ASSERT(htbl);
- HTABLE_DATA_FUNC__(release)(&htbl->table);
- darray_char_release(&htbl->table_slot_is_used);
+
+ FOR_EACH(islot, 0, HTABLE_DATA_FUNC__(size_get)(&htbl->table)) {
+ struct HTABLE_PAIR__* pair = NULL;
+ if(in_use == htbl->table_size_in_use)
+ break; /* Early stop the rehasing since there is no more slot in htbl */
+
+ if(!darray_char_cdata_get(&htbl->table_slot_is_used)[islot])
+ continue;
+
+ 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);
+ }
}
static INLINE void
-HTABLE_FUNC__(clear)(struct HTABLE__* htbl)
+HTABLE_FUNC__(release)(struct HTABLE__* htbl)
{
- ASSERT( htbl );
- htbl->table_size_in_use = 0;
- memset
- (darray_char_data_get(&htbl->table_slot_is_used), 0,
- darray_char_size_get(&htbl->table_slot_is_used) * sizeof(char));
+ ASSERT(htbl);
+ HTABLE_FUNC__(clear)(htbl);
+ HTABLE_DATA_FUNC__(release)(&htbl->table);
+ darray_char_release(&htbl->table_slot_is_used);
}
/* Return 0 on success and -1 otherwise */
@@ -170,7 +249,7 @@ HTABLE_FUNC__(reserve)(struct HTABLE__* htbl, const size_t size_submitted)
{
struct HTABLE_DATA__ tbl;
struct darray_char tbl_slot_is_used;
- const struct HTABLE_PAIR__* old_pairs = NULL;
+ struct HTABLE_PAIR__* old_pairs = NULL;
struct HTABLE_PAIR__* new_pairs = NULL;
const char* old_used_pairs = NULL;
char* new_used_pairs = NULL;
@@ -194,7 +273,7 @@ HTABLE_FUNC__(reserve)(struct HTABLE__* htbl, const size_t size_submitted)
memset(darray_char_data_get(&tbl_slot_is_used), 0, size*sizeof(char));
/* Rehash the hash table */
- old_pairs = HTABLE_DATA_FUNC__(cdata_get)(&htbl->table);
+ old_pairs = HTABLE_DATA_FUNC__(data_get)(&htbl->table);
new_pairs = HTABLE_DATA_FUNC__(data_get)(&tbl);
old_used_pairs = darray_char_cdata_get(&htbl->table_slot_is_used);
new_used_pairs = darray_char_data_get(&tbl_slot_is_used);
@@ -213,7 +292,14 @@ HTABLE_FUNC__(reserve)(struct HTABLE__* htbl, const size_t size_submitted)
(!htbl->eq_key(&new_pairs[islot_new].key, &old_pairs[islot].key ));
islot_new = (islot_new + 1) & (size - 1); /* (islot_new + 1) % size */
}
- new_pairs[islot_new] = old_pairs[islot];
+
+ 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);
+
new_used_pairs[islot_new] = 1;
++in_use;
}
@@ -237,6 +323,7 @@ HTABLE_FUNC__(set)
HTABLE_KEY const* key,
HTABLE_DATA const* data )
{
+ struct HTABLE_PAIR__* pair = NULL;
size_t tbl_size = 0;
size_t i = 0;
int res = 0;
@@ -255,11 +342,15 @@ HTABLE_FUNC__(set)
}
i = HTABLE_FUNC__(find_slot__)(htbl, key);
+ pair = HTABLE_DATA_FUNC__(data_get)(&htbl->table) + i;
if(darray_char_cdata_get(&htbl->table_slot_is_used)[i]) {
- HTABLE_DATA_FUNC__(data_get)(&htbl->table)[i].data = *data;
+ HTABLE_DATA_FUNCTOR_COPY(&pair->data, data);
} else {
- HTABLE_DATA_FUNC__(data_get)(&htbl->table)[i].data = *data;
- HTABLE_DATA_FUNC__(data_get)(&htbl->table)[i].key = *key;
+ HTABLE_KEY_FUNCTOR_INIT(htbl->allocator, &pair->key);
+ 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;
++htbl->table_size_in_use;
}
@@ -286,6 +377,8 @@ HTABLE_FUNC__(erase)(struct HTABLE__* htbl, HTABLE_KEY const* key)
/* Remove the entry */
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 */
@@ -296,7 +389,8 @@ HTABLE_FUNC__(erase)(struct HTABLE__* htbl, HTABLE_KEY const* key)
if(i <= j ? (i < k && k <= j) : (i < k || k <= j))
continue;
- pairs[i] = pairs[j];
+ HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE(&pairs[i].key, &pairs[j].key);
+ HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE(&pairs[i].data, &pairs[j].data);
used_pairs[i] = 1;
used_pairs[j] = 0;
i = j;
@@ -337,7 +431,7 @@ HTABLE_FUNC__(size_get)(const struct HTABLE__* htbl)
static INLINE void
HTABLE_FUNC__(begin)
(struct HTABLE__* htbl,
- struct HTABLE_INTERATOR__* it)
+ struct HTABLE_ITERATOR__* it)
{
const char* used_pairs = NULL;
size_t i = 0;
@@ -348,7 +442,7 @@ HTABLE_FUNC__(begin)
used_pairs = darray_char_cdata_get(&htbl->table_slot_is_used);
it->slot = it->entries_scanned = 0;
- for( i = 0; i < tbl_size && !used_pairs[i]; ++i) {}
+ for(i = 0; i < tbl_size && !used_pairs[i]; ++i) {}
it->slot = i;
it->entries_scanned = i < tbl_size;
it->hash_table = htbl;
@@ -357,7 +451,7 @@ HTABLE_FUNC__(begin)
static INLINE void
HTABLE_FUNC__(end)
(struct HTABLE__* htbl,
- struct HTABLE_INTERATOR__* it)
+ struct HTABLE_ITERATOR__* it)
{
ASSERT(htbl && it);
it->slot = HTABLE_DATA_FUNC__(size_get)(&htbl->table);
@@ -366,7 +460,7 @@ HTABLE_FUNC__(end)
}
static INLINE void
-HTABLE_FUNC__(iterator_next)(struct HTABLE_INTERATOR__* it)
+HTABLE_FUNC__(iterator_next)(struct HTABLE_ITERATOR__* it)
{
size_t tbl_size = 0;
ASSERT(it);
@@ -385,8 +479,8 @@ HTABLE_FUNC__(iterator_next)(struct HTABLE_INTERATOR__* it)
static INLINE char
HTABLE_FUNC__(iterator_eq)
- (const struct HTABLE_INTERATOR__* it0,
- const struct HTABLE_INTERATOR__* it1)
+ (const struct HTABLE_ITERATOR__* it0,
+ const struct HTABLE_ITERATOR__* it1)
{
ASSERT(it0 && it1);
return
@@ -396,26 +490,30 @@ HTABLE_FUNC__(iterator_eq)
}
static INLINE HTABLE_KEY*
-HTABLE_FUNC__(iterator_key_get)(const struct HTABLE_INTERATOR__* it)
+HTABLE_FUNC__(iterator_key_get)(const struct HTABLE_ITERATOR__* it)
{
ASSERT(it && it->slot < HTABLE_DATA_FUNC__(size_get)(&it->hash_table->table));
return &HTABLE_DATA_FUNC__(data_get)(&it->hash_table->table)[it->slot].key;
}
static INLINE HTABLE_DATA*
-HTABLE_FUNC__(iterator_data_get)(const struct HTABLE_INTERATOR__* it)
+HTABLE_FUNC__(iterator_data_get)(const struct HTABLE_ITERATOR__* it)
{
ASSERT(it && it->slot < HTABLE_DATA_FUNC__(size_get)(&it->hash_table->table));
return &HTABLE_DATA_FUNC__(data_get)(&it->hash_table->table)[it->slot].data;
}
-#undef HTABLE_KEY
#undef HTABLE_DATA
+#undef HTABLE_FUNCTOR_COPY
+#undef HTABLE_FUNCTOR_COPY_AND_RELEASE
+#undef HTABLE_FUNCTOR_INIT
+#undef HTABLE_FUNCTOR_RELEASE
+#undef HTABLE_KEY
#undef HTABLE_NAME
-#undef HTABLE
+#undef HTABLE__
#undef HTABLE_PAIR__
-#undef HTABLE_INTERATOR__
+#undef HTABLE_ITERATOR__
#undef HTABLE_FUNC__
-#endif /* Pre inclusion */
+#endif /* !HTABLE_NAME || !HTABLE_KEY || !HTABLE_DATA */
