src/ceph/src/common/lru_map.h

   1 #ifndef CEPH_LRU_MAP_H
   2 #define CEPH_LRU_MAP_H
   3
   4 #include "common/Mutex.h"
   5
   6 template <class K, class V>
   7 class lru_map {
   8   struct entry {
   9     V value;
  10     typename std::list<K>::iterator lru_iter;
  11   };
  12
  13   std::map<K, entry> entries;
  14   std::list<K> entries_lru;
  15
  16   Mutex lock;
  17
  18   size_t max;
  19
  20 public:
  21   class UpdateContext {
  22     public:
  23       virtual ~UpdateContext() {}
  24
  25       /* update should return true if object is updated */
  26       virtual bool update(V *v) = 0;
  27   };
  28
  29   bool _find(const K& key, V *value, UpdateContext *ctx);
  30   void _add(const K& key, V& value);
  31
  32 public:
  33   lru_map(int _max) : lock("lru_map"), max(_max) {}
  34   virtual ~lru_map() {}
  35
  36   bool find(const K& key, V& value);
  37
  38   /*
  39    * find_and_update()
  40    *
  41    * - will return true if object is found
  42    * - if ctx is set will return true if object is found and updated
  43    */
  44   bool find_and_update(const K& key, V *value, UpdateContext *ctx);
  45   void add(const K& key, V& value);
  46   void erase(const K& key);
  47 };
  48
  49 template <class K, class V>
  50 bool lru_map<K, V>::_find(const K& key, V *value, UpdateContext *ctx)
  51 {
  52   typename std::map<K, entry>::iterator iter = entries.find(key);
  53   if (iter == entries.end()) {
  54     return false;
  55   }
  56
  57   entry& e = iter->second;
  58   entries_lru.erase(e.lru_iter);
  59
  60   bool r = true;
  61
  62   if (ctx)
  63     r = ctx->update(&e.value);
  64
  65   if (value)
  66     *value = e.value;
  67
  68   entries_lru.push_front(key);
  69   e.lru_iter = entries_lru.begin();
  70
  71   return r;
  72 }
  73
  74 template <class K, class V>
  75 bool lru_map<K, V>::find(const K& key, V& value)
  76 {
  77   Mutex::Locker l(lock);
  78   return _find(key, &value, NULL);
  79 }
  80
  81 template <class K, class V>
  82 bool lru_map<K, V>::find_and_update(const K& key, V *value, UpdateContext *ctx)
  83 {
  84   Mutex::Locker l(lock);
  85   return _find(key, value, ctx);
  86 }
  87
  88 template <class K, class V>
  89 void lru_map<K, V>::_add(const K& key, V& value)
  90 {
  91   typename std::map<K, entry>::iterator iter = entries.find(key);
  92   if (iter != entries.end()) {
  93     entry& e = iter->second;
  94     entries_lru.erase(e.lru_iter);
  95   }
  96
  97   entries_lru.push_front(key);
  98   entry& e = entries[key];
  99   e.value = value;
 100   e.lru_iter = entries_lru.begin();
 101
 102   while (entries.size() > max) {
 103     typename std::list<K>::reverse_iterator riter = entries_lru.rbegin();
 104     iter = entries.find(*riter);
 105     // assert(iter != entries.end());
 106     entries.erase(iter);
 107     entries_lru.pop_back();
 108   }
 109 }
 110
 111
 112 template <class K, class V>
 113 void lru_map<K, V>::add(const K& key, V& value)
 114 {
 115   Mutex::Locker l(lock);
 116   _add(key, value);
 117 }
 118
 119 template <class K, class V>
 120 void lru_map<K, V>::erase(const K& key)
 121 {
 122   Mutex::Locker l(lock);
 123   typename std::map<K, entry>::iterator iter = entries.find(key);
 124   if (iter == entries.end())
 125     return;
 126
 127   entry& e = iter->second;
 128   entries_lru.erase(e.lru_iter);
 129   entries.erase(iter);
 130 }
 131
 132 #endif