hash_table REFACTOR simplify collision management
The current implementation manages collision by browsing the next
records to find an unused one.
This has the following consequences:
- when there are a lot of collisions, the insertion can take a lot
of time before finding an empty entry.
- this may require to rehash the table to get rid of invalid records
- the code that handles the collisions is not trivial
This commit reworks the hash table to use a per-hash list of records.
It prepares the work to have an insertion in the hash table in O(1) even
if there are hash collisions. This commit is not sufficient for that yet,
since we always check for duplicates at insertion. See the introduction
of ly_ht_insert_no_check() in a latter commit.
Note: this change breaks the validation unit test. It is fixed by the
next commit.
Signed-off-by: Olivier Matz <olivier.matz@6wind.com>
diff --git a/tests/utests/basic/test_hash_table.c b/tests/utests/basic/test_hash_table.c
index efb5554..041af26 100644
--- a/tests/utests/basic/test_hash_table.c
+++ b/tests/utests/basic/test_hash_table.c
@@ -19,8 +19,6 @@
#include "common.h"
#include "hash_table.h"
-struct ly_ht_rec *lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx);
-
static void
test_invalid_arguments(void **state)
{
@@ -103,7 +101,6 @@
test_ht_resize(void **state)
{
uint32_t i;
- struct ly_ht_rec *rec;
struct ly_ht *ht;
assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
@@ -120,13 +117,12 @@
for (i = 0; i < 16; ++i) {
if ((i >= 2) && (i < 8)) {
/* inserted data on indexes 2-7 */
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(1, rec->hits);
- assert_int_equal(i, rec->hash);
+ assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
} else {
/* nothing otherwise */
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(0, rec->hits);
+ assert_int_equal(UINT32_MAX, ht->hlists[i]);
+ assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
}
}
@@ -164,6 +160,8 @@
uint32_t i;
struct ly_ht_rec *rec;
struct ly_ht *ht;
+ uint32_t rec_idx;
+ int count;
assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
@@ -172,66 +170,64 @@
}
/* check all records */
- for (i = 0; i < 2; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 0);
+ for (i = 0; i < 8; ++i) {
+ if (i == 2)
+ assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+ else
+ assert_int_equal(UINT32_MAX, ht->hlists[i]);
}
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 4);
- assert_int_equal(GET_REC_INT(rec), i);
- ++i;
- for ( ; i < 6; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 1);
- assert_int_equal(GET_REC_INT(rec), i);
+ for (i = 0; i < 8; ++i) {
+ if (i >= 2 && i < 6)
+ assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
+ else
+ assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
}
- for ( ; i < 8; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 0);
+ rec_idx = ht->hlists[2];
+ count = 0;
+ while (rec_idx != UINT32_MAX) {
+ rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+ rec_idx = rec->next;
+ assert_int_equal(rec->hash, 2);
+ count++;
}
+ assert_int_equal(count, 4);
i = 4;
assert_int_equal(lyht_remove(ht, &i, 2), 0);
rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, -1);
i = 2;
assert_int_equal(lyht_remove(ht, &i, 2), 0);
/* check all records */
- for (i = 0; i < 2; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 0);
+ for (i = 0; i < 8; ++i) {
+ if (i == 2)
+ assert_int_not_equal(UINT32_MAX, ht->hlists[i]);
+ else
+ assert_int_equal(UINT32_MAX, ht->hlists[i]);
}
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 2);
- assert_int_equal(GET_REC_INT(rec), 5);
- ++i;
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 1);
- assert_int_equal(GET_REC_INT(rec), 3);
- ++i;
- for ( ; i < 6; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, -1);
+ for (i = 0; i < 8; ++i) {
+ if (i == 3 || i == 5)
+ assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
+ else
+ assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
}
- for ( ; i < 8; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 0);
+ rec_idx = ht->hlists[2];
+ count = 0;
+ while (rec_idx != UINT32_MAX) {
+ rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+ rec_idx = rec->next;
+ assert_int_equal(rec->hash, 2);
+ count++;
}
+ assert_int_equal(count, 2);
- for (i = 0; i < 3; ++i) {
- assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
- }
- assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
- ++i;
- assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
- ++i;
- assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
- ++i;
- for ( ; i < 8; ++i) {
- assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
+ for (i = 0; i < 8; ++i) {
+ if (i == 3 || i == 5)
+ assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
+ else
+ assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
}
i = 3;
@@ -240,17 +236,8 @@
assert_int_equal(lyht_remove(ht, &i, 2), 0);
/* check all records */
- for (i = 0; i < 2; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 0);
- }
- for ( ; i < 6; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, -1);
- }
- for ( ; i < 8; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- assert_int_equal(rec->hits, 0);
+ for (i = 0; i < 8; ++i) {
+ assert_int_equal(UINT32_MAX, ht->hlists[i]);
}
lyht_free(ht, NULL);