Method insert

libCacheSim/dataStructure/splaytree.hpp:390–428

template <typename K, typename V>
void SplayTree<K, V>::insert(const K &key, const V &val)
{
    node *p = root_.get();
    node *prev = nullptr;
    while (p)
    {
        prev = p;
        if (key == p->first)
        {
            p->second = val;
            return;
        }
        else if (key < p->first)
            p = p->left.get();
        else if (key > p->first)
            p = p->right.get();
    }
    node_ptr n(new node(key, val));

    ++node_count_;
    sum += val;

    if (prev == nullptr)
    {
        root_ = move(n);
    }
    else if (key < prev->first)
    {
        prev->left = move(n);
        prev->left->parent = prev;
        splay(prev->left.get());
    }
    else
    {
        prev->right = move(n);
        prev->right->parent = prev;
        splay(prev->right.get());
    }
}

template <typename K, typename V>
typename SplayTree<K, V>::node *SplayTree<K, V>::find_(const K &key)