UT_ARTMapImpl.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_ARTMapImpl.h
 *
 * COMMENTS:
 *
 *
 */

#ifndef __UT_ARTMAPIMPL_H__
#define __UT_ARTMAPIMPL_H__

// -----------------------------------------------------------------------------
// UT_ARTNode4
// -----------------------------------------------------------------------------

template <typename T>
inline bool
UT_ARTNode4<T>::isFull() const
{
    return this->myNumChildren == 4;
}

template <typename T>
inline UT_ARTNode<T>**
UT_ARTNode4<T>::insertChild(parent_t** ref, parent_ptr_t child)
{
    UT_ASSERT(child != nullptr);
    if (!isFull())
    {
        UT_StringView prefix = child->prefix();
        unsigned c = prefix[0];

        myChildKeys[this->myNumChildren] = c;
        myChildren[this->myNumChildren] = child.release();
        parent_t** node = &myChildren[this->myNumChildren];
        this->myNumChildren++;
        return node;
    }
    else
    {
        auto upgrade = this->template newNode<UT_ARTNode16<T>>();
        this->moveHeader(*upgrade);
        UT_ARTNodePtr<parent_t> holder(*ref);

        upgrade->myNumChildren = this->myNumChildren;
        memcpy(upgrade->myChildKeys, myChildKeys,
               sizeof(unsigned char) * this->myNumChildren);
        for (int i = 0; i < 4; ++i)
        {
            upgrade->myChildren[i] = myChildren[i];
            myChildren[i] = nullptr;
        }

        *ref = upgrade.release();
        return (*ref)->insertChild(ref, std::move(child));
    }

    return nullptr;
}

template <typename T>
inline UT_ARTNodePtr<UT_ARTNode<T>>
UT_ARTNode4<T>::stealChild(parent_t** ref, parent_t* child)
{
    uchar c = child->prefix()[0];
    int idx = 0;
    if (myChildKeys[0] == c)
        idx = 0;
    else if (myChildKeys[1] == c)
        idx = 1;
    else if (myChildKeys[2] == c)
        idx = 2;
    else if (myChildKeys[3] == c)
        idx = 3;
    else
        return nullptr;

    return stealChild(ref, idx);
}

template <typename T>
inline UT_ARTNode<T>**
UT_ARTNode4<T>::findPartialPrefixChild(const UT_StringView& prefix)
{
    parent_t** found = nullptr;

    uchar c = prefix[0];
    if (myChildKeys[0] == c)
        found = &myChildren[0];
    else if (myChildKeys[1] == c)
        found = &myChildren[1];
    else if (myChildKeys[2] == c)
        found = &myChildren[2];
    else if (myChildKeys[3] == c)
        found = &myChildren[3];

    return found;
}

template <typename T>
inline UT_ARTNode<T>*
UT_ARTNode4<T>::nextChild(int& index)
{
    for (; index < this->myNumChildren; index++)
    {
        if (myChildren[index] != nullptr)
            return myChildren[index];
    }
    return nullptr;
}

template <typename T>
inline const UT_ARTNode<T>*
UT_ARTNode4<T>::nextChild(int& index) const
{
    for (; index < this->myNumChildren; index++)
    {
        if (myChildren[index] != nullptr)
            return myChildren[index];
    }
    return nullptr;
}

template <typename T>
inline UT_ARTNodePtr<UT_ARTNode<T>>
UT_ARTNode4<T>::stealChild(parent_t** /*ref*/, int idx)
{
    this->myNumChildren--;
    UT_ARTNodePtr<parent_t> stolen(myChildren[idx]);
    myChildren[idx] = myChildren[this->myNumChildren];
    myChildKeys[idx] = myChildKeys[this->myNumChildren];
    myChildKeys[this->myNumChildren] = 0;
    myChildren[this->myNumChildren] = nullptr;
    return stolen;
}

// -----------------------------------------------------------------------------
// UT_ARTNode16
// -----------------------------------------------------------------------------

template <typename T>
inline bool
UT_ARTNode16<T>::isFull() const
{
    return this->myNumChildren == 16;
}

template <typename T>
inline UT_ARTNode<T>**
UT_ARTNode16<T>::insertChild(
        parent_t** ref,
        UT_ARTNodePtr<parent_t> child)
{
    if (this->myNumChildren < 16)
    {
        uchar c = child->prefix()[0];
        int idx = prefixToIndex_(c);

        if (idx < 0)
            idx = this->myNumChildren;

        myChildKeys[idx] = c;
        myChildren[idx] = child.release();
        this->myNumChildren++;

        return &myChildren[idx];
    }
    else
    {
        UT_ARTNodePtr<parent_t> holder(*ref);
        auto upgrade = this->template newNode<UT_ARTNode48<T>>();
        this->moveHeader(*upgrade);
        for (int i = 0; i < this->myNumChildren; i++)
        {
            upgrade->myChildKeys[myChildKeys[i]] = i + 1;
            upgrade->myChildren[i] = myChildren[i];
            myChildren[i] = nullptr;
        }
        *ref = upgrade.release();
        return (*ref)->insertChild(ref, std::move(child));
    }
}

