/src/libyang/src/tree_data_hash.c

Source (jump to first uncovered line)
/**
 * @file tree_data_hash.c
 * @author Radek Krejci <rkrejci@cesnet.cz>
 * @brief Functions to manipulate with the data node's hashes.
 *
 * Copyright (c) 2019 CESNET, z.s.p.o.
 *
 * This source code is licensed under BSD 3-Clause License (the "License").
 * You may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     https://opensource.org/licenses/BSD-3-Clause
 */

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "common.h"
#include "compat.h"
#include "hash_table.h"
#include "log.h"
#include "plugins_types.h"
#include "tree.h"
#include "tree_data.h"
#include "tree_schema.h"

LY_ERR
lyd_hash(struct lyd_node *node)
{
    struct lyd_node *iter;
    const void *hash_key;
    ly_bool dyn;
    size_t key_len;

    if (!node->schema) {
        return LY_SUCCESS;
    }

    /* hash always starts with the module and schema name */
    node->hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
    node->hash = dict_hash_multi(node->hash, node->schema->name, strlen(node->schema->name));

    if (node->schema->nodetype == LYS_LIST) {
        if (node->schema->flags & LYS_KEYLESS) {
            /* key-less list simply adds its schema name again to the hash, just so that it differs from the first-instance hash */
            node->hash = dict_hash_multi(node->hash, node->schema->name, strlen(node->schema->name));
        } else {
            struct lyd_node_inner *list = (struct lyd_node_inner *)node;

            /* list hash is made up from its keys */
            for (iter = list->child; iter && (iter->schema->flags & LYS_KEY); iter = iter->next) {
                struct lyd_node_term *key = (struct lyd_node_term *)iter;

                hash_key = key->value.realtype->plugin->print(NULL, &key->value, LY_VALUE_LYB, NULL, &dyn, &key_len);
                node->hash = dict_hash_multi(node->hash, hash_key, key_len);
                if (dyn) {
                    free((void *)hash_key);
                }
            }
        }
    } else if (node->schema->nodetype == LYS_LEAFLIST) {
        /* leaf-list adds its hash key */
        struct lyd_node_term *llist = (struct lyd_node_term *)node;

        hash_key = llist->value.realtype->plugin->print(NULL, &llist->value, LY_VALUE_LYB, NULL, &dyn, &key_len);
        node->hash = dict_hash_multi(node->hash, hash_key, key_len);
        if (dyn) {
            free((void *)hash_key);
        }
    }

    /* finish the hash */
    node->hash = dict_hash_multi(node->hash, NULL, 0);

    return LY_SUCCESS;
}

/**
 * @brief Compare callback for values in hash table.
 *
 * Implementation of ::lyht_value_equal_cb.
 */
static ly_bool
lyd_hash_table_val_equal(void *val1_p, void *val2_p, ly_bool mod, void *UNUSED(cb_data))
{
    struct lyd_node *val1, *val2;

    val1 = *((struct lyd_node **)val1_p);
    val2 = *((struct lyd_node **)val2_p);

    if (mod) {
        if (val1 == val2) {
            return 1;
        } else {
            return 0;
        }
    }

    if (val1->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
        /* match on exact instance */
        if (!lyd_compare_single(val1, val2, 0)) {
            return 1;
        }
    } else if (val1->schema == val2->schema) {
        /* just schema match */
        return 1;
    }
    return 0;
}

/**
 * @brief Add single node into children hash table.
 *
 * @param[in] ht Children hash table.
 * @param[in] node Node to insert.
 * @param[in] empty_ht Whether we started with an empty HT meaning no nodes were inserted yet.
 * @return LY_ERR value.
 */
