commit c0a3c9c6f1e67d3f77da298454e52919767ff776
parent 3727b0670857d3e99af7b0d98a368416d67fbc7a
Author: vaplv <vaplv@free.fr>
Date: Sun, 6 Apr 2014 15:04:52 +0200
Fix dynamic_array and hash_table issues
Push further the hash_table tests
Diffstat:
3 files changed, 169 insertions(+), 6 deletions(-)
diff --git a/src/dynamic_array.h b/src/dynamic_array.h
@@ -250,8 +250,10 @@ DARRAY_FUNC__(copy_and_clear)
if(src->data != src->buf && src->allocator == dst->allocator) {
/* Give the ownership of src->m_Data to dst */
- if(dst->data != dst->buf)
+ if(dst->data != dst->buf) {
+ DARRAY_FUNC__(clear)(dst);
MEM_FREE(dst->allocator, dst->data);
+ }
dst->data = src->data;
dst->capacity = src->capacity;
dst->size = src->size;
diff --git a/src/hash_table.h b/src/hash_table.h
@@ -276,7 +276,10 @@ 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;
+ /* Release the pair data and re-init it since it must keep valid for
+ * subsequent uses */
HTABLE_FUNC__(pair_release__)(pair);
+ HTABLE_FUNC__(pair_init__)(htbl->allocator, pair);
}
htbl->table_size_in_use = 0;
}
@@ -340,9 +343,11 @@ HTABLE_FUNC__(reserve)(struct HTABLE__* htbl, const size_t size_submitted)
islot_new = (islot_new + 1) & (size - 1); /* (islot_new + 1) % size */
}
- HTABLE_FUNC__(pair_init__)(htbl->allocator, &new_pairs[islot_new]);
+ /* Transfer ownership of old_pairs[islot] data to new_pairs[islot_new].
+ * Re-init the old_pairs[islot] structure since it must keep valid */
HTABLE_FUNC__(pair_copy_and_release__)
(&new_pairs[islot_new], &old_pairs[islot]);
+ HTABLE_FUNC__(pair_init__)(htbl->allocator, &old_pairs[islot]);
new_used_pairs[islot_new] = 1;
++in_use;
@@ -390,7 +395,6 @@ HTABLE_FUNC__(set)
if(darray_char_cdata_get(&htbl->table_slot_is_used)[i]) {
HTABLE_DATA_FUNCTOR_COPY(&pair->data, data);
} else {
- HTABLE_FUNC__(pair_init__)(htbl->allocator, pair);
HTABLE_KEY_FUNCTOR_COPY(&pair->key, key);
HTABLE_DATA_FUNCTOR_COPY(&pair->data, data);
@@ -418,8 +422,7 @@ HTABLE_FUNC__(erase)(struct HTABLE__* htbl, HTABLE_KEY const* key)
if(!used_pairs[i])
return 0; /* No entry */
- /* Remove the entry */
- HTABLE_FUNC__(pair_release__)(&pairs[i]);
+ /* Remove the entry but does not release it */
used_pairs[i] = 0;
--htbl->table_size_in_use;
@@ -431,8 +434,10 @@ HTABLE_FUNC__(erase)(struct HTABLE__* htbl, HTABLE_KEY const* key)
if(i <= j ? (i < k && k <= j) : (i < k || k <= j))
continue;
- HTABLE_FUNC__(pair_init__)(htbl->allocator, &pairs[i]);
+ /* Transfer ownership of pairs[j] data to pairs[i]. Re-init pairs[j] since
+ * it must keep valid for subsequent uses */
HTABLE_FUNC__(pair_copy_and_release__)(&pairs[i], &pairs[j]);
+ HTABLE_FUNC__(pair_init__)(htbl->allocator, &pairs[j]);
used_pairs[i] = 1;
used_pairs[j] = 0;
i = j;
diff --git a/src/test_hash_table.c b/src/test_hash_table.c
@@ -1,3 +1,4 @@
+#include "dynamic_array_char.h"
#include "hash.h"
#include "hash_table.h"
#include "str.h"
@@ -263,12 +264,167 @@ test_htbl_str_int(void)
mem_shutdown_proxy_allocator(&allocator_proxy);
}
+#define HTABLE_KEY struct str
+#define HTABLE_DATA struct darray_char
+#define HTABLE_NAME str_darray
+#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_DATA_FUNCTOR_INIT darray_char_init
+#define HTABLE_DATA_FUNCTOR_RELEASE darray_char_release
+#define HTABLE_DATA_FUNCTOR_COPY darray_char_copy
+#define HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE darray_char_copy_and_release
+#include "hash_table.h"
+
+static void
+test_htbl_str_darray(void)
+{
+ struct mem_allocator allocator_proxy;
+ struct htable_str_darray htbl;
+ struct htable_str_darray_iterator it0;
+ struct htable_str_darray_iterator it1;
+ struct darray_char darray;
+ struct darray_char* data = NULL;
+ struct str* key = NULL;
+ struct str tmp;
+ const char* str[] = {
+"Rcvfbqr 1, XARR-QRRC VA GUR QRNQ:\n\
+---------------------------------",
+
+"BAPR LBH ORNG GUR OVT ONQNFFRF NAQ PYRNA BHG GUR ZBBA ONFR LBH'ER FHCCBFRQ GB\n\
+JVA, NERA'G LBH? NERA'G LBH? JURER'F LBHE SNG ERJNEQ NAQ GVPXRG UBZR? JUNG\n\
+GUR URYY VF GUVF? VG'F ABG FHCCBFRQ GB RAQ GUVF JNL!",
+
+"VG FGVAXF YVXR EBGGRA ZRNG, OHG YBBXF YVXR GUR YBFG QRVZBF ONFR. YBBXF YVXR\n\
+LBH'ER FGHPX BA GUR FUBERF BS URYY. GUR BAYL JNL BHG VF GUEBHTU.",
+
+"GB PBAGVAHR GUR QBBZ RKCREVRAPR, CYNL GUR FUBERF BS URYY NAQ VGF NZNMVAT\n\
+FRDHRY, VASREAB!",
+
+"Rcvfbqr 2, GUR FUBERF BS URYY:\n\
+------------------------------",
+
+"LBH'IR QBAR VG! GUR UVQRBHF PLORE- QRZBA YBEQ GUNG EHYRQ GUR YBFG QRVZBF ZBBA\n\
+ONFR UNF ORRA FYNVA NAQ LBH NER GEVHZCUNAG! OHG ... JURER NER LBH? LBH\n\
+PYNZORE GB GUR RQTR BS GUR ZBBA NAQ YBBX QBJA GB FRR GUR NJSHY GEHGU.",
+
+"QRVZBF SYBNGF NOBIR URYY VGFRYS! LBH'IR ARIRE URNEQ BS NALBAR RFPNCVAT SEBZ\n\
+URYY, OHG LBH'YY ZNXR GUR ONFGNEQF FBEEL GURL RIRE URNEQ BS LBH! DHVPXYL, LBH\n\
+ENCCRY QBJA GB GUR FHESNPR BS URYY.",
+
+"ABJ, VG'F BA GB GUR SVANY PUNCGRE BS QBBZ! -- VASREAB.",
+
+"Rcvfbqr 3, VASREAB:\n\
+-------------------",
+
+"GUR YBNGUFBZR FCVQREQRZBA GUNG ZNFGREZVAQRQ GUR VAINFVBA BS GUR ZBBA ONFRF\n\
+NAQ PNHFRQ FB ZHPU QRNGU UNF UNQ VGF NFF XVPXRQ SBE NYY GVZR.",
+
+"N UVQQRA QBBEJNL BCRAF NAQ LBH RAGRE. LBH'IR CEBIRA GBB GBHTU SBE URYY GB\n\
+PBAGNVA, NAQ ABJ URYY NG YNFG CYNLF SNVE -- SBE LBH RZRETR SEBZ GUR QBBE GB\n\
+FRR GUR TERRA SVRYQF BS RNEGU! UBZR NG YNFG.",
+
+"LBH JBAQRE JUNG'F ORRA UNCCRAVAT BA RNEGU JUVYR LBH JRER ONGGYVAT RIVY\n\
+HAYRNFURQ. VG'F TBBQ GUNG AB URYY- FCNJA PBHYQ UNIR PBZR GUEBHTU GUNG QBBE\n\
+JVGU LBH ...",
+
+"Rcvfbqr 4, GUL SYRFU PBAFHZRQ:\n\
+------------------------------",
+
+"GUR FCVQRE ZNFGREZVAQ ZHFG UNIR FRAG SBEGU VGF YRTVBAF BS URYYFCNJA ORSBER\n\
+LBHE SVANY PBASEBAGNGVBA JVGU GUNG GREEVOYR ORNFG SEBZ URYY. OHG LBH FGRCCRQ\n\
+SBEJNEQ NAQ OEBHTUG SBEGU RGREANY QNZANGVBA NAQ FHSSREVAT HCBA GUR UBEQR NF N\n\
+GEHR UREB JBHYQ VA GUR SNPR BS FBZRGUVAT FB RIVY.",
+
+"ORFVQRF, FBZRBAR JNF TBAAN CNL SBE JUNG UNCCRARQ GB QNVFL, LBHE CRG ENOOVG.",
+
+"OHG ABJ, LBH FRR FCERNQ ORSBER LBH ZBER CBGRAGVNY CNVA NAQ TVOOVGHQR NF N\n\
+ANGVBA BS QRZBAF EHA NZBX VA BHE PVGVRF.",
+
+"ARKG FGBC, URYY BA RNEGU!"
+ };
+ size_t nstrs = sizeof(str)/sizeof(const char*);
+ size_t i = 0, j = 0, k = 0;
+ size_t buf[16];
+ 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);
+ darray_char_init(&allocator_proxy, &darray);
+ str_init(&allocator_proxy, &tmp);
+
+ FOR_EACH(i, 0, nstrs) {
+ darray_char_clear(&darray);
+ FOR_EACH(j, 0, strlen(str[i]) + 1) {
+ CHECK(darray_char_push_back(&darray, str[i] + j), 0);
+ }
+ str_set(&tmp, str[i]);
+ CHECK(htable_str_darray_set(&htbl, &tmp, &darray), 0);
+ }
+
+ FOR_EACH(j, 0, nerase) {
+ for(;;) {
+ i = (size_t)rand() % nstrs;
+ FOR_EACH(k, 0, j)
+ if(buf[k] == i) break;
+ if(k >= j) break;
+ }
+
+ buf[j] = i;
+
+ str_set(&tmp, str[i]);
+ data = htable_str_darray_find(&htbl, &tmp);
+ NCHECK(data, NULL);
+ CHECK(strcmp(darray_char_cdata_get(data), str_cget(&tmp)), 0);
+ CHECK(htable_str_darray_erase(&htbl, &tmp), 1);
+ CHECK(htable_str_darray_erase(&htbl, &tmp), 0);
+ }
+ CHECK(htable_str_darray_size_get(&htbl), nstrs - 3);
+
+ htable_str_darray_begin(&htbl, &it0);
+ htable_str_darray_end(&htbl, &it1);
+ while(!htable_str_darray_iterator_eq(&it0, &it1)) {
+ key = htable_str_darray_iterator_key_get(&it0);
+ data = htable_str_darray_iterator_data_get(&it0);
+ CHECK(strcmp(str_cget(key), darray_char_cdata_get(data)), 0);
+ htable_str_darray_iterator_next(&it0);
+ }
+
+ CHECK(htable_str_darray_reserve(&htbl, 2891), 0);
+
+ FOR_EACH(j, 0, 5) {
+ for(;;) {
+ i = (size_t)rand() % nstrs;
+ FOR_EACH(k, 0, nerase)
+ if(buf[k] == i) break;
+ if(k >= nerase) break;
+ }
+ str_set(&tmp, str[i]);
+ data = htable_str_darray_find(&htbl, &tmp);
+ NCHECK(data, NULL);
+ CHECK(strcmp(darray_char_cdata_get(data), str_cget(&tmp)), 0);
+ }
+
+ str_release(&tmp);
+ darray_char_release(&darray);
+ htable_str_darray_release(&htbl);
+ 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();
+ test_htbl_str_darray();
return 0;
}