template <typename T>
inline UT_ARTNodePtr<UT_ARTNode<T>>
UT_ARTNode16<T>::stealChild(parent_t** ref, parent_t* child)
{
    uchar c = child->prefix()[0];
    int idx = prefixToIndex_(c);
    if (idx >= 0)
        return stealChild(ref, idx);

    return nullptr;
}

template <typename T>
inline UT_ARTNode<T>**
UT_ARTNode16<T>::findPartialPrefixChild(const UT_StringView& prefix)
{
    uchar c = prefix[0];

    int idx = prefixToIndex_(c);
    if (idx >= 0)
    {
        return &myChildren[idx];
    }

    return nullptr;
}

template <typename T>
inline UT_ARTNode<T>*
UT_ARTNode16<T>::nextChild(int& index)
{
    for (; index < this->myNumChildren; index++)
    {
        if (myChildren[index] != nullptr)
            return myChildren[index];
    }
    return nullptr;
}

template <typename T>
inline const UT_ARTNode<T>*
UT_ARTNode16<T>::nextChild(int& index) const
{
    for (; index < this->myNumChildren; index++)
    {
        if (myChildren[index] != nullptr)
            return myChildren[index];
    }
    return nullptr;
}

template <typename T>
inline UT_ARTNodePtr<UT_ARTNode<T>>
UT_ARTNode16<T>::stealChild(parent_t** ref, int idx)
{
    this->myNumChildren--;
    UT_ARTNodePtr<parent_t> stolen(myChildren[idx]);
    myChildren[idx] = myChildren[this->myNumChildren];
    myChildKeys[idx] = myChildKeys[this->myNumChildren];
    myChildKeys[this->myNumChildren] = 0;
    myChildren[this->myNumChildren] = nullptr;

    if (this->myNumChildren == 2)
    {
        auto downgrade = this->template newNode<UT_ARTNode4<T>>();
        this->moveHeader(*downgrade);
        memcpy(downgrade->myChildKeys, myChildKeys, 4);
        for (int i = 0; i < this->myNumChildren; i++)
        {
            downgrade->myChildren[i] = myChildren[i];
            myChildren[i] = nullptr;
        }

        UT_ARTNodePtr<parent_t> holder(*ref);

        *ref = downgrade.release();
    }

    return stolen;
}

// -----------------------------------------------------------------------------
// UT_ARTNode48
// -----------------------------------------------------------------------------

template <typename T>
inline bool
UT_ARTNode48<T>::isFull() const
{
    return this->myNumChildren == 48;
}

template <typename T>
inline UT_ARTNode<T>**
UT_ARTNode48<T>::insertChild(parent_t** ref, parent_ptr_t child)
{
    uchar c = child->prefix()[0];
    if (this->myNumChildren < 48)
    {
        int pos;
        for (pos = 0; pos < 48; pos++)
        {
            if (myChildren[pos] == nullptr)
                break;
        }
        myChildren[pos] = child.release();
        myChildKeys[c] = pos + 1;
        this->myNumChildren++;

        return &myChildren[pos];
    }
    else
    {
        UT_ARTNodePtr<parent_t> holder(*ref);
        auto upgrade = this->template newNode<UT_ARTNode256<T>>();
        this->moveHeader(*upgrade);
        for (int i = 0; i < 256; i++)
        {
            if (myChildKeys[i])
            {
                upgrade->myChildren[i] = myChildren[myChildKeys[i] - 1];
                myChildren[myChildKeys[i] - 1] = nullptr;
            }
        }

        *ref = upgrade.release();
        return (*ref)->insertChild(ref, std::move(child));
    }
}

template <typename T>
inline UT_ARTNodePtr<UT_ARTNode<T>>
UT_ARTNode48<T>::stealChild(parent_t** ref, parent_t* child)
{
    uchar c = child->prefix()[0];
    int idx = myChildKeys[c];
    if (idx > 0)
        return stealChild(ref, idx - 1);
    return nullptr;
}

template <typename T>
inline UT_ARTNode<T>**
UT_ARTNode48<T>::findPartialPrefixChild(const UT_StringView& prefix)
{
    uchar c = prefix[0];
    int idx = myChildKeys[c];
    if (idx > 0)
        return &myChildren[idx - 1];
    return nullptr;
}

