From b8bad68c16e839f9a8a4575439bb24a977c01dd2 Mon Sep 17 00:00:00 2001
From: robertc <>
Date: Mon, 22 Sep 2003 14:50:50 +0000
Subject: [PATCH] Summary: Implement mem_hdr debugging. Keywords:

Implement Array copy constructor.
Implement Iterators for Splay trees.
Implement tests for the above.
Implement a debug call to use the above.
---
 include/Array.h            |  14 +++-
 include/Range.h            |  11 ++-
 include/splay.h            | 138 ++++++++++++++++++++++++++++++++++++-
 src/Generic.h              |  30 +++++++-
 src/mem_node.h             |   8 ++-
 src/stmem.cc               |  36 +++++++---
 src/stmem.h                |   3 +-
 test-suite/mem_hdr_test.cc |  21 +++---
 8 files changed, 234 insertions(+), 27 deletions(-)

diff --git a/include/Array.h b/include/Array.h
index a07cb34889..94484e4490 100644
--- a/include/Array.h
+++ b/include/Array.h
@@ -1,5 +1,5 @@
 /*
- * $Id: Array.h,v 1.15 2003/07/15 06:50:38 robertc Exp $
+ * $Id: Array.h,v 1.16 2003/09/22 08:50:51 robertc Exp $
  *
  * AUTHOR: Alex Rousskov
  *
@@ -212,6 +212,18 @@ Vector<E>::preAppend(int app_count)
         reserve(size() + app_count);
 }
 
+template<class E>
+Vector<E>::Vector<E> (Vector const &rhs)
+{
+    items = NULL;
+    capacity = 0;
+    count = 0;
+    reserve (rhs.size());
+
+    for (size_t counter = 0; counter < rhs.size(); ++counter)
+        push_back (rhs.items[counter]);
+}
+
 template<class E>
 Vector<E> &
 Vector<E>::operator = (Vector const &old)
diff --git a/include/Range.h b/include/Range.h
index ac302d8d99..1fcafb2dfe 100644
--- a/include/Range.h
+++ b/include/Range.h
@@ -1,6 +1,6 @@
 
 /*
- * $Id: Range.h,v 1.4 2003/06/09 03:10:00 robertc Exp $
+ * $Id: Range.h,v 1.5 2003/09/22 08:50:51 robertc Exp $
  *
  *
  * SQUID Web Proxy Cache          http://www.squid-cache.org/
@@ -34,6 +34,8 @@
 #ifndef SQUID_RANGE_H
 #define SQUID_RANGE_H
 
+#include <iosfwd>
+
 /* represents [start, end) */
 
 template <class C>
@@ -50,6 +52,13 @@ public:
     size_t size() const;
 };
 
+template <class C>
+std::ostream& operator << (std::ostream &os, Range<C> const &aRange)
+{
+    os << "[" << aRange.start << "," << aRange.end << ")";
+    return os;
+}
+
 template<class C>
 Range<C>::Range () : start(), end() {}
 
diff --git a/include/splay.h b/include/splay.h
index dfc46ddd46..96be7ca714 100644
--- a/include/splay.h
+++ b/include/splay.h
@@ -1,5 +1,5 @@
 /*
- * $Id: splay.h,v 1.25 2003/09/22 03:31:03 robertc Exp $
+ * $Id: splay.h,v 1.26 2003/09/22 08:50:51 robertc Exp $
  */
 
 #ifndef SQUID_SPLAY_H
@@ -31,6 +31,7 @@ SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, SPLAYCMP *);
 SQUIDCEXTERN void splay_walk(splayNode *, SPLAYWALKEE *, void *);
 #else
 
+#include "Stack.h"
 
 template <class V>
 
@@ -65,6 +66,10 @@ typedef SplayNode<void *> splayNode;
 
 template <class V>
 
+class SplayConstIterator;
+
+template <class V>
+
 class SplayIterator;
 
 template <class V>
@@ -76,6 +81,8 @@ public:
     typedef V Value;
     typedef int SPLAYCMP(Value const &a, Value const &b);
     typedef void SPLAYFREE(Value &);
+    typedef SplayIterator<V> iterator;
+    typedef const SplayConstIterator<V> const_iterator;
     Splay():head(NULL), elements (0){}
 
     mutable SplayNode<V> * head;
