UT_ARTMap.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        UT_ARTMap.h
 *
 * COMMENTS: Implementation of an Adaptive Radix Tree
 *
 * UT_ARTMap<entry> map;
 * entry item;
 *
 * map[id] = item; // insert or replace
 * 
 * item = map[id]; // find or create new
 *
 * UT_ARTMap<entry>::iterator map_it = map.find(id); // find only
 * if (map_it != map.end())
 *   item = map_it->second;
 *
 * map.erase(id); // remove entry
 *
 * for (auto&& [id, item] : map) // traverse
 * {
 * }
 *
 * map.contains(id); // check existence
 *
 * map.clear(); // clear all entries
 *
 * RELATION TO THE STL:
 *
 * Use UT_ARTMap over all maps WHEN your strings are fairly unique to each other.
 *
 * Reasoning to not use other maps:
 * - Performance for queries is far greater then all other map types.
 * - Does a good job on saving space as it uses the smaller node sizes where possible
 *
 * Reasong to no use UT_ARTMap:
 * - If youre doing more inserting over querying then you'll want to profile first
 *   before using as its performance will be far less then if youre doing mostly queries
 * - If the keys are mostly the same strings (ie the same except the last character)
 *   then theres a performance cost as it needs to check the entire string length
 *   instead of the ideal case where it only needs to check a couple characters
 *   at the beginning.
 *
 * NOTES:
 * - Keys need to be binary-comparible keys and as such UNICODE strings need to
 *   encoded using a third party library like ICU to produce appropriate
 *   unicode sort keys. Unicode decoding is not well defined and as such
 *   normally you would store the unicode string alongside the items data for
 *   proper retrieval of the original unicode string.
 */

#ifndef __UT_ARTMAP_H__
#define __UT_ARTMAP_H__

#include "UT_API.h"

#include "UT_Array.h"
#include "UT_Assert.h"
#include "UT_Debug.h"
#include "UT_Optional.h"
#include "UT_StringHolder.h"
#include "UT_UniquePtr.h"
#include "UT_WorkBuffer.h"

#include <SYS/SYS_Compiler.h>
#include <SYS/SYS_Platform.h>
#include <SYS/SYS_ProcessorDefines.h>

#include <cctype>
#include <variant>

#if defined(__i386__) || defined(__amd64__)
#include <emmintrin.h>
#include <immintrin.h>
#elif defined (_WIN32)
#include <intrin.h>
#endif


#if defined(USE_MEMORY_RESOURCE)
#include <memory_resource>
namespace UT_PMR = std::pmr;
#endif

#if defined(LINUX) || defined(MBSD)
    #if defined(__i386) || defined(__amd64)
        #define SUPPORT_FAST_STR
    #endif
#elif !defined(__clang__) && defined(_M_AMD64)
    #define SUPPORT_FAST_STR
#endif

#define UT_VERIFY_ROOT UT_ASSERT(myRoot && !myRoot->hasValue())

template <typename T>
class UT_ARTMap;
template <typename T>
class UT_ARTNode;

/// Deletor for node types which is mostly used for the memory resource
/// version of this tree.
class UT_ARTNodeDelete
{
public:
    template <typename T>
    void operator()(T* ptr);

private:
};
template <typename T>
using UT_ARTNodePtr = UT_UniquePtr<T, UT_ARTNodeDelete>;

/// Based node type used to store common functionality across node types and
/// to store the item value.
template <typename T>
class UT_ARTNode
{
public:
    using value_type = T;

    explicit UT_ARTNode(
            const UT_StringHolder& key,
            const UT_StringView& prefix
#if defined(USE_MEMORY_RESOURCE)
            , UT_PMR::polymorphic_allocator<UT_ARTNode<T>> alloc
#endif
        )
        : myKey(key)
        , myPrefix(prefix)
        , myValue()
        , myAllowsPartial(false)
#if defined(USE_MEMORY_RESOURCE)
        , myAllocator(alloc)
#endif
    {
    }
    virtual ~UT_ARTNode() = default;
    UT_NON_COPYABLE(UT_ARTNode);

