Line data    Source code

       1             : // Copyright (c) 2012-2014 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         291 : 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          97 :     limitedmap(size_type nMaxSizeIn)
      31         194 :     {
      32          97 :         assert(nMaxSizeIn > 0);
      33          97 :         nMaxSize = nMaxSizeIn;
      34          97 :     }
      35           1 :     const_iterator begin() const { return map.begin(); }
      36        1037 :     const_iterator end() const { return map.end(); }
      37           5 :     size_type size() const { return map.size(); }
      38           1 :     bool empty() const { return map.empty(); }
      39         538 :     const_iterator find(const key_type& k) const { return map.find(k); }
      40          22 :     size_type count(const key_type& k) const { return map.count(k); }
      41         374 :     void insert(const value_type& x)
      42             :     {
      43         748 :         std::pair<iterator, bool> ret = map.insert(x);
      44         374 :         if (ret.second) {
      45         748 :             if (map.size() > nMaxSize) {
      46           3 :                 map.erase(rmap.begin()->second);
      47           2 :                 rmap.erase(rmap.begin());
      48             :             }
      49        1122 :             rmap.insert(make_pair(x.second, ret.first));
      50             :         }
      51         374 :     }
      52         377 :     void erase(const key_type& k)
      53             :     {
      54         754 :         iterator itTarget = map.find(k);
      55         754 :         if (itTarget == map.end())
      56             :             return;
      57         736 :         std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
      58         736 :         for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
      59         736 :             if (it->second == itTarget) {
      60         368 :                 rmap.erase(it);
      61         368 :                 map.erase(itTarget);
      62             :                 return;
      63             :             }
      64             :         // Shouldn't ever get here
      65           0 :         assert(0);
      66             :     }
      67         165 :     void update(const_iterator itIn, const mapped_type& v)
      68             :     {
      69             :         // TODO: When we switch to C++11, use map.erase(itIn, itIn) to get the non-const iterator.
      70         330 :         iterator itTarget = map.find(itIn->first);
      71         330 :         if (itTarget == map.end())
      72             :             return;
      73         330 :         std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
      74         330 :         for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
      75         330 :             if (it->second == itTarget) {
      76         165 :                 rmap.erase(it);
      77         165 :                 itTarget->second = v;
      78         495 :                 rmap.insert(make_pair(v, itTarget));
      79             :                 return;
      80             :             }
      81             :         // Shouldn't ever get here
      82           0 :         assert(0);
      83             :     }
      84           0 :     size_type max_size() const { return nMaxSize; }
      85           1 :     size_type max_size(size_type s)
      86             :     {
      87           1 :         assert(s > 0);
      88          12 :         while (map.size() > s) {
      89          15 :             map.erase(rmap.begin()->second);
      90          10 :             rmap.erase(rmap.begin());
      91             :         }
      92           1 :         nMaxSize = s;
      93           1 :         return nMaxSize;
      94             :     }
      95             : };
      96             : 
      97             : #endif // BITCOIN_LIMITEDMAP_H