@@ -93,6 +100,10 @@ public:
 
     size_t size() const;
 
+    const_iterator begin() const;
+
+    const_iterator end() const;
+
     size_t elements;
 };
 
@@ -369,6 +380,129 @@ Splay<V>::size() const
     return elements;
 }
 
-#endif
+template <class V>
+typename Splay<V>::const_iterator
+Splay<V>::begin() const
+{
+    return const_iterator(head);
+}
+
+template <class V>
+typename Splay<V>::const_iterator
+Splay<V>::end() const
+{
+    return const_iterator(NULL);
+}
+
+template <class V>
+
+class SplayConstIterator
+{
+
+public:
+    typedef const V value_type;
+    SplayConstIterator (SplayNode<V> *aNode);
+    bool operator == (SplayConstIterator const &right) const;
+    SplayConstIterator operator ++ (int dummy);
+    SplayConstIterator &operator ++ ();
+    V const & operator * () const;
+
+private:
+    void advance();
+    void addLeftPath(SplayNode<V> *aNode);
+    void init(SplayNode<V> *);
+    Stack<SplayNode<V> *> toVisit;
+};
+
+template <class V>
+SplayConstIterator<V>::SplayConstIterator (SplayNode<V> *aNode)
+{
+    init(aNode);
+}
+
+template <class V>
+bool
+SplayConstIterator<V>::operator == (SplayConstIterator const &right) const
+{
+    return toVisit.top() == right.toVisit.top();
+}
+
+template <class V>
+SplayConstIterator<V> &
+SplayConstIterator<V>::operator ++ ()
+{
+    advance();
+    return *this;
+}
+
+template <class V>
+SplayConstIterator<V>
+SplayConstIterator<V>::operator ++ (int dummy)
+{
+    SplayConstIterator<V> result = *this;
+    advance();
+    return result;
+}
+
+/* advance is simple enough:
+* if the stack is empty, we're done.
+* otherwise, pop the last visited node
+* then, pop the next node to visit
+* if that has a right child, add it and it's
+* left-to-end path.
+* then add the node back.
+*/
+template <class V>
+void
+SplayConstIterator<V>::advance()
+{
+    if (toVisit.size() == 0)
+        return;
+
+    toVisit.pop();
+
+    if (toVisit.size() == 0)
+        return;
+
+    SplayNode<V> *currentNode = toVisit.pop();
+
+    addLeftPath(currentNode->right);
+
+    toVisit.push_back(currentNode);
+}
+
+template <class V>
+void
+SplayConstIterator<V>::addLeftPath(SplayNode<V> *aNode)
+{
+    if (aNode == NULL)
+        return;
+
+    do {
+        toVisit.push_back(aNode);
+        aNode = aNode->left;
+    } while (aNode != NULL);
+}
+
+template <class V>
+void
+SplayConstIterator<V>::init(SplayNode<V> *head)
+{
+    addLeftPath(head);
+}
+
+template <class V>
+V const &
+SplayConstIterator<V>::operator * () const
+{
+    /* can't dereference when past the end */
+
+    if (toVisit.size() == 0)
+        fatal ("Attempt to dereference SplayConstIterator past-the-end\n");
+
+    return toVisit.top()->data;
+}
+
+#endif /* cplusplus */
 
 #endif /* SQUID_SPLAY_H */
diff --git a/src/Generic.h b/src/Generic.h
index 7eaa0f2ffa..9dbb017ccb 100644
--- a/src/Generic.h
+++ b/src/Generic.h
@@ -1,6 +1,6 @@
 
 /*
- * $Id: Generic.h,v 1.5 2003/07/14 10:36:41 robertc Exp $
+ * $Id: Generic.h,v 1.6 2003/09/22 08:50:51 robertc Exp $
  *
  *
  * SQUID Web Proxy Cache          http://www.squid-cache.org/
@@ -73,4 +73,32 @@ T& for_each(Stack<E> const &collection, T& visitor)
     return visitor;
 };
 
+template <class InputIterator , class Visitor>
+Visitor& for_each(InputIterator from, InputIterator to, Visitor& visitor)
+{
+    while (!(from == to)) {
+        typename InputIterator::value_type &value = *from;
+        ++from;
+        visitor(value);
+    }
+
+    return visitor;
+}
+
+/* generic ostream printer */
+template <class Pointer>
+
+struct PointerPrinter
+{
+    PointerPrinter(std::ostream &astream, std::string aDelimiter) : os(astream), delimiter (aDelimiter) {}
+
+    void operator () (Pointer aNode)
+    {
+        os << *aNode << delimiter;
+    }
+
+    std::ostream &os;
+    std::string delimiter;
+};
+
 #endif /* SQUID_GENERIC_H */
