hash_table UPDATE insert record at the end of the hlist
Change the type of hlist head: instead of only referencing the first
record, reference both first and last records. Therefore we can add
new elements at the tail of the list.
This impacts how the records of a hlist will be browsed in case of
collisions:
- before this commit: last inserted is browsed first
- after this commit: first inserted is browsed first
It solves the validation unit test that was broken by the previous
commit.
Signed-off-by: Olivier Matz <olivier.matz@6wind.com>
diff --git a/src/hash_table.c b/src/hash_table.c
index cdd2163..03154ed 100644
--- a/src/hash_table.c
+++ b/src/hash_table.c
@@ -73,8 +73,10 @@
ht->hlists = malloc(sizeof(ht->hlists[0]) * ht->size);
LY_CHECK_ERR_RET(!ht->hlists, free(ht->recs); LOGMEM(NULL), LY_EMEM);
- for (i = 0; i < ht->size; i++)
- ht->hlists[i] = LYHT_NO_RECORD;
+ for (i = 0; i < ht->size; i++) {
+ ht->hlists[i].first = LYHT_NO_RECORD;
+ ht->hlists[i].last = LYHT_NO_RECORD;
+ }
ht->first_free_rec = 0;
return LY_SUCCESS;
@@ -181,7 +183,7 @@
lyht_resize(struct ly_ht *ht, int operation)
{
struct ly_ht_rec *rec;
- uint32_t *old_hlists;
+ struct ly_ht_hlist *old_hlists;
unsigned char *old_recs;
uint32_t old_first_free_rec;
uint32_t i, old_size;
@@ -213,7 +215,7 @@
/* add all the old records into the new records array */
for (i = 0; i < old_size; i++) {
- for (rec_idx = old_hlists[i], rec = lyht_get_rec(old_recs, ht->rec_size, rec_idx);
+ for (rec_idx = old_hlists[i].first, rec = lyht_get_rec(old_recs, ht->rec_size, rec_idx);
rec_idx != LYHT_NO_RECORD;
rec_idx = rec->next, rec = lyht_get_rec(old_recs, ht->rec_size, rec_idx)) {
LY_ERR ret;
@@ -346,7 +348,7 @@
{
uint32_t hlist_idx = hash & (ht->size - 1);
LY_ERR r, ret = LY_SUCCESS;
- struct ly_ht_rec *rec;
+ struct ly_ht_rec *rec, *prev_rec;
lyht_value_equal_cb old_val_equal = NULL;
uint32_t rec_idx;
@@ -361,8 +363,15 @@
assert(rec_idx < ht->size);
rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
ht->first_free_rec = rec->next;
- rec->next = ht->hlists[hlist_idx];
- ht->hlists[hlist_idx] = rec_idx;
+
+ if (ht->hlists[hlist_idx].first == LYHT_NO_RECORD) {
+ ht->hlists[hlist_idx].first = rec_idx;
+ } else {
+ prev_rec = lyht_get_rec(ht->recs, ht->rec_size, ht->hlists[hlist_idx].last);
+ prev_rec->next = rec_idx;
+ }
+ rec->next = LYHT_NO_RECORD;
+ ht->hlists[hlist_idx].last = rec_idx;
rec->hash = hash;
memcpy(&rec->val, val_p, ht->rec_size - SIZEOF_LY_HT_REC);
@@ -432,10 +441,14 @@
}
if (prev_rec_idx == LYHT_NO_RECORD) {
- ht->hlists[hlist_idx] = rec->next;
+ ht->hlists[hlist_idx].first = rec->next;
+ if (rec->next == LYHT_NO_RECORD)
+ ht->hlists[hlist_idx].last = LYHT_NO_RECORD;
} else {
prev_rec = lyht_get_rec(ht->recs, ht->rec_size, prev_rec_idx);
prev_rec->next = rec->next;
+ if (rec->next == LYHT_NO_RECORD)
+ ht->hlists[hlist_idx].last = prev_rec_idx;
}
rec->next = ht->first_free_rec;
diff --git a/src/hash_table_internal.h b/src/hash_table_internal.h
index 1921fca..22b6cf4 100644
--- a/src/hash_table_internal.h
+++ b/src/hash_table_internal.h
@@ -50,6 +50,11 @@
/* real size, without taking the val[1] in account */
#define SIZEOF_LY_HT_REC (sizeof(struct ly_ht_rec) - 1)
+struct ly_ht_hlist {
+ uint32_t first;
+ uint32_t last;
+};
+
/**
* @brief (Very) generic hash table.
*
@@ -81,7 +86,7 @@
* 2 - both shrinking and enlarging is enabled */
uint16_t rec_size; /* real size (in bytes) of one record for accessing recs array */
uint32_t first_free_rec; /* index of the first free record */
- uint32_t *hlists; /* pointer to the hlists table */
+ struct ly_ht_hlist *hlists; /* pointer to the hlists table */
unsigned char *recs; /* pointer to the hash table itself (array of struct ht_rec) */
};
@@ -97,7 +102,7 @@
/* Iterate all records in a hlist */
#define LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) \
- for (rec_idx = ht->hlists[hlist_idx], \
+ for (rec_idx = ht->hlists[hlist_idx].first, \
rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx); \
rec_idx != LYHT_NO_RECORD; \
rec_idx = rec->next, \
diff --git a/tests/utests/basic/test_hash_table.c b/tests/utests/basic/test_hash_table.c
index 041af26..f19ff36 100644
--- a/tests/utests/basic/test_hash_table.c
+++ b/tests/utests/basic/test_hash_table.c
@@ -117,11 +117,11 @@
for (i = 0; i < 16; ++i) {
if ((i >= 2) && (i < 8)) {
/* inserted data on indexes 2-7 */
- assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
} else {
/* nothing otherwise */
- assert_int_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_equal(UINT32_MAX, ht->hlists[i].first);
assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
}
}
@@ -172,9 +172,9 @@
/* check all records */
for (i = 0; i < 8; ++i) {
if (i == 2)
- assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
else
- assert_int_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_equal(UINT32_MAX, ht->hlists[i].first);
}
for (i = 0; i < 8; ++i) {
if (i >= 2 && i < 6)
@@ -182,7 +182,7 @@
else
assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
}
- rec_idx = ht->hlists[2];
+ rec_idx = ht->hlists[2].first;
count = 0;
while (rec_idx != UINT32_MAX) {
rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
@@ -203,9 +203,9 @@
/* check all records */
for (i = 0; i < 8; ++i) {
if (i == 2)
- assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
else
- assert_int_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_equal(UINT32_MAX, ht->hlists[i].first);
}
for (i = 0; i < 8; ++i) {
if (i == 3 || i == 5)
@@ -213,7 +213,7 @@
else
assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
}
- rec_idx = ht->hlists[2];
+ rec_idx = ht->hlists[2].first;
count = 0;
while (rec_idx != UINT32_MAX) {
rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
@@ -237,7 +237,7 @@
/* check all records */
for (i = 0; i < 8; ++i) {
- assert_int_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_equal(UINT32_MAX, ht->hlists[i].first);
}
lyht_free(ht, NULL);