Cache.h

Go to the documentation of this file.

#ifndef OSMSCOUT_CACHE_H
#define OSMSCOUT_CACHE_H
 
/*
  This source is part of the libosmscout library
  Copyright (C) 2009  Tim Teulings
 
  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.
 
  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.
 
  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
*/
 
#include <limits>
#include <list>
#include <unordered_map>
#include <vector>
 
#include <osmscout/lib/CoreFeatures.h>
 
#include <osmscout/system/Assert.h>
 
#include <osmscout/OSMScoutTypes.h>
 
#include <osmscout/log/Logger.h>
 
namespace osmscout {

  template <class K, class V, class IK = PageId>
  class Cache
  {
  public:
    struct CacheEntry
    {
      K key; // NOLINT
      V value; // NOLINT
 
      explicit CacheEntry(const K& key)
      : key(key)
      {
        // no code
      }
 
      CacheEntry(const K& key,
                 const V& value)
      : key(key),
        value(value)
      {
        // no code
      }
    };

    class ValueSizer
    {
    public:
      virtual ~ValueSizer() = default;
 
      virtual size_t GetSize(const V& value) const = 0;
    };
 
    using OrderList = std::list<CacheEntry>;
    using CacheRef  = typename OrderList::iterator;
    using Map       = std::unordered_map<K, typename OrderList::iterator>;
 
  private:
    size_t    size=0;        //<! Current size fo the cache
    size_t    maxSize;       //<! Maximum size of the cache
    OrderList order;         //<! Order list (by cache access) of cache entries for least recently used cache flush
    Map       map;           //<! Key=>Value map
    CacheRef  previousEntry; //<! Reference to the last access cache entry
 
  private:
 
    IK KeyToInternalKey(K key)
    {
      return key - std::numeric_limits<K>::min();
    }

    void StripCache()
    {
      while (size>maxSize) {
        // Remove oldest entry from cache...
 
        // Get oldest entry an dremove it from the map
        map.erase(map.find(order.back().key));
 
        // Remove it from order list
        order.pop_back();
 
        previousEntry=order.end();
 
        size--;
      }
    }
 
  public:
    explicit Cache(size_t maxSize)
     : maxSize(maxSize)
    {
      map.reserve(maxSize);
      previousEntry=order.end();
    }

    bool IsActive() const
    {
      return maxSize>0;
    }

    bool GetEntry(const K& key,
                  CacheRef& reference)
    {
      if (!IsActive()) {
        return false;
      }
 
      // Cached cache access
      if (previousEntry!=order.end() &&
          previousEntry->key==key) {
        reference=previousEntry;
        return true;
      }
 
      typename Map::iterator iter=map.find(key);
 
      if (iter!=map.end()) {
        // Move key/value to the start of the order list
        order.splice(order.begin(),order,iter->second);
 
        // Update the map with the new iterator into the order list
        iter->second=order.begin();
 
        reference=order.begin();
        previousEntry=reference;
 
        return true;
      }
 
      return false;
    }

    typename Cache::CacheRef SetEntry(const CacheEntry& entry)
    {
      if (!IsActive()) {
        order.clear();
 
        order.push_front(entry);
 
        previousEntry=order.begin();
        return order.begin();
      }
 
      typename Map::iterator iter=map.find(entry.key);
 
      if (iter!=map.end()) {
        // Move key/value to the start of the order list
        order.splice(order.begin(),order,iter->second);
 
        // Update the map with the new iterator into the order list
        iter->second=order.begin();
 
        order.front().value=entry.value;
      }
      else {
        // Place key/value to the start of the order list
        order.push_front(entry);
        size++;
        // Update the map with the new iterator into the order list
        map[entry.key]=order.begin();
 
        StripCache();
      }
 
      previousEntry=order.begin();
      return order.begin();
    }

    void SetMaxSize(size_t maxSize)
    {
      this->maxSize=maxSize;
 
      StripCache();
 
      map.reserve(maxSize);
    }

    size_t GetMaxSize() const
    {
      return maxSize;
    }

    void Flush()
    {
      order.clear();
      map.clear();
      size=0;
      previousEntry=order.end();
    }

    size_t GetSize() const
    {
      return size;
    }
 
    size_t GetMemory(const ValueSizer& sizer) const
    {
      size_t memory=0;
 
      // Size of map
      memory+=map.size()*sizeof(CacheRef);
 
      // Size of list
      memory+=size*sizeof(CacheEntry);
 
      for (typename std::list<CacheEntry>::const_iterator entry=order.begin();
           entry!=order.end();
           ++entry) {
        memory+=sizer.GetSize(entry->value);
      }
 
      return memory;
    }

    void DumpStatistics(const char* cacheName, const ValueSizer& sizer)
    {
      log.Debug() << cacheName << " entries: " << size << ", memory " << GetMemory(sizer);
    }
  };
}
 
#endif