From 0f87a483a4c145dd0e1affb1b17642fad408b777 Mon Sep 17 00:00:00 2001
From: Francesco Chemolli <kinkie@squid-cache.org>
Date: Tue, 11 Feb 2014 12:22:39 +0100
Subject: [PATCH] Refactor Splay and MemPoolMalloc to use std::stack

---
 include/MemPoolMalloc.h |  4 +++-
 include/splay.h         | 25 +++++++++++++++++--------
 2 files changed, 20 insertions(+), 9 deletions(-)

diff --git a/include/MemPoolMalloc.h b/include/MemPoolMalloc.h
index 2999dd4620..43064203ea 100644
--- a/include/MemPoolMalloc.h
+++ b/include/MemPoolMalloc.h
@@ -22,6 +22,8 @@
 
 #include "MemPool.h"
 
+#include <stack>
+
 /// \ingroup MemPoolsAPI
 class MemPoolMalloc : public MemImplementingAllocator
 {
@@ -42,7 +44,7 @@ protected:
     virtual void *allocate();
     virtual void deallocate(void *, bool aggressive);
 private:
-    Stack<void *> freelist;
+    std::stack<void *> freelist;
 };
 
 #endif /* _MEM_POOL_MALLOC_H_ */
diff --git a/include/splay.h b/include/splay.h
index ea4f2c3e03..daafdd19b6 100644
--- a/include/splay.h
+++ b/include/splay.h
@@ -3,7 +3,9 @@
 
 #if defined(__cplusplus)
 
-#include "Stack.h"
+#include "fatal.h"
+
+#include <stack>
 
 template <class V>
 class SplayNode
@@ -376,7 +378,7 @@ private:
     void advance();
     void addLeftPath(SplayNode<V> *aNode);
     void init(SplayNode<V> *);
-    Stack<SplayNode<V> *> toVisit;
+    std::stack<SplayNode<V> *> toVisit;
 };
 
 template <class V>
@@ -389,7 +391,12 @@ template <class V>
 bool
 SplayConstIterator<V>::operator == (SplayConstIterator const &right) const
 {
-    return toVisit.top() == right.toVisit.top();
+    if (toVisit.empty() && right.toVisit.empty())
+        return true;
+    if (!toVisit.empty() && !right.toVisit.empty())
+        return toVisit.top() == right.toVisit.top();
+    // only one of the two is empty
+    return false;
 }
 
 template <class V>
@@ -421,19 +428,21 @@ template <class V>
 void
 SplayConstIterator<V>::advance()
 {
-    if (toVisit.size() == 0)
+    if (toVisit.empty())
         return;
 
     toVisit.pop();
 
-    if (toVisit.size() == 0)
+    if (toVisit.empty())
         return;
 
-    SplayNode<V> *currentNode = toVisit.pop();
+    // not empty
+    SplayNode<V> *currentNode = toVisit.top();
+    toVisit.pop();
 
     addLeftPath(currentNode->right);
 
-    toVisit.push_back(currentNode);
+    toVisit.push(currentNode);
 }
 
 template <class V>
@@ -444,7 +453,7 @@ SplayConstIterator<V>::addLeftPath(SplayNode<V> *aNode)
         return;
 
     do {
-        toVisit.push_back(aNode);
+        toVisit.push(aNode);
         aNode = aNode->left;
     } while (aNode != NULL);
 }
-- 
2.47.2