src/core/SkPictureFlat.h - skia - Git at Google


 /*
  * Copyright 2011 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #ifndef SkPictureFlat_DEFINED
 #define SkPictureFlat_DEFINED

 //#define SK_DEBUG_SIZE

 #include "SkBitmapHeap.h"
 #include "SkChecksum.h"
 #include "SkChunkAlloc.h"
 #include "SkReadBuffer.h"
 #include "SkWriteBuffer.h"
 #include "SkPaint.h"
 #include "SkPicture.h"
 #include "SkPtrRecorder.h"
 #include "SkTDynamicHash.h"
 #include "SkTRefArray.h"

 enum DrawType {
     UNUSED,
     CLIP_PATH,
     CLIP_REGION,
     CLIP_RECT,
     CLIP_RRECT,
     CONCAT,
     DRAW_BITMAP,
     DRAW_BITMAP_MATRIX,
     DRAW_BITMAP_NINE,
     DRAW_BITMAP_RECT_TO_RECT,
     DRAW_CLEAR,
     DRAW_DATA,
     DRAW_OVAL,
     DRAW_PAINT,
     DRAW_PATH,
     DRAW_PICTURE,
     DRAW_POINTS,
     DRAW_POS_TEXT,
     DRAW_POS_TEXT_TOP_BOTTOM, // fast variant of DRAW_POS_TEXT
     DRAW_POS_TEXT_H,
     DRAW_POS_TEXT_H_TOP_BOTTOM, // fast variant of DRAW_POS_TEXT_H
     DRAW_RECT,
     DRAW_RRECT,
     DRAW_SPRITE,
     DRAW_TEXT,
     DRAW_TEXT_ON_PATH,
     DRAW_TEXT_TOP_BOTTOM,   // fast variant of DRAW_TEXT
     DRAW_VERTICES,
     RESTORE,
     ROTATE,
     SAVE,
     SAVE_LAYER,
     SCALE,
     SET_MATRIX,
     SKEW,
     TRANSLATE,
     NOOP,
     BEGIN_COMMENT_GROUP,
     COMMENT,
     END_COMMENT_GROUP,

     // new ops -- feel free to re-alphabetize on next version bump
     DRAW_DRRECT,
     PUSH_CULL,
     POP_CULL,

     LAST_DRAWTYPE_ENUM = POP_CULL
 };

 // In the 'match' method, this constant will match any flavor of DRAW_BITMAP*
 static const int kDRAW_BITMAP_FLAVOR = LAST_DRAWTYPE_ENUM+1;

 enum DrawVertexFlags {
     DRAW_VERTICES_HAS_TEXS    = 0x01,
     DRAW_VERTICES_HAS_COLORS  = 0x02,
     DRAW_VERTICES_HAS_INDICES = 0x04,
     DRAW_VERTICES_HAS_XFER    = 0x08,
 };

 ///////////////////////////////////////////////////////////////////////////////
 // clipparams are packed in 5 bits
 //  doAA:1 | regionOp:4

 static inline uint32_t ClipParams_pack(SkRegion::Op op, bool doAA) {
     unsigned doAABit = doAA ? 1 : 0;
     return (doAABit << 4) | op;
 }

 static inline SkRegion::Op ClipParams_unpackRegionOp(uint32_t packed) {
     return (SkRegion::Op)(packed & 0xF);
 }

 static inline bool ClipParams_unpackDoAA(uint32_t packed) {
     return SkToBool((packed >> 4) & 1);
 }

 ///////////////////////////////////////////////////////////////////////////////

 class SkTypefacePlayback {
 public:
     SkTypefacePlayback();
     virtual ~SkTypefacePlayback();

     int count() const { return fCount; }

     void reset(const SkRefCntSet*);

     void setCount(int count);
     SkRefCnt* set(int index, SkRefCnt*);

     void setupBuffer(SkReadBuffer& buffer) const {
         buffer.setTypefaceArray((SkTypeface**)fArray, fCount);
     }

 protected:
     int fCount;
     SkRefCnt** fArray;
 };

 class SkFactoryPlayback {
 public:
     SkFactoryPlayback(int count) : fCount(count) {
         fArray = SkNEW_ARRAY(SkFlattenable::Factory, count);
     }

     ~SkFactoryPlayback() {
         SkDELETE_ARRAY(fArray);
     }

     SkFlattenable::Factory* base() const { return fArray; }

     void setupBuffer(SkReadBuffer& buffer) const {
         buffer.setFactoryPlayback(fArray, fCount);
     }

 private:
     int fCount;
     SkFlattenable::Factory* fArray;
 };

 ///////////////////////////////////////////////////////////////////////////////
 //
 //
 // The following templated classes provide an efficient way to store and compare
 // objects that have been flattened (i.e. serialized in an ordered binary
 // format).
 //
 // SkFlatData:       is a simple indexable container for the flattened data
 //                   which is agnostic to the type of data is is indexing. It is
 //                   also responsible for flattening/unflattening objects but
 //                   details of that operation are hidden in the provided traits
 // SkFlatDictionary: is an abstract templated dictionary that maintains a
 //                   searchable set of SkFlatData objects of type T.
 // SkFlatController: is an interface provided to SkFlatDictionary which handles
 //                   allocation (and unallocation in some cases). It also holds
 //                   ref count recorders and the like.
 //
 // NOTE: any class that wishes to be used in conjunction with SkFlatDictionary must subclass the
 // dictionary and provide the necessary flattening traits.  SkFlatController must also be
 // implemented, or SkChunkFlatController can be used to use an SkChunkAllocator and never do
 // replacements.
 //
 //
 ///////////////////////////////////////////////////////////////////////////////

 class SkFlatData;

 class SkFlatController : public SkRefCnt {
 public:
     SK_DECLARE_INST_COUNT(SkFlatController)

     SkFlatController(uint32_t writeBufferFlags = 0);
     virtual ~SkFlatController();
     /**
      * Return a new block of memory for the SkFlatDictionary to use.
      * This memory is owned by the controller and has the same lifetime unless you
      * call unalloc(), in which case it may be freed early.
      */
     virtual void* allocThrow(size_t bytes) = 0;

     /**
      * Hint that this block, which was allocated with allocThrow, is no longer needed.
      * The implementation may choose to free this memory any time beteween now and destruction.
      */
     virtual void unalloc(void* ptr) = 0;

     /**
      * Used during creation and unflattening of SkFlatData objects. If the
      * objects being flattened contain bitmaps they are stored in this heap
      * and the flattenable stores the index to the bitmap on the heap.
      * This should be set by the protected setBitmapHeap.
      */
     SkBitmapHeap* getBitmapHeap() { return fBitmapHeap; }

     /**
      * Used during creation of SkFlatData objects. If a typeface recorder is
      * required to flatten the objects being flattened (i.e. for SkPaints), this
      * should be set by the protected setTypefaceSet.
      */
     SkRefCntSet* getTypefaceSet() { return fTypefaceSet; }

     /**
      * Used during unflattening of the SkFlatData objects in the
      * SkFlatDictionary. Needs to be set by the protected setTypefacePlayback
      * and needs to be reset to the SkRefCntSet passed to setTypefaceSet.
      */
     SkTypefacePlayback* getTypefacePlayback() { return fTypefacePlayback; }

     /**
      * Optional factory recorder used during creation of SkFlatData objects. Set
      * using the protected method setNamedFactorySet.
      */
     SkNamedFactorySet* getNamedFactorySet() { return fFactorySet; }

     /**
      * Flags to use during creation of SkFlatData objects. Defaults to zero.
      */
     uint32_t getWriteBufferFlags() { return fWriteBufferFlags; }

 protected:
     /**
      * Set an SkBitmapHeap to be used to store/read SkBitmaps. Ref counted.
      */
     void setBitmapHeap(SkBitmapHeap*);

     /**
      * Set an SkRefCntSet to be used to store SkTypefaces during flattening. Ref
      * counted.
      */
     void setTypefaceSet(SkRefCntSet*);

     /**
      * Set an SkTypefacePlayback to be used to find references to SkTypefaces
      * during unflattening. Should be reset to the set provided to
      * setTypefaceSet.
      */
     void setTypefacePlayback(SkTypefacePlayback*);

     /**
      * Set an SkNamedFactorySet to be used to store Factorys and their
      * corresponding names during flattening. Ref counted. Returns the same
      * set as a convenience.
      */
     SkNamedFactorySet* setNamedFactorySet(SkNamedFactorySet*);

 private:
     SkBitmapHeap*       fBitmapHeap;
     SkRefCntSet*        fTypefaceSet;
     SkTypefacePlayback* fTypefacePlayback;
     SkNamedFactorySet*  fFactorySet;
     const uint32_t      fWriteBufferFlags;

     typedef SkRefCnt INHERITED;
 };

 class SkFlatData {
 public:
     // Flatten obj into an SkFlatData with this index.  controller owns the SkFlatData*.
     template <typename Traits, typename T>
     static SkFlatData* Create(SkFlatController* controller, const T& obj, int index) {
         // A buffer of 256 bytes should fit most paints, regions, and matrices.
         uint32_t storage[64];
         SkWriteBuffer buffer(storage, sizeof(storage), controller->getWriteBufferFlags());

         buffer.setBitmapHeap(controller->getBitmapHeap());
         buffer.setTypefaceRecorder(controller->getTypefaceSet());
         buffer.setNamedFactoryRecorder(controller->getNamedFactorySet());

         Traits::Flatten(buffer, obj);
         size_t size = buffer.bytesWritten();
         SkASSERT(SkIsAlign4(size));

         // Allocate enough memory to hold SkFlatData struct and the flat data itself.
         size_t allocSize = sizeof(SkFlatData) + size;
         SkFlatData* result = (SkFlatData*) controller->allocThrow(allocSize);

         // Put the serialized contents into the data section of the new allocation.
         buffer.writeToMemory(result->data());
         // Stamp the index, size and checksum in the header.
         result->stampHeader(index, SkToS32(size));
         return result;
     }

     // Unflatten this into result, using bitmapHeap and facePlayback for bitmaps and fonts if given
     template <typename Traits, typename T>
     void unflatten(T* result,
                    SkBitmapHeap* bitmapHeap = NULL,
                    SkTypefacePlayback* facePlayback = NULL) const {
         SkReadBuffer buffer(this->data(), fFlatSize);

         if (bitmapHeap) {
             buffer.setBitmapStorage(bitmapHeap);
         }
         if (facePlayback) {
             facePlayback->setupBuffer(buffer);
         }

         Traits::Unflatten(buffer, result);
         SkASSERT(fFlatSize == (int32_t)buffer.offset());
     }

     // Do these contain the same data?  Ignores index() and topBot().
     bool operator==(const SkFlatData& that) const {
         if (this->checksum() != that.checksum() || this->flatSize() != that.flatSize()) {
             return false;
         }
         return memcmp(this->data(), that.data(), this->flatSize()) == 0;
     }

     int index() const { return fIndex; }
     const uint8_t* data() const { return (const uint8_t*)this + sizeof(*this); }
     size_t flatSize() const { return fFlatSize; }
     uint32_t checksum() const { return fChecksum; }

     // Returns true if fTopBot[] has been recorded.
     bool isTopBotWritten() const {
         return !SkScalarIsNaN(fTopBot[0]);
     }

     // Returns fTopBot array, so it can be passed to a routine to compute them.
     // For efficiency, we assert that fTopBot have not been recorded yet.
     SkScalar* writableTopBot() const {
         SkASSERT(!this->isTopBotWritten());
         return fTopBot;
     }

     // Return the topbot[] after it has been recorded.
     const SkScalar* topBot() const {
         SkASSERT(this->isTopBotWritten());
         return fTopBot;
     }

 private:
     struct HashTraits {
         static const SkFlatData& GetKey(const SkFlatData& flat) { return flat; }
         static uint32_t Hash(const SkFlatData& flat) { return flat.checksum(); }
     };

     void setIndex(int index) { fIndex = index; }
     uint8_t* data() { return (uint8_t*)this + sizeof(*this); }

     // This assumes the payload flat data has already been written and does not modify it.
     void stampHeader(int index, int32_t size) {
         SkASSERT(SkIsAlign4(size));
         fIndex     = index;
         fFlatSize  = size;
         fTopBot[0] = SK_ScalarNaN;  // Mark as unwritten.
         fChecksum  = SkChecksum::Compute((uint32_t*)this->data(), size);
     }

     int fIndex;
     int32_t fFlatSize;
     uint32_t fChecksum;
     mutable SkScalar fTopBot[2];  // Cache of FontMetrics fTop, fBottom.  Starts as [NaN,?].
     // uint32_t flattenedData[] implicitly hangs off the end.

     template <typename T, typename Traits> friend class SkFlatDictionary;
 };

 template <typename T, typename Traits>
 class SkFlatDictionary {
 public:
     explicit SkFlatDictionary(SkFlatController* controller)
     : fController(SkRef(controller))
     , fScratch(controller->getWriteBufferFlags())
     , fReady(false) {
         this->reset();
     }

     /**
      * Clears the dictionary of all entries. However, it does NOT free the
      * memory that was allocated for each entry (that's owned by controller).
      */
     void reset() {
         fIndexedData.rewind();
     }

     int count() const {
         SkASSERT(fHash.count() == fIndexedData.count());
         return fHash.count();
     }

     // For testing only.  Index is zero-based.
     const SkFlatData* operator[](int index) {
         return fIndexedData[index];
     }

     /**
      * Given an element of type T return its 1-based index in the dictionary. If
      * the element wasn't previously in the dictionary it is automatically
      * added.
      *
      */
     int find(const T& element) {
         return this->findAndReturnFlat(element)->index();
     }

     /**
      * Similar to find. Allows the caller to specify an SkFlatData to replace in
      * the case of an add. Also tells the caller whether a new SkFlatData was
      * added and whether the old one was replaced. The parameters added and
      * replaced are required to be non-NULL. Rather than returning the index of
      * the entry in the dictionary, it returns the actual SkFlatData.
      */
     const SkFlatData* findAndReplace(const T& element,
                                      const SkFlatData* toReplace,
                                      bool* added,
                                      bool* replaced) {
         SkASSERT(added != NULL && replaced != NULL);

         const int oldCount = this->count();
         SkFlatData* flat = this->findAndReturnMutableFlat(element);
         *added = this->count() > oldCount;

         // If we don't want to replace anything, we're done.
         if (!*added || toReplace == NULL) {
             *replaced = false;
             return flat;
         }

         // If we don't have the thing to replace, we're done.
         const SkFlatData* found = fHash.find(*toReplace);
         if (found == NULL) {
             *replaced = false;
             return flat;
         }

         // findAndReturnMutableFlat put flat at the back.  Swap it into found->index() instead.
         // indices in SkFlatData are 1-based, while fIndexedData is 0-based.  Watch out!
         SkASSERT(flat->index() == this->count());
         flat->setIndex(found->index());
         fIndexedData.removeShuffle(found->index()-1);
         SkASSERT(flat == fIndexedData[found->index()-1]);

         // findAndReturnMutableFlat already called fHash.add(), so we just clean up the old entry.
         fHash.remove(*found);
         fController->unalloc((void*)found);
         SkASSERT(this->count() == oldCount);

         *replaced = true;
         return flat;
     }

     /**
      *  Unflatten the objects and return them in SkTRefArray, or return NULL
      *  if there no objects.  Caller takes ownership of result.
      */
     SkTRefArray<T>* unflattenToArray() const {
         const int count = this->count();
         if (count == 0) {
             return NULL;
         }
         SkTRefArray<T>* array = SkTRefArray<T>::Create(count);
         for (int i = 0; i < count; i++) {
             this->unflatten(&array->writableAt(i), fIndexedData[i]);
         }
         return array;
     }

     /**
      * Unflatten the specific object at the given index.
      * Caller takes ownership of the result.
      */
     T* unflatten(int index) const {
         // index is 1-based, while fIndexedData is 0-based.
         const SkFlatData* element = fIndexedData[index-1];
         SkASSERT(index == element->index());

         T* dst = new T;
         this->unflatten(dst, element);
         return dst;
     }

     /**
      * Find or insert a flattened version of element into the dictionary.
      * Caller does not take ownership of the result.  This will not return NULL.
      */
     const SkFlatData* findAndReturnFlat(const T& element) {
         return this->findAndReturnMutableFlat(element);
     }

 private:
     // We have to delay fScratch's initialization until its first use; fController might not
     // be fully set up by the time we get it in the constructor.
     void lazyInit() {
         if (fReady) {
             return;
         }

         // Without a bitmap heap, we'll flatten bitmaps into paints.  That's never what you want.
         SkASSERT(fController->getBitmapHeap() != NULL);
         fScratch.setBitmapHeap(fController->getBitmapHeap());
         fScratch.setTypefaceRecorder(fController->getTypefaceSet());
         fScratch.setNamedFactoryRecorder(fController->getNamedFactorySet());
         fReady = true;
     }

     // As findAndReturnFlat, but returns a mutable pointer for internal use.
     SkFlatData* findAndReturnMutableFlat(const T& element) {
         // Only valid until the next call to resetScratch().
         const SkFlatData& scratch = this->resetScratch(element, this->count()+1);

         SkFlatData* candidate = fHash.find(scratch);
         if (candidate != NULL) {
             return candidate;
         }

         SkFlatData* detached = this->detachScratch();
         fHash.add(detached);
         *fIndexedData.append() = detached;
         SkASSERT(fIndexedData.top()->index() == this->count());
         return detached;
     }

     // This reference is valid only until the next call to resetScratch() or detachScratch().
     const SkFlatData& resetScratch(const T& element, int index) {
         this->lazyInit();

         // Layout of fScratch: [ SkFlatData header, 20 bytes ] [ data ..., 4-byte aligned ]
         fScratch.reset();
         fScratch.reserve(sizeof(SkFlatData));
         Traits::Flatten(fScratch, element);
         const size_t dataSize = fScratch.bytesWritten() - sizeof(SkFlatData);

         // Reinterpret data in fScratch as an SkFlatData.
         SkFlatData* scratch = (SkFlatData*)fScratch.getWriter32()->contiguousArray();
         SkASSERT(scratch != NULL);
         scratch->stampHeader(index, SkToS32(dataSize));
         return *scratch;
     }

     // This result is owned by fController and lives as long as it does (unless unalloc'd).
     SkFlatData* detachScratch() {
         // Allocate a new SkFlatData exactly big enough to hold our current scratch.
         // We use the controller for this allocation to extend the allocation's lifetime and allow
         // the controller to do whatever memory management it wants.
         SkFlatData* detached = (SkFlatData*)fController->allocThrow(fScratch.bytesWritten());

         // Copy scratch into the new SkFlatData.
         SkFlatData* scratch = (SkFlatData*)fScratch.getWriter32()->contiguousArray();
         SkASSERT(scratch != NULL);
         memcpy(detached, scratch, fScratch.bytesWritten());

         // We can now reuse fScratch, and detached will live until fController dies.
         return detached;
     }

     void unflatten(T* dst, const SkFlatData* element) const {
         element->unflatten<Traits>(dst,
                                    fController->getBitmapHeap(),
                                    fController->getTypefacePlayback());
     }

     // All SkFlatData* stored in fIndexedData and fHash are owned by the controller.
     SkAutoTUnref<SkFlatController> fController;
     SkWriteBuffer fScratch;
     bool fReady;

     // For index -> SkFlatData.  0-based, while all indices in the API are 1-based.  Careful!
     SkTDArray<const SkFlatData*> fIndexedData;

     // For SkFlatData -> cached SkFlatData, which has index().
     SkTDynamicHash<SkFlatData, SkFlatData, SkFlatData::HashTraits> fHash;
 };

 typedef SkFlatDictionary<SkPaint, SkPaint::FlatteningTraits> SkPaintDictionary;

 class SkChunkFlatController : public SkFlatController {
 public:
     SkChunkFlatController(size_t minSize)
     : fHeap(minSize)
     , fTypefaceSet(SkNEW(SkRefCntSet))
     , fLastAllocated(NULL) {
         this->setTypefaceSet(fTypefaceSet);
         this->setTypefacePlayback(&fTypefacePlayback);
     }

     virtual void* allocThrow(size_t bytes) SK_OVERRIDE {
         fLastAllocated = fHeap.allocThrow(bytes);
         return fLastAllocated;
     }

     virtual void unalloc(void* ptr) SK_OVERRIDE {
         // fHeap can only free a pointer if it was the last one allocated.  Otherwise, we'll just
         // have to wait until fHeap is destroyed.
         if (ptr == fLastAllocated) (void)fHeap.unalloc(ptr);
     }

     void setupPlaybacks() const {
         fTypefacePlayback.reset(fTypefaceSet.get());
     }

     void setBitmapStorage(SkBitmapHeap* heap) {
         this->setBitmapHeap(heap);
     }

 private:
     SkChunkAlloc               fHeap;
     SkAutoTUnref<SkRefCntSet>  fTypefaceSet;
     void*                      fLastAllocated;
     mutable SkTypefacePlayback fTypefacePlayback;
 };

 #endif

	/*
	* Copyright 2011 Google Inc.
	*
	* Use of this source code is governed by a BSD-style license that can be
	* found in the LICENSE file.
	*/
	#ifndef SkPictureFlat_DEFINED
	#define SkPictureFlat_DEFINED

	//#define SK_DEBUG_SIZE

	#include "SkBitmapHeap.h"
	#include "SkChecksum.h"
	#include "SkChunkAlloc.h"
	#include "SkReadBuffer.h"
	#include "SkWriteBuffer.h"
	#include "SkPaint.h"
	#include "SkPicture.h"
	#include "SkPtrRecorder.h"
	#include "SkTDynamicHash.h"
	#include "SkTRefArray.h"

	enum DrawType {
	UNUSED,
	CLIP_PATH,
	CLIP_REGION,
	CLIP_RECT,
	CLIP_RRECT,
	CONCAT,
	DRAW_BITMAP,
	DRAW_BITMAP_MATRIX,
	DRAW_BITMAP_NINE,
	DRAW_BITMAP_RECT_TO_RECT,
	DRAW_CLEAR,
	DRAW_DATA,
	DRAW_OVAL,
	DRAW_PAINT,
	DRAW_PATH,
	DRAW_PICTURE,
	DRAW_POINTS,
	DRAW_POS_TEXT,
	DRAW_POS_TEXT_TOP_BOTTOM, // fast variant of DRAW_POS_TEXT
	DRAW_POS_TEXT_H,
	DRAW_POS_TEXT_H_TOP_BOTTOM, // fast variant of DRAW_POS_TEXT_H
	DRAW_RECT,
	DRAW_RRECT,
	DRAW_SPRITE,
	DRAW_TEXT,
	DRAW_TEXT_ON_PATH,
	DRAW_TEXT_TOP_BOTTOM, // fast variant of DRAW_TEXT
	DRAW_VERTICES,
	RESTORE,
	ROTATE,
	SAVE,
	SAVE_LAYER,
	SCALE,
	SET_MATRIX,
	SKEW,
	TRANSLATE,
	NOOP,
	BEGIN_COMMENT_GROUP,
	COMMENT,
	END_COMMENT_GROUP,

	// new ops -- feel free to re-alphabetize on next version bump
	DRAW_DRRECT,
	PUSH_CULL,
	POP_CULL,

	LAST_DRAWTYPE_ENUM = POP_CULL
	};

	// In the 'match' method, this constant will match any flavor of DRAW_BITMAP*
	static const int kDRAW_BITMAP_FLAVOR = LAST_DRAWTYPE_ENUM+1;

	enum DrawVertexFlags {
	DRAW_VERTICES_HAS_TEXS = 0x01,
	DRAW_VERTICES_HAS_COLORS = 0x02,
	DRAW_VERTICES_HAS_INDICES = 0x04,
	DRAW_VERTICES_HAS_XFER = 0x08,
	};

	///////////////////////////////////////////////////////////////////////////////
	// clipparams are packed in 5 bits
	// doAA:1 \| regionOp:4

	static inline uint32_t ClipParams_pack(SkRegion::Op op, bool doAA) {
	unsigned doAABit = doAA ? 1 : 0;
	return (doAABit << 4) \| op;
	}

	static inline SkRegion::Op ClipParams_unpackRegionOp(uint32_t packed) {
	return (SkRegion::Op)(packed & 0xF);
	}

	static inline bool ClipParams_unpackDoAA(uint32_t packed) {
	return SkToBool((packed >> 4) & 1);
	}

	///////////////////////////////////////////////////////////////////////////////

	class SkTypefacePlayback {
	public:
	SkTypefacePlayback();
	virtual ~SkTypefacePlayback();

	int count() const { return fCount; }

	void reset(const SkRefCntSet*);

	void setCount(int count);
	SkRefCnt* set(int index, SkRefCnt*);

	void setupBuffer(SkReadBuffer& buffer) const {
	buffer.setTypefaceArray((SkTypeface**)fArray, fCount);
	}

	protected:
	int fCount;
	SkRefCnt** fArray;
	};

	class SkFactoryPlayback {
	public:
	SkFactoryPlayback(int count) : fCount(count) {
	fArray = SkNEW_ARRAY(SkFlattenable::Factory, count);
	}

	~SkFactoryPlayback() {
	SkDELETE_ARRAY(fArray);
	}

	SkFlattenable::Factory* base() const { return fArray; }

	void setupBuffer(SkReadBuffer& buffer) const {
	buffer.setFactoryPlayback(fArray, fCount);
	}

	private:
	int fCount;
	SkFlattenable::Factory* fArray;
	};

	///////////////////////////////////////////////////////////////////////////////
	//
	//
	// The following templated classes provide an efficient way to store and compare
	// objects that have been flattened (i.e. serialized in an ordered binary
	// format).
	//
	// SkFlatData: is a simple indexable container for the flattened data
	// which is agnostic to the type of data is is indexing. It is
	// also responsible for flattening/unflattening objects but
	// details of that operation are hidden in the provided traits
	// SkFlatDictionary: is an abstract templated dictionary that maintains a
	// searchable set of SkFlatData objects of type T.
	// SkFlatController: is an interface provided to SkFlatDictionary which handles
	// allocation (and unallocation in some cases). It also holds
	// ref count recorders and the like.
	//
	// NOTE: any class that wishes to be used in conjunction with SkFlatDictionary must subclass the
	// dictionary and provide the necessary flattening traits. SkFlatController must also be
	// implemented, or SkChunkFlatController can be used to use an SkChunkAllocator and never do
	// replacements.
	//
	//
	///////////////////////////////////////////////////////////////////////////////

	class SkFlatData;

	class SkFlatController : public SkRefCnt {
	public:
	SK_DECLARE_INST_COUNT(SkFlatController)

	SkFlatController(uint32_t writeBufferFlags = 0);
	virtual ~SkFlatController();
	/**
	* Return a new block of memory for the SkFlatDictionary to use.
	* This memory is owned by the controller and has the same lifetime unless you
	* call unalloc(), in which case it may be freed early.
	*/
	virtual void* allocThrow(size_t bytes) = 0;

	/**
	* Hint that this block, which was allocated with allocThrow, is no longer needed.
	* The implementation may choose to free this memory any time beteween now and destruction.
	*/
	virtual void unalloc(void* ptr) = 0;

	/**
	* Used during creation and unflattening of SkFlatData objects. If the
	* objects being flattened contain bitmaps they are stored in this heap
	* and the flattenable stores the index to the bitmap on the heap.
	* This should be set by the protected setBitmapHeap.
	*/
	SkBitmapHeap* getBitmapHeap() { return fBitmapHeap; }

	/**
	* Used during creation of SkFlatData objects. If a typeface recorder is
	* required to flatten the objects being flattened (i.e. for SkPaints), this
	* should be set by the protected setTypefaceSet.
	*/
	SkRefCntSet* getTypefaceSet() { return fTypefaceSet; }

	/**
	* Used during unflattening of the SkFlatData objects in the
	* SkFlatDictionary. Needs to be set by the protected setTypefacePlayback
	* and needs to be reset to the SkRefCntSet passed to setTypefaceSet.
	*/
	SkTypefacePlayback* getTypefacePlayback() { return fTypefacePlayback; }

	/**
	* Optional factory recorder used during creation of SkFlatData objects. Set
	* using the protected method setNamedFactorySet.
	*/
	SkNamedFactorySet* getNamedFactorySet() { return fFactorySet; }

	/**
	* Flags to use during creation of SkFlatData objects. Defaults to zero.
	*/
	uint32_t getWriteBufferFlags() { return fWriteBufferFlags; }

	protected:
	/**
	* Set an SkBitmapHeap to be used to store/read SkBitmaps. Ref counted.
	*/
	void setBitmapHeap(SkBitmapHeap*);

	/**
	* Set an SkRefCntSet to be used to store SkTypefaces during flattening. Ref
	* counted.
	*/
	void setTypefaceSet(SkRefCntSet*);

	/**
	* Set an SkTypefacePlayback to be used to find references to SkTypefaces
	* during unflattening. Should be reset to the set provided to
	* setTypefaceSet.
	*/
	void setTypefacePlayback(SkTypefacePlayback*);

	/**
	* Set an SkNamedFactorySet to be used to store Factorys and their
	* corresponding names during flattening. Ref counted. Returns the same
	* set as a convenience.
	*/
	SkNamedFactorySet* setNamedFactorySet(SkNamedFactorySet*);

	private:
	SkBitmapHeap* fBitmapHeap;
	SkRefCntSet* fTypefaceSet;
	SkTypefacePlayback* fTypefacePlayback;
	SkNamedFactorySet* fFactorySet;
	const uint32_t fWriteBufferFlags;

	typedef SkRefCnt INHERITED;
	};

	class SkFlatData {
	public:
	// Flatten obj into an SkFlatData with this index. controller owns the SkFlatData*.
	template <typename Traits, typename T>
	static SkFlatData* Create(SkFlatController* controller, const T& obj, int index) {
	// A buffer of 256 bytes should fit most paints, regions, and matrices.
	uint32_t storage[64];
	SkWriteBuffer buffer(storage, sizeof(storage), controller->getWriteBufferFlags());

	buffer.setBitmapHeap(controller->getBitmapHeap());
	buffer.setTypefaceRecorder(controller->getTypefaceSet());
	buffer.setNamedFactoryRecorder(controller->getNamedFactorySet());

	Traits::Flatten(buffer, obj);
	size_t size = buffer.bytesWritten();
	SkASSERT(SkIsAlign4(size));

	// Allocate enough memory to hold SkFlatData struct and the flat data itself.
	size_t allocSize = sizeof(SkFlatData) + size;
	SkFlatData* result = (SkFlatData*) controller->allocThrow(allocSize);

	// Put the serialized contents into the data section of the new allocation.
	buffer.writeToMemory(result->data());
	// Stamp the index, size and checksum in the header.
	result->stampHeader(index, SkToS32(size));
	return result;
	}

	// Unflatten this into result, using bitmapHeap and facePlayback for bitmaps and fonts if given
	template <typename Traits, typename T>
	void unflatten(T* result,
	SkBitmapHeap* bitmapHeap = NULL,
	SkTypefacePlayback* facePlayback = NULL) const {
	SkReadBuffer buffer(this->data(), fFlatSize);

	if (bitmapHeap) {
	buffer.setBitmapStorage(bitmapHeap);
	}
	if (facePlayback) {
	facePlayback->setupBuffer(buffer);
	}

	Traits::Unflatten(buffer, result);
	SkASSERT(fFlatSize == (int32_t)buffer.offset());
	}

	// Do these contain the same data? Ignores index() and topBot().
	bool operator==(const SkFlatData& that) const {
	if (this->checksum() != that.checksum() \|\| this->flatSize() != that.flatSize()) {
	return false;
	}
	return memcmp(this->data(), that.data(), this->flatSize()) == 0;
	}

	int index() const { return fIndex; }
	const uint8_t* data() const { return (const uint8_t)this + sizeof(this); }
	size_t flatSize() const { return fFlatSize; }
	uint32_t checksum() const { return fChecksum; }

	// Returns true if fTopBot[] has been recorded.
	bool isTopBotWritten() const {
	return !SkScalarIsNaN(fTopBot[0]);
	}

	// Returns fTopBot array, so it can be passed to a routine to compute them.
	// For efficiency, we assert that fTopBot have not been recorded yet.
	SkScalar* writableTopBot() const {
	SkASSERT(!this->isTopBotWritten());
	return fTopBot;
	}

	// Return the topbot[] after it has been recorded.
	const SkScalar* topBot() const {
	SkASSERT(this->isTopBotWritten());
	return fTopBot;
	}

	private:
	struct HashTraits {
	static const SkFlatData& GetKey(const SkFlatData& flat) { return flat; }
	static uint32_t Hash(const SkFlatData& flat) { return flat.checksum(); }
	};

	void setIndex(int index) { fIndex = index; }
	uint8_t* data() { return (uint8_t)this + sizeof(this); }

	// This assumes the payload flat data has already been written and does not modify it.
	void stampHeader(int index, int32_t size) {
	SkASSERT(SkIsAlign4(size));
	fIndex = index;
	fFlatSize = size;
	fTopBot[0] = SK_ScalarNaN; // Mark as unwritten.
	fChecksum = SkChecksum::Compute((uint32_t*)this->data(), size);
	}

	int fIndex;
	int32_t fFlatSize;
	uint32_t fChecksum;
	mutable SkScalar fTopBot[2]; // Cache of FontMetrics fTop, fBottom. Starts as [NaN,?].
	// uint32_t flattenedData[] implicitly hangs off the end.

	template <typename T, typename Traits> friend class SkFlatDictionary;
	};

	template <typename T, typename Traits>
	class SkFlatDictionary {
	public:
	explicit SkFlatDictionary(SkFlatController* controller)
	: fController(SkRef(controller))
	, fScratch(controller->getWriteBufferFlags())
	, fReady(false) {
	this->reset();
	}

	/**
	* Clears the dictionary of all entries. However, it does NOT free the
	* memory that was allocated for each entry (that's owned by controller).
	*/
	void reset() {
	fIndexedData.rewind();
	}

	int count() const {
	SkASSERT(fHash.count() == fIndexedData.count());
	return fHash.count();
	}

	// For testing only. Index is zero-based.
	const SkFlatData* operator[](int index) {
	return fIndexedData[index];
	}

	/**
	* Given an element of type T return its 1-based index in the dictionary. If
	* the element wasn't previously in the dictionary it is automatically
	* added.
	*
	*/
	int find(const T& element) {
	return this->findAndReturnFlat(element)->index();
	}

	/**
	* Similar to find. Allows the caller to specify an SkFlatData to replace in
	* the case of an add. Also tells the caller whether a new SkFlatData was
	* added and whether the old one was replaced. The parameters added and
	* replaced are required to be non-NULL. Rather than returning the index of
	* the entry in the dictionary, it returns the actual SkFlatData.
	*/
	const SkFlatData* findAndReplace(const T& element,
	const SkFlatData* toReplace,
	bool* added,
	bool* replaced) {
	SkASSERT(added != NULL && replaced != NULL);

	const int oldCount = this->count();
	SkFlatData* flat = this->findAndReturnMutableFlat(element);
	*added = this->count() > oldCount;

	// If we don't want to replace anything, we're done.
	if (!*added \|\| toReplace == NULL) {
	*replaced = false;
	return flat;
	}

	// If we don't have the thing to replace, we're done.
	const SkFlatData* found = fHash.find(*toReplace);
	if (found == NULL) {
	*replaced = false;
	return flat;
	}

	// findAndReturnMutableFlat put flat at the back. Swap it into found->index() instead.
	// indices in SkFlatData are 1-based, while fIndexedData is 0-based. Watch out!
	SkASSERT(flat->index() == this->count());
	flat->setIndex(found->index());
	fIndexedData.removeShuffle(found->index()-1);
	SkASSERT(flat == fIndexedData[found->index()-1]);

	// findAndReturnMutableFlat already called fHash.add(), so we just clean up the old entry.
	fHash.remove(*found);
	fController->unalloc((void*)found);
	SkASSERT(this->count() == oldCount);

	*replaced = true;
	return flat;
	}

	/**
	* Unflatten the objects and return them in SkTRefArray, or return NULL
	* if there no objects. Caller takes ownership of result.
	*/
	SkTRefArray<T>* unflattenToArray() const {
	const int count = this->count();
	if (count == 0) {
	return NULL;
	}
	SkTRefArray<T>* array = SkTRefArray<T>::Create(count);
	for (int i = 0; i < count; i++) {
	this->unflatten(&array->writableAt(i), fIndexedData[i]);
	}
	return array;
	}

	/**
	* Unflatten the specific object at the given index.
	* Caller takes ownership of the result.
	*/
	T* unflatten(int index) const {
	// index is 1-based, while fIndexedData is 0-based.
	const SkFlatData* element = fIndexedData[index-1];
	SkASSERT(index == element->index());

	T* dst = new T;
	this->unflatten(dst, element);
	return dst;
	}

	/**
	* Find or insert a flattened version of element into the dictionary.
	* Caller does not take ownership of the result. This will not return NULL.
	*/
	const SkFlatData* findAndReturnFlat(const T& element) {
	return this->findAndReturnMutableFlat(element);
	}

	private:
	// We have to delay fScratch's initialization until its first use; fController might not
	// be fully set up by the time we get it in the constructor.
	void lazyInit() {
	if (fReady) {
	return;
	}

	// Without a bitmap heap, we'll flatten bitmaps into paints. That's never what you want.
	SkASSERT(fController->getBitmapHeap() != NULL);
	fScratch.setBitmapHeap(fController->getBitmapHeap());
	fScratch.setTypefaceRecorder(fController->getTypefaceSet());
	fScratch.setNamedFactoryRecorder(fController->getNamedFactorySet());
	fReady = true;
	}

	// As findAndReturnFlat, but returns a mutable pointer for internal use.
	SkFlatData* findAndReturnMutableFlat(const T& element) {
	// Only valid until the next call to resetScratch().
	const SkFlatData& scratch = this->resetScratch(element, this->count()+1);

	SkFlatData* candidate = fHash.find(scratch);
	if (candidate != NULL) {
	return candidate;
	}

	SkFlatData* detached = this->detachScratch();
	fHash.add(detached);
	*fIndexedData.append() = detached;
	SkASSERT(fIndexedData.top()->index() == this->count());
	return detached;
	}

	// This reference is valid only until the next call to resetScratch() or detachScratch().
	const SkFlatData& resetScratch(const T& element, int index) {
	this->lazyInit();

	// Layout of fScratch: [ SkFlatData header, 20 bytes ] [ data ..., 4-byte aligned ]
	fScratch.reset();
	fScratch.reserve(sizeof(SkFlatData));
	Traits::Flatten(fScratch, element);
	const size_t dataSize = fScratch.bytesWritten() - sizeof(SkFlatData);

	// Reinterpret data in fScratch as an SkFlatData.
	SkFlatData* scratch = (SkFlatData*)fScratch.getWriter32()->contiguousArray();
	SkASSERT(scratch != NULL);
	scratch->stampHeader(index, SkToS32(dataSize));
	return *scratch;
	}

	// This result is owned by fController and lives as long as it does (unless unalloc'd).
	SkFlatData* detachScratch() {
	// Allocate a new SkFlatData exactly big enough to hold our current scratch.
	// We use the controller for this allocation to extend the allocation's lifetime and allow
	// the controller to do whatever memory management it wants.
	SkFlatData* detached = (SkFlatData*)fController->allocThrow(fScratch.bytesWritten());

	// Copy scratch into the new SkFlatData.
	SkFlatData* scratch = (SkFlatData*)fScratch.getWriter32()->contiguousArray();
	SkASSERT(scratch != NULL);
	memcpy(detached, scratch, fScratch.bytesWritten());

	// We can now reuse fScratch, and detached will live until fController dies.
	return detached;
	}

	void unflatten(T* dst, const SkFlatData* element) const {
	element->unflatten<Traits>(dst,
	fController->getBitmapHeap(),
	fController->getTypefacePlayback());
	}

	// All SkFlatData* stored in fIndexedData and fHash are owned by the controller.
	SkAutoTUnref<SkFlatController> fController;
	SkWriteBuffer fScratch;
	bool fReady;

	// For index -> SkFlatData. 0-based, while all indices in the API are 1-based. Careful!
	SkTDArray<const SkFlatData*> fIndexedData;

	// For SkFlatData -> cached SkFlatData, which has index().
	SkTDynamicHash<SkFlatData, SkFlatData, SkFlatData::HashTraits> fHash;
	};

	typedef SkFlatDictionary<SkPaint, SkPaint::FlatteningTraits> SkPaintDictionary;

	class SkChunkFlatController : public SkFlatController {
	public:
	SkChunkFlatController(size_t minSize)
	: fHeap(minSize)
	, fTypefaceSet(SkNEW(SkRefCntSet))
	, fLastAllocated(NULL) {
	this->setTypefaceSet(fTypefaceSet);
	this->setTypefacePlayback(&fTypefacePlayback);
	}

	virtual void* allocThrow(size_t bytes) SK_OVERRIDE {
	fLastAllocated = fHeap.allocThrow(bytes);
	return fLastAllocated;
	}

	virtual void unalloc(void* ptr) SK_OVERRIDE {
	// fHeap can only free a pointer if it was the last one allocated. Otherwise, we'll just
	// have to wait until fHeap is destroyed.
	if (ptr == fLastAllocated) (void)fHeap.unalloc(ptr);
	}

	void setupPlaybacks() const {
	fTypefacePlayback.reset(fTypefaceSet.get());
	}

	void setBitmapStorage(SkBitmapHeap* heap) {
	this->setBitmapHeap(heap);
	}

	private:
	SkChunkAlloc fHeap;
	SkAutoTUnref<SkRefCntSet> fTypefaceSet;
	void* fLastAllocated;
	mutable SkTypefacePlayback fTypefacePlayback;
	};

	#endif