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 <osmscout/CoreFeatures.h>

#include <limits>
#include <list>
#include <unordered_map>
#include <vector>

#include <osmscout/system/Assert.h>

#include <osmscout/OSMScoutTypes.h>

#include <osmscout/util/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