test

[VerusCoin.git] / src / mruset.h

diff --git a/src/mruset.h b/src/mruset.h
index b9f325d874acc161aac9c07df36a9bfb74a9a9b3..398aa173bf1e3c788e35a388116becc16d7ba201 100644 (file)
--- a/src/mruset.h
+++ b/src/mruset.h
@@ -1,16 +1,17 @@
-// Copyright (c) 2012 The Bitcoin developers
-// Distributed under the MIT/X11 software license, see the accompanying
+// Copyright (c) 2012-2015 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #ifndef BITCOIN_MRUSET_H
 #define BITCOIN_MRUSET_H
 
-#include <deque>
 #include <set>
+#include <vector>
 #include <utility>
 
 /** STL-like set container that only keeps the most recent N elements. */
-template <typename T> class mruset
+template <typename T>
+class mruset
 {
 public:
     typedef T key_type;
@@ -21,47 +22,44 @@ public:
 
 protected:
     std::set<T> set;
-    std::deque<T> queue;
-    size_type nMaxSize;
+    std::vector<iterator> order;
+    size_type first_used;
+    size_type first_unused;
+    const size_type nMaxSize;
 
 public:
-    mruset(size_type nMaxSizeIn = 0) { nMaxSize = nMaxSizeIn; }
+    mruset(size_type nMaxSizeIn = 1) : nMaxSize(nMaxSizeIn) { clear(); }
     iterator begin() const { return set.begin(); }
     iterator end() const { return set.end(); }
     size_type size() const { return set.size(); }
     bool empty() const { return set.empty(); }
     iterator find(const key_type& k) const { return set.find(k); }
     size_type count(const key_type& k) const { return set.count(k); }
-    void clear() { set.clear(); queue.clear(); }
+    void clear()
+    {
+        set.clear();
+        order.assign(nMaxSize, set.end());
+        first_used = 0;
+        first_unused = 0;
+    }
     bool inline friend operator==(const mruset<T>& a, const mruset<T>& b) { return a.set == b.set; }
     bool inline friend operator==(const mruset<T>& a, const std::set<T>& b) { return a.set == b; }
     bool inline friend operator<(const mruset<T>& a, const mruset<T>& b) { return a.set < b.set; }
     std::pair<iterator, bool> insert(const key_type& x)
     {
         std::pair<iterator, bool> ret = set.insert(x);
-        if (ret.second)
-        {
-            if (nMaxSize && queue.size() == nMaxSize)
-            {
-                set.erase(queue.front());
-                queue.pop_front();
+        if (ret.second) {
+            if (set.size() == nMaxSize + 1) {
+                set.erase(order[first_used]);
+                order[first_used] = set.end();
+                if (++first_used == nMaxSize) first_used = 0;
             }
-            queue.push_back(x);
+            order[first_unused] = ret.first;
+            if (++first_unused == nMaxSize) first_unused = 0;
         }
         return ret;
     }
     size_type max_size() const { return nMaxSize; }
-    size_type max_size(size_type s)
-    {
-        if (s)
-            while (queue.size() > s)
-            {
-                set.erase(queue.front());
-                queue.pop_front();
-            }
-        nMaxSize = s;
-        return nMaxSize;
-    }
 };
 
 #endif // BITCOIN_MRUSET_H