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         586 :     explicit unordered_limitedmap(size_type nMaxSizeIn, size_type nPruneAfterSizeIn = 0)
      35         293 :     {
      36         293 :         assert(nMaxSizeIn > 0);
      37         293 :         nMaxSize = nMaxSizeIn;
      38         293 :         if (nPruneAfterSizeIn == 0) {
      39           1 :             nPruneAfterSize = nMaxSize;
      40           1 :         } else {
      41         292 :             nPruneAfterSize = nPruneAfterSizeIn;
      42             :         }
      43         293 :         assert(nPruneAfterSize >= nMaxSize);
      44         586 :     }
      45           1 :     const_iterator begin() const { return map.begin(); }
      46           1 :     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          30 :     const_iterator find(const key_type& k) const { return map.find(k); }
      50          22 :     size_type count(const key_type& k) const { return map.count(k); }
      51          11 :     void insert(const value_type& x)
      52             :     {
      53          11 :         std::pair<iterator, bool> ret = map.insert(x);
      54          11 :         if (ret.second)
      55          11 :             prune();
      56          11 :     }
      57          14 :     void erase(const key_type& k)
      58             :     {
      59          14 :         map.erase(k);
      60          14 :     }
      61          10 :     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          10 :         iterator itTarget = map.erase(itIn, itIn);
      67          10 :         if (itTarget == map.end())
      68           0 :             return;
      69          10 :         itTarget->second = v;
      70          10 :     }
      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          12 :     void prune()
      86             :     {
      87          12 :         if (map.size() <= nPruneAfterSize) {
      88          10 :             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          12 :     }
     108             : };
     109             : 
     110             : #endif // BITCOIN_LIMITEDMAP_H