tree data OPTIMIZE use hash table for dup inst cache
Now that dup inst is being calculated for all
the nodes, we can no longer use a linear list.
Diff and merge were inefficient because of this.
diff --git a/src/diff.c b/src/diff.c
index edfcb34..63c2fe3 100644
--- a/src/diff.c
+++ b/src/diff.c
@@ -648,13 +648,13 @@
* @param[in] siblings Siblings to search in.
* @param[in] target Target node to search for.
* @param[in] defaults Whether to consider (or ignore) default values.
- * @param[in,out] dup_inst_cache Duplicate instance cache.
+ * @param[in,out] dup_inst_ht Duplicate instance cache.
* @param[out] match Found match, NULL if no matching node found.
* @return LY_ERR value.
*/
static LY_ERR
lyd_diff_find_match(const struct lyd_node *siblings, const struct lyd_node *target, ly_bool defaults,
- struct lyd_dup_inst **dup_inst_cache, struct lyd_node **match)
+ struct hash_table **dup_inst_ht, struct lyd_node **match)
{
LY_ERR r;
@@ -670,7 +670,7 @@
}
/* update match as needed */
- LY_CHECK_RET(lyd_dup_inst_next(match, siblings, dup_inst_cache));
+ LY_CHECK_RET(lyd_dup_inst_next(match, siblings, dup_inst_ht));
if (*match && ((*match)->flags & LYD_DEFAULT) && !defaults) {
/* ignore default nodes */
@@ -728,7 +728,7 @@
const struct lyd_node *iter_first, *iter_second;
struct lyd_node *match_second, *match_first;
struct lyd_diff_userord *userord = NULL, *userord_item;
- struct lyd_dup_inst *dup_inst_first = NULL, *dup_inst_second = NULL;
+ struct hash_table *dup_inst_first = NULL, *dup_inst_second = NULL;
LY_ARRAY_COUNT_TYPE u;
enum lyd_diff_op op;
const char *orig_default;
@@ -1079,14 +1079,14 @@
*/
static LY_ERR
lyd_diff_apply_r(struct lyd_node **first_node, struct lyd_node *parent_node, const struct lyd_node *diff_node,
- lyd_diff_cb diff_cb, void *cb_data, struct lyd_dup_inst **dup_inst)
+ lyd_diff_cb diff_cb, void *cb_data, struct hash_table **dup_inst)
{
LY_ERR ret;
struct lyd_node *match, *diff_child;
const char *str_val, *meta_str;
enum lyd_diff_op op;
struct lyd_meta *meta;
- struct lyd_dup_inst *child_dup_inst = NULL;
+ struct hash_table *child_dup_inst = NULL;
const struct ly_ctx *ctx = LYD_CTX(diff_node);
/* read all the valid attributes */
@@ -1242,7 +1242,7 @@
lyd_diff_cb diff_cb, void *cb_data)
{
const struct lyd_node *root;
- struct lyd_dup_inst *dup_inst = NULL;
+ struct hash_table *dup_inst = NULL;
LY_ERR ret = LY_SUCCESS;
LY_LIST_FOR(diff, root) {
@@ -1757,12 +1757,12 @@
*/
static LY_ERR
lyd_diff_merge_r(const struct lyd_node *src_diff, struct lyd_node *diff_parent, lyd_diff_cb diff_cb, void *cb_data,
- struct lyd_dup_inst **dup_inst, uint16_t options, struct lyd_node **diff)
+ struct hash_table **dup_inst, uint16_t options, struct lyd_node **diff)
{
LY_ERR ret = LY_SUCCESS;
struct lyd_node *child, *diff_node = NULL;
enum lyd_diff_op src_op, cur_op;
- struct lyd_dup_inst *child_dup_inst = NULL;
+ struct hash_table *child_dup_inst = NULL;
/* get source node operation */
LY_CHECK_RET(lyd_diff_get_op(src_diff, &src_op));
@@ -1868,7 +1868,7 @@
lyd_diff_cb diff_cb, void *cb_data, uint16_t options)
{
const struct lyd_node *src_root;
- struct lyd_dup_inst *dup_inst = NULL;
+ struct hash_table *dup_inst = NULL;
LY_ERR ret = LY_SUCCESS;
LY_LIST_FOR(src_diff, src_root) {
@@ -1891,7 +1891,7 @@
lyd_diff_cb diff_cb, void *cb_data, uint16_t options)
{
LY_ERR ret;
- struct lyd_dup_inst *dup_inst = NULL;
+ struct hash_table *dup_inst = NULL;
if (!src_sibling) {
return LY_SUCCESS;