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>
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--;
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));
diff --git a/tests/utests/basic/test_hash_table.c b/tests/utests/basic/test_hash_table.c
index f19ff36..78950cd 100644
--- a/tests/utests/basic/test_hash_table.c
+++ b/tests/utests/basic/test_hash_table.c
@@ -171,16 +171,18 @@
/* check all records */
for (i = 0; i < 8; ++i) {
- if (i == 2)
+ if (i == 2) {
assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
- else
+ } else {
assert_int_equal(UINT32_MAX, ht->hlists[i].first);
+ }
}
for (i = 0; i < 8; ++i) {
- if (i >= 2 && i < 6)
+ if ((i >= 2) && (i < 6)) {
assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
- else
+ } else {
assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
+ }
}
rec_idx = ht->hlists[2].first;
count = 0;
@@ -202,16 +204,18 @@
/* check all records */
for (i = 0; i < 8; ++i) {
- if (i == 2)
+ if (i == 2) {
assert_int_not_equal(UINT32_MAX, ht->hlists[i].first);
- else
+ } else {
assert_int_equal(UINT32_MAX, ht->hlists[i].first);
+ }
}
for (i = 0; i < 8; ++i) {
- if (i == 3 || i == 5)
+ if ((i == 3) || (i == 5)) {
assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, 2, NULL));
- else
+ } else {
assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, 2, NULL));
+ }
}
rec_idx = ht->hlists[2].first;
count = 0;
@@ -224,10 +228,11 @@
assert_int_equal(count, 2);
for (i = 0; i < 8; ++i) {
- if (i == 3 || i == 5)
+ if ((i == 3) || (i == 5)) {
assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
- else
+ } else {
assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
+ }
}
i = 3;