Reland r6649 with fix for build errors.

git-svn-id: http://skia.googlecode.com/svn/trunk@6653 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 88 insertions, 4 deletions

diff --git a/src/core/SkTLList.h b/src/core/SkTLList.h
index 41f0c0b4af..bf7c93b781 100644
--- a/src/core/SkTLList.h
+++ b/src/core/SkTLList.h
@@ -8,9 +8,22 @@
 #include "SkTInternalLList.h"
 #include "SkTemplates.h"
 
+template <typename T> class SkTLList;
+template <typename T>
+inline void* operator new(size_t, SkTLList<T>* list,
+                          typename SkTLList<T>::Placement placement,
+                          const typename SkTLList<T>::Iter& location);
+
 /** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the
     the list creates the objects and they are deleted upon removal. This class block-allocates
-    space for entries based on a param passed to the constructor. */
+    space for entries based on a param passed to the constructor.
+
+    Elements of the list can be constructed in place using the following macros:
+        SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args)
+        SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args)
+    where list is a SkTLList<type_name>*, location is an iterator, and args is the paren-surrounded
+    constructor arguments for type_name. These macros behave like addBefore() and addAfter().
+*/
 template <typename T>
 class SkTLList : public SkNoncopyable {
 private:
@@ -23,6 +36,9 @@ private:
     typedef SkTInternalLList<Node> NodeList;
 
 public:
+
+    class Iter;
+
     /** allocCnt is the number of objects to allocate as a group. In the worst case fragmentation
         each object is using the space required for allocCnt unfragmented objects. */
     SkTLList(int allocCnt = 1) : fCount(0), fAllocCnt(allocCnt) {
@@ -35,7 +51,7 @@ public:
         typename NodeList::Iter iter;
         Node* node = iter.init(fList, Iter::kHead_IterStart);
         while (NULL != node) {
-            reinterpret_cast<T*>(node->fObj)->~T();
+            SkTCast<T*>(node->fObj)->~T();
             Block* block = node->fBlock;
             node = iter.next();
             if (0 == --block->fNodesInUse) {
@@ -63,6 +79,22 @@ public:
         this->validate();
     }
 
+    /** Adds a new element to the list before the location indicated by the iterator. If the
+        iterator refers to a NULL location then the new element is added at the tail */
+    void addBefore(const T& t, const Iter& location) {
+        SkNEW_PLACEMENT_ARGS(this->internalAddBefore(location), T, (t));
+    }
+
+    /** Adds a new element to the list after the location indicated by the iterator. If the
+        iterator refers to a NULL location then the new element is added at the head */
+    void addAfter(const T& t, const Iter& location) {
+        SkNEW_PLACEMENT_ARGS(this->internalAddAfter(location), T, (t));
+    }
+
+    /** Convenience methods for getting an iterator initialized to the head/tail of the list. */
+    Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); }
+    Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); }
+
     void popHead() {
         this->validate();
         Node* node = fList.head();
@@ -155,6 +187,9 @@ public:
         Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
 
     private:
+        friend class SkTLList;
+        Node* getNode() { return INHERITED::get(); }
+
         T* nodeToObj(Node* node) {
             if (NULL != node) {
                 return reinterpret_cast<T*>(node->fObj);
@@ -164,6 +199,12 @@ public:
         }
     };
 
+    // For use with operator new
+    enum Placement {
+        kBefore_Placement,
+        kAfter_Placement,
+    };
+
 private:
     struct Block {
         int fNodesInUse;
@@ -196,9 +237,8 @@ private:
     void removeNode(Node* node) {
         SkASSERT(NULL != node);
         fList.remove(node);
-        reinterpret_cast<T*>(node->fObj)->~T();
+        SkTCast<T*>(node->fObj)->~T();
         if (0 == --node->fBlock->fNodesInUse) {
-            // Delete a block when it no longer has any nodes in use to reduce memory consumption.
             Block* block = node->fBlock;
             for (int i = 0; i < fAllocCnt; ++i) {
                 if (block->fNodes + i != node) {
@@ -265,8 +305,52 @@ private:
 #endif
     }
 
+    // Support in-place initializing of objects inserted into the list via operator new.
+    friend void* operator new<T>(size_t,
+                                 SkTLList* list,
+                                 Placement placement,
+                                 const Iter& location);
+
+
+    // Helpers that insert the node and returns a pointer to where the new object should be init'ed.
+    void* internalAddBefore(Iter location) {
+        this->validate();
+        Node* node = this->createNode();
+        fList.addBefore(node, location.getNode());
+        this->validate();
+        return node->fObj;
+    }
+
+    void* internalAddAfter(Iter location) {
+        this->validate();
+        Node* node = this->createNode();
+        fList.addAfter(node, location.getNode());
+        this->validate();
+        return node->fObj;
+    }
+
     NodeList fList;
     NodeList fFreeList;
     int fCount;
     int fAllocCnt;
+
 };
+
+// Use the below macros rather than calling this directly
+template <typename T>
+void *operator new(size_t, SkTLList<T>* list,
+                   typename SkTLList<T>::Placement placement,
+                   const typename SkTLList<T>::Iter& location) {
+    SkASSERT(NULL != list);
+    if (SkTLList<T>::kBefore_Placement == placement) {
+        return list->internalAddBefore(location);
+    } else {
+        return list->internalAddAfter(location);
+    }
+}
+
+#define SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) \
+    (new (list, SkTLList< type_name >::kBefore_Placement, location) type_name args)
+
+#define SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) \
+    (new (list, SkTLList< type_name >::kAfter_Placement, location) type_name args)