commit bad824e3680e2d5f17a749bc6b86f1ee9a014be7
parent 05d593e017074f43c732e781d9bb6492b8f6e9e9
Author: vaplv <vaplv@free.fr>
Date: Tue, 27 Oct 2020 15:42:31 +0100
Add and test the find_iterator function to the hash table
Diffstat:
2 files changed, 134 insertions(+), 5 deletions(-)
diff --git a/src/hash_table.h b/src/hash_table.h
@@ -240,7 +240,7 @@ struct HTABLE__ {
struct HTABLE_ITERATOR__ {
struct HTABLE__* hash_table;
size_t slot;
- size_t entries_scanned;
+ size_t entries_scanned; /* Used to early stop the next procedure */
};
/*******************************************************************************
@@ -618,13 +618,36 @@ HTABLE_FUNC__(end)
}
static INLINE void
+HTABLE_FUNC__(find_iterator)
+ (struct HTABLE__* htbl,
+ HTABLE_KEY const* key,
+ struct HTABLE_ITERATOR__* it)
+{
+ size_t i = 0;
+ ASSERT(htbl && key && it);
+ if(HTABLE_FUNC__(is_empty)(htbl)) {
+ HTABLE_FUNC__(end)(htbl, it);
+ return;
+ }
+
+ i = HTABLE_FUNC__(find_slot__)(htbl, key);
+ if(!darray_char_cdata_get(&htbl->table_slot_is_used)[i]) {
+ HTABLE_FUNC__(end)(htbl, it);
+ } else {
+ it->slot = i;
+ it->hash_table = htbl;
+ it->entries_scanned = 0;
+ }
+}
+
+static INLINE void
HTABLE_FUNC__(iterator_next)(struct HTABLE_ITERATOR__* it)
{
size_t tbl_size = 0;
ASSERT(it);
tbl_size = HTABLE_DATA_FUNC__(size_get)(&it->hash_table->table);
- if(it->entries_scanned >= it->hash_table->table_size_in_use) {
+ if(it->entries_scanned >= it->hash_table->table_size_in_use) {/* Early stop */
it->slot = tbl_size;
} else {
size_t i = 0;
@@ -641,9 +664,10 @@ HTABLE_FUNC__(iterator_eq)
const struct HTABLE_ITERATOR__* it1)
{
ASSERT(it0 && it1);
+ /* Do not compare the 'entries_scanned' field used only to early stop the
+ * iterator_next function in some situations */
return
it0->slot == it1->slot
- && it0->entries_scanned == it1->entries_scanned
&& it0->hash_table == it1->hash_table;
}
diff --git a/src/test_hash_table.c b/src/test_hash_table.c
@@ -48,8 +48,15 @@ test_htbl_int_float(void)
FOR_EACH(i, 0, n) {
float* p = htable_int_float_find(&htbl, &i);
+ struct htable_int_float_iterator it;
+ struct htable_int_float_iterator end;
+ htable_int_float_find_iterator(&htbl, &i, &it);
+ htable_int_float_end(&htbl, &end);
CHK(p != NULL);
CHK(*p == (float) i);
+ CHK(!htable_int_float_iterator_eq(&it, &end));
+ CHK(*htable_int_float_iterator_key_get(&it) == i);
+ CHK(*htable_int_float_iterator_data_get(&it) == (float)i);
}
CHK(htable_int_float_size_get(&htbl) == (size_t)n);
FOR_EACH(i, 0, n / 2) {
@@ -58,12 +65,24 @@ test_htbl_int_float(void)
CHK(htable_int_float_size_get(&htbl) == (size_t)(n/2));
FOR_EACH(i, 0, n/2) {
float* p = htable_int_float_find(&htbl, &i);
+ struct htable_int_float_iterator it;
+ struct htable_int_float_iterator end;
+ htable_int_float_find_iterator(&htbl, &i, &it);
+ htable_int_float_end(&htbl, &end);
CHK(p == NULL);
+ CHK(htable_int_float_iterator_eq(&it, &end));
}
FOR_EACH(i, n/2, n) {
float* p = htable_int_float_find(&htbl, &i);
+ struct htable_int_float_iterator it;
+ struct htable_int_float_iterator end;
+ htable_int_float_find_iterator(&htbl, &i, &it);
+ htable_int_float_end(&htbl, &end);
CHK(p != NULL);
CHK(*p == (float) i);
+ CHK(!htable_int_float_iterator_eq(&it, &end));
+ CHK(*htable_int_float_iterator_key_get(&it) == i);
+ CHK(*htable_int_float_iterator_data_get(&it) == (float)i);
}
htable_int_float_release(&htbl);
@@ -101,6 +120,7 @@ test_htbl_str_int(void)
struct htable_str_int htbl;
struct htable_str_int_iterator it0;
struct htable_str_int_iterator it1;
+ struct htable_str_int_iterator it2;
const char* str[] = {
"analyse", "analysis", "analyst", "analytic", "analytical", "analytically",
"analyze", "approach", "approachable", "area", "assess", "assessable",
@@ -129,6 +149,7 @@ test_htbl_str_int(void)
const int array_size = (int)(sizeof(array) / sizeof(int));
struct str tmp;
int i = 0;
+ struct str* key = NULL;
int* data = NULL;
STATIC_ASSERT
(sizeof(str)/sizeof(const char*) >= sizeof(array)/sizeof(int),
@@ -157,6 +178,11 @@ test_htbl_str_int(void)
str_set(&tmp, "empty");
CHK(htable_str_int_find(&htbl, &tmp) == NULL);
CHK(htable_str_int_size_get(&htbl) == 0);
+ htable_str_int_find_iterator(&htbl, &tmp, &it0);
+ htable_str_int_end(&htbl, &it1);
+ CHK(htable_str_int_iterator_eq(&it0, &it1));
+ htable_str_int_iterator_next(&it0);
+ CHK(htable_str_int_iterator_eq(&it0, &it1));
i = 0;
str_set(&tmp, str[i]);
CHK(htable_str_int_set(&htbl, &tmp, &i) == RES_OK);
@@ -169,6 +195,17 @@ test_htbl_str_int(void)
}
CHK(htable_str_int_size_get(&htbl) == (size_t)str_size);
+ str_set(&tmp, str[str_size/2]);
+ htable_str_int_find_iterator(&htbl, &tmp, &it0);
+ htable_str_int_end(&htbl, &it1);
+ CHK(!htable_str_int_iterator_eq(&it0, &it1));
+ while(!htable_str_int_iterator_eq(&it0, &it1)) {
+ key = htable_str_int_iterator_key_get(&it0);
+ data = htable_str_int_iterator_data_get(&it0);
+ CHK(*htable_str_int_find(&htbl, key) == *data);
+ htable_str_int_iterator_next(&it0);
+ }
+
str_set(&tmp, "Terra icognita");
CHK(htable_str_int_find(&htbl, &tmp) == NULL);
FOR_EACH(i, 0, 64) {
@@ -177,6 +214,11 @@ test_htbl_str_int(void)
data = htable_str_int_find(&htbl, &tmp);
CHK(data != NULL);
CHK(*data == (int)j);
+ htable_str_int_find_iterator(&htbl, &tmp, &it0);
+ htable_str_int_end(&htbl, &it1);
+ CHK(!htable_str_int_iterator_eq(&it0, &it1));
+ CHK(!str_cmp(htable_str_int_iterator_key_get(&it0), &tmp));
+ CHK(*htable_str_int_iterator_data_get(&it0) == (int)j);
}
str_set(&tmp, "Terra icognita");
@@ -188,6 +230,9 @@ test_htbl_str_int(void)
FOR_EACH(i, 0, array_size) {
str_set(&tmp, str[array[i]]);
CHK(htable_str_int_find(&htbl, &tmp) == 0);
+ htable_str_int_find_iterator(&htbl, &tmp, &it0);
+ htable_str_int_end(&htbl, &it1);
+ CHK(htable_str_int_iterator_eq(&it0, &it1));
}
CHK(htable_str_int_size_get(&htbl) == (size_t)(str_size - array_size));
FOR_EACH(i, 0, str_size) {
@@ -201,6 +246,11 @@ test_htbl_str_int(void)
data = htable_str_int_find(&htbl, &tmp);
CHK(data != NULL);
CHK(*data == (int)i);
+ htable_str_int_find_iterator(&htbl, &tmp, &it0);
+ htable_str_int_end(&htbl, &it1);
+ CHK(!htable_str_int_iterator_eq(&it0, &it1));
+ CHK(!str_cmp(htable_str_int_iterator_key_get(&it0), &tmp));
+ CHK(*htable_str_int_iterator_data_get(&it0) == (int)i);
}
}
FOR_EACH(i, 0, array_size) {
@@ -216,9 +266,15 @@ test_htbl_str_int(void)
CHK(htable_str_int_iterator_eq(&it0, &it1) == 0);
memset(str_found, 0, sizeof(str_found));
while(!htable_str_int_iterator_eq(&it0, &it1) ) {
+ key = htable_str_int_iterator_key_get(&it0);
data = htable_str_int_iterator_data_get(&it0);
- CHK(*htable_str_int_find(&htbl, htable_str_int_iterator_key_get(&it0))
- == *data);
+ CHK(*htable_str_int_find(&htbl, key) == *data);
+
+ htable_str_int_find_iterator(&htbl, key, &it2);
+ CHK(htable_str_int_iterator_eq(&it0, &it2));
+ CHK(!str_cmp(htable_str_int_iterator_key_get(&it2), key));
+ CHK(*htable_str_int_iterator_data_get(&it2) == *data);
+
CHK(str_found[*data] == 0);
str_found[*data] = 1;
htable_str_int_iterator_next(&it0);
@@ -255,8 +311,13 @@ test_htbl_str_int(void)
CHK(htable_str_int_size_get(&htbl) == 5);
data = htable_str_int_find(&htbl, &tmp);
+ htable_str_int_find_iterator(&htbl, &tmp, &it0);
+ htable_str_int_end(&htbl, &it1);
CHK(data != NULL);
CHK(*data == 'a');
+ CHK(!htable_str_int_iterator_eq(&it0, &it1));
+ CHK(!str_cmp(htable_str_int_iterator_key_get(&it0), &tmp));
+ CHK(*htable_str_int_iterator_data_get(&it0) == *data);
htable_str_int_clear(&htbl);
htable_str_int_begin(&htbl, &it0);
@@ -409,16 +470,37 @@ ANGVBA BS QRZBAF EHA NZBX VA BHE PVGVRF.",
str_set(&tmp, str[i]);
data = htable_str_darray_find(&htbl, &tmp);
+ htable_str_darray_find_iterator(&htbl, &tmp, &it0);
+ htable_str_darray_end(&htbl, &it1);
CHK(data != NULL);
CHK(strcmp(darray_char_cdata_get(data), str[i]) == 0);
+ CHK(!htable_str_darray_iterator_eq(&it0, &it1));
+ key = htable_str_darray_iterator_key_get(&it0);
+ data = htable_str_darray_iterator_data_get(&it0);
+ CHK(!str_cmp(key, &tmp));
+ CHK(strcmp(darray_char_cdata_get(data), str[i]) == 0);
data = htable_str_darray_find(&htbl2, &tmp);
+ htable_str_darray_find_iterator(&htbl2, &tmp, &it0);
+ htable_str_darray_end(&htbl2, &it1);
CHK(data != NULL);
CHK(strcmp(darray_char_cdata_get(data), str[i]) == 0);
+ CHK(!htable_str_darray_iterator_eq(&it0, &it1));
+ key = htable_str_darray_iterator_key_get(&it0);
+ data = htable_str_darray_iterator_data_get(&it0);
+ CHK(!str_cmp(key, &tmp));
+ CHK(strcmp(darray_char_cdata_get(data), str[i]) == 0);
data = htable_str_darray_find(&htbl3, &tmp);
+ htable_str_darray_find_iterator(&htbl3, &tmp, &it0);
+ htable_str_darray_end(&htbl3, &it1);
CHK(data != NULL);
CHK(strcmp(darray_char_cdata_get(data), str[i]) == 0);
+ CHK(!htable_str_darray_iterator_eq(&it0, &it1));
+ key = htable_str_darray_iterator_key_get(&it0);
+ data = htable_str_darray_iterator_data_get(&it0);
+ CHK(!str_cmp(key, &tmp));
+ CHK(strcmp(darray_char_cdata_get(data), str[i]) == 0);
}
FOR_EACH(j, 0, nerase) {
@@ -433,8 +515,14 @@ ANGVBA BS QRZBAF EHA NZBX VA BHE PVGVRF.",
str_set(&tmp, str[i]);
data = htable_str_darray_find(&htbl, &tmp);
+ htable_str_darray_find_iterator(&htbl, &tmp, &it0);
+ htable_str_darray_end(&htbl, &it1);
CHK(data != NULL);
CHK(strcmp(darray_char_cdata_get(data), str_cget(&tmp)) == 0);
+ key = htable_str_darray_iterator_key_get(&it0);
+ data = htable_str_darray_find(&htbl, &tmp);
+ CHK(!str_cmp(key, &tmp));
+ CHK(strcmp(darray_char_cdata_get(data), str_cget(&tmp)) == 0);
CHK(htable_str_darray_erase(&htbl, &tmp) == 1);
CHK(htable_str_darray_erase(&htbl, &tmp) == 0);
}
@@ -444,15 +532,32 @@ ANGVBA BS QRZBAF EHA NZBX VA BHE PVGVRF.",
str_set(&tmp, str[buf[j]]);
data = htable_str_darray_find(&htbl, &tmp);
+ htable_str_darray_find_iterator(&htbl, &tmp, &it0);
+ htable_str_darray_end(&htbl, &it1);
CHK(data == NULL);
+ CHK(htable_str_darray_iterator_eq(&it0, &it1));
data = htable_str_darray_find(&htbl2, &tmp);
+ htable_str_darray_find_iterator(&htbl2, &tmp, &it0);
+ htable_str_darray_end(&htbl2, &it1);
CHK(data != NULL);
CHK(strcmp(darray_char_cdata_get(data), str[buf[j]]) == 0);
+ CHK(!htable_str_darray_iterator_eq(&it0, &it1));
+ key = htable_str_darray_iterator_key_get(&it0);
+ data = htable_str_darray_iterator_data_get(&it0);
+ CHK(!str_cmp(key, &tmp));
+ CHK(strcmp(darray_char_cdata_get(data), str[buf[j]]) == 0);
data = htable_str_darray_find(&htbl3, &tmp);
+ htable_str_darray_find_iterator(&htbl3, &tmp, &it0);
+ htable_str_darray_end(&htbl3, &it1);
CHK(data != NULL);
CHK(strcmp(darray_char_cdata_get(data), str[buf[j]]) == 0);
+ CHK(!htable_str_darray_iterator_eq(&it0, &it1));
+ key = htable_str_darray_iterator_key_get(&it0);
+ data = htable_str_darray_iterator_data_get(&it0);
+ CHK(!str_cmp(key, &tmp));
+ CHK(strcmp(darray_char_cdata_get(data), str[buf[j]]) == 0);
}
