src/mruset.h

   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 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     mruset(size_type nMaxSizeIn = 1) : nMaxSize(nMaxSizeIn) { clear(); }
  32     iterator begin() const { return set.begin(); }
  33     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     size_type count(const key_type& k) const { return set.count(k); }
  38     void clear()
  39     {
  40         set.clear();
  41         order.assign(nMaxSize, set.end());
  42         first_used = 0;
  43         first_unused = 0;
  44     }
  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     std::pair<iterator, bool> insert(const key_type& x)
  49     {
  50         std::pair<iterator, bool> ret = set.insert(x);
  51         if (ret.second) {
  52             if (set.size() == nMaxSize + 1) {
  53                 set.erase(order[first_used]);
  54                 order[first_used] = set.end();
  55                 if (++first_used == nMaxSize) first_used = 0;
  56             }
  57             order[first_unused] = ret.first;
  58             if (++first_unused == nMaxSize) first_unused = 0;
  59         }
  60         return ret;
  61     }
  62     size_type max_size() const { return nMaxSize; }
  63 };
  64
  65 #endif // BITCOIN_MRUSET_H