cert validation cache

[thirdparty/squid.git] / src / base / LruMap.h

/*
 */

#ifndef SQUID_LRUMAP_H
#define SQUID_LRUMAP_H

#include "SquidTime.h"
#if HAVE_LIST
#include <list>
#endif
#if HAVE_MAP
#include <map>
#endif

template <class EntryValue, size_t EntryCost = sizeof(EntryValue)> class LruMap
{
public:
    class Entry
    {
    public:
        Entry(const char *aKey, EntryValue *t): key(aKey), value(t), date(squid_curtime) {}
        ~Entry() {delete value;}
    private:
        Entry(LruMap<EntryValue, EntryCost>::Entry &);
        LruMap<EntryValue, EntryCost>::Entry & operator = (LruMap<EntryValue, EntryCost>::Entry &);
    public:
        std::string key; ///< the key of entry
        EntryValue *value; ///< A pointer to the stored value
        time_t date; ///< The date the entry created
    };
    typedef std::list<Entry *> Queue;
    typedef typename std::list<Entry *>::iterator QueueIterator;
    
    /// key:queue_item mapping for fast lookups by key
    typedef std::map<std::string, QueueIterator> Map;
    typedef typename Map::iterator MapIterator;
    typedef std::pair<std::string, QueueIterator> MapPair;


    LruMap(int ttl, size_t size);
    ~LruMap();
    /// Search for an entry, and return a pointer
    EntryValue *get(const char *key);
    /// Add an entry to the map
    bool add(const char *key, EntryValue *t);
    /// Delete an entry from the map
    bool del(const char *key);
    /// (Re-)set the maximum size for this map
    void setMemLimit(size_t aSize);
    /// The available size for the map
    size_t memLimit() const {return memLimit_;}
    /// The free space of the map
    size_t freeMem() const { return (memLimit() - size());}
    /// The current size of the map
    size_t size() const {return (entries_ * EntryCost);}
    /// The number of stored entries
    int entries() const {return entries_;}
private:
    LruMap(LruMap<EntryValue, EntryCost> const &);
    LruMap<EntryValue, EntryCost> & operator = (LruMap<EntryValue, EntryCost> const &);
    
    bool expired(Entry &e);
    void trim();
    void touch(const MapIterator &i);
    bool del(const MapIterator &i);
    void findEntry(const char *key, LruMap::MapIterator &i);

    Map storage; ///< The Key/value * pairs
    Queue index; ///< LRU cache index
    int ttl;///< >0 ttl for caching, == 0 cache is disabled, < 0 store for ever
    size_t memLimit_; ///< The maximum memory to use
    int entries_; ///< The stored entries
};

template <class EntryValue, size_t EntryCost>
LruMap<EntryValue, EntryCost>::LruMap(int aTtl, size_t aSize): entries_(0)
{
    ttl = aTtl;

    setMemLimit(aSize);
}

template <class EntryValue, size_t EntryCost>
LruMap<EntryValue, EntryCost>::~LruMap()
{
    for (QueueIterator i = index.begin(); i != index.end(); ++i) {
        delete *i;
    }
}

template <class EntryValue, size_t EntryCost>
void
LruMap<EntryValue, EntryCost>::setMemLimit(size_t aSize)
{
    if (aSize > 0)
        memLimit_ = aSize;
    else
        memLimit_ = 0;
}

template <class EntryValue, size_t EntryCost>
void
LruMap<EntryValue, EntryCost>::findEntry(const char *key, LruMap::MapIterator &i)
{
    i = storage.find(key);
    if (i == storage.end()) {
        return;
    }
    index.push_front(*(i->second));
    index.erase(i->second);
    i->second = index.begin();
    
    LruMap::Entry *e = *i->second;

    if (e && expired(*e)) {
        del(i);
        e = NULL;
    }
}

template <class EntryValue, size_t EntryCost>
EntryValue *
LruMap<EntryValue, EntryCost>::get(const char *key)
{
    LruMap::MapIterator i;
    findEntry(key, i);
    LruMap::Entry *e = *i->second;
    if (i != storage.end()) {
        touch(i);
        return e->value;
    }
    return NULL;
}

template <class EntryValue, size_t EntryCost>
bool
LruMap<EntryValue, EntryCost>::add(const char *key, EntryValue *t)
{
    if (ttl == 0)
        return false;

    del(key);
    trim();
    index.push_front(new Entry(key, t));
    storage.insert(MapPair(key, index.begin()));

    ++entries_;
    return true;
}

template <class EntryValue, size_t EntryCost>
bool
LruMap<EntryValue, EntryCost>::expired(LruMap::Entry &entry)
{
    if (ttl < 0)
        return false;

    return (entry.date + ttl < squid_curtime);
}

template <class EntryValue, size_t EntryCost>
bool
LruMap<EntryValue, EntryCost>::del(LruMap::MapIterator const &i)
{
     if (i != storage.end()) {
        delete *(i->second);
        index.erase(i->second);
        storage.erase(i);
        --entries_;
        return true;
    }
    return false;
}

template <class EntryValue, size_t EntryCost>
bool
LruMap<EntryValue, EntryCost>::del(const char *key)
{
    LruMap::MapIterator i;
    findEntry(key, i);
    return del(i);
}

template <class EntryValue, size_t EntryCost>
void
LruMap<EntryValue, EntryCost>::trim()
{
    while(memLimit() > 0 && size() >= memLimit()) {
        LruMap::QueueIterator i = index.end();
        --i;
        if (i != index.end()) {
            del((*i)->key.c_str());
        }
    }
}

template <class EntryValue, size_t EntryCost>
void
LruMap<EntryValue, EntryCost>::touch(LruMap::MapIterator const &i)
{
    // this must not be done when nothing is being cached.
    if (ttl == 0)
        return;

    index.push_front(*(i->second));
    index.erase(i->second);
    i->second = index.begin();
}

#endif