lru_map: infrastructure for a bounded map

Useful for cache-like maps, where we want to control
the max number of entries in the map.

Signed-off-by: Yehuda Sadeh <yehuda@inktank.com>

2 files changed, 95 insertions, 0 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 523bb8ccccc..a45dd4e9830 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -1697,6 +1697,7 @@ noinst_HEADERS = \
 	common/ceph_crypto.h\
 	common/ceph_crypto_cms.h\
 	common/ceph_json.h\
+	common/lru_map.h\
 	common/utf8.h\
 	common/mime.h\
 	common/pick_address.h\
diff --git a/src/common/lru_map.h b/src/common/lru_map.h
new file mode 100644
index 00000000000..fb637478884
--- /dev/null
+++ b/src/common/lru_map.h
@@ -0,0 +1,94 @@
+#ifndef CEPH_LRU_MAP_H
+#define CEPH_LRU_MAP_H
+
+#include <list>
+#include <map>
+#include "common/Mutex.h"
+
+
+template <class K, class V>
+class lru_map {
+  struct entry {
+    V value;
+    typename std::list<K>::iterator lru_iter;
+  };
+
+  std::map<K, entry> tokens;
+  std::list<K> tokens_lru;
+
+  Mutex lock;
+
+  size_t max;
+
+public:
+  lru_map(int _max) : lock("lru_map"), max(_max) {}
+  virtual ~lru_map() {}
+
+  bool find(const K& key, V& value);
+  void add(const K& key, V& value);
+  void erase(const K& key);
+};
+
+template <class K, class V>
+bool lru_map<K, V>::find(const K& key, V& value)
+{
+  lock.Lock();
+  typename std::map<K, entry>::iterator iter = tokens.find(key);
+  if (iter == tokens.end()) {
+    lock.Unlock();
+    return false;
+  }
+
+  entry& e = iter->second;
+  tokens_lru.erase(e.lru_iter);
+
+  value = e.value;
+
+  tokens_lru.push_front(key);
+  e.lru_iter = tokens_lru.begin();
+
+  lock.Unlock();
+
+  return true;
+}
+
+template <class K, class V>
+void lru_map<K, V>::add(const K& key, V& value)
+{
+  lock.Lock();
+  typename std::map<K, entry>::iterator iter = tokens.find(key);
+  if (iter != tokens.end()) {
+    entry& e = iter->second;
+    tokens_lru.erase(e.lru_iter);
+  }
+
+  tokens_lru.push_front(key);
+  entry& e = tokens[key];
+  e.value = value;
+  e.lru_iter = tokens_lru.begin();
+
+  while (tokens_lru.size() > max) {
+    typename std::list<K>::reverse_iterator riter = tokens_lru.rbegin();
+    iter = tokens.find(*riter);
+    // assert(iter != tokens.end());
+    tokens.erase(iter);
+    tokens_lru.pop_back();
+  }
+  
+  lock.Unlock();
+}
+
+template <class K, class V>
+void lru_map<K, V>::erase(const K& key)
+{
+  Mutex::Locker l(lock);
+  typename std::map<K, entry>::iterator iter = tokens.find(key);
+  if (iter == tokens.end())
+    return;
+
+  entry& e = iter->second;
+  tokens_lru.erase(e.lru_iter);
+  tokens.erase(iter);
+}
+
+#endif