    UT_StringHolder key() const { return myKey; }
    SYS_FORCE_INLINE const value_type* value() const
    {
        if (myValue.has_value())
            return &myValue.value();
        return nullptr;
    }
    template <typename... Args>
    void emplace(Args&&... args)
    {
        myValue.emplace(std::forward<Args>(args)...);
    }
    SYS_FORCE_INLINE value_type* value()
    {
        if (myValue.has_value())
            return &myValue.value();
        return nullptr;
    }
    SYS_FORCE_INLINE bool hasValue() const { return myValue.has_value(); }
    SYS_FORCE_INLINE const UT_StringView& prefix() const { return myPrefix; }
    SYS_FORCE_INLINE bool isLeaf() const
    {
        return myNumChildren == 0;
    }
    virtual bool isFull() const = 0;
    SYS_FORCE_INLINE bool allowsPartial() const { return myAllowsPartial; }
    void setAllowsPartial(bool allow) { myAllowsPartial = allow; }

    virtual const UT_StringHolder& type() const = 0;

    void debug(UT_WorkBuffer& wbuf, unsigned indent = 0) const
    {
        wbuf.append(indent, ' ');
        if (myPrefix)
            wbuf.append(myPrefix);
        else
            wbuf.append("<empty>");
        wbuf.append(' ');
        if (hasValue())
            wbuf.appendFormat("{}", *value());
        else
            wbuf.append("<None>");
        wbuf.append('\n');

        int idx = 0;
        const UT_ARTNode<T>* child = nullptr;
        do
        {
            child = nextChild(idx);
            idx++;
            if (child != nullptr)
            {
                child->debug(wbuf, indent + 1);
            }
        } while (child != nullptr);
    }

    /// Compress the current node and its child. Compression happens when
    /// this node has no value (edge) and its only child has a value. When
    /// this occurs we can move the child up to this node.
    void compress(UT_ARTNode<T>** ref)
    {
        if (myNumChildren == 1)
        {            
            // If this node is not a root and has no value move the child
            // up.
            if (!hasValue())
            {
                UT_ARTNodePtr<UT_ARTNode<T>> stolen
                        = stealChild(ref, 0);
                if (stolen)
                {
                    exint prefix_length = myPrefix.length();
                    myKey = stolen->myKey;
                    myPrefix = UT_StringView(
                            stolen->myPrefix.begin() - prefix_length,
                            stolen->myPrefix.end());
                    myAllowsPartial = stolen->myAllowsPartial;
                    myValue = std::move(stolen->myValue);

                    stolen->moveChildren(ref);
                }
            }
        }
    }

    virtual UT_ARTNode<T>** insertChild(
            UT_ARTNode** ref,
            UT_ARTNodePtr<UT_ARTNode<T>> node)
            = 0;
    virtual UT_ARTNodePtr<UT_ARTNode<T>> stealChild(
            UT_ARTNode** ref,
            UT_ARTNode* child)
            = 0;
    void moveChildren(UT_ARTNode<T>** ref)
    {
        exint node_prefix_length = this->myPrefix.length();

        for (int i = this->myNumChildren; i-- > 0;)
        {
            UT_ARTNodePtr<UT_ARTNode<T>> child = stealChild(ref, i);
            const char* start = child->myPrefix.begin() - node_prefix_length;
            UT_ASSERT(start >= child->myKey.buffer());
            child->myPrefix = UT_StringView(start, child->myPrefix.end());

            (*ref)->insertChild(ref, std::move(child));
        }
    }
    virtual UT_ARTNode<T>* nextChild(int& idx) = 0;
    virtual const UT_ARTNode<T>* nextChild(int& idx) const = 0;
    virtual UT_ARTNodePtr<UT_ARTNode<T>> stealChild(
            UT_ARTNode<T>** ref,
            int idx)
            = 0;

    // Find the max length that both key and node prefix share
    exint getCommonPrefixLength(
            const UT_StringView& key,
            const UT_StringView& node_prefix)
    {
        if (key.isEmpty() || node_prefix.isEmpty())
            return 0;

        exint length = 0;
        const char* k = key.data();
        const char* p = node_prefix.data();
        exint n = std::min(key.length(), node_prefix.length());

#if defined(SUPPORT_FAST_STR) && !defined(ASAN_ENABLED)
        static constexpr exint theMaxSIMDLen = 16;
        const int mode = _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_EACH
                         | _SIDD_LEAST_SIGNIFICANT | _SIDD_NEGATIVE_POLARITY;
        while (n > theMaxSIMDLen)
        {
            const __m128i data = _mm_loadu_si128(
                    reinterpret_cast<const __m128i*>(k));
            const __m128i prefix = _mm_loadu_si128(
                    reinterpret_cast<const __m128i*>(p));

            int check_len = std::min(n, theMaxSIMDLen);
            int res = _mm_cmpestri(data, check_len, prefix, check_len, mode);

            // For some reason if the length of the string is less then the
            // max and the entire string matches it returns 16 instead of
            // the length of the string so we cover that case here
            if (n < 16 && res == 16)
                res = n;

            length += res;

            n -= check_len;

            k += check_len;
            p += check_len;
        }
#endif

        while (n > 0)
        {
            if (*k != *p)
                break;

            length++;
            k++;
            p++;
            n--;
        }
        return length;
    }

