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_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, \