static LY_ERR
lyd_insert_hash_add(struct hash_table *ht, struct lyd_node *node, ly_bool empty_ht)
{
    uint32_t hash;

    assert(ht && node && node->schema);

    /* add node itself */
    if (lyht_insert(ht, &node, node->hash, NULL)) {
        LOGINT_RET(LYD_CTX(node));
    }

    /* add first instance of a (leaf-)list */
    if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) &&
            (!node->prev->next || (node->prev->schema != node->schema))) {
        /* get the simple hash */
        hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
        hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
        hash = dict_hash_multi(hash, NULL, 0);

        /* remove any previous stored instance, only if we did not start with an empty HT */
        if (!empty_ht && node->next && (node->next->schema == node->schema)) {
            if (lyht_remove(ht, &node->next, hash)) {
                LOGINT_RET(LYD_CTX(node));
            }
        }

        /* in this case there would be the exact same value twice in the hash table, not supported (by the HT) */
        assert(hash != node->hash);

        /* insert this instance as the first (leaf-)list instance */
        if (lyht_insert(ht, &node, hash, NULL)) {
            LOGINT_RET(LYD_CTX(node));
        }
    }

    return LY_SUCCESS;
}

LY_ERR
lyd_insert_hash(struct lyd_node *node)
{
    struct lyd_node *iter;
    uint32_t u;

    if (!node->parent || !node->schema || !node->parent->schema) {
        /* nothing to do */
        return LY_SUCCESS;
    }

    /* create parent hash table if required, otherwise just add the new child */
    if (!node->parent->children_ht) {
        /* the hash table is created only when the number of children in a node exceeds the
         * defined minimal limit LYD_HT_MIN_ITEMS
         */
        u = 0;
        LY_LIST_FOR(node->parent->child, iter) {
            if (iter->schema) {
                ++u;
            }
        }
        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);
            LY_LIST_FOR(node->parent->child, iter) {
                if (iter->schema) {
                    LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, iter, 1));
                }
            }
        }
    } else {
        LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, node, 0));
    }

    return LY_SUCCESS;
}

void
lyd_unlink_hash(struct lyd_node *node)
{
    uint32_t hash;

    if (!node->parent || !node->schema || !node->parent->schema || !node->parent->children_ht) {
        /* not in any HT */
        return;
    }

    /* remove from the parent HT */
    if (lyht_remove(node->parent->children_ht, &node, node->hash)) {
        LOGINT(LYD_CTX(node));
        return;
    }

    /* first instance of the (leaf-)list, needs to be removed from HT */
    if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) && (!node->prev->next || (node->prev->schema != node->schema))) {
        /* get the simple hash */
        hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
        hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
        hash = dict_hash_multi(hash, NULL, 0);

        /* remove the instance */
        if (lyht_remove(node->parent->children_ht, &node, hash)) {
            LOGINT(LYD_CTX(node));
            return;
        }

        /* add the next instance */
        if (node->next && (node->next->schema == node->schema)) {
            if (lyht_insert(node->parent->children_ht, &node->next, hash, NULL)) {
                LOGINT(LYD_CTX(node));
                return;
            }
        }
    }
}

Coverage Report

Created: 2025-08-26 06:20