    // Find a child that is a partial match to the prefix.
    virtual UT_ARTNode<T>** findPartialPrefixChild(
            const UT_StringView& prefix)
            = 0;

    void moveHeader(UT_ARTNode<T>& move_to)
    {
        move_to.myKey = myKey;
        move_to.myPrefix = myPrefix;
        move_to.myValue = std::move(myValue);
        move_to.myAllowsPartial = myAllowsPartial;
        move_to.myNumChildren = myNumChildren;
    }

#if defined(USE_MEMORY_RESOURCE)
    UT_PMR::polymorphic_allocator<UT_ARTNode<T>> getAllocator()
    {
        return myAllocator;
    }
#endif

    template <typename NodeT>
    UT_ARTNodePtr<NodeT> newNode()
    {
#if defined(USE_MEMORY_RESOURCE)
        UT_PMR::polymorphic_allocator<NodeT> alloc(myAllocator);
        NodeT* node = alloc.allocate(1);
        alloc.construct(node, myKey, myPrefix, alloc);
        UT_ARTNodePtr<NodeT> ptr(node);
        return ptr;
#else
        UT_ARTNodePtr<NodeT> ptr(new NodeT(myKey, myPrefix));
        return ptr;
#endif
    }
    static void destroy(UT_ARTNode<T>* node)
    {
        if (node)
        {
            UT_ARTNodeDelete del;
            del(node);
        }
    }

#if defined(USE_MEMORY_RESOURCE)
    UT_PMR::polymorphic_allocator<UT_ARTNode<T>> myAllocator;
#endif
    UT_StringHolder myKey;
    UT_StringView myPrefix;
    UT_Optional<value_type> myValue;

    // If the node allows for partial matches
    bool myAllowsPartial = false;

    uint8_t myNumChildren = 0;
};

template <typename T>
inline void
UT_ARTNodeDelete::operator()(T* ptr)
{
#if defined(USE_MEMORY_RESOURCE)
    auto alloc = ptr->getAllocator();
    alloc.destroy(ptr);
    alloc.deallocate(ptr, 1);
#else
    delete ptr;
#endif
}

/// Iterator for traversing the adaptive radix tree.
template <typename T>
class UT_ARTIterator
{
public:
    using difference_type = std::ptrdiff_t;
    using value_type = UT_ARTIterator<T>;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using reference = value_type&;
    using const_reference = value_type&;
    using iterator_category = std::forward_iterator_tag;

    UT_ARTIterator() = default;

    bool operator==(const UT_ARTIterator& it) const
    {
        return myCurrent == it.myCurrent;
    }
    bool operator!=(const UT_ARTIterator& it) const
    {
        return !(*this == it);
    }
    const_reference operator*() const { return *this; }
    reference operator*() { return *this; }
    const_pointer operator->() const { return this; }
    pointer operator->() { return this; }

    UT_ARTIterator& operator++()
    {
        if (!myCurrent)
            return *this;

        findNextValue_();

        return *this;
    }

    UT_ARTIterator operator++(int)
    {
        UT_ARTIterator tmp = *this;
        ++(*this);
        return tmp;
    }

    bool hasValue() const { return myCurrent && myCurrent->hasValue(); }

    const T& value() const { return *myCurrent->value(); }
    T& value() { return *myCurrent->value(); }

    UT_StringHolder key() const { return myCurrent->key(); }

private:
    friend class UT_ARTMap<T>;

    explicit UT_ARTIterator(UT_ARTNode<T>* node) : myCurrent(node)
    {
        // If the given value is not a value node skip to the next value node.
        // Note that this should only be the case when the node is a root node.
        if (myCurrent && !myCurrent->hasValue())
            findNextValue_();
    }

    void findNextValue_()
    {
        if (!myCurrent)
            return;

        bool has_seen = false;
        do
        {
            has_seen = false;
            UT_ARTNode<T>* child = myCurrent->nextChild(myIndex);
            if (child)
            {
                myIndex++;
                myNodeStack.emplace_back(std::make_pair(myCurrent, myIndex));
                myCurrent = child;
                myIndex = 0;
            }
            else if (!myNodeStack.isEmpty())
            {
                auto&& [node, index] = myNodeStack.last();
                myNodeStack.removeLast();

                // we have already seen this node so we need another iteration
                // to find the next unseen value.
                has_seen = true;
                myCurrent = node;
                myIndex = index;
            }
            else
            {
                myCurrent = nullptr;
                myIndex = 0;
            }
        } while (myCurrent != nullptr && (has_seen || !myCurrent->hasValue()));

        return;
    }

