Add ReverseIter to GrTRecorder

src/gpu/GrTRecorder.h

 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef GrTRecorder_DEFINED
 #define GrTRecorder_DEFINED
 
@@ skipping 28 matching lines @@
  *                on an obscure compiler) may not be compatible. This is runtime asserted
  *                in debug builds.
  *
  * @param TAlign  A type whose size is the desired memory alignment for object allocations.
  *                This should be the largest known alignment requirement for all objects
  *                that may be stored in the list.
  */
 template<typename TBase, typename TAlign> class GrTRecorder : SkNoncopyable {
 public:
     class Iter;
+    class ReverseIter;
 
     /**
      * Create a recorder.
      *
      * @param initialSizeInBytes  The amount of memory reserved by the recorder initially,
                                   and after calls to reset().
      */
     GrTRecorder(int initialSizeInBytes)
         : fHeadBlock(MemBlock::Alloc(LengthOf(initialSizeInBytes), NULL)),
           fTailBlock(fHeadBlock),
@@ skipping 96 matching lines @@
 
     TBase*    fLastItem;
 
     template<typename TItem> friend struct GrTRecorderAllocWrapper;
 
     template <typename UBase, typename UAlign, typename UItem>
     friend void* operator new(size_t, GrTRecorder<UBase, UAlign>&,
                               const GrTRecorderAllocWrapper<UItem>&);
 
     friend class Iter;
+    friend class ReverseIter;
 };
 
 ////////////////////////////////////////////////////////////////////////////////
 
 template<typename TBase, typename TAlign>
 void GrTRecorder<TBase, TAlign>::pop_back() {
     SkASSERT(fLastItem);
     Header* header = reinterpret_cast<Header*>(
         reinterpret_cast<TAlign*>(fLastItem) - length_of<Header>::kValue);
     fTailBlock->fBack -= header->fTotalLength;
     fLastItem->~TBase();
 
     int lastItemLength = header->fPrevLength;
 
     if (!header->fPrevLength) {
         // We popped the first entry in the recorder.
         SkASSERT(0 == fTailBlock->fBack);
         fLastItem = NULL;
         return;
     }
-    if (!fTailBlock->fBack) {
+    while (!fTailBlock->fBack) {
         // We popped the last entry in a block that isn't the head block. Move back a block but
         // don't free it since we'll probably grow into it shortly.
         fTailBlock = fTailBlock->fPrev;
         SkASSERT(fTailBlock);
     }
     fLastItem = reinterpret_cast<TBase*>(
         &(*fTailBlock)[fTailBlock->fBack - lastItemLength + length_of<Header>::kValue]);
 }
 
 template<typename TBase, typename TAlign>
@@ skipping 36 matching lines @@
     // multiple inheritance or a base class that doesn't have virtual methods (when the
     // subclass does). It would be ideal to find a more robust solution that comes at no
     // extra cost to performance or code generality.
     SkDEBUGCODE(void* baseAddr = fLastItem;
                 void* subclassAddr = rawPtr);
     SkASSERT(baseAddr == subclassAddr);
 
     return rawPtr;
 }
 
+/**
+ * Iterates through a recorder from front to back. The initial state of the iterator is
+ * to not have the front item loaded yet; next() must be called first. Usage model:
+ *
+ *    GrTRecorder<TBase, TAlign>::Iter iter(recorder);
+ *    while (iter.next()) {
+ *        iter->doSomething();
+ *    }
+ */
 template<typename TBase, typename TAlign>
 class GrTRecorder<TBase, TAlign>::Iter {
 public:
     Iter(GrTRecorder& recorder) : fBlock(recorder.fHeadBlock), fPosition(0), fItem(NULL) {}
 
     bool next() {
         while (fPosition >= fBlock->fBack) {
             SkASSERT(fPosition == fBlock->fBack);
             if (!fBlock->fNext) {
                 return false;
@@ skipping 14 matching lines @@
     }
 
     TBase* operator->() const { return this->get(); }
 
 private:
     MemBlock* fBlock;
     int       fPosition;
     TBase*    fItem;
 };
 
+/**
+ * Iterates through a recorder in reverse, from back to front. This version mirrors "Iter",
+ * so the initial state is to have recorder.back() loaded already. (Note that this will
+ * assert if the recorder is empty.) Usage model:
+ *
+ *    GrTRecorder<TBase, TAlign>::ReverseIter reverseIter(recorder);
+ *    do {
+ *        reverseIter->doSomething();
+ *    } while (reverseIter.previous());
+ */
+template<typename TBase, typename TAlign>
+class GrTRecorder<TBase, TAlign>::ReverseIter {
+public:
+    ReverseIter(GrTRecorder& recorder)
+        : fBlock(recorder.fTailBlock),
+          fItem(&recorder.back()) {
+        Header* lastHeader = reinterpret_cast<Header*>(
+            reinterpret_cast<TAlign*>(fItem) - length_of<Header>::kValue);
+        fPosition = fBlock->fBack - lastHeader->fTotalLength;
+    }
+
+    bool previous() {
+        Header* header = reinterpret_cast<Header*>(&(*fBlock)[fPosition]);
+
+        while (0 == fPosition) {
+            if (!fBlock->fPrev) {
+                // We've reached the front of the recorder.
+                return false;
+            }
+            fBlock = fBlock->fPrev;
+            fPosition = fBlock->fBack;
+        }
+
+        fPosition -= header->fPrevLength;
+        SkASSERT(fPosition >= 0);
+
+        fItem = reinterpret_cast<TBase*>(&(*fBlock)[fPosition + length_of<Header>::kValue]);
+        return true;
+    }
+
+    TBase* get() const { return fItem; }
+    TBase* operator->() const { return this->get(); }
+
+private:
+    MemBlock* fBlock;
+    int       fPosition;
+    TBase*    fItem;
+};
+
 template<typename TBase, typename TAlign>
 void GrTRecorder<TBase, TAlign>::reset() {
     Iter iter(*this);
     while (iter.next()) {
         iter->~TBase();
     }
 
     // Assume the next time this recorder fills up it will use approximately the same
     // amount of space as last time. Leave enough space for up to ~50% growth; free
     // everything else.
@@ skipping 38 matching lines @@
     SK_CRASH();
 }
 
 #define GrNEW_APPEND_TO_RECORDER(recorder, type_name, args) \
     (new (recorder, GrTRecorderAllocWrapper<type_name>()) type_name args)
 
 #define GrNEW_APPEND_WITH_DATA_TO_RECORDER(recorder, type_name, args, size_of_data) \
     (new (recorder, GrTRecorderAllocWrapper<type_name>(recorder, size_of_data)) type_name args)
 
 #endif