diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:55:11 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:55:11 +0000 |
commit | cd07912073c951b4bbb871ed2653af1be2cfc714 (patch) | |
tree | 1073c2308492e6aea4c66cb7436ee92db2abfd42 /src/tree_data_hash.c | |
parent | Initial commit. (diff) | |
download | libyang2-cd07912073c951b4bbb871ed2653af1be2cfc714.tar.xz libyang2-cd07912073c951b4bbb871ed2653af1be2cfc714.zip |
Adding upstream version 2.1.30.upstream/2.1.30upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/tree_data_hash.c')
-rw-r--r-- | src/tree_data_hash.c | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/src/tree_data_hash.c b/src/tree_data_hash.c new file mode 100644 index 0000000..52f99a8 --- /dev/null +++ b/src/tree_data_hash.c @@ -0,0 +1,237 @@ +/** + * @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 calls hash function again with empty key, + * just so that it differs from the first-instance hash + */ + node->hash = dict_hash_multi(node->hash, NULL, 0); + } 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 && (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; + } + } + } +} |