MRU NIH

mru.cpp

#include <new>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>

class Mru
{
public:
    Mru(size_t size): _size(0), _capacity(size), _buckets(nullptr), _bucketCount(size * 2), _first(nullptr), _last(nullptr)
    {
        _buckets = new Node*[_bucketCount];
        for (size_t i = 0; i < _bucketCount; ++i) _buckets[i] = nullptr;
    }

    ~Mru()
    {
        for (size_t i = 0; i < _bucketCount; ++i)
            while (_buckets[i])
            {
                Node* node = _buckets[i];
                _buckets[i] = node->nexthash;
                delete node;
            }
        
        delete[] _buckets;
    }

    void touch(const std::string& name)
    {
        size_t h = hash(name);

        for (Node* node = _buckets[h]; node; node = node->nexthash)
            if (node->data == name)
            {
                removeList(node);
                addListFront(node);
                return;
            }

        Node* node = new Node();
        node->data = name;
        node->nexthash = _buckets[h];

        _buckets[h] = node;

        addListFront(node);

        if (_size > _capacity)
        {
            Node* node = _last;

            removeList(node);
            removeHash(node);

            delete node;
        }
    }

    std::vector<std::string> contents() const
    {
        std::vector<std::string> result;
        result.reserve(_size);

        for (Node* node = _first; node; node = node->next)
            result.push_back(node->data);

        return result;
    }

private:
    struct Node
    {
        std::string data;

        Node* nexthash;
        Node* next;
        Node* prev;

        Node(): nexthash(nullptr), next(nullptr), prev(nullptr)
        {
        }
    };

    size_t _size;
    size_t _capacity;

    Node** _buckets;
    size_t _bucketCount;

    Node* _first;
    Node* _last;

    size_t hash(const std::string& s)
    {
        size_t r = 0;

        for (size_t i = 0; i < s.size(); ++i) r = r * 5 + s[i];

        return r % _bucketCount;
    }

    void removeHash(Node* node)
    {
        size_t h = hash(node->data);

        for (Node** place = &_buckets[h]; *place; place = &(*place)->nexthash)
            if (*place == node)
            {
                *place = node->nexthash;
                return;
            }
    }

    void removeList(Node* node)
    {
        if (node->prev) node->prev->next = node->next;
        else _first = node->next;

        if (node->next) node->next->prev = node->prev;
        else _last = node->prev;

        _size--;
    }

    void addListFront(Node* node)
    {
        node->prev = nullptr;
        node->next = _first;

        if (_first) _first->prev = node;
        _first = node;

        if (_last == nullptr) _last = node;

        _size++;
    }
};

void DumpMru(Mru& mru, const char* comment)
{
    printf("Mru:");
    for (auto& s: mru.contents()) printf(" %s", s.c_str());
    printf(" -- %s\n", comment);
}

int main()
{
    Mru mru(3);

    mru.touch("a");
    mru.touch("b");
    mru.touch("c");
    DumpMru(mru, "touch abc");

    mru.touch("b");
    DumpMru(mru, "touch b");

    mru.touch("b");
    DumpMru(mru, "retouch b");

    mru.touch("d");
    DumpMru(mru, "introduce d");

    mru.touch("a");
    DumpMru(mru, "reintroduce a");
}