ceph/src/common/simple_cache.hpp

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
   7  *
   8  * This is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License version 2.1, as published by the Free Software
  11  * Foundation.  See file COPYING.
  12  *
  13  */
  14
  15 #ifndef CEPH_SIMPLECACHE_H
  16 #define CEPH_SIMPLECACHE_H
  17
  18 #include <map>
  19 #include <list>
  20 #include <memory>
  21 #include "common/Mutex.h"
  22 #include "common/Cond.h"
  23 #include "include/unordered_map.h"
  24
  25 template <class K, class V, class C = std::less<K>, class H = std::hash<K> >
  26 class SimpleLRU {
  27   Mutex lock;
  28   size_t max_size;
  29   ceph::unordered_map<K, typename list<pair<K, V> >::iterator, H> contents;
  30   list<pair<K, V> > lru;
  31   map<K, V, C> pinned;
  32
  33   void trim_cache() {
  34     while (lru.size() > max_size) {
  35       contents.erase(lru.back().first);
  36       lru.pop_back();
  37     }
  38   }
  39
  40   void _add(K key, V&& value) {
  41     lru.emplace_front(key, std::move(value)); // can't move key because we access it below
  42     contents[key] = lru.begin();
  43     trim_cache();
  44   }
  45
  46 public:
  47   SimpleLRU(size_t max_size) : lock("SimpleLRU::lock"), max_size(max_size) {
  48     contents.rehash(max_size);
  49   }
  50
  51   void pin(K key, V val) {
  52     Mutex::Locker l(lock);
  53     pinned.emplace(std::move(key), std::move(val));
  54   }
  55
  56   void clear_pinned(K e) {
  57     Mutex::Locker l(lock);
  58     for (typename map<K, V, C>::iterator i = pinned.begin();
  59          i != pinned.end() && i->first <= e;
  60          pinned.erase(i++)) {
  61       typename ceph::unordered_map<K, typename list<pair<K, V> >::iterator, H>::iterator iter =
  62         contents.find(i->first);
  63       if (iter == contents.end())
  64         _add(i->first, std::move(i->second));
  65       else
  66         lru.splice(lru.begin(), lru, iter->second);
  67     }
  68   }
  69
  70   void clear(K key) {
  71     Mutex::Locker l(lock);
  72     typename ceph::unordered_map<K, typename list<pair<K, V> >::iterator, H>::iterator i =
  73       contents.find(key);
  74     if (i == contents.end())
  75       return;
  76     lru.erase(i->second);
  77     contents.erase(i);
  78   }
  79
  80   void set_size(size_t new_size) {
  81     Mutex::Locker l(lock);
  82     max_size = new_size;
  83     trim_cache();
  84   }
  85
  86   bool lookup(K key, V *out) {
  87     Mutex::Locker l(lock);
  88     typename ceph::unordered_map<K, typename list<pair<K, V> >::iterator, H>::iterator i =
  89       contents.find(key);
  90     if (i != contents.end()) {
  91       *out = i->second->second;
  92       lru.splice(lru.begin(), lru, i->second);
  93       return true;
  94     }
  95     typename map<K, V, C>::iterator i_pinned = pinned.find(key);
  96     if (i_pinned != pinned.end()) {
  97       *out = i_pinned->second;
  98       return true;
  99     }
 100     return false;
 101   }
 102
 103   void add(K key, V value) {
 104     Mutex::Locker l(lock);
 105     _add(std::move(key), std::move(value));
 106   }
 107 };
 108
 109 #endif