path: root/src/knot/zone/zone-tree.h

/*  Copyright (C) 2022 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

#pragma once

#include "contrib/qp-trie/trie.h"
#include "contrib/ucw/lists.h"
#include "knot/zone/node.h"

enum {
	/*! Indication of a zone tree with bi-nodes (two zone_node_t structures allocated for one node). */
	ZONE_TREE_USE_BINODES = (1 << 0),
	/*! If set, from each bi-node in the zone tree, the second zone_node_t is valid. */
	ZONE_TREE_BINO_SECOND = (1 << 1),
};

typedef struct {
	trie_t *trie;
	trie_cow_t *cow; // non-NULL only during zone update
	uint16_t flags;
} zone_tree_t;

/*!
 * \brief Signature of callback for zone apply functions.
 */
typedef int (*zone_tree_apply_cb_t)(zone_node_t *node, void *data);

typedef zone_node_t *(*zone_tree_new_node_cb_t)(const knot_dname_t *dname, void *ctx);

/*!
 * \brief Zone tree iteration context.
 */
typedef struct {
	zone_tree_t *tree;
	trie_it_t *it;
	int binode_second;

	zone_tree_t *next_tree;
	knot_dname_t *sub_root;
} zone_tree_it_t;

typedef struct {
	zone_node_t **nodes;
	size_t total;
	size_t current;
	bool incl_del;
} zone_tree_delsafe_it_t;

/*!
 * \brief Creates the zone tree.
 *
 * \return created zone tree structure.
 */
zone_tree_t *zone_tree_create(bool use_binodes);

zone_tree_t *zone_tree_cow(zone_tree_t *from);

/*!
 * \brief Create a clone of existing zone_tree.
 *
 * \note Copies only the trie, not individual nodes.
 *
 * \warning Don't use COW in the duplicate.
 */
zone_tree_t *zone_tree_shallow_copy(zone_tree_t *from);

/*!
 * \brief Return number of nodes in the zone tree.
 *
 * \param tree Zone tree.
 *
 * \return number of nodes in tree.
 */
inline static size_t zone_tree_count(const zone_tree_t *tree)
{
	if (tree == NULL || tree->trie == NULL) {
		return 0;
	}

	return trie_weight(tree->trie);
}

/*!
 * \brief Checks if the zone tree is empty.
 *
 * \param tree Zone tree to check.
 *
 * \return Nonzero if the zone tree is empty.
 */
inline static bool zone_tree_is_empty(const zone_tree_t *tree)
{
	return zone_tree_count(tree) == 0;
}

inline static zone_node_t *zone_tree_fix_get(zone_node_t *node, const zone_tree_t *tree)
{
	assert(((node->flags & NODE_FLAGS_BINODE) ? 1 : 0) == ((tree->flags & ZONE_TREE_USE_BINODES) ? 1 : 0));
	assert((tree->flags & ZONE_TREE_USE_BINODES) || !(tree->flags & ZONE_TREE_BINO_SECOND));
	return binode_node(node, (tree->flags & ZONE_TREE_BINO_SECOND));
}

inline static zone_node_t *node_new_for_tree(const knot_dname_t *owner, const zone_tree_t *tree, knot_mm_t *mm)
{
	assert((tree->flags & ZONE_TREE_USE_BINODES) || !(tree->flags & ZONE_TREE_BINO_SECOND));
	return node_new(owner, (tree->flags & ZONE_TREE_USE_BINODES), (tree->flags & ZONE_TREE_BINO_SECOND), mm);
}

/*!
 * \brief Inserts the given node into the zone tree.
 *
 * \param tree Zone tree to insert the node into.
 * \param node Node to insert. If it's binode, the pointer will be adjusted to correct node.
 *
 * \retval KNOT_EOK
 * \retval KNOT_EINVAL
 * \retval KNOT_ENOMEM
 */
int zone_tree_insert(zone_tree_t *tree, zone_node_t **node);

/*!
 * \brief Insert a node together with its parents (iteratively node->parent).
 *
 * \param tree   Zone tree to insert into.
 * \param node   Node to be inserted with parents.
 * \param without_parents   Actually, insert it without parents.
 *
 * \return KNOT_E*
 */
int zone_tree_insert_with_parents(zone_tree_t *tree, zone_node_t *node, bool without_parents);

/*!
 * \brief Finds node with the given owner in the zone tree.
 *
 * \param tree Zone tree to search in.
 * \param owner Owner of the node to find.
 *
 * \retval Found node or NULL.
 */
zone_node_t *zone_tree_get(zone_tree_t *tree, const knot_dname_t *owner);

/*!
 * \brief Tries to find the given domain name in the zone tree and returns the
 *        associated node and previous node in canonical order.
 *
 * \param tree Zone to search in.
 * \param owner Owner of the node to find.
 * \param found Found node.
 * \param previous Previous node in canonical order (i.e. the one directly
 *                 preceding \a owner in canonical order, regardless if the name
 *                 is in the zone or not).
 *
 * \retval > 0 if the domain name was found. In such case \a found holds the
 *             zone node with \a owner as its owner.
 *             \a previous is set properly.
 * \retval 0 if the domain name was not found. \a found may hold any (or none)
 *           node. \a previous is set properly.
 * \retval KNOT_EINVAL
 * \retval KNOT_ENOMEM
 */
int zone_tree_get_less_or_equal(zone_tree_t *tree,
                                const knot_dname_t *owner,
                                zone_node_t **found,
                                zone_node_t **previous);

/*!
 * \brief Remove a node from a tree with no checks.
 *
 * \param tree  The tree to remove from.
 * \param owner The node to remove.
 */
