Line data    Source code

       1             : // Copyright (c) 2012-2015 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 <algorithm>
      10             : #include <unordered_map>
      11             : #include <vector>
      12             : 
      13             : /** STL-like map container that only keeps the N elements with the highest value. */
      14             : // WARNING, this was initially the "limitedmap" class from Bitcoin, but now does not maintain ordering. If any backports
      15             : // ever start using this map in a way that requires ordering, do NOT use this as it is but instead reintroduce the original
      16             : // limitedmap
      17             : template <typename K, typename V, typename Hash = std::hash<K>>
      18             : class unordered_limitedmap
      19             : {
      20             : public:
      21             :     typedef K key_type;
      22             :     typedef V mapped_type;
      23             :     typedef std::pair<const key_type, mapped_type> value_type;
      24             :     typedef typename std::unordered_map<K, V, Hash>::const_iterator const_iterator;
      25             :     typedef typename std::unordered_map<K, V, Hash>::size_type size_type;
      26             : 
      27             : protected:
      28             :     std::unordered_map<K, V, Hash> map;
      29             :     typedef typename std::unordered_map<K, V, Hash>::iterator iterator;
      30             :     size_type nMaxSize;
      31             :     size_type nPruneAfterSize;
      32             : 
      33             : public:
      34       13234 :     explicit unordered_limitedmap(size_type nMaxSizeIn, size_type nPruneAfterSizeIn = 0)
      35        6617 :     {
      36        6617 :         assert(nMaxSizeIn > 0);
      37        6617 :         nMaxSize = nMaxSizeIn;
      38        6617 :         if (nPruneAfterSizeIn == 0) {
      39           1 :             nPruneAfterSize = nMaxSize;
      40           1 :         } else {
      41        6616 :             nPruneAfterSize = nPruneAfterSizeIn;
      42             :         }
      43        6617 :         assert(nPruneAfterSize >= nMaxSize);
      44       13234 :     }
      45           1 :     const_iterator begin() const { return map.begin(); }
      46      190652 :     const_iterator end() const { return map.end(); }
      47           5 :     size_type size() const { return map.size(); }
      48           1 :     bool empty() const { return map.empty(); }
      49      190681 :     const_iterator find(const key_type& k) const { return map.find(k); }
      50       77477 :     size_type count(const key_type& k) const { return map.count(k); }
      51      135235 :     void insert(const value_type& x)
      52             :     {
      53      135235 :         std::pair<iterator, bool> ret = map.insert(x);
      54      135235 :         if (ret.second)
      55      125567 :             prune();
      56      135235 :     }
      57       83708 :     void erase(const key_type& k)
      58             :     {
      59       83708 :         map.erase(k);
      60       83708 :     }
      61         132 :     void update(const_iterator itIn, const mapped_type& v)
      62             :     {
      63             :         // Using map::erase() with empty range instead of map::find() to get a non-const iterator,
      64             :         // since it is a constant time operation in C++11. For more details, see
      65             :         // https://stackoverflow.com/questions/765148/how-to-remove-constness-of-const-iterator
      66         132 :         iterator itTarget = map.erase(itIn, itIn);
      67         132 :         if (itTarget == map.end())
      68           0 :             return;
      69         132 :         itTarget->second = v;
      70         132 :     }
      71           2 :     size_type max_size() const { return nMaxSize; }
      72           1 :     size_type max_size(size_type nMaxSizeIn, size_type nPruneAfterSizeIn = 0)
      73             :     {
      74           1 :         assert(nMaxSizeIn > 0);
      75           1 :         nMaxSize = nMaxSizeIn;
      76           1 :         if (nPruneAfterSizeIn == 0) {
      77           1 :             nPruneAfterSize = nMaxSize;
      78           1 :         } else {
      79           0 :             nPruneAfterSize = nPruneAfterSizeIn;
      80             :         }
      81           1 :         assert(nPruneAfterSize >= nMaxSize);
      82           1 :         prune();
      83           1 :         return nMaxSize;
      84             :     }
      85      125568 :     void prune()
      86             :     {
      87      125568 :         if (map.size() <= nPruneAfterSize) {
      88      125566 :             return;
      89             :         }
      90             : 
      91           2 :         std::vector<iterator> sortedIterators;
      92           2 :         sortedIterators.reserve(map.size());
      93          23 :         for (auto it = map.begin(); it != map.end(); ++it) {
      94          21 :             sortedIterators.emplace_back(it);
      95          21 :         }
      96          96 :         std::sort(sortedIterators.begin(), sortedIterators.end(), [](const iterator& it1, const iterator& it2) {
      97          94 :             return it1->second < it2->second;
      98             :         });
      99             : 
     100           2 :         size_type tooMuch = map.size() - nMaxSize;
     101           2 :         assert(tooMuch > 0);
     102           2 :         sortedIterators.resize(tooMuch);
     103             : 
     104           8 :         for (auto& it : sortedIterators) {
     105           6 :             map.erase(it);
     106             :         }
     107      125568 :     }
     108             : };
     109             : 
     110             : #endif // BITCOIN_LIMITEDMAP_H