blob: f69a552d9c8980bf988429e2a5b664963ecf6623 [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
Radek Krejcie7b95092019-05-15 11:03:07 +020020#include "common.h"
Michal Vasko69730152020-10-09 16:30:07 +020021#include "compat.h"
Radek Krejcie7b95092019-05-15 11:03:07 +020022#include "hash_table.h"
Radek Krejci535ea9f2020-05-29 16:01:05 +020023#include "log.h"
Radek Krejci1f05b6a2019-07-18 16:15:06 +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
29static void
30lyd_hash_keyless_list_dfs(struct lyd_node *child, uint32_t *hash)
31{
32 struct lyd_node *iter;
33
34 LY_LIST_FOR(child, iter) {
35 switch (iter->schema->nodetype) {
36 case LYS_CONTAINER:
37 case LYS_LIST:
Michal Vasko22df3f02020-08-24 13:29:22 +020038 lyd_hash_keyless_list_dfs(((struct lyd_node_inner *)iter)->child, hash);
Radek Krejci1f05b6a2019-07-18 16:15:06 +020039 break;
40 case LYS_LEAFLIST:
41 case LYS_ANYXML:
42 case LYS_ANYDATA:
43 case LYS_LEAF:
44 *hash = dict_hash_multi(*hash, (char *)&iter->hash, sizeof iter->hash);
45 break;
46 default:
47 LOGINT(NULL);
48 }
49 }
50}
51
52LY_ERR
53lyd_hash(struct lyd_node *node)
54{
55 struct lyd_node *iter;
56
Michal Vasko52927e22020-03-16 17:26:14 +010057 if (!node->schema) {
58 return LY_SUCCESS;
59 }
60
Radek Krejci1f05b6a2019-07-18 16:15:06 +020061 node->hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
62 node->hash = dict_hash_multi(node->hash, node->schema->name, strlen(node->schema->name));
63
64 if (node->schema->nodetype == LYS_LIST) {
Michal Vasko22df3f02020-08-24 13:29:22 +020065 struct lyd_node_inner *list = (struct lyd_node_inner *)node;
Radek Krejci0fe9b512019-07-26 17:51:05 +020066 if (!(node->schema->flags & LYS_KEYLESS)) {
Radek Krejci1f05b6a2019-07-18 16:15:06 +020067 /* list's hash is made of its keys */
Michal Vaskoba99a3e2020-08-18 15:50:05 +020068 for (iter = list->child; iter && (iter->schema->flags & LYS_KEY); iter = iter->next) {
Michal Vaskob7be7a82020-08-20 09:09:04 +020069 const char *value = LYD_CANON_VALUE(iter);
Radek Krejci1f05b6a2019-07-18 16:15:06 +020070 node->hash = dict_hash_multi(node->hash, value, strlen(value));
Radek Krejci1f05b6a2019-07-18 16:15:06 +020071 }
72 } else {
73 /* keyless status list */
74 lyd_hash_keyless_list_dfs(list->child, &node->hash);
75 }
76 } else if (node->schema->nodetype == LYS_LEAFLIST) {
Michal Vaskob7be7a82020-08-20 09:09:04 +020077 const char *value = LYD_CANON_VALUE(node);
Radek Krejci1f05b6a2019-07-18 16:15:06 +020078 node->hash = dict_hash_multi(node->hash, value, strlen(value));
Radek Krejci1f05b6a2019-07-18 16:15:06 +020079 }
80 /* finish the hash */
81 node->hash = dict_hash_multi(node->hash, NULL, 0);
82
83 return LY_SUCCESS;
84}
85
Radek Krejci857189e2020-09-01 13:26:36 +020086/**
87 * @brief Compare callback for values in hash table.
88 *
89 * Implementation of ::values_equal_cb.
90 */
91static ly_bool
92lyd_hash_table_val_equal(void *val1_p, void *val2_p, ly_bool mod, void *UNUSED(cb_data))
Radek Krejci1f05b6a2019-07-18 16:15:06 +020093{
94 struct lyd_node *val1, *val2;
95
96 val1 = *((struct lyd_node **)val1_p);
97 val2 = *((struct lyd_node **)val2_p);
98
99 if (mod) {
100 if (val1 == val2) {
101 return 1;
102 } else {
103 return 0;
104 }
105 }
106
Michal Vaskoda859032020-07-14 12:20:14 +0200107 if (val1->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
108 /* match on exact instance */
Michal Vasko8f359bf2020-07-28 10:41:15 +0200109 if (!lyd_compare_single(val1, val2, 0)) {
Michal Vaskoda859032020-07-14 12:20:14 +0200110 return 1;
111 }
112 } else if (val1->schema == val2->schema) {
113 /* just schema match */
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200114 return 1;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200115 }
Michal Vaskoda859032020-07-14 12:20:14 +0200116 return 0;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200117}
118
Michal Vaskob104f112020-07-17 09:54:54 +0200119/**
120 * @brief Add single node into children hash table.
121 *
122 * @param[in] ht Children hash table.
123 * @param[in] node Node to insert.
124 * @param[in] empty_ht Whether we started with an empty HT meaning no nodes were inserted yet.
125 * @return LY_ERR value.
126 */
127static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200128lyd_insert_hash_add(struct hash_table *ht, struct lyd_node *node, ly_bool empty_ht)
Michal Vaskob104f112020-07-17 09:54:54 +0200129{
130 uint32_t hash;
131
132 assert(ht && node && node->schema);
133
134 /* add node itself */
135 if (lyht_insert(ht, &node, node->hash, NULL)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200136 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200137 return LY_EINT;
138 }
139
140 /* add first instance of a (leaf-)list */
Michal Vasko69730152020-10-09 16:30:07 +0200141 if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) &&
142 (!node->prev->next || (node->prev->schema != node->schema))) {
Michal Vaskob104f112020-07-17 09:54:54 +0200143 /* get the simple hash */
144 hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
145 hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
146 hash = dict_hash_multi(hash, NULL, 0);
147
148 /* remove any previous stored instance, only if we did not start with an empty HT */
149 if (!empty_ht && node->next && (node->next->schema == node->schema)) {
150 if (lyht_remove(ht, &node->next, hash)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200151 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200152 return LY_EINT;
153 }
154 }
155
156 /* insert this instance as the first (leaf-)list instance */
157 if (lyht_insert(ht, &node, hash, NULL)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200158 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200159 return LY_EINT;
160 }
161 }
162
163 return LY_SUCCESS;
164}
165
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200166LY_ERR
167lyd_insert_hash(struct lyd_node *node)
168{
169 struct lyd_node *iter;
Michal Vaskob104f112020-07-17 09:54:54 +0200170 uint32_t u;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200171
Michal Vasko52927e22020-03-16 17:26:14 +0100172 if (!node->parent || !node->schema || !node->parent->schema) {
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200173 /* nothing to do */
174 return LY_SUCCESS;
175 }
176
177 /* create parent hash table if required, otherwise just add the new child */
178 if (!node->parent->children_ht) {
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200179 /* the hash table is created only when the number of children in a node exceeds the
Michal Vasko60ea6352020-06-29 13:39:39 +0200180 * defined minimal limit LYD_HT_MIN_ITEMS
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200181 */
Michal Vaskob104f112020-07-17 09:54:54 +0200182 u = 0;
183 LY_LIST_FOR(node->parent->child, iter) {
184 if (iter->schema) {
185 ++u;
186 }
187 }
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200188 if (u >= LYD_HT_MIN_ITEMS) {
189 /* create hash table, insert all the children */
190 node->parent->children_ht = lyht_new(1, sizeof(struct lyd_node *), lyd_hash_table_val_equal, NULL, 1);
191 LY_LIST_FOR(node->parent->child, iter) {
Michal Vaskob104f112020-07-17 09:54:54 +0200192 if (iter->schema) {
193 LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, iter, 1));
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200194 }
195 }
196 }
197 } else {
Michal Vaskob104f112020-07-17 09:54:54 +0200198 LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, node, 0));
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200199 }
200
201 return LY_SUCCESS;
202}
Radek Krejcie7b95092019-05-15 11:03:07 +0200203
204void
205lyd_unlink_hash(struct lyd_node *node)
206{
Michal Vaskob104f112020-07-17 09:54:54 +0200207 uint32_t hash;
208
209 if (!node->parent || !node->schema || !node->parent->schema || !node->parent->children_ht) {
210 /* not in any HT */
211 return;
212 }
213
214 /* remove from the parent HT */
215 if (lyht_remove(node->parent->children_ht, &node, node->hash)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200216 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200217 return;
218 }
219
220 /* first instance of the (leaf-)list, needs to be removed from HT */
221 if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) && (!node->prev->next || (node->prev->schema != node->schema))) {
222 /* get the simple hash */
223 hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
224 hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
225 hash = dict_hash_multi(hash, NULL, 0);
226
227 /* remove the instance */
228 if (lyht_remove(node->parent->children_ht, &node, hash)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200229 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200230 return;
231 }
232
233 /* add the next instance */
234 if (node->next && (node->next->schema == node->schema)) {
235 if (lyht_insert(node->parent->children_ht, &node->next, hash, NULL)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200236 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200237 return;
238 }
239 }
Radek Krejcie7b95092019-05-15 11:03:07 +0200240 }
241}