diff --git a/src/mem_node.h b/src/mem_node.h
index 016c63d976..1fe3bd4c0c 100644
--- a/src/mem_node.h
+++ b/src/mem_node.h
@@ -1,6 +1,6 @@
 
 /*
- * $Id: mem_node.h,v 1.5 2003/08/04 22:14:42 robertc Exp $
+ * $Id: mem_node.h,v 1.6 2003/09/22 08:50:51 robertc Exp $
  *
  *
  * SQUID Web Proxy Cache          http://www.squid-cache.org/
@@ -64,5 +64,11 @@ private:
     static MemPool *pool;
 };
 
+inline std::ostream &
+operator << (std::ostream &os, mem_node &aNode)
+{
+    os << aNode.nodeBuffer.range();
+    return os;
+}
 
 #endif /* SQUID_MEM_NODE_H */
diff --git a/src/stmem.cc b/src/stmem.cc
index 3998a2b2f8..0ad1a12cfa 100644
--- a/src/stmem.cc
+++ b/src/stmem.cc
@@ -1,6 +1,6 @@
 
 /*
- * $Id: stmem.cc,v 1.81 2003/09/06 12:47:35 robertc Exp $
+ * $Id: stmem.cc,v 1.82 2003/09/22 08:50:50 robertc Exp $
  *
  * DEBUG: section 19    Store Memory Primitives
  * AUTHOR: Harvest Derived
@@ -38,6 +38,7 @@
 #include "stmem.h"
 #include "mem_node.h"
 #include "MemObject.h"
+#include "Generic.h"
 
 int
 mem_hdr::lowestOffset () const
@@ -54,7 +55,7 @@ off_t
 mem_hdr::endOffset () const
 {
     off_t result = 0;
-    const SplayNode<mem_node *> *theEnd = nodes.end();
+    const SplayNode<mem_node *> *theEnd = nodes.finish();
 
     if (theEnd)
         result = theEnd->data->dataRange().end;
@@ -85,7 +86,7 @@ mem_hdr::freeDataUpto(int target_offset)
 
     SplayNode<mem_node*> const * theStart = nodes.start();
 
-    while (theStart && theStart != nodes.end() &&
+    while (theStart && theStart != nodes.finish() &&
             theStart->data->end() <= (size_t) target_offset ) {
         unlink(theStart->data);
         theStart = nodes.start();
@@ -142,10 +143,10 @@ mem_hdr::makeAppendSpace()
         return;
     }
 
-    if (!nodes.end()->data->space())
+    if (!nodes.finish()->data->space())
         appendNode (new mem_node (endOffset()));
 
-    assert (nodes.end()->data->space());
+    assert (nodes.finish()->data->space());
 }
 
 void
@@ -155,7 +156,7 @@ mem_hdr::internalAppend(const char *data, int len)
 
     while (len > 0) {
         makeAppendSpace();
-        int copied = appendToNode (nodes.end()->data, data, len);
+        int copied = appendToNode (nodes.finish()->data, data, len);
         assert (copied);
 
         len -= copied;
@@ -198,6 +199,15 @@ mem_hdr::copyAvailable(mem_node *aNode, size_t location, size_t amount, char *ta
     return copyLen;
 }
 
+void
+mem_hdr::debugDump() const
+{
+    std::ostringstream result;
+    PointerPrinter<mem_node *> foo(result, " - ");
+    for_each (getNodes().begin(), getNodes().end(), foo);
+    debugs (19, 1, "mem_hdr::debugDump: Current available data is: " << result.str() << ".");
+}
+
 /* FIXME: how do we deal with sparse results -
  * where we have (say)
  * 0-500 and 1000-1500, but are asked for 
@@ -211,8 +221,11 @@ mem_hdr::copy(off_t offset, char *buf, size_t size) const
 
     debug(19, 6) ("memCopy: offset %ld: size %u\n", (long int) offset, size);
 
+    /* we shouldn't ever ask for absent offsets */
+
     if (nodes.size() == 0) {
-        /* we shouldn't ever ask for absent offsets */
+        debugs(19, 1, "mem_hdr::copy: No data to read");
+        debugDump();
         assert (0);
         return 0;
     }
