hash table FEATURE invalid record counter
Used to improve the performance.
Refs #1250
diff --git a/src/hash_table.c b/src/hash_table.c
index 609f408..3624e1d 100644
--- a/src/hash_table.c
+++ b/src/hash_table.c
@@ -327,6 +327,7 @@
ht->used = 0;
ht->size = size;
+ ht->invalid = 0;
ht->val_equal = val_equal;
ht->cb_data = cb_data;
ht->resize = resize;
@@ -373,6 +374,7 @@
memcpy(ht->recs, orig->recs, orig->used * orig->rec_size);
ht->used = orig->used;
+ ht->invalid = orig->invalid;
return ht;
}
@@ -385,8 +387,15 @@
}
}
+/**
+ * @brief Resize a hash table.
+ *
+ * @param[in] ht Hash table to resize.
+ * @param[in] operation Operation to perform. 1 to enlarge, -1 to shrink, 0 to only rehash all records.
+ * @return LY_ERR value.
+ */
static LY_ERR
-lyht_resize(struct hash_table *ht, ly_bool enlarge)
+lyht_resize(struct hash_table *ht, int operation)
{
struct ht_rec *rec;
unsigned char *old_recs;
@@ -395,10 +404,10 @@
old_recs = ht->recs;
old_size = ht->size;
- if (enlarge) {
+ if (operation > 0) {
/* double the size */
ht->size <<= 1;
- } else {
+ } else if (operation < 0) {
/* half the size */
ht->size >>= 1;
}
@@ -406,8 +415,9 @@
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);
- /* reset used, it will increase again */
+ /* reset used and invalid, 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) {
@@ -682,6 +692,9 @@
/* insert it into the returned record */
assert(rec->hits < 1);
+ if (rec->hits < 0) {
+ --ht->invalid;
+ }
rec->hash = hash;
rec->hits = 1;
memcpy(&rec->val, val_p, ht->rec_size - (sizeof(struct ht_rec) - 1));
@@ -779,6 +792,7 @@
/* 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)) {
@@ -787,7 +801,7 @@
}
/* shrink */
- ret = lyht_resize(ht, 0);
+ ret = lyht_resize(ht, -1);
if (resize_val_equal) {
lyht_set_cb(ht, old_val_equal);
@@ -795,6 +809,21 @@
}
}
+ /* 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;
}
diff --git a/src/hash_table.h b/src/hash_table.h
index 510ac4f..b223362 100644
--- a/src/hash_table.h
+++ b/src/hash_table.h
@@ -61,6 +61,9 @@
/** 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
@@ -85,6 +88,7 @@
struct hash_table {
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, *