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_MRUSET_H
       6             : #define BITCOIN_MRUSET_H
       7             : 
       8             : #include <set>
       9             : #include <vector>
      10             : #include <utility>
      11             : 
      12             : /** STL-like set container that only keeps the most recent N elements. */
      13             : template <typename T>
      14        1642 : class mruset
      15             : {
      16             : public:
      17             :     typedef T key_type;
      18             :     typedef T value_type;
      19             :     typedef typename std::set<T>::iterator iterator;
      20             :     typedef typename std::set<T>::const_iterator const_iterator;
      21             :     typedef typename std::set<T>::size_type size_type;
      22             : 
      23             : protected:
      24             :     std::set<T> set;
      25             :     std::vector<iterator> order;
      26             :     size_type first_used;
      27             :     size_type first_unused;
      28             :     const size_type nMaxSize;
      29             : 
      30             : public:
      31        1092 :     mruset(size_type nMaxSizeIn = 1) : nMaxSize(nMaxSizeIn) { clear(); }
      32         220 :     iterator begin() const { return set.begin(); }
      33         220 :     iterator end() const { return set.end(); }
      34             :     size_type size() const { return set.size(); }
      35             :     bool empty() const { return set.empty(); }
      36             :     iterator find(const key_type& k) const { return set.find(k); }
      37      778790 :     size_type count(const key_type& k) const { return set.count(k); }
      38         374 :     void clear()
      39             :     {
      40         374 :         set.clear();
      41        1122 :         order.assign(nMaxSize, set.end());
      42         374 :         first_used = 0;
      43         374 :         first_unused = 0;
      44         374 :     }
      45             :     bool inline friend operator==(const mruset<T>& a, const mruset<T>& b) { return a.set == b.set; }
      46             :     bool inline friend operator==(const mruset<T>& a, const std::set<T>& b) { return a.set == b; }
      47             :     bool inline friend operator<(const mruset<T>& a, const mruset<T>& b) { return a.set < b.set; }
      48      120726 :     std::pair<iterator, bool> insert(const key_type& x)
      49             :     {
      50      241452 :         std::pair<iterator, bool> ret = set.insert(x);
      51      120726 :         if (ret.second) {
      52      183780 :             if (set.size() == nMaxSize + 1) {
      53       52348 :                 set.erase(order[first_used]);
      54       78522 :                 order[first_used] = set.end();
      55       26174 :                 if (++first_used == nMaxSize) first_used = 0;
      56             :             }
      57      183780 :             order[first_unused] = ret.first;
      58       91890 :             if (++first_unused == nMaxSize) first_unused = 0;
      59             :         }
      60      120726 :         return ret;
      61             :     }
      62             :     size_type max_size() const { return nMaxSize; }
      63             : };
      64             : 
      65             : #endif // BITCOIN_MRUSET_H