/* Copyright (C) 2019 CZ.NIC, z.s.p.o. Copyright (C) 2018 Tony Finch 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 . */ #pragma once #include #include #include "libknot/mm_ctx.h" /*! * \brief Native API of QP-tries: * * - keys are uint8_t strings, not necessarily zero-terminated, * the structure copies the contents of the passed keys * - values are void* pointers, typically you get an ephemeral pointer to it * - key lengths are limited by 2^32-1 ATM */ /*! \brief Element value. */ typedef void* trie_val_t; /*! \brief Key for indexing tries. Sign could be flipped easily. */ typedef uint8_t trie_key_t; /*! \brief Opaque structure holding a QP-trie. */ typedef struct trie trie_t; /*! \brief Opaque type for holding a QP-trie iterator. */ typedef struct trie_it trie_it_t; /*! \brief Callback for cloning trie values. */ typedef trie_val_t (*trie_dup_cb)(const trie_val_t val, knot_mm_t *mm); /*! \brief Callback for performing actions on a trie leaf * * Used during copy-on-write transactions * * \param val The value of the element to be altered * \param key The key of the element to be altered * \param len The length of key * \param d Additional user data */ typedef void trie_cb(trie_val_t val, const trie_key_t *key, size_t len, void *d); /*! \brief Opaque type for holding the copy-on-write state for a QP-trie. */ typedef struct trie_cow trie_cow_t; /*! \brief Create a trie instance. */ trie_t* trie_create(knot_mm_t *mm); /*! \brief Free a trie instance. */ void trie_free(trie_t *tbl); /*! \brief Clear a trie instance (make it empty). */ void trie_clear(trie_t *tbl); /*! \brief Create a clone of existing trie. */ trie_t* trie_dup(const trie_t *orig, trie_dup_cb dup_cb, knot_mm_t *mm); /*! \brief Return the number of keys in the trie. */ size_t trie_weight(const trie_t *tbl); /*! \brief Search the trie, returning NULL on failure. */ trie_val_t* trie_get_try(trie_t *tbl, const trie_key_t *key, uint32_t len); /*! \brief Search the trie including DNS wildcard semantics, returning NULL on failure. * * \note We assume the key is in knot_dname_lf() format, i.e. labels are ordered * from root to leaf and separated by zero bytes (and no other zeros are allowed). * \note Beware that DNS wildcard matching is not exactly what normal people would expect. */ trie_val_t* trie_get_try_wildcard(trie_t *tbl, const trie_key_t *key, uint32_t len); /*! \brief Search the trie, inserting NULL trie_val_t on failure. */ trie_val_t* trie_get_ins(trie_t *tbl, const trie_key_t *key, uint32_t len); /*! * \brief Search for less-or-equal element. * * \param tbl Trie. * \param key Searched key. * \param len Key length. * \param val (optional) Value found; it will be set to NULL if not found or errored. * \return KNOT_EOK for exact match, 1 for previous, KNOT_ENOENT for not-found, * or KNOT_E*. */ int trie_get_leq(trie_t *tbl, const trie_key_t *key, uint32_t len, trie_val_t **val); /*! * \brief Apply a function to every trie_val_t, in order. * * \return KNOT_EOK if success or KNOT_E* if error. */ int trie_apply(trie_t *tbl, int (*f)(trie_val_t *, void *), void *d); /*! * \brief Remove an item, returning KNOT_EOK if succeeded or KNOT_ENOENT if not found. * * If val!=NULL and deletion succeeded, the deleted value is set. */ int trie_del(trie_t *tbl, const trie_key_t *key, uint32_t len, trie_val_t *val); /*! \brief Create a new iterator pointing to the first element (if any). * * trie_it_* functions deal with these iterators capable of walking and jumping * over the trie. Note that any modification to key-set stored by the trie * will in general invalidate all iterators and you will need to begin anew. * (It won't be detected - you may end up reading freed memory, etc.) */ trie_it_t* trie_it_begin(trie_t *tbl); /*! \brief Test if the iterator has gone "past the end" (and points nowhere). */ bool trie_it_finished(trie_it_t *it); /*! \brief Free any resources of the iterator. It's OK to call it on NULL. */ void trie_it_free(trie_it_t *it); /*! \brief Copy the iterator. See the warning in trie_it_begin(). */ trie_it_t *trie_it_clone(const trie_it_t *it); /*! * \brief Return pointer to the key of the current element. * * \note The len is uint32_t internally but size_t is better for our usage * as it is without an additional type conversion. */ const trie_key_t* trie_it_key(trie_it_t *it, size_t *len); /*! \brief Return pointer to the value of the current element (writable). */ trie_val_t* trie_it_val(trie_it_t *it); /*! * \brief Advance the iterator to the next element. * * Iteration is in ascending lexicographical order. * In particular, the empty string would be considered as the very first. * * \TODO: in most iterator operations, ENOMEM is very unlikely * but it leads to a _finished() iterator (silently). * Perhaps the functions should simply return KNOT_E* */ void trie_it_next(trie_it_t *it); /*! \brief Advance the iterator to the previous element. See trie_it_next(). */ void trie_it_prev(trie_it_t *it); /*! \brief Advance iterator to the next element, looping to first after last. */ void trie_it_next_loop(trie_it_t *it); /*! \brief Advance iterator to the previous element, looping to last after first. */ void trie_it_prev_loop(trie_it_t *it); /*! \brief Advance iterator to the next element while ignoring the subtree. * * \note Another formulation: skip keys that are prefixed by the current key. * \TODO: name, maybe _unprefixed? The thing is that in the "subtree" meaning * doesn't correspond to how the pointers go in the implementation, * but we may not care much for implementation in the API... */ void trie_it_next_nosub(trie_it_t *it); /*! \brief Advance iterator to the longest prefix of the current key. * * \TODO: name, maybe _prefix? Arguments similar to _nosub vs. _unprefixed. */ void trie_it_parent(trie_it_t *it); /*! \brief trie_get_leq() but with an iterator. */ int trie_it_get_leq(trie_it_t *it, const trie_key_t *key, uint32_t len); /*! \brief Remove the current element. The iterator will get trie_it_finished() */ void trie_it_del(trie_it_t *it); /*! \brief Start a COW transaction * * A copy-on-write transaction starts by obtaining a write lock (in * your application code) followed by a call to trie_cow(). This * creates a shared clone of the trie and saves both old and new roots * in the COW context. * * During the COW transaction, you call trie_cow_ins() or * trie_cow_del() as necessary. These calls ensure that the relevant * parts of the (new) trie are copied so that they can be modified * freely. * * Your trie_val_t objects must be able to distinguish their * reachability, either shared, or old-only, or new-only. Before a COW * transaction the reachability of your objects is indeterminate. * During a transaction, any trie_val_t objects that might be affected * (because they are adjacent to a trie_get_cow() or trie_del_cow()) * are first marked as shared using the callback you pass to * trie_cow(). * * When the transaction is complete, to commit, call trie_cow_new() to * get the new root, swap the old and new trie roots (e.g. with * rcu_xchg_pointer()), wait for readers to finish with the old trie * (e.g. using synchronize_rcu()), then call trie_cow_commit(). For a * rollback, you can just call trie_cow_rollback() without waiting * since that doesn't conflict with readers. After trie_cow_commit() * or trie_cow_rollback() have finished, you can release your write * lock. * * Concurrent reading of the old trie is allowed during a transaction * provided that it is known when all readers have finished with the * old version, e.g. using rcu_read_lock() and rcu_read_unlock(). * There must be only one write transaction at a time. * * \param old the old trie * \param mark_shared callback to mark a leaf as shared (can be NULL) * \param d extra data for the callback * \return a pointer to a COW context, * or NULL if there was a failure */ trie_cow_t* trie_cow(trie_t *old, trie_cb *mark_shared, void *d); /*! \brief get the new trie from a COW context */ trie_t* trie_cow_new(trie_cow_t *cow); /*! \brief variant of trie_get_ins() for use during COW transactions * * As necessary, this copies path from the root of the trie to the * leaf, so that it is no longer shared. Any leaves adjacent to this * path are marked as shared using the mark_shared callback passed to * trie_cow(). * * It is your responsibility to COW your trie_val_t objects. If you copy an * object you must change the original's reachability from shared to old-only. * New objects (including copies) must have new-only reachability. */ trie_val_t* trie_get_cow(trie_cow_t *cow, const trie_key_t *key, uint32_t len); /*! * \brief variant of trie_del() for use during COW transactions * * The mark_shared callback is invoked as necessary, in the same way * as trie_get_cow(). * * Returns KNOT_EOK if the key was removed or KNOT_ENOENT if not found. * If val!=NULL and deletion succeeded, the *val is set to the deleted * value pointer. */ int trie_del_cow(trie_cow_t *cow, const trie_key_t *key, uint32_t len, trie_val_t *val); /*! \brief clean up the old trie after committing a COW transaction * * Your callback is invoked for any trie_val_t objects that might need * cleaning up; you must free any objects you have marked as old-only * and retain objects with shared reachability. * * \note The callback can be NULL. * * The cow object is free()d, and the new trie root is returned. */ trie_t* trie_cow_commit(trie_cow_t *cow, trie_cb *cb, void *d); /*! \brief clean up the new trie after rolling back a COW transaction * * Your callback is invoked for any trie_val_t objects that might need * cleaning up; you must free any objects you have marked as new-only * and retain objects with shared reachability. * * \note The callback can be NULL. * * The cow object is free()d, and the old trie root is returned. */ trie_t* trie_cow_rollback(trie_cow_t *cow, trie_cb *cb, void *d);