void zone_tree_remove_node(zone_tree_t *tree, const knot_dname_t *owner);

/*!
 * \brief Create a node in zone tree if not already exists, and also all parent nodes.
 *
 * \param tree         Zone tree to insert into.
 * \param apex         Zone contents apex node.
 * \param dname        Name of the node to be added.
 * \param new_cb       Callback for allocating new node.
 * \param new_cb_ctx   Context to be passed to allocating callback.
 * \param new_node     Output: pointer on added (or existing) node with specified dname.
 *
 * \return KNOT_E*
 */
int zone_tree_add_node(zone_tree_t *tree, zone_node_t *apex, const knot_dname_t *dname,
                       zone_tree_new_node_cb_t new_cb, void *new_cb_ctx, zone_node_t **new_node);

/*!
 * \brief Remove a node in zone tree, removing also empty parents.
 *
 * \param tree          Zone tree to remove from.
 * \param node          Node to be removed.
 * \param free_deleted  Indication to free node.
 *
 * \return KNOT_E*
 */
int zone_tree_del_node(zone_tree_t *tree, zone_node_t *node, bool free_deleted);

/*!
 * \brief Applies the given function to each node in the zone in order.
 *
 * \param tree Zone tree to apply the function to.
 * \param function Function to be applied to each node of the zone.
 * \param data Arbitrary data to be passed to the function.
 *
 * \retval KNOT_EOK
 * \retval KNOT_EINVAL
 */
int zone_tree_apply(zone_tree_t *tree, zone_tree_apply_cb_t function, void *data);

/*!
 * \brief Applies given function to each node in a subtree.
 *
 * \param tree        Zone tree.
 * \param sub_root    Name denoting the subtree.
 * \param excl_root   Exclude the subtree root.
 * \param function    Callback to be applied.
 * \param data        Callback context.
 *
 * \return KNOT_E*
 */
int zone_tree_sub_apply(zone_tree_t *tree, const knot_dname_t *sub_root,
                        bool excl_root, zone_tree_apply_cb_t function, void *data);

/*!
 * \brief Start zone tree iteration.
 *
 * \param tree   Zone tree to iterate over.
 * \param it     Out: iteration context. It shall be zeroed before.
 *
 * \return KNOT_OK, KNOT_ENOMEM
 */
int zone_tree_it_begin(zone_tree_t *tree, zone_tree_it_t *it);

/*!
 * \brief Start iteration over a subtree.
 *
 * \param tree        Zone tree to iterate in.
 * \param sub_root    Iterate over node of this name and all children.
 * \param it          Out: iteration context, shall be zeroed before.
 *
 * \return KNOT_E*
 */
int zone_tree_it_sub_begin(zone_tree_t *tree, const knot_dname_t *sub_root,
                           zone_tree_it_t *it);

/*!
 * \brief Start iteration of two zone trees.
 *
 * This is useful e.g. for iteration over normal and NSEC3 nodes.
 *
 * \param first    First tree to be iterated over.
 * \param second   Second tree to be iterated over.
 * \param it       Out: iteration context. It shall be zeroed before.
 *
 * \return KNOT_OK, KNOT_ENOMEM
 */
int zone_tree_it_double_begin(zone_tree_t *first, zone_tree_t *second, zone_tree_it_t *it);

/*!
 * \brief Return true iff iteration is finished.
 *
 * \note The iteration context needs to be freed afterwards nevertheless.
 */
bool zone_tree_it_finished(zone_tree_it_t *it);

/*!
 * \brief Return the node, zone iteration is currently pointing at.
 *
 * \note Don't call this when zone_tree_it_finished.
 */
zone_node_t *zone_tree_it_val(zone_tree_it_t *it);

/*!
 * \brief Remove from zone tree the node that iteration is pointing at.
 *
 * \note This doesn't free the node.
 */
void zone_tree_it_del(zone_tree_it_t *it);

/*!
 * \brief Move the iteration to next node.
 */
void zone_tree_it_next(zone_tree_it_t *it);

/*!
 * \brief Free zone iteration context.
 */
void zone_tree_it_free(zone_tree_it_t *it);

/*!
 * \brief Zone tree iteration allowing tree changes.
 *
 * The semantics is the same like for normal iteration.
 * The set of iterated nodes is according to zone tree state on the beginning.
 */
int zone_tree_delsafe_it_begin(zone_tree_t *tree, zone_tree_delsafe_it_t *it, bool include_deleted);
bool zone_tree_delsafe_it_finished(zone_tree_delsafe_it_t *it);
void zone_tree_delsafe_it_restart(zone_tree_delsafe_it_t *it);
zone_node_t *zone_tree_delsafe_it_val(zone_tree_delsafe_it_t *it);
void zone_tree_delsafe_it_next(zone_tree_delsafe_it_t *it);
void zone_tree_delsafe_it_free(zone_tree_delsafe_it_t *it);

/*!
 * \brief Merge all nodes from 'what' to 'into'.
 *
 * \param into  Zone tree to be inserted into..
 * \param what  ...all nodes from this one.
 *
 * \return KNOT_E*
 */
int zone_tree_merge(zone_tree_t *into, zone_tree_t *what);

/*!
 * \brief Unify all bi-nodes in specified trees.
 */
void zone_trees_unify_binodes(zone_tree_t *nodes, zone_tree_t *nsec3_nodes, bool free_deleted);

/*!
 * \brief Destroys the zone tree, not touching the saved data.
 *
 * \param tree Zone tree to be destroyed.
 */
void zone_tree_free(zone_tree_t **tree);