src/limitedmap.h

   1 // Copyright (c) 2012-2016 The Bitcoin Core developers
   2 // Distributed under the MIT software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #ifndef BITCOIN_LIMITEDMAP_H
   6 #define BITCOIN_LIMITEDMAP_H
   7
   8 #include <assert.h>
   9 #include <map>
  10
  11 /** STL-like map container that only keeps the N elements with the highest value. */
  12 template <typename K, typename V>
  13 class limitedmap
  14 {
  15 public:
  16     typedef K key_type;
  17     typedef V mapped_type;
  18     typedef std::pair<const key_type, mapped_type> value_type;
  19     typedef typename std::map<K, V>::const_iterator const_iterator;
  20     typedef typename std::map<K, V>::size_type size_type;
  21
  22 protected:
  23     std::map<K, V> map;
  24     typedef typename std::map<K, V>::iterator iterator;
  25     std::multimap<V, iterator> rmap;
  26     typedef typename std::multimap<V, iterator>::iterator rmap_iterator;
  27     size_type nMaxSize;
  28
  29 public:
  30     explicit limitedmap(size_type nMaxSizeIn)
  31     {
  32         assert(nMaxSizeIn > 0);
  33         nMaxSize = nMaxSizeIn;
  34     }
  35     const_iterator begin() const { return map.begin(); }
  36     const_iterator end() const { return map.end(); }
  37     size_type size() const { return map.size(); }
  38     bool empty() const { return map.empty(); }
  39     const_iterator find(const key_type& k) const { return map.find(k); }
  40     size_type count(const key_type& k) const { return map.count(k); }
  41     void insert(const value_type& x)
  42     {
  43         std::pair<iterator, bool> ret = map.insert(x);
  44         if (ret.second) {
  45             if (map.size() > nMaxSize) {
  46                 map.erase(rmap.begin()->second);
  47                 rmap.erase(rmap.begin());
  48             }
  49             rmap.insert(make_pair(x.second, ret.first));
  50         }
  51     }
  52     void erase(const key_type& k)
  53     {
  54         iterator itTarget = map.find(k);
  55         if (itTarget == map.end())
  56             return;
  57         std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
  58         for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
  59             if (it->second == itTarget) {
  60                 rmap.erase(it);
  61                 map.erase(itTarget);
  62                 return;
  63             }
  64         // Shouldn't ever get here
  65         assert(0);
  66     }
  67     void update(const_iterator itIn, const mapped_type& v)
  68     {
  69         // Using map::erase() with empty range instead of map::find() to get a non-const iterator,
  70         // since it is a constant time operation in C++11. For more details, see
  71         // https://stackoverflow.com/questions/765148/how-to-remove-constness-of-const-iterator
  72         iterator itTarget = map.erase(itIn, itIn);
  73
  74         if (itTarget == map.end())
  75             return;
  76         std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
  77         for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
  78             if (it->second == itTarget) {
  79                 rmap.erase(it);
  80                 itTarget->second = v;
  81                 rmap.insert(make_pair(v, itTarget));
  82                 return;
  83             }
  84         // Shouldn't ever get here
  85         assert(0);
  86     }
  87     size_type max_size() const { return nMaxSize; }
  88     size_type max_size(size_type s)
  89     {
  90         assert(s > 0);
  91         while (map.size() > s) {
  92             map.erase(rmap.begin()->second);
  93             rmap.erase(rmap.begin());
  94         }
  95         nMaxSize = s;
  96         return nMaxSize;
  97     }
  98 };
  99
 100 #endif // BITCOIN_LIMITEDMAP_H