    UT_Array<std::pair<UT_ARTNode<T>*, int>> myNodeStack;
    UT_ARTNode<T>* myCurrent = nullptr;
    int myIndex = 0;
};

/// The smallest (also known as base node) node with 4 max children.
template <typename T>
class UT_ARTNode4 final : public UT_ARTNode<T>
{
public:
    using parent_t = UT_ARTNode<T>;
    using parent_ptr_t = UT_ARTNodePtr<parent_t>;

#if defined(USE_MEMORY_RESOURCE)
    UT_ARTNode4(
            const UT_StringHolder& key,
            UT_StringView prefix
            , UT_PMR::polymorphic_allocator<UT_ARTNode4<T>> alloc)
        : UT_ARTNode<T>(key, prefix, alloc)
    {
    }
#else
    UT_ARTNode4(const UT_StringHolder& key,
            UT_StringView prefix) :
        UT_ARTNode<T>(key, prefix)
    {}
#endif
    UT_NON_COPYABLE(UT_ARTNode4);
    ~UT_ARTNode4() override
    {
        parent_t::destroy(myChildren[0]);
        parent_t::destroy(myChildren[1]);
        parent_t::destroy(myChildren[2]);
        parent_t::destroy(myChildren[3]);
    }

    const UT_StringHolder& type() const override
    {
        static constexpr UT_StringLit theType("node4");
        return theType.asHolder();
    }
    bool isFull() const override;
    parent_t** insertChild(
            parent_t** ref,
            parent_ptr_t child) override;
    parent_ptr_t stealChild(
            parent_t** ref,
            parent_t* child) override;
    parent_t** findPartialPrefixChild(
            const UT_StringView& prefix) override;
    parent_t* nextChild(int& index) override;
    const parent_t* nextChild(int& index) const override;
    parent_ptr_t stealChild(parent_t** ref, int idx) override;

    unsigned char myChildKeys[4] = {0,0,0,0};
    parent_t* myChildren[4] = {nullptr, nullptr, nullptr, nullptr};
};

/// The middle sized node with 16 max children.
template <typename T>
class UT_ARTNode16 final : public UT_ARTNode<T>
{
public:
    using parent_t = UT_ARTNode<T>;
    using parent_ptr_t = UT_ARTNodePtr<parent_t>;

#if defined(USE_MEMORY_RESOURCE)
    UT_ARTNode16(
            const UT_StringHolder& key,
            UT_StringView prefix,
            UT_PMR::polymorphic_allocator<UT_ARTNode4<T>> alloc)
        : UT_ARTNode<T>(key, prefix, alloc)
#else
    UT_ARTNode16(const UT_StringHolder& key, UT_StringView prefix)
        : UT_ARTNode<T>(key, prefix)
#endif
    {
        memset(myChildKeys, 0, 16);
    }
    UT_NON_COPYABLE(UT_ARTNode16);
    ~UT_ARTNode16() override
    {
        for (int i = 16; i-->0; )
            parent_t::destroy(myChildren[i]);
    }

    const UT_StringHolder& type() const override
    {
        static constexpr UT_StringLit theType("node16");
        return theType.asHolder();
    }
    bool isFull() const override;
    parent_t** insertChild(
            parent_t** ref,
            parent_ptr_t child) override;
    parent_ptr_t stealChild(
            parent_t** ref,
            parent_t* child) override;
    parent_t** findPartialPrefixChild(
            const UT_StringView& prefix) override;
    parent_t* nextChild(int& index) override;
    const parent_t* nextChild(int& index) const override;
    parent_ptr_t stealChild(parent_t** ref, int idx)
            override;

    int prefixToIndex_(char c) const
    {
        unsigned mask = (1 << this->myNumChildren) - 1;
        unsigned bitfield = 0;
#if defined(__i386) || defined(__amd64)
        // SSE2 instructions so shouldnt need to check processor...
        __m128i key_vec = _mm_set1_epi8(c);
        __m128i results = _mm_cmpeq_epi8(
                key_vec, _mm_loadu_si128((__m128i*)myChildKeys));
        bitfield = _mm_movemask_epi8(results) & mask;
#else
        for (int i = 0; i < 16; ++i)
        {
            if (myChildKeys[i] == c)
                bitfield |= (1 << i);
        }

        bitfield &= mask;
#endif

        if (bitfield)
        {
#if !defined(_WIN32)
            return __builtin_ctz(bitfield);
#else
            return _tzcnt_u32(bitfield);
#endif
        }
        return -1;
    }

