assoccache.h

Go to the documentation of this file.

/**********************************************************************
 * LeechCraft - modular cross-platform feature rich internet client.
 * Copyright (C) 2006-2014  Georg Rudoy
 *
 * Boost Software License - Version 1.0 - August 17th, 2003
 *
 * Permission is hereby granted, free of charge, to any person or organization
 * obtaining a copy of the software and accompanying documentation covered by
 * this license (the "Software") to use, reproduce, display, distribute,
 * execute, and transmit the Software, and to prepare derivative works of the
 * Software, and to permit third-parties to whom the Software is furnished to
 * do so, all subject to the following:
 *
 * The copyright notices in the Software and this entire statement, including
 * the above license grant, this restriction and the following disclaimer,
 * must be included in all copies of the Software, in whole or in part, and
 * all derivative works of the Software, unless such copies or derivative
 * works are solely in the form of machine-executable object code generated by
 * a source language processor.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
 * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
 * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 **********************************************************************/
 
#pragma once
 
#include <algorithm>
#include <QHash>
 
namespace LC
{
namespace Util
{
    namespace CacheStrat
    {
        class LRU
        {
            size_t Current_ = 0;
        public:
            struct ValueAddon
            {
                size_t LastAccess_ = 0;
 
                ValueAddon () = default;
 
                ValueAddon (size_t la)
                : LastAccess_ { la }
                {
                }
            };
 
            ValueAddon CreateInfo ()
            {
                return { ++Current_ };
            }
 
            void Clear ()
            {
                Current_ = 0;
            }
 
            void Touch (ValueAddon& add)
            {
                add.LastAccess_ = ++Current_;
            }
        };
 
        inline bool operator< (const LRU::ValueAddon& v1, const LRU::ValueAddon& v2)
        {
            return v1.LastAccess_ < v2.LastAccess_;
        }
    }
 
    template<typename K, typename V, typename CS = CacheStrat::LRU>
    class AssocCache
    {
        struct ValueHolder
        {
            V V_;
            size_t Cost_;
            typename CS::ValueAddon CacheInfo_;
        };
 
        QHash<K, ValueHolder> Hash_;
 
        size_t CurrentCost_ = 0;
        const size_t MaxCost_;
 
        CS CacheStratState_;
    public:
        AssocCache (size_t maxCost)
        : MaxCost_ { maxCost }
        {
        }
 
        size_t size () const;
        void clear ();
        bool contains (const K&) const;
 
        V& operator[] (const K&);
    private:
        void CheckShrink ();
    };
 
    template<typename K, typename V, typename CS>
    size_t AssocCache<K, V, CS>::size () const
    {
        return Hash_.size ();
    }
 
    template<typename K, typename V, typename CS>
    void AssocCache<K, V, CS>::clear ()
    {
        Hash_.clear ();
        CacheStratState_.Clear ();
    }
 
    template<typename K, typename V, typename CS>
    bool AssocCache<K, V, CS>::contains (const K& k) const
    {
        return Hash_.contains (k);
    }
 
    template<typename K, typename V, typename CS>
    V& AssocCache<K, V, CS>::operator[] (const K& key)
    {
        if (!Hash_.contains (key))
        {
            Hash_.insert (key, { {}, 1, CacheStratState_.CreateInfo () });
            ++CurrentCost_;
 
            CheckShrink ();
        }
        else
            CacheStratState_.Touch (Hash_ [key].CacheInfo_);
 
        return Hash_ [key].V_;
    }
 
    template<typename K, typename V, typename CS>
    void AssocCache<K, V, CS>::CheckShrink ()
    {
        while (CurrentCost_ > MaxCost_)
        {
            const auto pos = std::min_element (Hash_.begin (), Hash_.end (),
                    [] (const ValueHolder& left, const ValueHolder& right)
                        { return left.CacheInfo_ < right.CacheInfo_; });
            CurrentCost_ -= pos->Cost_;
            Hash_.erase (pos);
        }
    }
}
}