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/src/dict.c b/src/dict.c
index 7f89cc0..e1426ca 100644
--- a/src/dict.c
+++ b/src/dict.c
@@ -70,25 +70,23 @@
{
struct ly_dict_rec *dict_rec = NULL;
struct ly_ht_rec *rec = NULL;
+ uint32_t hlist_idx;
+ uint32_t rec_idx;
LY_CHECK_ARG_RET(NULL, dict, );
- for (uint32_t i = 0; i < dict->hash_tab->size; i++) {
- /* get ith record */
- rec = (struct ly_ht_rec *)&dict->hash_tab->recs[i * dict->hash_tab->rec_size];
- if (rec->hits == 1) {
- /*
- * this should not happen, all records inserted into
- * dictionary are supposed to be removed using lydict_remove()
- * before calling lydict_clean()
- */
- dict_rec = (struct ly_dict_rec *)rec->val;
- LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
- /* if record wasn't removed before free string allocated for that record */
+ LYHT_ITER_ALL_RECS(dict->hash_tab, hlist_idx, rec_idx, rec) {
+ /*
+ * this should not happen, all records inserted into
+ * dictionary are supposed to be removed using lydict_remove()
+ * before calling lydict_clean()
+ */
+ dict_rec = (struct ly_dict_rec *)rec->val;
+ LOGWRN(NULL, "String \"%s\" not freed from the dictionary, refcount %d", dict_rec->value, dict_rec->refcount);
+ /* if record wasn't removed before free string allocated for that record */
#ifdef NDEBUG
- free(dict_rec->value);
+ free(dict_rec->value);
#endif
- }
}
/* free table and destroy mutex */
diff --git a/src/hash_table.c b/src/hash_table.c
index 246fb34..cdd2163 100644
--- a/src/hash_table.c
+++ b/src/hash_table.c
@@ -55,10 +55,29 @@
return lyht_hash_multi(hash, NULL, len);
}
-struct ly_ht_rec *
-lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
+static LY_ERR
+lyht_init_hlists_and_records(struct ly_ht *ht)
{
- return (struct ly_ht_rec *)&recs[idx * rec_size];
+ struct ly_ht_rec *rec;
+ uint32_t i;
+
+ ht->recs = calloc(ht->size, ht->rec_size);
+ LY_CHECK_ERR_RET(!ht->recs, LOGMEM(NULL), LY_EMEM);
+ for (i = 0; i < ht->size; i++) {
+ rec = lyht_get_rec(ht->recs, ht->rec_size, i);
+ if (i != ht->size)
+ rec->next = i + 1;
+ else
+ rec->next = LYHT_NO_RECORD;
+ }
+
+ 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;
+ ht->first_free_rec = 0;
+
+ return LY_SUCCESS;
}
LIBYANG_API_DEF struct ly_ht *
@@ -80,15 +99,15 @@
ht->used = 0;
ht->size = size;
- ht->invalid = 0;
ht->val_equal = val_equal;
ht->cb_data = cb_data;
ht->resize = resize;
- ht->rec_size = (sizeof(struct ly_ht_rec) - 1) + val_size;
- /* allocate the records correctly */
- ht->recs = calloc(size, ht->rec_size);
- LY_CHECK_ERR_RET(!ht->recs, free(ht); LOGMEM(NULL), NULL);
+ ht->rec_size = SIZEOF_LY_HT_REC + val_size;
+ if (lyht_init_hlists_and_records(ht) != LY_SUCCESS) {
+ free(ht);
+ return NULL;
+ }
return ht;
}
@@ -120,14 +139,14 @@
LY_CHECK_ARG_RET(NULL, orig, NULL);
- ht = lyht_new(orig->size, orig->rec_size - (sizeof(struct ly_ht_rec) - 1), orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
+ ht = lyht_new(orig->size, orig->rec_size - SIZEOF_LY_HT_REC, orig->val_equal, orig->cb_data, orig->resize ? 1 : 0);
if (!ht) {
return NULL;
}
- memcpy(ht->recs, orig->recs, (size_t)orig->used * (size_t)orig->rec_size);
+ memcpy(ht->hlists, orig->hlists, sizeof(ht->hlists[0]) * orig->size);
+ memcpy(ht->recs, orig->recs, (size_t)orig->size * orig->rec_size);
ht->used = orig->used;
- ht->invalid = orig->invalid;
return ht;
}
@@ -135,20 +154,18 @@
lyht_free(struct ly_ht *ht, void (*val_free)(void *val_p))
{
struct ly_ht_rec *rec;
- uint32_t i;
+ uint32_t hlist_idx;
+ uint32_t rec_idx;
if (!ht) {
return;
}
if (val_free) {
- for (i = 0; i < ht->size; ++i) {
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- if (rec->hits > 0) {
- val_free(&rec->val);
- }
- }
+ LYHT_ITER_ALL_RECS(ht, hlist_idx, rec_idx, rec)
+ val_free(&rec->val);
}
+ free(ht->hlists);
free(ht->recs);
free(ht);
}
@@ -164,11 +181,16 @@
lyht_resize(struct ly_ht *ht, int operation)
{
struct ly_ht_rec *rec;
+ uint32_t *old_hlists;
unsigned char *old_recs;
+ uint32_t old_first_free_rec;
uint32_t i, old_size;
+ uint32_t rec_idx;
+ old_hlists = ht->hlists;
old_recs = ht->recs;
old_size = ht->size;
+ old_first_free_rec = ht->first_free_rec;
if (operation > 0) {
/* double the size */
@@ -178,18 +200,25 @@
ht->size >>= 1;
}
- ht->recs = calloc(ht->size, ht->rec_size);
- LY_CHECK_ERR_RET(!ht->recs, LOGMEM(NULL); ht->recs = old_recs; ht->size = old_size, LY_EMEM);
+ if (lyht_init_hlists_and_records(ht) != LY_SUCCESS) {
+ ht->hlists = old_hlists;
+ ht->recs = old_recs;
+ ht->size = old_size;
+ ht->first_free_rec = old_first_free_rec;
+ return LY_EMEM;
+ }
- /* reset used and invalid, it will increase again */
+ /* reset used, it will increase again */
ht->used = 0;
- ht->invalid = 0;
/* add all the old records into the new records array */
- for (i = 0; i < old_size; ++i) {
- rec = lyht_get_rec(old_recs, ht->rec_size, i);
- if (rec->hits > 0) {
- LY_ERR ret = lyht_insert(ht, rec->val, rec->hash, NULL);
+ for (i = 0; i < old_size; i++) {
+ for (rec_idx = old_hlists[i], 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;
+
+ ret = lyht_insert(ht, rec->val, rec->hash, NULL);
assert(!ret);
(void)ret;
@@ -198,111 +227,11 @@
/* final touches */
free(old_recs);
+ free(old_hlists);
return LY_SUCCESS;
}
/**
- * @brief Search for the first match.
- *
- * @param[in] ht Hash table to search in.
- * @param[in] hash Hash to find.
- * @param[out] rec_p Optional found record.
- * @return LY_SUCCESS hash found, returned its record,
- * @return LY_ENOTFOUND hash not found, returned the record where it would be inserted.
- */
-static LY_ERR
-lyht_find_first(struct ly_ht *ht, uint32_t hash, struct ly_ht_rec **rec_p)
-{
- struct ly_ht_rec *rec;
- uint32_t i, idx;
-
- if (rec_p) {
- *rec_p = NULL;
- }
-
- idx = i = hash & (ht->size - 1);
- rec = lyht_get_rec(ht->recs, ht->rec_size, idx);
-
- /* skip through overflow and deleted records */
- while ((rec->hits != 0) && ((rec->hits == -1) || ((rec->hash & (ht->size - 1)) != idx))) {
- if ((rec->hits == -1) && rec_p && !(*rec_p)) {
- /* remember this record for return */
- *rec_p = rec;
- }
- i = (i + 1) % ht->size;
- if (i == idx) {
- /* we went through all the records (very unlikely, but possible when many records are invalid),
- * just return not found */
- assert(!rec_p || *rec_p);
- return LY_ENOTFOUND;
- }
- rec = lyht_get_rec(ht->recs, ht->rec_size, i);
- }
- if (rec->hits == 0) {
- /* we could not find the value */
- if (rec_p && !*rec_p) {
- *rec_p = rec;
- }
- return LY_ENOTFOUND;
- }
-
- /* we have found a record with equal (shortened) hash */
- if (rec_p) {
- *rec_p = rec;
- }
- return LY_SUCCESS;
-}
-
-/**
- * @brief Search for the next collision.
- *
- * @param[in] ht Hash table to search in.
- * @param[in,out] last Last returned collision record.
- * @param[in] first First collision record (hits > 1).
- * @return LY_SUCCESS when hash collision found, \p last points to this next collision,
- * @return LY_ENOTFOUND when hash collision not found, \p last points to the record where it would be inserted.
- */
-static LY_ERR
-lyht_find_collision(struct ly_ht *ht, struct ly_ht_rec **last, struct ly_ht_rec *first)
-{
- struct ly_ht_rec *empty = NULL;
- uint32_t i, idx;
-
- assert(last && *last);
-
- idx = (*last)->hash & (ht->size - 1);
- i = (((unsigned char *)*last) - ht->recs) / ht->rec_size;
-
- do {
- i = (i + 1) % ht->size;
- *last = lyht_get_rec(ht->recs, ht->rec_size, i);
- if (*last == first) {
- /* we went through all the records (very unlikely, but possible when many records are invalid),
- * just return an invalid record */
- assert(empty);
- *last = empty;
- return LY_ENOTFOUND;
- }
-
- if (((*last)->hits == -1) && !empty) {
- empty = *last;
- }
- } while (((*last)->hits != 0) && (((*last)->hits == -1) || (((*last)->hash & (ht->size - 1)) != idx)));
-
- if ((*last)->hits > 0) {
- /* we found a collision */
- assert((*last)->hits == 1);
- return LY_SUCCESS;
- }
-
- /* no next collision found, return the record where it would be inserted */
- if (empty) {
- *last = empty;
- } /* else (*last)->hits == 0, it is already correct */
- return LY_ENOTFOUND;
-}
-
-/**
* @brief Search for a record with specific value and hash.
*
* @param[in] ht Hash table to search in.
@@ -319,9 +248,9 @@
lyht_find_rec(struct ly_ht *ht, void *val_p, uint32_t hash, ly_bool mod, struct ly_ht_rec **crec_p, uint32_t *col,
struct ly_ht_rec **rec_p)
{
- struct ly_ht_rec *rec, *crec;
- uint32_t i, c;
- LY_ERR r;
+ uint32_t hlist_idx = hash & (ht->size - 1);
+ struct ly_ht_rec *rec;
+ uint32_t rec_idx;
if (crec_p) {
*crec_p = NULL;
@@ -331,41 +260,18 @@
}
*rec_p = NULL;
- if (lyht_find_first(ht, hash, &rec)) {
- /* not found */
- return LY_ENOTFOUND;
- }
- if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
- /* even the value matches */
- if (crec_p) {
- *crec_p = rec;
- }
- if (col) {
- *col = 0;
- }
- *rec_p = rec;
- return LY_SUCCESS;
- }
-
- /* some collisions, we need to go through them, too */
- crec = rec;
- c = crec->hits;
- for (i = 1; i < c; ++i) {
- r = lyht_find_collision(ht, &rec, crec);
- assert(!r);
- (void)r;
-
- /* compare values */
+ LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) {
if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, mod, ht->cb_data)) {
if (crec_p) {
- *crec_p = crec;
- }
- if (col) {
- *col = i;
+ *crec_p = rec;
}
*rec_p = rec;
return LY_SUCCESS;
}
+
+ if (col) {
+ *col = *col + 1;
+ }
}
/* not found even in collisions */
@@ -390,8 +296,8 @@
lyht_value_equal_cb collision_val_equal, void **match_p)
{
struct ly_ht_rec *rec, *crec;
- uint32_t i, c;
- LY_ERR r;
+ uint32_t rec_idx;
+ uint32_t i;
/* find the record of the previously found value */
if (lyht_find_rec(ht, val_p, hash, 1, &crec, &i, &rec)) {
@@ -399,12 +305,9 @@
LOGINT_RET(NULL);
}
- /* go through collisions and find the next one after the previous one */
- c = crec->hits;
- for (++i; i < c; ++i) {
- r = lyht_find_collision(ht, &rec, crec);
- assert(!r);
- (void)r;
+ for (rec_idx = rec->next, rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx);
+ rec_idx != LYHT_NO_RECORD;
+ rec_idx = rec->next, rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx)) {
if (rec->hash != hash) {
continue;
@@ -437,65 +340,36 @@
return lyht_find_next_with_collision_cb(ht, val_p, hash, NULL, match_p);
}
-LIBYANG_API_DEF LY_ERR
-lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
+static LY_ERR
+__lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
void **match_p)
{
+ uint32_t hlist_idx = hash & (ht->size - 1);
LY_ERR r, ret = LY_SUCCESS;
- struct ly_ht_rec *rec, *crec = NULL;
- int32_t i;
+ struct ly_ht_rec *rec;
lyht_value_equal_cb old_val_equal = NULL;
+ uint32_t rec_idx;
- if (!lyht_find_first(ht, hash, &rec)) {
- /* we found matching shortened hash */
- if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
- /* even the value matches */
- if (match_p) {
- *match_p = (void *)&rec->val;
- }
- return LY_EEXIST;
+ if (lyht_find_rec(ht, val_p, hash, 1, NULL, NULL, &rec) == LY_SUCCESS) {
+ if (rec && match_p) {
+ *match_p = rec->val;
}
-
- /* some collisions, we need to go through them, too */
- crec = rec;
- for (i = 1; i < crec->hits; ++i) {
- r = lyht_find_collision(ht, &rec, crec);
- assert(!r);
-
- /* compare values */
- if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
- if (match_p) {
- *match_p = (void *)&rec->val;
- }
- return LY_EEXIST;
- }
- }
-
- /* value not found, get the record where it will be inserted */
- r = lyht_find_collision(ht, &rec, crec);
- assert(r);
+ return LY_EEXIST;
}
- /* insert it into the returned record */
- assert(rec->hits < 1);
- if (rec->hits < 0) {
- --ht->invalid;
- }
+ rec_idx = ht->first_free_rec;
+ 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;
+
rec->hash = hash;
- rec->hits = 1;
- memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ly_ht_rec) - 1));
+ memcpy(&rec->val, val_p, ht->rec_size - SIZEOF_LY_HT_REC);
if (match_p) {
*match_p = (void *)&rec->val;
}
- if (crec) {
- /* there was a collision, increase hits */
- if (crec->hits == INT32_MAX) {
- LOGINT(NULL);
- }
- ++crec->hits;
- }
-
/* check size & enlarge if needed */
++ht->used;
if (ht->resize) {
@@ -525,60 +399,50 @@
}
LIBYANG_API_DEF LY_ERR
+lyht_insert_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal,
+ void **match_p)
+{
+ return __lyht_insert_with_resize_cb(ht, val_p, hash, resize_val_equal, match_p);
+}
+
+LIBYANG_API_DEF LY_ERR
lyht_insert(struct ly_ht *ht, void *val_p, uint32_t hash, void **match_p)
{
- return lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
+ return __lyht_insert_with_resize_cb(ht, val_p, hash, NULL, match_p);
}
LIBYANG_API_DEF LY_ERR
lyht_remove_with_resize_cb(struct ly_ht *ht, void *val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal)
{
- struct ly_ht_rec *rec, *crec;
- int32_t i;
- ly_bool first_matched = 0;
+ struct ly_ht_rec *found_rec, *prev_rec, *rec;
+ uint32_t hlist_idx = hash & (ht->size - 1);
LY_ERR r, ret = LY_SUCCESS;
lyht_value_equal_cb old_val_equal = NULL;
+ uint32_t prev_rec_idx;
+ uint32_t rec_idx;
- LY_CHECK_ERR_RET(lyht_find_first(ht, hash, &rec), LOGARG(NULL, hash), LY_ENOTFOUND); /* hash not found */
+ LY_CHECK_ERR_RET(lyht_find_rec(ht, val_p, hash, 1, NULL, NULL, &found_rec),
+ LOGARG(NULL, hash), LY_ENOTFOUND); /* hash not found */
- if ((rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
- /* even the value matches */
- first_matched = 1;
- }
-
- /* we always need to go through collisions */
- crec = rec;
- for (i = 1; i < crec->hits; ++i) {
- r = lyht_find_collision(ht, &rec, crec);
- assert(!r);
-
- /* compare values */
- if (!first_matched && (rec->hash == hash) && ht->val_equal(val_p, &rec->val, 1, ht->cb_data)) {
+ prev_rec_idx = LYHT_NO_RECORD;
+ LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) {
+ if (rec == found_rec)
break;
- }
+ prev_rec_idx = rec_idx;
}
- if (i < crec->hits) {
- /* one of collisions matched, reduce collision count, remove the record */
- assert(!first_matched);
- --crec->hits;
- rec->hits = -1;
- } else if (first_matched) {
- /* the first record matches */
- if (crec != rec) {
- /* ... so put the last collision in its place */
- rec->hits = crec->hits - 1;
- memcpy(crec, rec, ht->rec_size);
- }
- rec->hits = -1;
+ if (prev_rec_idx == LYHT_NO_RECORD) {
+ ht->hlists[hlist_idx] = rec->next;
} else {
- /* value not found even in collisions */
- return LY_ENOTFOUND;
+ prev_rec = lyht_get_rec(ht->recs, ht->rec_size, prev_rec_idx);
+ prev_rec->next = rec->next;
}
+ rec->next = ht->first_free_rec;
+ ht->first_free_rec = rec_idx;
+
/* check size & shrink if needed */
--ht->used;
- ++ht->invalid;
if (ht->resize == 2) {
r = (ht->used * LYHT_HUNDRED_PERCENTAGE) / ht->size;
if ((r < LYHT_SHRINK_PERCENTAGE) && (ht->size > LYHT_MIN_SIZE)) {
@@ -595,21 +459,6 @@
}
}
- /* rehash all records if needed */
- r = ((ht->size - ht->used - ht->invalid) * 100) / ht->size;
- if (r < LYHT_REHASH_PERCENTAGE) {
- if (resize_val_equal) {
- old_val_equal = lyht_set_cb(ht, resize_val_equal);
- }
-
- /* rehash */
- ret = lyht_resize(ht, 0);
-
- if (resize_val_equal) {
- lyht_set_cb(ht, old_val_equal);
- }
- }
-
return ret;
}
@@ -622,23 +471,16 @@
LIBYANG_API_DEF uint32_t
lyht_get_fixed_size(uint32_t item_count)
{
- uint32_t i, size = 0;
+ if (item_count == 0)
+ return 1;
- /* detect number of upper zero bits in the items' counter value ... */
- for (i = (sizeof item_count * CHAR_BIT) - 1; i > 0; i--) {
- size = item_count << i;
- size = size >> i;
- if (size == item_count) {
- break;
- }
- }
- assert(i);
+ /* return next power of 2 (greater or equal) */
+ item_count--;
+ item_count |= item_count >> 1;
+ item_count |= item_count >> 2;
+ item_count |= item_count >> 4;
+ item_count |= item_count >> 8;
+ item_count |= item_count >> 16;
- /* ... and then we convert it to the position of the highest non-zero bit ... */
- i = (sizeof item_count * CHAR_BIT) - i;
-
- /* ... and by using it to shift 1 to the left we get the closest sufficient hash table size */
- size = 1 << i;
-
- return size;
+ return item_count + 1;
}
diff --git a/src/hash_table_internal.h b/src/hash_table_internal.h
index eaadbc7..1921fca 100644
--- a/src/hash_table_internal.h
+++ b/src/hash_table_internal.h
@@ -35,9 +35,6 @@
/** when the table is less than this much percent full, it is shrunk (half the size) */
#define LYHT_SHRINK_PERCENTAGE 25
-/** when the table has less than this much percent empty records, it is rehashed to get rid of all the invalid records */
-#define LYHT_REHASH_PERCENTAGE 2
-
/** never shrink beyond this size */
#define LYHT_MIN_SIZE 8
@@ -46,32 +43,71 @@
*/
struct ly_ht_rec {
uint32_t hash; /* hash of the value */
- int32_t hits; /* collision/overflow value count - 1 (a filled entry has 1 hit,
- * special value -1 means a deleted record) */
+ uint32_t next; /* index of next collision */
unsigned char val[1]; /* arbitrary-size value */
} _PACKED;
+/* real size, without taking the val[1] in account */
+#define SIZEOF_LY_HT_REC (sizeof(struct ly_ht_rec) - 1)
+
/**
* @brief (Very) generic hash table.
*
- * Hash table with open addressing collision resolution and
- * linear probing of interval 1 (next free record is used).
- * Removal is lazy (removed records are only marked), but
- * if possible, they are fully emptied.
+ * This structure implements a hash table, providing fast accesses to stored
+ * values from their hash.
+ *
+ * The hash table structure contains 2 pointers to tables that are allocated
+ * at initialization:
+ * - a table of records: each record is composed of a struct ly_ht_rec header,
+ * followed by the user value. The header contains the hash value and a
+ * next index that can be used to chain records.
+ * - a table of list heads: each list head entry contains the index of the
+ * first record in the records table whose hash (modulo hash table size)
+ * is equal to the index of the list head entry. The other matching records
+ * are chained together.
+ *
+ * The unused records are chained in first_free_rec, which contains the index
+ * of the first unused record entry in the records table.
+ *
+ * The LYHT_NO_RECORD magic value is used when an index points to nothing.
*/
struct ly_ht {
uint32_t used; /* number of values stored in the hash table (filled records) */
uint32_t size; /* always holds 2^x == size (is power of 2), actually number of records allocated */
- uint32_t invalid; /* number of invalid records (deleted) */
lyht_value_equal_cb val_equal; /* callback for testing value equivalence */
void *cb_data; /* user data callback arbitrary value */
uint16_t resize; /* 0 - resizing is disabled, *
* 1 - enlarging is enabled, *
* 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 */
unsigned char *recs; /* pointer to the hash table itself (array of struct ht_rec) */
};
+/* index that points to nothing */
+#define LYHT_NO_RECORD UINT32_MAX
+
+/* get the record associated to */
+static inline struct ly_ht_rec *
+lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx)
+{
+ return (struct ly_ht_rec *)&recs[idx * rec_size];
+}
+
+/* Iterate all records in a hlist */
+#define LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) \
+ for (rec_idx = ht->hlists[hlist_idx], \
+ rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx); \
+ rec_idx != LYHT_NO_RECORD; \
+ rec_idx = rec->next, \
+ rec = lyht_get_rec(ht->recs, ht->rec_size, rec_idx))
+
+/* Iterate all records in the hash table */
+#define LYHT_ITER_ALL_RECS(ht, hlist_idx, rec_idx, rec) \
+ for (hlist_idx = 0; hlist_idx < ht->size; hlist_idx++) \
+ LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec)
+
/**
* @brief Dictionary hash table record.
*/
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);