    unsigned char myChildKeys[16];
    parent_t* myChildren[16] = {};
};

/// The second largest node size with 48 max children.
template <typename T>
class UT_ARTNode48 final : public UT_ARTNode<T>
{
public:
    using parent_t = UT_ARTNode<T>;
    using parent_ptr_t = UT_ARTNodePtr<parent_t>;

#if defined(USE_MEMORY_RESOURCE)
    UT_ARTNode48(
            const UT_StringHolder& key,
            UT_StringView prefix,
            UT_PMR::polymorphic_allocator<UT_ARTNode4<T>> alloc)
        : UT_ARTNode<T>(key, prefix, alloc)
#else
    UT_ARTNode48(const UT_StringHolder& key, UT_StringView prefix)
        : UT_ARTNode<T>(key, prefix)
#endif
    {
        memset(myChildKeys, 0, 256);
    }
    UT_NON_COPYABLE(UT_ARTNode48);
    ~UT_ARTNode48() override
    {
        for (int i = 48; i-->0; )
            parent_t::destroy(myChildren[i]);
    }
    const UT_StringHolder& type() const override
    {
        static constexpr UT_StringLit theType("node48");
        return theType.asHolder();
    }
    bool isFull() const override;
    parent_t** insertChild(
            parent_t** ref,
            parent_ptr_t child) override;
    parent_ptr_t stealChild(
            parent_t** ref,
            parent_t* child) override;
    parent_t** findPartialPrefixChild(
            const UT_StringView& prefix) override;
    parent_t* nextChild(int& index) override;
    const parent_t* nextChild(int& index) const override;
    parent_ptr_t stealChild(parent_t** ref, int idx)
            override;

    unsigned char myChildKeys[256];
    parent_t* myChildren[48] = {};
};

/// The largest node size in the art map. The 256 node has at most 256 children
template <typename T>
class UT_ARTNode256 final : public UT_ARTNode<T>
{
public:
    using parent_t = UT_ARTNode<T>;
    using parent_ptr_t = UT_ARTNodePtr<parent_t>;

#if defined(USE_MEMORY_RESOURCE)
    UT_ARTNode256(
            const UT_StringHolder& key,
            UT_StringView prefix,
            UT_PMR::polymorphic_allocator<UT_ARTNode4<T>> alloc)
        : UT_ARTNode<T>(key, prefix, alloc)
#else
    UT_ARTNode256(const UT_StringHolder& key, UT_StringView prefix)
        : UT_ARTNode<T>(key, prefix)
#endif
    {
    }
    UT_NON_COPYABLE(UT_ARTNode256);
    ~UT_ARTNode256() override
    {
        for (int i = 256; i-->0; )
            parent_t::destroy(myChildren[i]);
    }

    const UT_StringHolder& type() const override
    {
        static constexpr UT_StringLit theType("node256");
        return theType.asHolder();
    }
    bool isFull() const override;
    parent_t** insertChild(
            parent_t** ref,
            parent_ptr_t child) override;
    parent_ptr_t stealChild(
            parent_t** ref,
            parent_t* child) override;
    parent_t** findPartialPrefixChild(
            const UT_StringView& prefix) override;
    parent_t* nextChild(int& index) override;
    const parent_t* nextChild(int& index) const override;
    parent_ptr_t stealChild(parent_t** ref, int idx)
            override;

    parent_t* myChildren[256] = {};
};

/// A basic adaptive radix tree implementation using node4, node16, node48,
/// and node256 for space and performance.
template <typename T>
class UT_ARTMap
{
private:
    using Node = UT_ARTNode<T>;
    using StartNode = UT_ARTNode4<T>;

public:
    using iterator = UT_ARTIterator<T>;
    using key_type = UT_StringHolder;
    using mapped_type = T;