template <typename T>
inline UT_ARTNode<T>*
UT_ARTNode48<T>::nextChild(int& index)
{
    for (; index < 48; index++)
    {
        if (myChildren[index] != nullptr)
            return myChildren[index];
    }
    return nullptr;
}

template <typename T>
inline const UT_ARTNode<T>*
UT_ARTNode48<T>::nextChild(int& index) const
{
    for (; index < 48; index++)
    {
        if (myChildren[index] != nullptr)
            return myChildren[index];
    }
    return nullptr;
}

template <typename T>
inline UT_ARTNodePtr<UT_ARTNode<T>>
UT_ARTNode48<T>::stealChild(parent_t** ref, int idx)
{
    this->myNumChildren--;
    parent_ptr_t stolen(myChildren[idx]);
    uchar c = myChildren[idx]->prefix()[0];
    myChildKeys[c] = 0;
    myChildren[idx] = nullptr;

    // if we dont hold enough children then downgrade to the previous node.
    // Make sure we dont do this downgrade to close to the previous nodes
    // max so that we prevent fliping between node16 and node48
    if (this->myNumChildren == 12)
    {
        parent_ptr_t holder(*ref);
        auto downgrade = this->template newNode<UT_ARTNode16<T>>();
        this->moveHeader(*downgrade);

        int cidx = 0;
        for (int i = 0; i < 256; i++)
        {
            int pos = myChildKeys[i];
            if (pos)
            {
                downgrade->myChildKeys[cidx] = i;
                downgrade->myChildren[cidx] = myChildren[pos - 1];
                myChildren[pos - 1] = nullptr;
                cidx++;
            }
        }

        *ref = downgrade.release();
        return stolen;
    }

    return stolen;
}

// -----------------------------------------------------------------------------
// UT_ARTNode256
// -----------------------------------------------------------------------------

template <typename T>
inline bool
UT_ARTNode256<T>::isFull() const
{
    return this->myNumChildren == 256;
}

template <typename T>
inline UT_ARTNode<T>**
UT_ARTNode256<T>::insertChild(parent_t** ref, parent_ptr_t child)
{
    uchar c = child->prefix()[0];
    this->myNumChildren++;
    myChildren[c] = child.release();

    return &myChildren[c];
}

template <typename T>
inline UT_ARTNodePtr<UT_ARTNode<T>>
UT_ARTNode256<T>::stealChild(parent_t** ref, parent_t* child)
{
    uchar c = child->prefix()[0];
    return stealChild(ref, c);
}

template <typename T>
inline UT_ARTNode<T>**
UT_ARTNode256<T>::findPartialPrefixChild(
        const UT_StringView& prefix)
{
    uchar c = prefix[0];
    if (myChildren[c] != nullptr)
        return &myChildren[c];
    return nullptr;
}

template <typename T>
inline UT_ARTNode<T>*
UT_ARTNode256<T>::nextChild(int& index)
{
    // NB: we dont shuffle children when inserting/deleting so we cant use
    // the child count and instead of have to loop through the entire 256
    // array.
    for (; index < 256; index++)
    {
        if (myChildren[index] != nullptr)
            return myChildren[index];
    }
    return nullptr;
}

template <typename T>
inline const UT_ARTNode<T>*
UT_ARTNode256<T>::nextChild(int& index) const
{
    for (; index < 256; index++)
    {
        if (myChildren[index] != nullptr)
            return myChildren[index];
    }
    return nullptr;
}

template <typename T>
inline UT_ARTNodePtr<UT_ARTNode<T>>
UT_ARTNode256<T>::stealChild(parent_t** ref, int idx)
{
    this->myNumChildren--;
    parent_ptr_t stolen(myChildren[idx]);
    myChildren[idx] = nullptr;

    // If we hold less then the max of the lower node we need to downgrade
    // ourselves. We dont use the boundary to downgrade to prevent constantly
    // switching between node48 and node256.
    if (this->myNumChildren == 37)
    {
        parent_ptr_t holder(*ref);
        auto downgrade = this->template newNode<UT_ARTNode48<T>>();
        this->moveHeader(*downgrade);
        int pos = 0;
        for (int i = 0; i < 256; i++)
        {
            if (myChildren[i] != nullptr)
            {
                downgrade->myChildren[pos] = myChildren[i];
                downgrade->myChildKeys[i] = pos + 1;
                pos++;
                myChildren[i] = nullptr;
            }
        }

        *ref = downgrade.release();
        return stolen;
    }

    return stolen;
}

#endif // __UT_ARTMAPIMPL_H__