Line	Count	Source (jump to first uncovered line)
1		/**
2		* @file tree_data_hash.c
3		* @author Radek Krejci <rkrejci@cesnet.cz>
4		* @brief Functions to manipulate with the data node's hashes.
5		*
6		* Copyright (c) 2019 CESNET, z.s.p.o.
7		*
8		* This source code is licensed under BSD 3-Clause License (the "License").
9		* You may not use this file except in compliance with the License.
10		* You may obtain a copy of the License at
11		*
12		* https://opensource.org/licenses/BSD-3-Clause
13		*/
14
15		#include <assert.h>
16		#include <stdint.h>
17		#include <stdlib.h>
18		#include <string.h>
19
20		#include "common.h"
21		#include "compat.h"
22		#include "hash_table.h"
23		#include "log.h"
24		#include "plugins_types.h"
25		#include "tree.h"
26		#include "tree_data.h"
27		#include "tree_schema.h"
28
29		LY_ERR
30		lyd_hash(struct lyd_node *node)
31	0	{
32	0	struct lyd_node *iter;
33	0	const void *hash_key;
34	0	ly_bool dyn;
35	0	size_t key_len;
36
37	0	if (!node->schema) {
38	0	return LY_SUCCESS;
39	0	}
40
41		/* hash always starts with the module and schema name */
42	0	node->hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
43	0	node->hash = dict_hash_multi(node->hash, node->schema->name, strlen(node->schema->name));
44
45	0	if (node->schema->nodetype == LYS_LIST) {
46	0	if (node->schema->flags & LYS_KEYLESS) {
47		/* key-less list simply adds its schema name again to the hash, just so that it differs from the first-instance hash */
48	0	node->hash = dict_hash_multi(node->hash, node->schema->name, strlen(node->schema->name));
49	0	} else {
50	0	struct lyd_node_inner list = (struct lyd_node_inner )node;
51
52		/* list hash is made up from its keys */
53	0	for (iter = list->child; iter && (iter->schema->flags & LYS_KEY); iter = iter->next) {
54	0	struct lyd_node_term key = (struct lyd_node_term )iter;
55
56	0	hash_key = key->value.realtype->plugin->print(NULL, &key->value, LY_VALUE_LYB, NULL, &dyn, &key_len);
57	0	node->hash = dict_hash_multi(node->hash, hash_key, key_len);
58	0	if (dyn) {
59	0	free((void *)hash_key);
60	0	}
61	0	}
62	0	}
63	0	} else if (node->schema->nodetype == LYS_LEAFLIST) {
64		/* leaf-list adds its hash key */
65	0	struct lyd_node_term llist = (struct lyd_node_term )node;
66
67	0	hash_key = llist->value.realtype->plugin->print(NULL, &llist->value, LY_VALUE_LYB, NULL, &dyn, &key_len);
68	0	node->hash = dict_hash_multi(node->hash, hash_key, key_len);
69	0	if (dyn) {
70	0	free((void *)hash_key);
71	0	}
72	0	}
73
74		/* finish the hash */
75	0	node->hash = dict_hash_multi(node->hash, NULL, 0);
76
77	0	return LY_SUCCESS;
78	0	}
79
80		/**
81		* @brief Compare callback for values in hash table.
82		*
83		* Implementation of ::lyht_value_equal_cb.
84		*/
85		static ly_bool
86		lyd_hash_table_val_equal(void val1_p, void val2_p, ly_bool mod, void *UNUSED(cb_data))
87	0	{
88	0	struct lyd_node val1, val2;
89
90	0	val1 = ((struct lyd_node *)val1_p);
91	0	val2 = ((struct lyd_node *)val2_p);
92
93	0	if (mod) {
94	0	if (val1 == val2) {
95	0	return 1;
96	0	} else {
97	0	return 0;
98	0	}
99	0	}
100
101	0	if (val1->schema->nodetype & (LYS_LIST \| LYS_LEAFLIST)) {
102		/* match on exact instance */
103	0	if (!lyd_compare_single(val1, val2, 0)) {
104	0	return 1;
105	0	}
106	0	} else if (val1->schema == val2->schema) {
107		/* just schema match */
108	0	return 1;
109	0	}
110	0	return 0;
111	0	}
112
113		/**
114		* @brief Add single node into children hash table.
115		*
116		* @param[in] ht Children hash table.
117		* @param[in] node Node to insert.
118		* @param[in] empty_ht Whether we started with an empty HT meaning no nodes were inserted yet.
119		* @return LY_ERR value.
120		*/
121		static LY_ERR
122		lyd_insert_hash_add(struct hash_table ht, struct lyd_node node, ly_bool empty_ht)
123	0	{
124	0	uint32_t hash;
125
126	0	assert(ht && node && node->schema);
127
128		/* add node itself */
129	0	if (lyht_insert(ht, &node, node->hash, NULL)) {
130	0	LOGINT_RET(LYD_CTX(node));
131	0	}
132
133		/* add first instance of a (leaf-)list */
134	0	if ((node->schema->nodetype & (LYS_LIST \| LYS_LEAFLIST)) &&
135	0	(!node->prev->next \|\| (node->prev->schema != node->schema))) {
136		/* get the simple hash */
137	0	hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
138	0	hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
139	0	hash = dict_hash_multi(hash, NULL, 0);
140
141		/* remove any previous stored instance, only if we did not start with an empty HT */
142	0	if (!empty_ht && node->next && (node->next->schema == node->schema)) {
143	0	if (lyht_remove(ht, &node->next, hash)) {
144	0	LOGINT_RET(LYD_CTX(node));
145	0	}
146	0	}
147
148		/* in this case there would be the exact same value twice in the hash table, not supported (by the HT) */
149	0	assert(hash != node->hash);
150
151		/* insert this instance as the first (leaf-)list instance */
152	0	if (lyht_insert(ht, &node, hash, NULL)) {
153	0	LOGINT_RET(LYD_CTX(node));
154	0	}
155	0	}
156
157	0	return LY_SUCCESS;
158	0	}
159
160		LY_ERR
161		lyd_insert_hash(struct lyd_node *node)
162	0	{
163	0	struct lyd_node *iter;
164	0	uint32_t u;
165
166	0	if (!node->parent \|\| !node->schema \|\| !node->parent->schema) {
167		/* nothing to do */
168	0	return LY_SUCCESS;
169	0	}
170
171		/* create parent hash table if required, otherwise just add the new child */
172	0	if (!node->parent->children_ht) {
173		/* the hash table is created only when the number of children in a node exceeds the
174		* defined minimal limit LYD_HT_MIN_ITEMS
175		*/
176	0	u = 0;
177	0	LY_LIST_FOR(node->parent->child, iter) {
178	0	if (iter->schema) {
179	0	++u;
180	0	}
181	0	}
182	0	if (u >= LYD_HT_MIN_ITEMS) {
183		/* create hash table, insert all the children */
184	0	node->parent->children_ht = lyht_new(1, sizeof(struct lyd_node *), lyd_hash_table_val_equal, NULL, 1);
185	0	LY_LIST_FOR(node->parent->child, iter) {
186	0	if (iter->schema) {
187	0	LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, iter, 1));
188	0	}
189	0	}
190	0	}
191	0	} else {
192	0	LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, node, 0));
193	0	}
194
195	0	return LY_SUCCESS;
196	0	}
197
198		void
199		lyd_unlink_hash(struct lyd_node *node)
200	0	{
201	0	uint32_t hash;
202
203	0	if (!node->parent \|\| !node->schema \|\| !node->parent->schema \|\| !node->parent->children_ht) {
204		/* not in any HT */
205	0	return;
206	0	}
207
208		/* remove from the parent HT */
209	0	if (lyht_remove(node->parent->children_ht, &node, node->hash)) {
210	0	LOGINT(LYD_CTX(node));
211	0	return;
212	0	}
213
214		/* first instance of the (leaf-)list, needs to be removed from HT */
215	0	if ((node->schema->nodetype & (LYS_LIST \| LYS_LEAFLIST)) && (!node->prev->next \|\| (node->prev->schema != node->schema))) {
216		/* get the simple hash */
217	0	hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
218	0	hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
219	0	hash = dict_hash_multi(hash, NULL, 0);
220
221		/* remove the instance */
222	0	if (lyht_remove(node->parent->children_ht, &node, hash)) {
223	0	LOGINT(LYD_CTX(node));
224	0	return;
225	0	}
226
227		/* add the next instance */
228	0	if (node->next && (node->next->schema == node->schema)) {
229	0	if (lyht_insert(node->parent->children_ht, &node->next, hash, NULL)) {
230	0	LOGINT(LYD_CTX(node));
231	0	return;
232	0	}
233	0	}
234	0	}
235	0	}