    /// Initialize an empty map.
#if defined(USE_MEMORY_RESOURCE)
    UT_ARTMap() :
        UT_ARTMap(UT_PMR::get_default_resource())
    {
    }
    explicit UT_ARTMap(UT_PMR::memory_resource* resource) :
        myAllocator(resource)
#else
    UT_ARTMap()
#endif
    {
        myRoot = createBaseNode(
                         UT_StringHolder::theEmptyString, UT_StringView())
                         .release();
    }
    UT_NON_COPYABLE(UT_ARTMap);
    ~UT_ARTMap()
    {
#if defined(USE_MEMORY_RESOURCE)
        UT_PMR::polymorphic_allocator<Node> alloc(myAllocator);
        alloc.destroy(myRoot);
        alloc.deallocate(myRoot, 1);
#else
        delete myRoot;
#endif
    }

    /// Insert a node with the additional option to specify if partial matches
    /// are allowed for this item. If you're using UT_ARTMap like a traditional
    /// map then partial matches arent something that needs to be considered.
    std::pair<iterator, bool> insert(
            const UT_StringHolder& name,
            const T& data,
            bool allow_partial = false)
    {
        return insert_(name, allow_partial, data);
    }

    /// Insert a node by moving its values instead of copying it. This function
    /// additionally supports specifying if partial matches are allowed for this
    /// item. If you're using UT_ARTMap like a traditional map then partial
    /// matches arent something that needs to be considered.
    std::pair<iterator, bool> insert(
            const UT_StringHolder& name,
            T&& value,
            bool allow_partial = false)
    {
        return insert_(name, allow_partial, value);
    }

    /// Insert a node into the tree by emplacing its value. This function does
    /// not allow specifying partial matches as its meant to be equivalent to
    /// STL maps.
    template <typename... Args>
    std::pair<iterator, bool> emplace(
            const UT_StringHolder& name,
            Args&&... args)
    {
        return insert_(
                name, /*allows_partial=*/false, std::forward<Args>(args)...);
    }

    /// Lookup an existing item based on the key. If no item is found a
    /// default constructible item is placed into the tree. This function
    /// does not support allowing partial matches.
    typename std::enable_if_t<std::is_default_constructible_v<T>, T&>
    operator[](const UT_StringHolder& key)
    {
        auto&& [it, inserted] = insert_(key, /*allows_partial=*/false);

        UT_ASSERT(it.myCurrent != nullptr);
        if (it.myCurrent && inserted)
        {
            it.myCurrent->emplace();
        }

        return it.value();
    }
 
    /// Lookup an existing item based on the key. If no item is found a
    /// default constructible item is placed into the tree. This function
    /// does not support allowing partial matches.   
    typename std::enable_if_t<std::is_default_constructible_v<T>, T&>
    operator[](UT_StringHolder&& key)
    {
        auto&& [it, inserted] = insert_(key, /*allows_partial=*/false);

        UT_ASSERT(it.myCurrent != nullptr);
        if (it.myCurrent && inserted)
        {
            it.myCurrent->emplace();
        }

        return it.value();
    }

    /// Find the node based on the provided prefix.
    SYS_NO_DISCARD_RESULT iterator
    find(UT_StringView prefix) const
    {
        UT_VERIFY_ROOT;
        Node* child = SYSconst_cast(this)->myRoot;
        Node* last_partial = nullptr;

        while (!prefix.isEmpty() && child != nullptr)
        {
            Node** found = child->findPartialPrefixChild(prefix);
            if (found && *found)
            {
                UT_StringView found_prefix((*found)->prefix());
                exint common_length = child->getCommonPrefixLength(
                        prefix, found_prefix);
                if (common_length == found_prefix.length())
                {
                    prefix.removePrefix(common_length);

                    // If we have found the last node but the common length is
                    // not an exact match then we have not found a node.
                    if (prefix.isEmpty()
                        && common_length != found_prefix.length())
                    {
                        child = nullptr;
                        break;
                    }

                    child = *found;
                    // If this child allows for partial matches then update the
                    // last partial node we found.
                    if (child->allowsPartial())
                        last_partial = child;

                    continue;
                }
                else
                {
                    child = nullptr;
                    break;
                }
            }
            else
            {
                child = nullptr;
                break;
            }
        }

        if (child && child->hasValue())
            return iterator(child);
        // If we didnt find a child that matches check if our traversal came
        // across a node that allows for partial matches. If we found one
        // then return this node instead of reporting nothing found.
        else if (last_partial != nullptr && last_partial->hasValue())
            return iterator(last_partial);
        return end();
    }

    /// Check if the tree contains the provided string
    SYS_NO_DISCARD_RESULT bool contains(const UT_StringHolder& prefix) const
    {
        return find(prefix) != end();
    }

