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 <list>
  19 #include <map>
  20 #include <unordered_map>
  21 #include <utility>
  22
  23 #include "common/ceph_mutex.h"
  24
  25 template <class K, class V, class C = std::less<K>, class H = std::hash<K> >
  26 class SimpleLRU {
  27   ceph::mutex lock = ceph::make_mutex("SimpleLRU::lock");
  28   size_t max_size;
  29   size_t max_bytes = 0;
  30   size_t total_bytes = 0;
  31   std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator, H> contents;
  32   std::list<std::pair<K, V> > lru;
  33   std::map<K, V, C> pinned;
  34
  35   void trim_cache() {
  36     while (contents.size() > max_size) {
  37       contents.erase(lru.back().first);
  38       lru.pop_back();
  39     }
  40   }
  41
  42   void trim_cache_bytes() {
  43     while(total_bytes > max_bytes) {
  44       total_bytes -= lru.back().second.length();
  45       contents.erase(lru.back().first);
  46       lru.pop_back();
  47     }
  48   }
  49
  50   void _add(K key, V&& value) {
  51     lru.emplace_front(key, std::move(value)); // can't move key because we access it below
  52     contents[key] = lru.begin();
  53     trim_cache();
  54   }
  55
  56   void _add_bytes(K key, V&& value) {
  57     lru.emplace_front(key, std::move(value)); // can't move key because we access it below
  58     contents[key] = lru.begin();
  59     trim_cache_bytes();
  60   }
  61
  62 public:
  63   SimpleLRU(size_t max_size) : max_size(max_size) {
  64     contents.rehash(max_size);
  65   }
  66
  67   void pin(K key, V val) {
  68     std::lock_guard l(lock);
  69     pinned.emplace(std::move(key), std::move(val));
  70   }
  71
  72   void clear_pinned(K e) {
  73     std::lock_guard l(lock);
  74     for (auto i = pinned.begin();
  75          i != pinned.end() && i->first <= e;
  76          pinned.erase(i++)) {
  77       auto iter = contents.find(i->first);
  78       if (iter == contents.end())
  79         _add(i->first, std::move(i->second));
  80       else
  81         lru.splice(lru.begin(), lru, iter->second);
  82     }
  83   }
  84
  85   void clear(K key) {
  86     std::lock_guard l(lock);
  87     auto i = contents.find(key);
  88     if (i == contents.end())
  89       return;
  90     total_bytes -= i->second->second.length();
  91     lru.erase(i->second);
  92     contents.erase(i);
  93   }
  94
  95   void set_size(size_t new_size) {
  96     std::lock_guard l(lock);
  97     max_size = new_size;
  98     trim_cache();
  99   }
 100
 101   size_t get_size() {
 102     std::lock_guard l(lock);
 103     return contents.size();
 104   }
 105
 106   void set_bytes(size_t num_bytes) {
 107     std::lock_guard l(lock);
 108     max_bytes = num_bytes;
 109     trim_cache_bytes();
 110   }
 111
 112   size_t get_bytes() {
 113     std::lock_guard l(lock);
 114     return total_bytes;
 115   }
 116
 117   bool lookup(K key, V *out) {
 118     std::lock_guard l(lock);
 119     auto i = contents.find(key);
 120     if (i != contents.end()) {
 121       *out = i->second->second;
 122       lru.splice(lru.begin(), lru, i->second);
 123       return true;
 124     }
 125     auto i_pinned = pinned.find(key);
 126     if (i_pinned != pinned.end()) {
 127       *out = i_pinned->second;
 128       return true;
 129     }
 130     return false;
 131   }
 132
 133   void add(K key, V value) {
 134     std::lock_guard l(lock);
 135     _add(std::move(key), std::move(value));
 136   }
 137
 138   void add_bytes(K key, V value) {
 139     std::lock_guard l(lock);
 140     total_bytes += value.length();
 141     _add_bytes(std::move(key), std::move(value));
 142   }
 143 };
 144
 145 #endif