Line data    Source code

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