    /// Write out the tree into the work buffer. This is pretty printed.
    void debug(UT_WorkBuffer& wbuf) const
    {
        wbuf.clear();

        UT_VERIFY_ROOT;
        myRoot->debug(wbuf, 0);
    }
    /// Erase a given entry based on the prefix. Returns true if the item was
    /// removed from the tree.
    bool erase(const UT_StringRef& prefix)
    {
        return doErase_(prefix);
    }

    /// Clear out the tree
    void clear()
    {
#if defined(USE_MEMORY_RESOURCE)
        UT_PMR::polymorphic_allocator<Node> alloc(myAllocator);
        alloc.destroy(myRoot);
        alloc.deallocate(myRoot, 1);

#else
        delete myRoot;
#endif
        myRoot = createBaseNode(
                UT_StringHolder::theEmptyString, UT_StringView()).release();
    }

    /// Returns true if the map has no items currently inserted.
    SYS_NO_DISCARD_RESULT bool isEmpty() const
    {
        return myRoot->childCount();
    }

    /// Returns the beginning of an iterator used to traverse the full tree.
    using const_iterator = const iterator;
    SYS_NO_DISCARD_RESULT const_iterator begin() const
    {
        auto me = SYSconst_cast(this);
        return iterator(me->myRoot);
    }
    /// Returns the beginning of an iterator used to traverse the full tree.
    SYS_NO_DISCARD_RESULT iterator begin()
    {
        return iterator(myRoot);
    }
    /// Returns the end of an iterator used with begin() to traverse the full
    /// tree.
    SYS_NO_DISCARD_RESULT const_iterator end() const { return iterator(); }
    /// Returns the end of an iterator used with begin() to traverse the full
    /// tree.
    SYS_NO_DISCARD_RESULT iterator end() { return iterator(); }
    /// Returns the end of an iterator used with begin() to traverse the full
    /// tree.
    SYS_NO_DISCARD_RESULT const_iterator cbegin() const { return begin(); }
    /// Returns the end of an iterator used with begin() to traverse the full
    /// tree.
    SYS_NO_DISCARD_RESULT const_iterator cend() const { return end(); }

private:
    // Internal function to initiate inserting an item into the tree.
    template <typename... Args>
    std::pair<iterator, bool> insert_(
            const UT_StringHolder& name,
            bool allows_partial,
            Args&&... args)
    {
        if (name.isEmpty())
            return std::make_pair(end(), false);

        bool inserted = false;
        Node* node = doInsert_(name, inserted);

        UT_ASSERT((inserted && node != nullptr) || !inserted);
        if (node && inserted)
        {
            node->emplace(std::forward<Args>(args)...);
            node->setAllowsPartial(allows_partial);
        }
        return std::make_pair(iterator(node), inserted);
    }

    /// Start the process of erasing a found item in the tree.
    bool doErase_(const UT_StringRef& str)
    {
        if (str.isEmpty())
            return false;

        UT_VERIFY_ROOT;
        Node** current = &myRoot;

        bool removed = false;
        UT_StringView prefix(str);
        while (!removed && current && prefix)
        {
            Node** node = (*current)->findPartialPrefixChild(prefix);

            // If no child matches the prefix then theres nothing to do.
            if (node == nullptr)
            {
                return false;
            }

            exint common_length = (*current)->getCommonPrefixLength(
                    prefix, (*node)->myPrefix);

            if (common_length == prefix.length())
            {
                // If we found the node but the found node does not have a value
                // it means its an edge so we dont delete it.
                if (!(*node)->hasValue())
                    return false;

                removed = true;

                if ((*node)->isLeaf())
                {
                    auto stolen = (*current)->stealChild(current, *node);
                }
                else
                {
                    UT_ARTNodePtr<Node> removed_node = (*current)->stealChild(
                            current, *node);
                    removed_node->moveChildren(current);
                }

                if ((*current) != myRoot)
                    (*current)->compress(current);
            }
            else
            {
                prefix.removePrefix(common_length);
                current = node;
            }
        }

        return removed;
    }

    /// Create a node4 also known as a based node.
    UT_ARTNodePtr<Node> createBaseNode(
            const UT_StringHolder& key,
            const UT_StringView& prefix)
    {
#if defined(USE_MEMORY_RESOURCE)
        UT_PMR::polymorphic_allocator<UT_ARTNode4<T>> alloc(myAllocator);
        UT_ARTNode4<T>* node = alloc.allocate(1);
        alloc.construct(node, key, prefix, alloc);
        UT_ARTNodePtr<UT_ARTNode4<T>> ptr(node);
        return ptr;
#else
        UT_ARTNodePtr<UT_ARTNode4<T>> ptr(new UT_ARTNode4<T>(key, prefix));
        return ptr;
#endif
    }

