commit c0feb68303d5449aeb11cc29ec1bcead63ba4327
author Olivier Matz <olivier.matz@6wind.com> Thu Sep 21 08:53:59 2023 +0200
committer Michal Vasko <mvasko@cesnet.cz> Wed Oct 04 15:40:23 2023 +0200
tree 3db659c04ce375f66b5bdbbd25a4c814c5720386
parent 78e96d81e71b90b29da426e7aaa62ab510ea761e

tree_data OPTIMIZE optimize creation of children htable

Here, we know the number of children that will be added in the hash
table, so create the hash table with the correct number of elements to
avoid automatic resizes.

Signed-off-by: Olivier Matz <olivier.matz@6wind.com>

src/hash_table.c

diff --git a/src/hash_table.c b/src/hash_table.c
index 86df07a..fd88e3d 100644
--- a/src/hash_table.c
+++ b/src/hash_table.c
@@ -65,10 +65,11 @@
     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)
+        if (i != ht->size) {
             rec->next = i + 1;
-        else
+        } else {
             rec->next = LYHT_NO_RECORD;
+        }
     }
 
     ht->hlists = malloc(sizeof(ht->hlists[0]) * ht->size);
@@ -164,8 +165,9 @@
     }
 
     if (val_free) {
-        LYHT_ITER_ALL_RECS(ht, hlist_idx, rec_idx, rec)
+        LYHT_ITER_ALL_RECS(ht, hlist_idx, rec_idx, rec) {
             val_free(&rec->val);
+        }
     }
     free(ht->hlists);
     free(ht->recs);
@@ -216,14 +218,15 @@
     /* add all the old records into the new records array */
     for (i = 0; i < old_size; i++) {
         for (rec_idx = old_hlists[i].first, 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)) {
+                rec_idx != LYHT_NO_RECORD;
+                rec_idx = rec->next, rec = lyht_get_rec(old_recs, ht->rec_size, rec_idx)) {
             LY_ERR ret;
 
-            if (check)
+            if (check) {
                 ret = lyht_insert(ht, rec->val, rec->hash, NULL);
-            else
+            } else {
                 ret = lyht_insert_no_check(ht, rec->val, rec->hash, NULL);
+            }
 
             assert(!ret);
             (void)ret;
@@ -311,8 +314,8 @@
     }
 
     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)) {
+            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;
@@ -442,24 +445,27 @@
     uint32_t rec_idx;
 
     LY_CHECK_ERR_RET(lyht_find_rec(ht, val_p, hash, 1, NULL, NULL, &found_rec),
-                     LOGARG(NULL, hash), LY_ENOTFOUND); /* hash not found */
+            LOGARG(NULL, hash), LY_ENOTFOUND);          /* hash not found */
 
     prev_rec_idx = LYHT_NO_RECORD;
     LYHT_ITER_HLIST_RECS(ht, hlist_idx, rec_idx, rec) {
-        if (rec == found_rec)
+        if (rec == found_rec) {
             break;
+        }
         prev_rec_idx = rec_idx;
     }
 
     if (prev_rec_idx == LYHT_NO_RECORD) {
         ht->hlists[hlist_idx].first = rec->next;
-        if (rec->next == LYHT_NO_RECORD)
+        if (rec->next == LYHT_NO_RECORD) {
             ht->hlists[hlist_idx].last = LYHT_NO_RECORD;
+        }
     } else {
         prev_rec = lyht_get_rec(ht->recs, ht->rec_size, prev_rec_idx);
         prev_rec->next = rec->next;
-        if (rec->next == LYHT_NO_RECORD)
+        if (rec->next == LYHT_NO_RECORD) {
             ht->hlists[hlist_idx].last = prev_rec_idx;
+        }
     }
 
     rec->next = ht->first_free_rec;
@@ -495,8 +501,9 @@
 LIBYANG_API_DEF uint32_t
 lyht_get_fixed_size(uint32_t item_count)
 {
-    if (item_count == 0)
+    if (item_count == 0) {
         return 1;
+    }
 
     /* return next power of 2 (greater or equal) */
     item_count--;

src/tree_data_hash.c

diff --git a/src/tree_data_hash.c b/src/tree_data_hash.c
index 65ece95..7235c27 100644
--- a/src/tree_data_hash.c
+++ b/src/tree_data_hash.c
@@ -182,8 +182,7 @@
             }
         }
         if (u >= LYD_HT_MIN_ITEMS) {
-            /* create hash table, insert all the children */
-            node->parent->children_ht = lyht_new(1, sizeof(struct lyd_node *), lyd_hash_table_val_equal, NULL, 1);
+            node->parent->children_ht = lyht_new(lyht_get_fixed_size(u), sizeof(struct lyd_node *), lyd_hash_table_val_equal, NULL, 1);
             LY_LIST_FOR(node->parent->child, iter) {
                 if (iter->schema) {
                     LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, iter, 1));