blob: 523c85d8ad8e23b8b025df3e93db6fe56bf0b448 [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 Krejci535ea9f2020-05-29 16:01:05 +020024#include "tree.h"
25#include "tree_data.h"
26#include "tree_schema.h"
Radek Krejci1f05b6a2019-07-18 16:15:06 +020027
28static void
29lyd_hash_keyless_list_dfs(struct lyd_node *child, uint32_t *hash)
30{
31 struct lyd_node *iter;
32
33 LY_LIST_FOR(child, iter) {
34 switch (iter->schema->nodetype) {
35 case LYS_CONTAINER:
36 case LYS_LIST:
Michal Vasko22df3f02020-08-24 13:29:22 +020037 lyd_hash_keyless_list_dfs(((struct lyd_node_inner *)iter)->child, hash);
Radek Krejci1f05b6a2019-07-18 16:15:06 +020038 break;
39 case LYS_LEAFLIST:
40 case LYS_ANYXML:
41 case LYS_ANYDATA:
42 case LYS_LEAF:
43 *hash = dict_hash_multi(*hash, (char *)&iter->hash, sizeof iter->hash);
44 break;
45 default:
46 LOGINT(NULL);
47 }
48 }
49}
50
51LY_ERR
52lyd_hash(struct lyd_node *node)
53{
54 struct lyd_node *iter;
55
Michal Vasko52927e22020-03-16 17:26:14 +010056 if (!node->schema) {
57 return LY_SUCCESS;
58 }
59
Radek Krejci1f05b6a2019-07-18 16:15:06 +020060 node->hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
61 node->hash = dict_hash_multi(node->hash, node->schema->name, strlen(node->schema->name));
62
63 if (node->schema->nodetype == LYS_LIST) {
Michal Vasko22df3f02020-08-24 13:29:22 +020064 struct lyd_node_inner *list = (struct lyd_node_inner *)node;
Radek Krejci0fe9b512019-07-26 17:51:05 +020065 if (!(node->schema->flags & LYS_KEYLESS)) {
Radek Krejci1f05b6a2019-07-18 16:15:06 +020066 /* list's hash is made of its keys */
Michal Vaskoba99a3e2020-08-18 15:50:05 +020067 for (iter = list->child; iter && (iter->schema->flags & LYS_KEY); iter = iter->next) {
Michal Vaskob7be7a82020-08-20 09:09:04 +020068 const char *value = LYD_CANON_VALUE(iter);
Radek Krejci1f05b6a2019-07-18 16:15:06 +020069 node->hash = dict_hash_multi(node->hash, value, strlen(value));
Radek Krejci1f05b6a2019-07-18 16:15:06 +020070 }
71 } else {
72 /* keyless status list */
73 lyd_hash_keyless_list_dfs(list->child, &node->hash);
74 }
75 } else if (node->schema->nodetype == LYS_LEAFLIST) {
Michal Vaskob7be7a82020-08-20 09:09:04 +020076 const char *value = LYD_CANON_VALUE(node);
Radek Krejci1f05b6a2019-07-18 16:15:06 +020077 node->hash = dict_hash_multi(node->hash, value, strlen(value));
Radek Krejci1f05b6a2019-07-18 16:15:06 +020078 }
79 /* finish the hash */
80 node->hash = dict_hash_multi(node->hash, NULL, 0);
81
82 return LY_SUCCESS;
83}
84
Radek Krejci857189e2020-09-01 13:26:36 +020085/**
86 * @brief Compare callback for values in hash table.
87 *
88 * Implementation of ::values_equal_cb.
89 */
90static ly_bool
91lyd_hash_table_val_equal(void *val1_p, void *val2_p, ly_bool mod, void *UNUSED(cb_data))
Radek Krejci1f05b6a2019-07-18 16:15:06 +020092{
93 struct lyd_node *val1, *val2;
94
95 val1 = *((struct lyd_node **)val1_p);
96 val2 = *((struct lyd_node **)val2_p);
97
98 if (mod) {
99 if (val1 == val2) {
100 return 1;
101 } else {
102 return 0;
103 }
104 }
105
Michal Vaskoda859032020-07-14 12:20:14 +0200106 if (val1->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) {
107 /* match on exact instance */
Michal Vasko8f359bf2020-07-28 10:41:15 +0200108 if (!lyd_compare_single(val1, val2, 0)) {
Michal Vaskoda859032020-07-14 12:20:14 +0200109 return 1;
110 }
111 } else if (val1->schema == val2->schema) {
112 /* just schema match */
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200113 return 1;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200114 }
Michal Vaskoda859032020-07-14 12:20:14 +0200115 return 0;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200116}
117
Michal Vaskob104f112020-07-17 09:54:54 +0200118/**
119 * @brief Add single node into children hash table.
120 *
121 * @param[in] ht Children hash table.
122 * @param[in] node Node to insert.
123 * @param[in] empty_ht Whether we started with an empty HT meaning no nodes were inserted yet.
124 * @return LY_ERR value.
125 */
126static LY_ERR
Radek Krejci857189e2020-09-01 13:26:36 +0200127lyd_insert_hash_add(struct hash_table *ht, struct lyd_node *node, ly_bool empty_ht)
Michal Vaskob104f112020-07-17 09:54:54 +0200128{
129 uint32_t hash;
130
131 assert(ht && node && node->schema);
132
133 /* add node itself */
134 if (lyht_insert(ht, &node, node->hash, NULL)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200135 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200136 return LY_EINT;
137 }
138
139 /* add first instance of a (leaf-)list */
Michal Vasko69730152020-10-09 16:30:07 +0200140 if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) &&
141 (!node->prev->next || (node->prev->schema != node->schema))) {
Michal Vaskob104f112020-07-17 09:54:54 +0200142 /* get the simple hash */
143 hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
144 hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
145 hash = dict_hash_multi(hash, NULL, 0);
146
147 /* remove any previous stored instance, only if we did not start with an empty HT */
148 if (!empty_ht && node->next && (node->next->schema == node->schema)) {
149 if (lyht_remove(ht, &node->next, hash)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200150 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200151 return LY_EINT;
152 }
153 }
154
155 /* insert this instance as the first (leaf-)list instance */
156 if (lyht_insert(ht, &node, hash, NULL)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200157 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200158 return LY_EINT;
159 }
160 }
161
162 return LY_SUCCESS;
163}
164
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200165LY_ERR
166lyd_insert_hash(struct lyd_node *node)
167{
168 struct lyd_node *iter;
Michal Vaskob104f112020-07-17 09:54:54 +0200169 uint32_t u;
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200170
Michal Vasko52927e22020-03-16 17:26:14 +0100171 if (!node->parent || !node->schema || !node->parent->schema) {
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200172 /* nothing to do */
173 return LY_SUCCESS;
174 }
175
176 /* create parent hash table if required, otherwise just add the new child */
177 if (!node->parent->children_ht) {
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200178 /* the hash table is created only when the number of children in a node exceeds the
Michal Vasko60ea6352020-06-29 13:39:39 +0200179 * defined minimal limit LYD_HT_MIN_ITEMS
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200180 */
Michal Vaskob104f112020-07-17 09:54:54 +0200181 u = 0;
182 LY_LIST_FOR(node->parent->child, iter) {
183 if (iter->schema) {
184 ++u;
185 }
186 }
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200187 if (u >= LYD_HT_MIN_ITEMS) {
188 /* create hash table, insert all the children */
189 node->parent->children_ht = lyht_new(1, sizeof(struct lyd_node *), lyd_hash_table_val_equal, NULL, 1);
190 LY_LIST_FOR(node->parent->child, iter) {
Michal Vaskob104f112020-07-17 09:54:54 +0200191 if (iter->schema) {
192 LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, iter, 1));
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200193 }
194 }
195 }
196 } else {
Michal Vaskob104f112020-07-17 09:54:54 +0200197 LY_CHECK_RET(lyd_insert_hash_add(node->parent->children_ht, node, 0));
Radek Krejci1f05b6a2019-07-18 16:15:06 +0200198 }
199
200 return LY_SUCCESS;
201}
Radek Krejcie7b95092019-05-15 11:03:07 +0200202
203void
204lyd_unlink_hash(struct lyd_node *node)
205{
Michal Vaskob104f112020-07-17 09:54:54 +0200206 uint32_t hash;
207
208 if (!node->parent || !node->schema || !node->parent->schema || !node->parent->children_ht) {
209 /* not in any HT */
210 return;
211 }
212
213 /* remove from the parent HT */
214 if (lyht_remove(node->parent->children_ht, &node, node->hash)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200215 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200216 return;
217 }
218
219 /* first instance of the (leaf-)list, needs to be removed from HT */
220 if ((node->schema->nodetype & (LYS_LIST | LYS_LEAFLIST)) && (!node->prev->next || (node->prev->schema != node->schema))) {
221 /* get the simple hash */
222 hash = dict_hash_multi(0, node->schema->module->name, strlen(node->schema->module->name));
223 hash = dict_hash_multi(hash, node->schema->name, strlen(node->schema->name));
224 hash = dict_hash_multi(hash, NULL, 0);
225
226 /* remove the instance */
227 if (lyht_remove(node->parent->children_ht, &node, hash)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200228 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200229 return;
230 }
231
232 /* add the next instance */
233 if (node->next && (node->next->schema == node->schema)) {
234 if (lyht_insert(node->parent->children_ht, &node->next, hash, NULL)) {
Michal Vaskob7be7a82020-08-20 09:09:04 +0200235 LOGINT(LYD_CTX(node));
Michal Vaskob104f112020-07-17 09:54:54 +0200236 return;
237 }
238 }
Radek Krejcie7b95092019-05-15 11:03:07 +0200239 }
240}