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, *