blob: 9be655ca462da9c587194cac2229ec3a53a08f77 [file] [log] [blame]
Radek Krejcie7b95092019-05-15 11:03:07 +02001/**
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 */
Radek Krejci535ea9f2020-05-29 16:01:05 +020014
Michal Vaskob104f112020-07-17 09:54:54 +020015#include <assert.h>
Radek Krejci535ea9f2020-05-29 16:01:05 +020016#include <stdint.h>
17#include <stdlib.h>
18#include <string.h>
19
Michal Vasko69730152020-10-09 16:30:07 +020020#include "compat.h"
Radek Krejcie7b95092019-05-15 11:03:07 +020021#include "hash_table.h"
Radek Krejci535ea9f2020-05-29 16:01:05 +020022#include "log.h"
Michal Vasko8f702ee2024-02-20 15:44:24 +010023#include "ly_common.h"
Radek Krejci813c02d2021-04-26 10:29:19 +020024#include "plugins_types.h"
Radek Krejci535ea9f2020-05-29 16:01:05 +020025#include "tree.h"
26#include "tree_data.h"
27#include "tree_schema.h"
Radek Krejci1f05b6a2019-07-18 16:15:06 +020028
Radek Krejci1f05b6a2019-07-18 16:15:06 +020029LY_ERR
30lyd_hash(struct lyd_node *node)
31{
32 struct lyd_node *iter;
Radek Krejci813c02d2021-04-26 10:29:19 +020033 const void *hash_key;
34 ly_bool dyn;
35 size_t key_len;
Radek Krejci1f05b6a2019-07-18 16:15:06 +020036
Michal Vasko52927e22020-03-16 17:26:14 +010037 if (!node->schema) {
38 return LY_SUCCESS;
39 }
40
Michal Vaskoe78faec2021-04-08 17:24:43 +020041 /* hash always starts with the module and schema name */
Michal Vaskoae130f52023-04-20 14:25:16 +020042 node->hash = lyht_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
43 node->hash = lyht_hash_multi(node->hash, node->schema->name, strlen(node->schema->name));
Radek Krejci1f05b6a2019-07-18 16:15:06 +020044
45 if (node->schema->nodetype == LYS_LIST) {
Michal Vaskoe78faec2021-04-08 17:24:43 +020046 if (node->schema->flags & LYS_KEYLESS) {
aPiecek4f07c3e2021-06-11 10:53:07 +020047 /* key-less list simply calls hash function again with empty key,
48 * just so that it differs from the first-instance hash
49 */
Michal Vaskoae130f52023-04-20 14:25:16 +020050 node->hash = lyht_hash_multi(node->hash, NULL, 0);
Michal Vaskoe78faec2021-04-08 17:24:43 +020051 } else {
52 struct lyd_node_inner *list = (struct lyd_node_inner *)node;
53
54 /* list hash is made up from its keys */
Michal Vasko5d3eaa72021-05-21 15:36:19 +020055 for (iter = list->child; iter && iter->schema && (iter->schema->flags & LYS_KEY); iter = iter->next) {
Radek Krejci813c02d2021-04-26 10:29:19 +020056 struct lyd_node_term *key = (struct lyd_node_term *)iter;
57
Michal Vaskodcfac2c2021-05-10 11:36:37 +020058 hash_key = key->value.realtype->plugin->print(NULL, &key->value, LY_VALUE_LYB, NULL, &dyn, &key_len);
Michal Vaskoae130f52023-04-20 14:25:16 +020059 node->hash = lyht_hash_multi(node->hash, hash_key, key_len);
Radek Krejci813c02d2021-04-26 10:29:19 +020060 if (dyn) {
61 free((void *)hash_key);
62 }
Radek Krejci1f05b6a2019-07-18 16:15:06 +020063 }
Radek Krejci1f05b6a2019-07-18 16:15:06 +020064 }
65 } else if (node->schema->nodetype == LYS_LEAFLIST) {
Radek Krejci813c02d2021-04-26 10:29:19 +020066 /* leaf-list adds its hash key */
67 struct lyd_node_term *llist = (struct lyd_node_term *)node;
68
Michal Vaskodcfac2c2021-05-10 11:36:37 +020069 hash_key = llist->value.realtype->plugin->print(NULL, &llist->value, LY_VALUE_LYB, NULL, &dyn, &key_len);
Michal Vaskoae130f52023-04-20 14:25:16 +020070 node->hash = lyht_hash_multi(node->hash, hash_key, key_len);
Radek Krejci813c02d2021-04-26 10:29:19 +020071 if (dyn) {
72 free((void *)hash_key);
73 }
Radek Krejci1f05b6a2019-07-18 16:15:06 +020074 }
Michal Vaskoe78faec2021-04-08 17:24:43 +020075
Radek Krejci1f05b6a2019-07-18 16:15:06 +020076 /* finish the hash */
Michal Vaskoae130f52023-04-20 14:25:16 +020077 node->hash = lyht_hash_multi(node->hash, NULL, 0);
Radek Krejci1f05b6a2019-07-18 16:15:06 +020078
79 return LY_SUCCESS;
80}
81
Radek Krejci857189e2020-09-01 13:26:36 +020082/**
83 * @brief Compare callback for values in hash table.
84 *
Michal Vasko62524a92021-02-26 10:08:50 +010085 * Implementation of ::lyht_value_equal_cb.
Radek Krejci857189e2020-09-01 13:26:36 +020086 */
Ondrej Kusnirik747486a2024-08-19 10:52:44 +020087ly_bool
Radek Krejci857189e2020-09-01 13:26:36 +020088lyd_hash_table_val_equal(void *val1_p, void *val2_p, ly_bool mod, void *UNUSED(cb_data))
Radek Krejci1f05b6a2019-07-18 16:15:06 +020089{
90 struct lyd_node *val1, *val2;
91
92 val1 = *((struct lyd_node **)val1_p);
93 val2 = *((struct lyd_node **)val2_p);
94
95 if (mod) {
96 if (val1 == val2) {
97 return 1;
98 } else {
99 return 0;
100 }
101 }
102
Michal Vaskoda859032020-07-14 12:20:14 +0200103 if (val1->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
104 /* match on exact instance */
Michal Vasko8f359bf2020-07-28 10:41:15 +0200105 if (!lyd_compare_single(val1, val2, 0)) {
Michal Vaskoda859032020-07-14 12:20:14 +0200106 return 1;
107 }
108 } else if (val1->schema == val2->schema) {
109 /* just schema match */
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200110 return 1;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200111 }
Michal Vaskoda859032020-07-14 12:20:14 +0200112 return 0;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200113}
114
Michal Vaskob104f112020-07-17 09:54:54 +0200115/**
116 * @brief Add single node into children hash table.
117 *
118 * @param[in] ht Children hash table.
119 * @param[in] node Node to insert.
120 * @param[in] empty_ht Whether we started with an empty HT meaning no nodes were inserted yet.
121 * @return LY_ERR value.
122 */
123static LY_ERR
Michal Vasko8efac242023-03-30 08:24:56 +0200124lyd_insert_hash_add(struct ly_ht *ht, struct lyd_node *node, ly_bool empty_ht)
Michal Vaskob104f112020-07-17 09:54:54 +0200125{
126 uint32_t hash;
127
128 assert(ht && node && node->schema);
129
130 /* add node itself */
Olivier Matz78e96d82023-09-21 21:23:02 +0200131 if (lyht_insert_no_check(ht, &node, node->hash, NULL)) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200132 LOGINT_RET(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200133 }
134
135 /* add first instance of a (leaf-)list */
Michal Vasko69730152020-10-09 16:30:07 +0200136 if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) &&
137 (!node->prev->next || (node->prev->schema != node->schema))) {
Michal Vaskob104f112020-07-17 09:54:54 +0200138 /* get the simple hash */
Michal Vaskoae130f52023-04-20 14:25:16 +0200139 hash = lyht_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
140 hash = lyht_hash_multi(hash, node->schema->name, strlen(node->schema->name));
141 hash = lyht_hash_multi(hash, NULL, 0);
Michal Vaskob104f112020-07-17 09:54:54 +0200142
143 /* remove any previous stored instance, only if we did not start with an empty HT */
144 if (!empty_ht && node->next && (node->next->schema == node->schema)) {
145 if (lyht_remove(ht, &node->next, hash)) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200146 LOGINT_RET(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200147 }
148 }
149
Michal Vaskoe78faec2021-04-08 17:24:43 +0200150 /* in this case there would be the exact same value twice in the hash table, not supported (by the HT) */
151 assert(hash != node->hash);
Michal Vasko47718292021-02-26 10:12:44 +0100152
Michal Vaskob104f112020-07-17 09:54:54 +0200153 /* insert this instance as the first (leaf-)list instance */
154 if (lyht_insert(ht, &node, hash, NULL)) {
Michal Vaskoe78faec2021-04-08 17:24:43 +0200155 LOGINT_RET(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200156 }
157 }
158
Michal Vaskoe78faec2021-04-08 17:24:43 +0200159 return LY_SUCCESS;
Michal Vaskob104f112020-07-17 09:54:54 +0200160}
161
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200162LY_ERR
163lyd_insert_hash(struct lyd_node *node)
164{
165 struct lyd_node *iter;
Michal Vaskob104f112020-07-17 09:54:54 +0200166 uint32_t u;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200167
Michal Vasko52927e22020-03-16 17:26:14 +0100168 if (!node->parent || !node->schema || !node->parent->schema) {
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200169 /* nothing to do */
170 return LY_SUCCESS;
171 }
172
173 /* create parent hash table if required, otherwise just add the new child */
174 if (!node->parent->children_ht) {
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200175 /* the hash table is created only when the number of children in a node exceeds the
Michal Vasko60ea6352020-06-29 13:39:39 +0200176 * defined minimal limit LYD_HT_MIN_ITEMS
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200177 */
Michal Vaskob104f112020-07-17 09:54:54 +0200178 u = 0;
179 LY_LIST_FOR(node->parent->child, iter) {
180 if (iter->schema) {
181 ++u;
182 }
183 }
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200184 if (u >= LYD_HT_MIN_ITEMS) {
Olivier Matzc0feb682023-09-21 08:53:59 +0200185 node->parent->children_ht = lyht_new(lyht_get_fixed_size(u), sizeof(struct lyd_node *), lyd_hash_table_val_equal, NULL, 1);
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200186 LY_LIST_FOR(node->parent->child, iter) {
Michal Vaskob104f112020-07-17 09:54:54 +0200187 if (iter->schema) {
188 LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, iter, 1));
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200189 }
190 }
191 }
192 } else {
Michal Vaskob104f112020-07-17 09:54:54 +0200193 LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, node, 0));
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200194 }
195
196 return LY_SUCCESS;
197}
Radek Krejcie7b95092019-05-15 11:03:07 +0200198
199void
200lyd_unlink_hash(struct lyd_node *node)
201{
Michal Vaskob104f112020-07-17 09:54:54 +0200202 uint32_t hash;
203
204 if (!node->parent || !node->schema || !node->parent->schema || !node->parent->children_ht) {
205 /* not in any HT */
206 return;
207 }
208
209 /* remove from the parent HT */
210 if (lyht_remove(node->parent->children_ht, &node, node->hash)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200211 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200212 return;
213 }
214
215 /* first instance of the (leaf-)list, needs to be removed from HT */
216 if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) && (!node->prev->next || (node->prev->schema != node->schema))) {
217 /* get the simple hash */
Michal Vaskoae130f52023-04-20 14:25:16 +0200218 hash = lyht_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
219 hash = lyht_hash_multi(hash, node->schema->name, strlen(node->schema->name));
220 hash = lyht_hash_multi(hash, NULL, 0);
Michal Vaskob104f112020-07-17 09:54:54 +0200221
222 /* remove the instance */
223 if (lyht_remove(node->parent->children_ht, &node, hash)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200224 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200225 return;
226 }
227
228 /* add the next instance */
229 if (node->next && (node->next->schema == node->schema)) {
230 if (lyht_insert(node->parent->children_ht, &node->next, hash, NULL)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200231 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200232 return;
233 }
234 }
Radek Krejcie7b95092019-05-15 11:03:07 +0200235 }
236}