    /// Start the process of finding the insertion node and inserting the new
    /// node. If necessary the tree rebalences itself and updates the node
    /// size accordingly.
    Node* doInsert_(const UT_StringHolder& key, bool& inserted)
    {
        UT_StringView prefix(key);
        UT_ASSERT(key.length() > 0);
        UT_ASSERT(myRoot != nullptr);
        UT_VERIFY_ROOT;

        Node** current = &myRoot;
        inserted = false;

        while (current != nullptr && prefix.length() > 0)
        {
            Node** node = (*current)->findPartialPrefixChild(prefix);
            if (node == nullptr)
            {
                // No child partially matched the prefix so we will create
                // one
                Node** inserted_node = (*current)->insertChild(
                        current, createBaseNode(key, prefix));
                inserted = true;
                return (*inserted_node);
            }
            else
            {
                const exint prefix_length = (*current)->getCommonPrefixLength(
                        prefix, (*node)->myPrefix);

                // Check if this is a duplicate key
                if (prefix.length() == (*node)->myPrefix.length()
                    && prefix.length() == prefix_length)
                {
                    inserted = !(*node)->hasValue();
                    return *node;
                }
                // The childs key is the prefix of the insert item
                // abc -> abc - d [ after inserting "abcd" ]
                else if (prefix_length == (*node)->myPrefix.length())
                {
                    prefix.removePrefix(prefix_length);
                    current = node;
                }
                // The insert item is the prefix of the childs prefix
                // abc -> ab - c [after inserting "abc"]
                else if (prefix_length == prefix.length())
                {
                    auto new_child = createBaseNode(key, prefix);

                    // Remove the current child
                    UT_ARTNodePtr<Node> stolen = (*current)->stealChild(
                            current, *node);
                    // Update the child prefix
                    stolen->myPrefix.removePrefix(prefix_length);
                    // Add old child to the new child
                    Node* ptr = new_child.get();
                    new_child->insertChild(&ptr, std::move(stolen));

                    // Attach the new child to the current children
                    Node** inserted_node = (*current)->insertChild(
                            current, std::move(new_child));

                    inserted = true;
                    return (*inserted_node);
                }
                // Inserting item and childs key have the same common prefix
                else
                {
                    // We need to split the current child and the suffix
                    // into
                    // two children whos parent is the prefix of the two
                    // children

                    // remove the existing child as this will be move to the
                    // parent of the two children.
                    UT_ARTNodePtr<Node> erased_child = (*current)
                                           ->stealChild(current, *node);

                    UT_StringView item_prefix(prefix.begin(), prefix_length);
                    auto parent = createBaseNode(key, item_prefix);
                    // update the new prefix
                    erased_child->myPrefix.removePrefix(prefix_length);
                    // Add the suffix of the old key into the new branch
                    Node* ptr = parent.get();
                    parent->insertChild(
                            &ptr, std::move(erased_child));

                    // Add the suffix of the key into the new split branch
                    prefix.removePrefix(prefix_length);
                    Node** inserted_node = parent->insertChild(
                            &ptr, createBaseNode(key, prefix));

                    // Add the prefix of the old child and the new key into
                    // this children set.
                    (*current)->insertChild(current, std::move(parent));

                    inserted = true;
                    return *inserted_node;
                }
            }
        }

        return nullptr;
    }

    Node* myRoot = nullptr;
#if defined(USE_MEMORY_RESOURCE)
    UT_PMR::polymorphic_allocator<std::byte> myAllocator;
#endif
};

// Structured binding support
template <std::size_t N, class T, std::enable_if_t<N == 0, int> = 0>
auto
get(const UT_ARTIterator<T>& it) -> decltype(it.key())
{
    return it.key();
}

template <std::size_t N, class T, std::enable_if_t<N == 1, int> = 0>
auto
get(const UT_ARTIterator<T>& it) -> decltype(it.value())
{
    return it.value();
}

namespace std
{
template <typename T>
struct tuple_size<UT_ARTIterator<T>>
    : public std::integral_constant<std::size_t, 2>
{
};

template <std::size_t N, typename T>
struct tuple_element<N, UT_ARTIterator<T>>
{
    using type = decltype(get<N>(
            std::declval<UT_ARTIterator<T>>()));
};
} // namespace std

#include "UT_ARTMapImpl.h"

#endif // __UT_ARTMAP_H__