src/mruset.h

   1 // Copyright (c) 2012 The Bitcoin developers
   2 // Distributed under the MIT/X11 software license, see the accompanying
   3 // file license.txt or http://www.opensource.org/licenses/mit-license.php.
   4 #ifndef BITCOIN_MRUSET_H
   5 #define BITCOIN_MRUSET_H
   6
   7 #include <set>
   8 #include <deque>
   9
  10 template <typename T> class mruset
  11 {
  12 public:
  13     typedef T key_type;
  14     typedef T value_type;
  15     typedef typename std::set<T>::iterator iterator;
  16     typedef typename std::set<T>::const_iterator const_iterator;
  17     typedef typename std::set<T>::size_type size_type;
  18
  19 protected:
  20     std::set<T> set;
  21     std::deque<T> queue;
  22     size_type nMaxSize;
  23
  24 public:
  25     mruset(size_type nMaxSizeIn = 0) { nMaxSize = nMaxSizeIn; }
  26     iterator begin() const { return set.begin(); }
  27     iterator end() const { return set.end(); }
  28     size_type size() const { return set.size(); }
  29     bool empty() const { return set.empty(); }
  30     iterator find(const key_type& k) const { return set.find(k); }
  31     size_type count(const key_type& k) const { return set.count(k); }
  32     bool inline friend operator==(const mruset<T>& a, const mruset<T>& b) { return a.set == b.set; }
  33     bool inline friend operator==(const mruset<T>& a, const std::set<T>& b) { return a.set == b; }
  34     bool inline friend operator<(const mruset<T>& a, const mruset<T>& b) { return a.set < b.set; }
  35     std::pair<iterator, bool> insert(const key_type& x)
  36     {
  37         std::pair<iterator, bool> ret = set.insert(x);
  38         if (ret.second)
  39         {
  40             if (nMaxSize && queue.size() == nMaxSize)
  41             {
  42                 set.erase(queue.front());
  43                 queue.pop_front();
  44             }
  45             queue.push_back(x);
  46         }
  47         return ret;
  48     }
  49     size_type max_size() const { return nMaxSize; }
  50     size_type max_size(size_type s)
  51     {
  52         if (s)
  53             while (queue.size() >= s)
  54             {
  55                 set.erase(queue.front());
  56                 queue.pop_front();
  57             }
  58         nMaxSize = s;
  59         return nMaxSize;
  60     }
  61 };
  62
  63 #endif