@@ -225,6 +238,7 @@ mem_hdr::copy(off_t offset, char *buf, size_t size) const
 
     if (!p) {
         debug(19, 1) ("memCopy: could not find offset %u in memory.\n", (size_t) offset);
+        debugDump();
         /* we shouldn't ever ask for absent offsets */
         assert (0);
         return 0;
@@ -377,7 +391,7 @@ void
 mem_hdr::dump() const
 {
     debug(20, 1) ("mem_hdr: %p nodes.start() %p\n", this, nodes.start());
-    debug(20, 1) ("mem_hdr: %p nodes.end() %p\n", this, nodes.end());
+    debug(20, 1) ("mem_hdr: %p nodes.finish() %p\n", this, nodes.finish());
 }
 
 size_t
@@ -396,3 +410,9 @@ mem_hdr::start() const
 
     return NULL;
 }
+
+const Splay<mem_node *> &
+mem_hdr::getNodes() const
+{
+    return nodes;
+}
diff --git a/src/stmem.h b/src/stmem.h
index 4a99351501..798173b2fc 100644
--- a/src/stmem.h
+++ b/src/stmem.h
@@ -1,6 +1,6 @@
 
 /*
- * $Id: stmem.h,v 1.5 2003/09/22 03:31:03 robertc Exp $
+ * $Id: stmem.h,v 1.6 2003/09/22 08:50:51 robertc Exp $
  *
  *
  * SQUID Web Proxy Cache          http://www.squid-cache.org/
@@ -72,6 +72,7 @@ public:
     static SplayNode<mem_node *>::SPLAYCMP NodeCompare;
 
 private:
+    void debugDump() const;
     void unlink(mem_node *aNode);
     void makeAppendSpace();
     int appendToNode(mem_node *aNode, const char *data, int maxLength);
diff --git a/test-suite/mem_hdr_test.cc b/test-suite/mem_hdr_test.cc
index ae950d977a..2c2a309cce 100644
--- a/test-suite/mem_hdr_test.cc
+++ b/test-suite/mem_hdr_test.cc
@@ -1,6 +1,6 @@
 
 /*
- * $Id: mem_hdr_test.cc,v 1.4 2003/09/22 03:31:02 robertc Exp $
+ * $Id: mem_hdr_test.cc,v 1.5 2003/09/22 08:50:51 robertc Exp $
  *
  * DEBUG: section 19    Store Memory Primitives
  * AUTHOR: Robert Collins
@@ -95,16 +95,6 @@ testSplayOfNodes()
     aSplay.destroy(SplayNode<mem_node *>::DefaultFree);
 }
 
-struct mem_node_print
-{
-    mem_node_print(std::ostream &astream) : os(astream) {}
-
-    void operator () (mem_node *aNode)
-    {}
-
-    std::ostream &os;
-};
-
 void
 testHdrVisit()
 {
@@ -115,7 +105,14 @@ testHdrVisit()
     sampleData = xstrdup ("B");
     assert (aHeader.write (StoreIOBuffer(1, 102, sampleData)));
     safe_free (sampleData);
-    //for_each (aHeader.getNodes().begin(). aHeader.getNodes().end(), mem_node_print(std::cout));
+    std::ostringstream result;
+    PointerPrinter<mem_node *> foo(result, "\n");
+    for_each (aHeader.getNodes().end(), aHeader.getNodes().end(), foo);
+    for_each (aHeader.getNodes().begin(), aHeader.getNodes().begin(), foo);
+    for_each (aHeader.getNodes().begin(), aHeader.getNodes().end(), foo);
+    std::ostringstream expectedResult;
+    expectedResult << "[100,101)" << std::endl << "[102,103)" << std::endl;
+    assert (result.str() == expectedResult.str());
 }
 
 int
-- 
2.39.2