code:
/*
    Copyright 2011 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrInOrderDrawBuffer_DEFINED
#define GrInOrderDrawBuffer_DEFINED

#include "GrDrawTarget.h"
#include "GrAllocPool.h"
#include "GrAllocator.h"
#include "GrClip.h"

class GrVertexBufferAllocPool;
class GrIndexBufferAllocPool;

/**
 * GrInOrderDrawBuffer is an implementation of GrDrawTarget that queues up
 * draws for eventual playback into a GrGpu. In theory one draw buffer could
 * playback into another. When index or vertex buffers are used as geometry
 * sources it is the callers the draw buffer only holds references to the
 * buffers. It is the callers responsibility to ensure that the data is still
 * valid when the draw buffer is played back into a GrGpu. Similarly, it is the
 * caller's responsibility to ensure that all referenced textures, buffers,
 * and rendertargets are associated in the GrGpu object that the buffer is
 * played back into. The buffer requires VB and IB pools to store geometry.
 */

class GrInOrderDrawBuffer : public GrDrawTarget {
public:

    /**
     * Creates a GrInOrderDrawBuffer
     *
     * @param vertexPool pool where vertices for queued draws will be saved when
     *                   the vertex source is either reserved or array.
     * @param indexPool  pool where indices for queued draws will be saved when
     *                   the index source is either reserved or array.
     */
    GrInOrderDrawBuffer(GrVertexBufferAllocPool* vertexPool,
                        GrIndexBufferAllocPool* indexPool);

    virtual ~GrInOrderDrawBuffer();

    /**
     * Copies the draw state and clip from target to this draw buffer.
     *
     * @param target    the target whose clip and state should be copied.
     */
    void initializeDrawStateAndClip(const GrDrawTarget& target);

    /**
     * Provides the buffer with an index buffer that can be used for quad rendering.
     * The buffer may be able to batch consecutive drawRects if this is provided.
     * @param indexBuffer   index buffer with quad indices.
     */
    void setQuadIndexBuffer(const GrIndexBuffer* indexBuffer);

    /**
     * Empties the draw buffer of any queued up draws.
     */
    void reset();

    /**
     * plays the queued up draws to another target. Does not empty this buffer so
     * that it can be played back multiple times.
     * @param target    the target to receive the playback
     */
    void playback(GrDrawTarget* target);

    // overrides from GrDrawTarget
    virtual void drawRect(const GrRect& rect,
                          const GrMatrix* matrix = NULL,
                          int stageEnableMask = 0,
                          const GrRect* srcRects[] = NULL,
                          const GrMatrix* srcMatrices[] = NULL);

    virtual bool geometryHints(GrVertexLayout vertexLayout,
                               int* vertexCount,
                               int* indexCount) const;

    virtual void clear(const GrIRect* rect, GrColor color);

private:

    struct Draw {
        GrPrimitiveType         fPrimitiveType;
        int                     fStartVertex;
        int                     fStartIndex;
        int                     fVertexCount;
        int                     fIndexCount;
        bool                    fStateChanged;
        bool                    fClipChanged;
        GrVertexLayout          fVertexLayout;
        const GrVertexBuffer*   fVertexBuffer;
        const GrIndexBuffer*    fIndexBuffer;
    };

    struct Clear {
        int fBeforeDrawIdx;
        GrIRect fRect;
        GrColor fColor;
    };

    // overrides from GrDrawTarget
    virtual void onDrawIndexed(GrPrimitiveType primitiveType,
                               int startVertex,
                               int startIndex,
                               int vertexCount,
                               int indexCount);
    virtual void onDrawNonIndexed(GrPrimitiveType primitiveType,
                                  int startVertex,
                                  int vertexCount);
    virtual bool onReserveVertexSpace(GrVertexLayout layout,
                                      int vertexCount,
                                      void** vertices);
    virtual bool onReserveIndexSpace(int indexCount, void** indices);
    virtual void releaseReservedVertexSpace();
    virtual void releaseReservedIndexSpace();
    virtual void onSetVertexSourceToArray(const void* vertexArray,
                                          int vertexCount);
    virtual void onSetIndexSourceToArray(const void* indexArray,
                                         int indexCount);
    virtual void releaseVertexArray();
    virtual void releaseIndexArray();
    virtual void geometrySourceWillPush();
    virtual void geometrySourceWillPop(const GeometrySrcState& restoredState);
    virtual void clipWillBeSet(const GrClip& newClip);

    bool needsNewState() const;
    bool needsNewClip() const;

    void pushState();
    void pushClip();

    GrTAllocator<Draw>              fDraws;
    GrTAllocator<SavedDrawState>    fStates;
    GrTAllocator<Clear>             fClears;

    GrTAllocator<GrClip>            fClips;
    bool                            fClipSet;

    GrVertexLayout                  fLastRectVertexLayout;
    const GrIndexBuffer*            fQuadIndexBuffer;
    int                             fMaxQuads;
    int                             fCurrQuad;

    GrVertexBufferAllocPool&        fVertexPool;

    GrIndexBufferAllocPool&         fIndexPool;
    struct GeometryPoolState {
        const GrVertexBuffer*           fPoolVertexBuffer;
        int                             fPoolStartVertex;
        const GrIndexBuffer*            fPoolIndexBuffer;
        int                             fPoolStartIndex;
        // caller may conservatively over reserve vertices / indices.
        // we release unused space back to allocator if possible
        // can only do this if there isn't an intervening pushGeometrySource()
        size_t                          fUsedPoolVertexBytes;
        size_t                          fUsedPoolIndexBytes;
    };
    GrTArray<GeometryPoolState> fGeoPoolStateStack;

    enum {
        kDrawPreallocCnt         = 8,
        kStatePreallocCnt        = 8,
        kClipPreallocCnt         = 8,
        kClearPreallocCnt        = 4,
        kGeoPoolStatePreAllocCnt = 4,
    };

    GrAlignedSTStorage<kDrawPreallocCnt, Draw>              fDrawStorage;
    GrAlignedSTStorage<kStatePreallocCnt, SavedDrawState>   fStateStorage;
    GrAlignedSTStorage<kClipPreallocCnt, GrClip>            fClipStorage;
    GrAlignedSTStorage<kClearPreallocCnt, Clear>            fClearStorage;
    GrAlignedSTStorage<kGeoPoolStatePreAllocCnt,
                        GeometryPoolState>                  fGeoStackStorage;

    typedef GrDrawTarget INHERITED;
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrIndexBuffer_DEFINED
#define GrIndexBuffer_DEFINED

#include "GrGeometryBuffer.h"

class GrIndexBuffer : public GrGeometryBuffer {
public:
        /**
         * Retrieves the maximum number of quads that could be rendered
         * from the index buffer (using kTriangles_PrimitiveType).
         * @return the maximum number of quads using full size of index buffer.
         */
        int maxQuads() const { return size() / (sizeof(uint16_t) * 6); }
protected:
    GrIndexBuffer(GrGpu* gpu, size_t sizeInBytes, bool dynamic)
        : INHERITED(gpu, sizeInBytes, dynamic) {}
private:
    typedef GrGeometryBuffer INHERITED;
};

#endif

license: mit


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrInstanceCounter_DEFINED
#define GrInstanceCounter_DEFINED

#include "GrTypes.h"

template <typename T> class GrInstanceCounter {
public:
    GrInstanceCounter() {
        ++gCounter;
        GrPrintf("+ %s %d\n", T::InstanceCounterClassName(), gCounter);
    }

    ~GrInstanceCounter() {
        --gCounter;
        GrPrintf("- %s %d\n", T::InstanceCounterClassName(), gCounter);
    }

private:
    static int gCounter;
};

template <typename T> int GrInstanceCounter<T>::gCounter;

#define DECLARE_INSTANCE_COUNTER(T)                                 \
    static const char* InstanceCounterClassName() { return #T; }    \
    friend class GrInstanceCounter<T>;                              \
    GrInstanceCounter<T> fInstanceCounter

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrKey_DEFINED
#define GrKey_DEFINED

#include "GrRefCnt.h"

class GrKey : public GrRefCnt {
public:
    typedef intptr_t Hash;

    explicit GrKey(Hash hash) : fHash(hash) {}

    intptr_t getHash() const { return fHash; }

    bool operator<(const GrKey& rh) const {
        return fHash < rh.fHash || (fHash == rh.fHash && this->lt(rh));
    }
    bool operator==(const GrKey& rh) const {
        return fHash == rh.fHash && this->eq(rh);
    }

protected:
    virtual bool lt(const GrKey& rh) const = 0;
    virtual bool eq(const GrKey& rh) const = 0;

private:
    const Hash fHash;
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrMatrix_DEFINED
#define GrMatrix_DEFINED

#include "GrRect.h"
#include "SkMatrix.h"

typedef SkMatrix GrMatrix;

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrMemory_DEFINED
#define GrMemory_DEFINED

#include "GrNoncopyable.h"

class GrAutoMalloc : GrNoncopyable {
public:
    GrAutoMalloc() : fPtr(NULL), fAllocatedBytes(0){
    }

    GrAutoMalloc(size_t bytes) : fPtr(GrMalloc(bytes)), fAllocatedBytes(bytes) {}
    ~GrAutoMalloc() { GrFree(fPtr); }

    /**
     *  Return the allocated memory, or NULL if it has already been freed or
     *  detached.
     */
    void* get() const { return fPtr; }

    size_t size() const { return fAllocatedBytes; }

    /**
     *  transfer ownership of the memory to the caller. It must be freed with
     *  a call to GrFree()
     */
    void* detach() {
        void* ptr = fPtr;
        fPtr = NULL;    // we no longer own the block
        fAllocatedBytes = 0;
        return ptr;
    }

    /**
     *  Reallocates to a new size. May or may not call malloc. The contents
     *  are not preserved. If growOnly is true it will never reduce the
     *  allocated size.
     */
    void* realloc(size_t newSize, bool growOnly = false) {
        bool alloc;
        if (growOnly) {
            alloc = newSize > fAllocatedBytes;
        } else {
            alloc = newSize != fAllocatedBytes;
        }
        if (alloc) {
            GrFree(fPtr);
            fPtr = newSize ? GrMalloc(newSize) : NULL;
            fAllocatedBytes = newSize;
        }
        GrAssert(fAllocatedBytes >= newSize);
        GR_DEBUGCODE(memset(fPtr, 0xEF, fAllocatedBytes));
        return fPtr;
    }

    /**
     *  free the block now. get() will now return NULL
     */
    void free() {
        GrFree(fPtr);
        fPtr = NULL;
        fAllocatedBytes = 0;
    }

private:
    void* fPtr;
    size_t fAllocatedBytes;
};

/**
 *  Variant of GrAutoMalloc with a compile-time specified byte size that is
 *  pre-allocated in the class object, avoiding a call to to GrMalloc if
 *  possible.
 */
template <size_t SIZE> class GrAutoSMalloc : GrNoncopyable {
public:
    GrAutoSMalloc() {
        fPtr = fStorage;
        fAllocatedBytes = SIZE;
    }

    explicit GrAutoSMalloc(size_t bytes) {
        if (bytes > SIZE) {
            fPtr = GrMalloc(bytes);
            fAllocatedBytes = bytes;
        } else {
            fPtr = fStorage;
            fAllocatedBytes = SIZE;
        }
    }

    ~GrAutoSMalloc() {
        if (fPtr != (void*)fStorage) {
            GrFree(fPtr);
        }
    }

    /**
     *  Return the allocated memory, or NULL if it has already been freed or
     *  detached.
     */
    void* get() const { return fPtr; }

    /**
     *  Reallocates to a new size. May or may not call malloc. The contents
     *  are not preserved. If growOnly is true it will never reduce the
     *  allocated size.
     */
    void* realloc(size_t newSize, bool growOnly = false) {
        if (newSize <= SIZE) {
            if (NULL == fPtr) {
                fPtr = fStorage;
                fAllocatedBytes = SIZE;
            } else if (!growOnly && fPtr != (void*)fStorage) {
                GrFree(fPtr);
                fPtr = fStorage;
                fAllocatedBytes = SIZE;
            }
        } else if ((newSize > fAllocatedBytes) ||
                   (!growOnly && newSize < (fAllocatedBytes >> 1))) {
            if (NULL != fPtr && fPtr != (void*)fStorage) {
                GrFree(fPtr);
            }
            fPtr = GrMalloc(newSize);
            fAllocatedBytes = newSize;
        }
        GrAssert(fAllocatedBytes >= newSize);
        GrAssert((fPtr == fStorage) == (fAllocatedBytes == SIZE));
        GR_DEBUGCODE(memset(fPtr, 0xEF, fAllocatedBytes));
        return fPtr;
    }

    /**
     *  free the block now. get() will now return NULL
     */
    void free() {
        if (fPtr != (void*)fStorage) {
            GrFree(fPtr);
        }
        fAllocatedBytes = 0;
        fPtr = NULL;
    }

private:
    void*    fPtr;
    uint32_t fAllocatedBytes;
    uint32_t fStorage[GrALIGN4(SIZE) >> 2];
};

/**
 *  Variant of GrAutoMalloc with a compile-time specified byte size that is
 *  pre-allocated in the class object, avoiding a call to to GrMalloc if
 *  possible.
 */
template <int COUNT, typename T>
class GrAutoSTMalloc : public GrAutoSMalloc<COUNT * sizeof(T)> {
public:
    GrAutoSTMalloc(int count) : GrAutoSMalloc<COUNT * sizeof(T)>(count * sizeof(T)) {}

    operator T*() { return (T*)this->get(); }
};

#endif


code:
#ifndef GrMesh_DEFINED
#define GrMesh_DEFINED

#include "SkRect.h"
#include "SkPoint.h"

class SkCanvas;
class SkPaint;

class GrMesh {
public:
    GrMesh();
    ~GrMesh();

    GrMesh& operator=(const GrMesh& src);

    void init(const SkRect& bounds, int rows, int cols,
              const SkRect& texture);

    const SkRect& bounds() const { return fBounds; }

    int rows() const { return fRows; }
    int cols() const { return fCols; }
    SkPoint& pt(int row, int col) {
        return fPts[row * (fRows + 1) + col];
    }

    void draw(SkCanvas*, const SkPaint&);
    void drawWireframe(SkCanvas* canvas, const SkPaint& paint);

private:
    SkRect      fBounds;
    int         fRows, fCols;
    SkPoint*    fPts;
    SkPoint*    fTex;   // just points into fPts, not separately allocated
    int         fCount;
    uint16_t*   fIndices;
    int         fIndexCount;
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrNoncopyable_DEFINED
#define GrNoncopyable_DEFINED

#include "GrTypes.h"

/**
 *  Base for classes that want to disallow copying themselves. It makes its
 *  copy-constructor and assignment operators private (and unimplemented).
 */
class GR_API GrNoncopyable {
public:
    GrNoncopyable() {}

private:
    // illegal
    GrNoncopyable(const GrNoncopyable&);
    GrNoncopyable& operator=(const GrNoncopyable&);
};

#endif


code:
/*
    Copyright 2011 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrPaint_DEFINED
#define GrPaint_DEFINED

#include "GrTexture.h"
#include "GrColor.h"
#include "GrSamplerState.h"

#include "SkXfermode.h"

/**
 * The paint describes how pixels are colored when the context draws to
 * them. TODO: Make this a "real" class with getters and setters, default
 * values, and documentation.
 */
class GrPaint {
public:
    enum {
        kMaxTextures = 1,
        kMaxMasks    = 1,
    };

    // All the paint fields are public except textures/samplers
    GrBlendCoeff                fSrcBlendCoeff;
    GrBlendCoeff                fDstBlendCoeff;
    bool                        fAntiAlias;
    bool                        fDither;
    bool                        fFallback;

    GrColor                     fColor;

    GrColor                     fColorFilterColor;
    SkXfermode::Mode            fColorFilterXfermode;

    void setTexture(int i, GrTexture* texture) {
        GrAssert((unsigned)i < kMaxTextures);
        GrSafeRef(texture);
        GrSafeUnref(fTextures[i]);
        fTextures[i] = texture;
    }

    GrTexture* getTexture(int i) const {
        GrAssert((unsigned)i < kMaxTextures);
        return fTextures[i];
    }

    GrSamplerState* getTextureSampler(int i) {
        GrAssert((unsigned)i < kMaxTextures);
        return fTextureSamplers + i;
    }

    const GrSamplerState* getTextureSampler(int i) const {
        GrAssert((unsigned)i < kMaxTextures);
        return fTextureSamplers + i;
    }

    // The mask can be alpha-only or per channel. It is applied
    // after the colorfilter
    void setMask(int i, GrTexture* mask) {
        GrAssert((unsigned)i < kMaxMasks);
        GrSafeRef(mask);
        GrSafeUnref(fMaskTextures[i]);
        fMaskTextures[i] = mask;
    }

    GrTexture* getMask(int i) const {
        GrAssert((unsigned)i < kMaxMasks);
        return fMaskTextures[i];
    }

    // mask's sampler matrix is always applied to the positions
    // (i.e. no explicit texture coordinates)
    GrSamplerState* getMaskSampler(int i) {
        GrAssert((unsigned)i < kMaxMasks);
        return fMaskSamplers + i;
    }

    const GrSamplerState* getMaskSampler(int i) const {
        GrAssert((unsigned)i < kMaxMasks);
        return fMaskSamplers + i;
    }

    // pre-concats sampler matrices for non-NULL textures and masks
    void preConcatActiveSamplerMatrices(const GrMatrix& matrix) {
        for (int i = 0; i < kMaxTextures; ++i) {
            fTextureSamplers[i].preConcatMatrix(matrix);
        }
        for (int i = 0; i < kMaxMasks; ++i) {
            fMaskSamplers[i].preConcatMatrix(matrix);
        }
    }

    // uninitialized
    GrPaint() {
        for (int i = 0; i < kMaxTextures; ++i) {
            fTextures[i] = NULL;
        }
        for (int i = 0; i < kMaxMasks; ++i) {
            fMaskTextures[i] = NULL;
        }

        fFallback = false;
    }

    GrPaint(const GrPaint& paint) {
        fSrcBlendCoeff = paint.fSrcBlendCoeff;
        fDstBlendCoeff = paint.fDstBlendCoeff;
        fAntiAlias = paint.fAntiAlias;
        fDither = paint.fDither;

        fColor = paint.fColor;

        fColorFilterColor = paint.fColorFilterColor;
        fColorFilterXfermode = paint.fColorFilterXfermode;

        for (int i = 0; i < kMaxTextures; ++i) {
            fTextureSamplers[i] = paint.fTextureSamplers[i];
            fTextures[i] = paint.fTextures[i];
            GrSafeRef(fTextures[i]);
        }
        for (int i = 0; i < kMaxMasks; ++i) {
            fMaskSamplers[i] = paint.fMaskSamplers[i];
            fMaskTextures[i] = paint.fMaskTextures[i];
            GrSafeRef(fMaskTextures[i]);
        }

        fFallback = false;
    }

    ~GrPaint() {
        for (int i = 0; i < kMaxTextures; ++i) {
            GrSafeUnref(fTextures[i]);
        }
        for (int i = 0; i < kMaxMasks; ++i) {
            GrSafeUnref(fMaskTextures[i]);
        }
    }

    // sets paint to src-over, solid white, no texture, no mask
    void reset() {
        this->resetBlend();
        this->resetOptions();
        this->resetColor();
        this->resetTextures();
        this->resetColorFilter();
        this->resetMasks();
    }

    void resetColorFilter() {
        fColorFilterXfermode = SkXfermode::kDst_Mode;
        fColorFilterColor = GrColorPackRGBA(0xff, 0xff, 0xff, 0xff);
    }

    bool hasTexture() const {
        return 0 != this->getActiveTextureStageMask();
    }

    bool hasMask() const {
        return 0 != this->getActiveMaskStageMask();
    }

    bool hasTextureOrMask() const {
        return this->hasTexture() || this->hasMask();
    }

    // helpers for GrContext, GrTextContext
    int getActiveTextureStageMask() const {
        int mask = 0;
        for (int i = 0; i < kMaxTextures; ++i) {
            if (NULL != fTextures[i]) {
                mask |= 1 << (i + kFirstTextureStage);
            }
        }
        return mask;
    }

    int getActiveMaskStageMask() const {
        int mask = 0;
        for (int i = 0; i < kMaxMasks; ++i) {
            if (NULL != fMaskTextures[i]) {
                mask |= 1 << (i + kFirstMaskStage);
            }
        }
        return mask;
    }

    int getActiveStageMask() const {
        return this->getActiveTextureStageMask() |
                this->getActiveMaskStageMask();
    }

    // internal use
    // GrPaint's textures and masks map to the first N stages
    // of GrDrawTarget in that order (textures followed by masks)
    enum {
        kFirstTextureStage = 0,
        kFirstMaskStage = kMaxTextures,
        kTotalStages = kMaxTextures + kMaxMasks,
    };

private:

    GrSamplerState              fTextureSamplers[kMaxTextures];
    GrSamplerState              fMaskSamplers[kMaxMasks];

    GrTexture*      fTextures[kMaxTextures];
    GrTexture*      fMaskTextures[kMaxMasks];

    void resetBlend() {
        fSrcBlendCoeff = kOne_BlendCoeff;
        fDstBlendCoeff = kZero_BlendCoeff;
    }

    void resetOptions() {
        fAntiAlias = false;
        fDither = false;
    }

    void resetColor() {
        fColor = GrColorPackRGBA(0xff, 0xff, 0xff, 0xff);
    }

    void resetTextures() {
        for (int i = 0; i < kMaxTextures; ++i) {
            this->setTexture(i, NULL);
            fTextureSamplers[i].setClampNoFilter();
        }
    }

    void resetMasks() {
        for (int i = 0; i < kMaxMasks; ++i) {
            this->setMask(i, NULL);
            fMaskSamplers[i].setClampNoFilter();
        }
    }
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrPath_DEFINED
#define GrPath_DEFINED

#include "GrTypes.h"
#include "SkPath.h"

typedef SkPath GrPath;

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrPathIter_DEFINED
#define GrPathIter_DEFINED

#include "GrTypes.h"

struct GrPoint;

/**
 2D Path iterator. Porting layer creates a subclass of this. It allows Ganesh to
 parse the top-level API's 2D paths. Supports lines, quadratics, and cubic
 pieces and moves (multi-part paths).
 */
class GrPathIter {
public:
    /**
     Returned by next(). Indicates the next piece of the path.
     */
    enum Command {
        kMove_Command,      //!< next() returns 1 pt
                            //   Starts a new subpath at
                            //   at the returned point
        kLine_Command,      //!< next() returns 2 pts
                            //   Adds a line segment
        kQuadratic_Command, //!< next() returns 3 pts
                            //   Adds a quadratic segment
        kCubic_Command,     //!< next() returns 4 pts
                            //   Adds a cubic segment
        kClose_Command,     //!< next() returns 0 pts
        kEnd_Command        //!< next() returns 0 pts
                            //   Implictly closes the last
                            //   point
    };

    enum ConvexHint {
        kNone_ConvexHint,                         //<! No hint about convexity
                                                  //   of the path
        kConvex_ConvexHint,                       //<! Path is one convex piece
        kNonOverlappingConvexPieces_ConvexHint,   //<! Multiple convex pieces,
                                                  //   pieces are known to be
                                                  //   disjoint
        kSameWindingConvexPieces_ConvexHint,      //<! Multiple convex pieces,
                                                  //   may or may not intersect,
                                                  //   either all wind cw or all
                                                  //   wind ccw.
        kConcave_ConvexHint                       //<! Path is known to be
                                                  //   concave
    };

    static int NumCommandPoints(Command cmd) {
        static const int numPoints[] = {
            1, 2, 3, 4, 0, 0
        };
        return numPoints[cmd];
    }

    virtual ~GrPathIter() {};

    /**
     Iterates through the path. Should not be called after
     kEnd_Command has been returned once. This version retrieves the
     points for the command.
     @param points  The points relevant to returned commend. See Command
                    enum for number of points valid for each command.
     @return The next command of the path.
     */
    virtual Command next(GrPoint points[4]) = 0;

    /**
     * If the host API has knowledge of the convexity of the path
     * it can be communicated by this hint. Ganesh can make these
     * determinations itself. So it is not necessary to compute
     * convexity status if it isn't already determined.
     *
     * @return a hint about the convexity of the path.
     */
    virtual ConvexHint hint() const { return kNone_ConvexHint; }

     /**
     Iterates through the path. Should not be called after
     kEnd_Command has been returned once. This version does not retrieve the
     points for the command.
     @return The next command of the path.
     */
     virtual Command next() = 0;

    /**
     Restarts iteration from the beginning.
     */
    virtual void rewind() = 0;

};

#endif


code:
/*
    Copyright 2011 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrPathRenderer_DEFINED
#define GrPathRenderer_DEFINED

#include "GrDrawTarget.h"

class SkPath;
struct GrPoint;

/**
 *  Base class for drawing paths into a GrDrawTarget.
 */
class GR_API GrPathRenderer : public GrRefCnt {
public:
    GrPathRenderer(void);

    /**
     * Returns true if this path renderer is able to render the path.
     * Returning false allows the caller to fallback to another path renderer.
     *
     * @param target    The target to draw into
     * @param path      The path to draw
     * @param fill      The fill rule to use
     *
     * @return  true if the path can be drawn by this object, false otherwise.
     */
    virtual bool canDrawPath(const GrDrawTarget* target, const SkPath& path,
                             GrPathFill fill) const = 0;

    /**
     * Draws a path into the draw target. The target will already have its draw
     * state configured for the draw.
     * @param target                the target to draw into.
     * @param stages                indicates which stages the are already
     *                              in use. All enabled stages expect positions
     *                              as texture coordinates. The path renderer
     *                              use the remaining stages for its path
     *                              filling algorithm.
     * @param path                  the path to draw.
     * @param fill                  the fill rule to apply.
     * @param translate             optional additional translation to apply to
     *                              the path. NULL means (0,0).
     */
    virtual void drawPath(GrDrawTarget* target,
                          GrDrawTarget::StageBitfield stages,
                          const SkPath& path,
                          GrPathFill fill,
                          const GrPoint* translate) = 0;

    /**
     * For complex clips Gr uses the stencil buffer. The path renderer must be
     * able to render paths into the stencil buffer. However, the path renderer
     * itself may require the stencil buffer to resolve the path fill rule. This
     * function queries whether the path render needs its own stencil
     * pass. If this returns false then drawPath() should not modify the
     * the target's stencil settings but use those already set on target.
     *
     * @param target target that the path will be rendered to
     * @param path   the path that will be drawn
     * @param fill   the fill rule that will be used, will never be an inverse
     *               rule.
     *
     * @return false if this path renderer can generate interior-only fragments
     *         without changing the stencil settings on the target. If it
     *         returns true the drawPathToStencil will be used when rendering
     *         clips.
     */
    virtual bool requiresStencilPass(const GrDrawTarget* target,
                                     const SkPath& path,
                                     GrPathFill fill) const { return false; }

    /**
     * Draws a path to the stencil buffer. Assume the writable stencil bits
     * are already initialized to zero. Fill will always be either
     * kWinding_PathFill or kEvenOdd_PathFill.
     *
     * Only called if requiresStencilPass returns true for the same combo of
     * target, path, and fill. Never called with an inverse fill.
     *
     * The default implementation assumes the path filling algorithm doesn't
     * require a separate stencil pass and so crashes.
     *
     *
     * @param target                the target to draw into.
     * @param path                  the path to draw.
     * @param fill                  the fill rule to apply.
     * @param translate             optional additional translation to apply to
     *                              the path. NULL means (0,0).
     */
    virtual void drawPathToStencil(GrDrawTarget* target,
                                   const SkPath& path,
                                   GrPathFill fill,
                                   const GrPoint* translate) {
        GrCrash("Unexpected call to drawPathToStencil.");
    }

    /**
     * @return true if the path renderer can perform anti-aliasing (aside from
     * having FSAA enabled for a render target)
     */
    virtual bool supportsAA(GrDrawTarget* target,
                            const SkPath& path,
                            GrPathFill fill) { return false; }

    /**
     * This is called to install a custom path renderer in every GrContext at
     * create time. The default implementation in GrCreatePathRenderer_none.cpp
     * returns NULL. Link against another implementation to install your own.
     */
    static GrPathRenderer* CreatePathRenderer();

    /**
     * Multiply curve tolerance by the given value, increasing or decreasing
     * the maximum error permitted in tesselating curves with short straight
     * line segments.
     */
    void scaleCurveTolerance(GrScalar multiplier) {
        GrAssert(multiplier > 0);
        fCurveTolerance = SkScalarMul(fCurveTolerance, multiplier);
    }

protected:
    GrScalar fCurveTolerance;

private:

    typedef GrRefCnt INHERITED;
};

/**
 *  Subclass that renders the path using the stencil buffer to resolve fill
 *  rules (e.g. winding, even-odd)
 */
class GR_API GrDefaultPathRenderer : public GrPathRenderer {
public:
    GrDefaultPathRenderer(bool separateStencilSupport,
                          bool stencilWrapOpsSupport);

    virtual bool canDrawPath(const GrDrawTarget* target,
                             const SkPath& path,
                             GrPathFill fill) const { return true; }

    virtual void drawPath(GrDrawTarget* target,
                          GrDrawTarget::StageBitfield stages,
                          const SkPath& path,
                          GrPathFill fill,
                          const GrPoint* translate);
    virtual bool requiresStencilPass(const GrDrawTarget* target,
                                     const SkPath& path,
                                     GrPathFill fill) const;
    virtual void drawPathToStencil(GrDrawTarget* target,
                                   const SkPath& path,
                                   GrPathFill fill,
                                   const GrPoint* translate);
private:

    void onDrawPath(GrDrawTarget* target,
                    GrDrawTarget::StageBitfield stages,
                    const SkPath& path,
                    GrPathFill fill,
                    const GrPoint* translate,
                    bool stencilOnly);

    bool    fSeparateStencil;
    bool    fStencilWrapOps;

    typedef GrPathRenderer INHERITED;
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrPathSink_DEFINED
#define GrPathSink_DEFINED

#include "GrScalar.h"

class GrPathSink {
public:
    virtual ~GrPathSink() {}

    virtual void moveTo(GrScalar x, GrScalar y) = 0;
    virtual void lineTo(GrScalar x, GrScalar y) = 0;
    virtual void quadTo(GrScalar x0, GrScalar y0, GrScalar x1, GrScalar y1) = 0;
    virtual void cubicTo(GrScalar x0, GrScalar y0, GrScalar x1, GrScalar y1,
                         GrScalar x2, GrScalar y2) = 0;
    virtual void close() = 0;
};

#endif


code:
/*
    Copyright 2011 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrPathUtils_DEFINED
#define GrPathUtils_DEFINED

#include "GrNoncopyable.h"
#include "GrPoint.h"
#include "GrPath.h"

/**
 *  Utilities for evaluating paths.
 */
class GrPathUtils : public GrNoncopyable {
public:
    /// Since we divide by tol if we're computing exact worst-case bounds,
    /// very small tolerances will be increased to gMinCurveTol.
    static int worstCasePointCount(const GrPath&,
                                   int* subpaths,
                                   GrScalar tol);
    /// Since we divide by tol if we're computing exact worst-case bounds,
    /// very small tolerances will be increased to gMinCurveTol.
    static uint32_t quadraticPointCount(const GrPoint points[], GrScalar tol);
    static uint32_t generateQuadraticPoints(const GrPoint& p0,
                                            const GrPoint& p1,
                                            const GrPoint& p2,
                                            GrScalar tolSqd,
                                            GrPoint** points,
                                            uint32_t pointsLeft);
    /// Since we divide by tol if we're computing exact worst-case bounds,
    /// very small tolerances will be increased to gMinCurveTol.
    static uint32_t cubicPointCount(const GrPoint points[], GrScalar tol);
    static uint32_t generateCubicPoints(const GrPoint& p0,
                                        const GrPoint& p1,
                                        const GrPoint& p2,
                                        const GrPoint& p3,
                                        GrScalar tolSqd,
                                        GrPoint** points,
                                        uint32_t pointsLeft);

private:
    static const GrScalar gMinCurveTol;
};
#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrPlotMgr_DEFINED
#define GrPlotMgr_DEFINED

#include "GrTypes.h"
#include "GrPoint.h"

class GrPlotMgr : GrNoncopyable {
public:
    GrPlotMgr(int width, int height) {
        fDim.set(width, height);
        size_t needed = width * height;
        if (needed <= sizeof(fStorage)) {
            fBusy = fStorage;
        } else {
            fBusy = new char[needed];
        }
        this->reset();
    }

    ~GrPlotMgr() {
        if (fBusy != fStorage) {
            delete[] fBusy;
        }
    }

    void reset() {
        Gr_bzero(fBusy, fDim.fX * fDim.fY);
    }

    bool newPlot(GrIPoint16* loc) {
        char* busy = fBusy;
        for (int y = 0; y < fDim.fY; y++) {
            for (int x = 0; x < fDim.fX; x++) {
                if (!*busy) {
                    *busy = true;
                    loc->set(x, y);
                    return true;
                }
                busy++;
            }
        }
        return false;
    }

    bool isBusy(int x, int y) const {
        GrAssert((unsigned)x < (unsigned)fDim.fX);
        GrAssert((unsigned)y < (unsigned)fDim.fY);
        return fBusy[y * fDim.fX + x] != 0;
    }

    void freePlot(int x, int y) {
        GrAssert((unsigned)x < (unsigned)fDim.fX);
        GrAssert((unsigned)y < (unsigned)fDim.fY);
        fBusy[y * fDim.fX + x] = false;
    }

private:
    enum {
        STORAGE = 64
    };
    char fStorage[STORAGE];
    char* fBusy;
    GrIPoint16  fDim;
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrPoint_DEFINED
#define GrPoint_DEFINED

#include "GrTypes.h"
#include "GrScalar.h"
#include "SkPoint.h"

#define GrPoint     SkPoint
#define GrVec       SkVector

struct GrIPoint16 {
    int16_t fX, fY;

    void set(intptr_t x, intptr_t y) {
        fX = GrToS16(x);
        fY = GrToS16(y);
    }
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

/*
    These are our vertex-indices for a series of "quads", which we implement
    as a series of pairs of triangles. See setRectFan() for the
    vertex order.

    The largest value is 255, so we could store these in any size
    (byte, short, int). Since the table is small, we just choose the size
    that we think will be fastest (e.g. some drivers don't have native support
    for byte-indices, so byte may not be the fastest)
*/
static const uint16_t gQuadIndexTable[] = {
      0,   1,   2,   0,   2,   3,
      4,   5,   6,   4,   6,   7,
      8,   9,  10,   8,  10,  11,
     12,  13,  14,  12,  14,  15,
     16,  17,  18,  16,  18,  19,
     20,  21,  22,  20,  22,  23,
     24,  25,  26,  24,  26,  27,
     28,  29,  30,  28,  30,  31,
     32,  33,  34,  32,  34,  35,
     36,  37,  38,  36,  38,  39,
     40,  41,  42,  40,  42,  43,
     44,  45,  46,  44,  46,  47,
     48,  49,  50,  48,  50,  51,
     52,  53,  54,  52,  54,  55,
     56,  57,  58,  56,  58,  59,
     60,  61,  62,  60,  62,  63,
     64,  65,  66,  64,  66,  67,
     68,  69,  70,  68,  70,  71,
     72,  73,  74,  72,  74,  75,
     76,  77,  78,  76,  78,  79,
     80,  81,  82,  80,  82,  83,
     84,  85,  86,  84,  86,  87,
     88,  89,  90,  88,  90,  91,
     92,  93,  94,  92,  94,  95,
     96,  97,  98,  96,  98,  99,
    100, 101, 102, 100, 102, 103,
    104, 105, 106, 104, 106, 107,
    108, 109, 110, 108, 110, 111,
    112, 113, 114, 112, 114, 115,
    116, 117, 118, 116, 118, 119,
    120, 121, 122, 120, 122, 123,
    124, 125, 126, 124, 126, 127,
    128, 129, 130, 128, 130, 131,
    132, 133, 134, 132, 134, 135,
    136, 137, 138, 136, 138, 139,
    140, 141, 142, 140, 142, 143,
    144, 145, 146, 144, 146, 147,
    148, 149, 150, 148, 150, 151,
    152, 153, 154, 152, 154, 155,
    156, 157, 158, 156, 158, 159,
    160, 161, 162, 160, 162, 163,
    164, 165, 166, 164, 166, 167,
    168, 169, 170, 168, 170, 171,
    172, 173, 174, 172, 174, 175,
    176, 177, 178, 176, 178, 179,
    180, 181, 182, 180, 182, 183,
    184, 185, 186, 184, 186, 187,
    188, 189, 190, 188, 190, 191,
    192, 193, 194, 192, 194, 195,
    196, 197, 198, 196, 198, 199,
    200, 201, 202, 200, 202, 203,
    204, 205, 206, 204, 206, 207,
    208, 209, 210, 208, 210, 211,
    212, 213, 214, 212, 214, 215,
    216, 217, 218, 216, 218, 219,
    220, 221, 222, 220, 222, 223,
    224, 225, 226, 224, 226, 227,
    228, 229, 230, 228, 230, 231,
    232, 233, 234, 232, 234, 235,
    236, 237, 238, 236, 238, 239,
    240, 241, 242, 240, 242, 243,
    244, 245, 246, 244, 246, 247,
    248, 249, 250, 248, 250, 251,
    252, 253, 254, 252, 254, 255,
};

#define GR_COUNT_QUADINDEXTABLE    GR_ARRAY_COUNT(gQuadIndexTable)


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrRandom_DEFINED
#define GrRandom_DEFINED

class GrRandom {
public:
    GrRandom() : fSeed(0) {}
    GrRandom(uint32_t seed) : fSeed(seed) {}

    uint32_t seed() const { return fSeed; }

    uint32_t nextU() {
        fSeed = fSeed * kMUL + kADD;
        return fSeed;
    }

    int32_t nextS() { return (int32_t)this->nextU(); }

    /**
     *  Returns value [0...1) as a float
     */
    float nextF() {
        // const is 1 / (2^32 - 1)
        return (float)(this->nextU() * 2.32830644e-10);
    }

    /**
     *  Returns value [min...max) as a float
     */
    float nextF(float min, float max) {
        return min + this->nextF() * (max - min);
    }

private:
    /*
     *  These constants taken from "Numerical Recipes in C", reprinted 1999
     */
    enum {
        kMUL = 1664525,
        kADD = 1013904223
    };
    uint32_t    fSeed;
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrRect_DEFINED
#define GrRect_DEFINED

#include "GrPoint.h"
#include "SkRect.h"

typedef SkIRect GrIRect;
typedef SkRect  GrRect;

struct GrIRect16 {
    int16_t fLeft, fTop, fRight, fBottom;

    int width() const { return fRight - fLeft; }
    int height() const { return fBottom - fTop; }
    int area() const { return this->width() * this->height(); }
    bool isEmpty() const { return fLeft >= fRight || fTop >= fBottom; }

    void set(const GrIRect& r) {
        fLeft   = SkToS16(r.fLeft);
        fTop    = SkToS16(r.fTop);
        fRight  = SkToS16(r.fRight);
        fBottom = SkToS16(r.fBottom);
    }
};

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrRectanizer_DEFINED
#define GrRectanizer_DEFINED

#include "GrRect.h"
#include "GrTDArray.h"

class GrRectanizerPurgeListener {
public:
    virtual ~GrRectanizerPurgeListener() {}

    virtual void notifyPurgeStrip(void*, int yCoord) = 0;
};

class GrRectanizer {
public:
    GrRectanizer(int width, int height) : fWidth(width), fHeight(height) {
        GrAssert(width >= 0);
        GrAssert(height >= 0);
    }

    virtual ~GrRectanizer() {}

    int width() const { return fWidth; }
    int height() const { return fHeight; }

    virtual bool addRect(int width, int height, GrIPoint16* loc) = 0;
    virtual float percentFull() const = 0;

    // return the Y-coordinate of a strip that should be purged, given height
    // i.e. return the oldest such strip, or some other criteria. Return -1
    // if there is no candidate
    virtual int stripToPurge(int height) const = 0;
    virtual void purgeStripAtY(int yCoord) = 0;

    /**
     *  Our factory, which returns the subclass du jour
     */
    static GrRectanizer* Factory(int width, int height);

private:
    int fWidth;
    int fHeight;
};

#endif


code:
/*
    Copyright 2011 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrRedBlackTree_DEFINED
#define GrRedBlackTree_DEFINED

#include "GrNoncopyable.h"

template <typename T>
class GrLess {
public:
    bool operator()(const T& a, const T& b) const { return a < b; }
};

template <typename T>
class GrLess<T*> {
public:
    bool operator()(const T* a, const T* b) const { return *a < *b; }
};

/**
 * In debug build this will cause full traversals of the tree when the validate
 * is called on insert and remove. Useful for debugging but very slow.
 */
#define DEEP_VALIDATE 0

/**
 * A sorted tree that uses the red-black tree algorithm. Allows duplicate
 * entries. Data is of type T and is compared using functor C. A single C object
 * will be created and used for all comparisons.
 */
template <typename T, typename C = GrLess<T> >
class GrRedBlackTree : public GrNoncopyable {
public:
    /**
     * Creates an empty tree.
     */
    GrRedBlackTree();
    virtual ~GrRedBlackTree();

    /**
     * Class used to iterater through the tree. The valid range of the tree
     * is given by [begin(), end()). It is legal to dereference begin() but not
     * end(). The iterator has preincrement and predecrement operators, it is
     * legal to decerement end() if the tree is not empty to get the last
     * element. However, a last() helper is provided.
     */
    class Iter;

    /**
     * Add an element to the tree. Duplicates are allowed.
     * @param t     the item to add.
     * @return  an iterator to the item.
     */
    Iter insert(const T& t);

    /**
     * Removes all items in the tree.
     */
    void reset();

    /**
     * @return true if there are no items in the tree, false otherwise.
     */
    bool empty() const {return 0 == fCount;}

    /**
     * @return the number of items in the tree.
     */
    int  count() const {return fCount;}

    /**
     * @return  an iterator to the first item in sorted order, or end() if empty
     */
    Iter begin();
    /**
     * Gets the last valid iterator. This is always valid, even on an empty.
     * However, it can never be dereferenced. Useful as a loop terminator.
     * @return  an iterator that is just beyond the last item in sorted order.
     */
    Iter end();
    /**
     * @return  an iterator that to the last item in sorted order, or end() if
     * empty.
     */
    Iter last();

    /**
     * Finds an occurrence of an item.
     * @param t     the item to find.
     * @return an iterator to a tree element equal to t or end() if none exists.
     */
    Iter find(const T& t);
    /**
     * Finds the first of an item in iterator order.
     * @param t     the item to find.
     * @return  an iterator to the first element equal to t or end() if
     *          none exists.
     */
    Iter findFirst(const T& t);
    /**
     * Finds the last of an item in iterator order.
     * @param t     the item to find.
     * @return  an iterator to the last element equal to t or end() if
     *          none exists.
     */
    Iter findLast(const T& t);
    /**
     * Gets the number of items in the tree equal to t.
     * @param t     the item to count.
     * @return  number of items equal to t in the tree
     */
    int countOf(const T& t) const;

    /**
     * Removes the item indicated by an iterator. The iterator will not be valid
     * afterwards.
     *
     * @param iter      iterator of item to remove. Must be valid (not end()).
     */
    void remove(const Iter& iter) { deleteAtNode(iter.fN); }

    static void UnitTest();

private:
    enum Color {
        kRed_Color,
        kBlack_Color
    };

    enum Child {
        kLeft_Child  = 0,
        kRight_Child = 1
    };

    struct Node {
        T       fItem;
        Color   fColor;

        Node*   fParent;
        Node*   fChildren[2];
    };

    void rotateRight(Node* n);
    void rotateLeft(Node* n);

    static Node* SuccessorNode(Node* x);
    static Node* PredecessorNode(Node* x);

    void deleteAtNode(Node* x);
    static void RecursiveDelete(Node* x);

    int onCountOf(const Node* n, const T& t) const;

#if GR_DEBUG
    void validate() const;
    int checkNode(Node* n, int* blackHeight) const;
    // checks relationship between a node and its children. allowRedRed means
    // node may be in an intermediate state where a red parent has a red child.
    bool validateChildRelations(const Node* n, bool allowRedRed) const;
    // place to stick break point if validateChildRelations is failing.
    bool validateChildRelationsFailed() const { return false; }
#else
    void validate() const {}
#endif

    int     fCount;
    Node*   fRoot;
    Node*   fFirst;
    Node*   fLast;

    const C fComp;
};

template <typename T, typename C>
class GrRedBlackTree<T,C>::Iter {
public:
    Iter() {};
    Iter(const Iter& i) {fN = i.fN; fTree = i.fTree;}
    Iter& operator =(const Iter& i) {
        fN = i.fN;
        fTree = i.fTree;
        return *this;
    }
    // altering the sort value of the item using this method will cause
    // errors.
    T& operator *() const { return fN->fItem; }
    bool operator ==(const Iter& i) const {
        return fN == i.fN && fTree == i.fTree;
    }
    bool operator !=(const Iter& i) const { return !(*this == i); }
    Iter& operator ++() {
        GrAssert(*this != fTree->end());
        fN = SuccessorNode(fN);
        return *this;
    }
    Iter& operator --() {
        GrAssert(*this != fTree->begin());
        if (NULL != fN) {
            fN = PredecessorNode(fN);
        } else {
            *this = fTree->last();
        }
        return *this;
    }

private:
    friend class GrRedBlackTree;
    explicit Iter(Node* n, GrRedBlackTree* tree) {
        fN = n;
        fTree = tree;
    }
    Node* fN;
    GrRedBlackTree* fTree;
};

template <typename T, typename C>
GrRedBlackTree<T,C>::GrRedBlackTree() : fComp() {
    fRoot = NULL;
    fFirst = NULL;
    fLast = NULL;
    fCount = 0;
    validate();
}

template <typename T, typename C>
GrRedBlackTree<T,C>::~GrRedBlackTree() {
    RecursiveDelete(fRoot);
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::begin() {
    return Iter(fFirst, this);
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::end() {
    return Iter(NULL, this);
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::last() {
    return Iter(fLast, this);
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::find(const T& t) {
    Node* n = fRoot;
    while (NULL != n) {
        if (fComp(t, n->fItem)) {
            n = n->fChildren[kLeft_Child];
        } else {
            if (!fComp(n->fItem, t)) {
                return Iter(n, this);
            }
            n = n->fChildren[kRight_Child];
        }
    }
    return end();
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findFirst(const T& t) {
    Node* n = fRoot;
    Node* leftMost = NULL;
    while (NULL != n) {
        if (fComp(t, n->fItem)) {
            n = n->fChildren[kLeft_Child];
        } else {
            if (!fComp(n->fItem, t)) {
                // found one. check if another in left subtree.
                leftMost = n;
                n = n->fChildren[kLeft_Child];
            } else {
                n = n->fChildren[kRight_Child];
            }
        }
    }
    return Iter(leftMost, this);
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::findLast(const T& t) {
    Node* n = fRoot;
    Node* rightMost = NULL;
    while (NULL != n) {
        if (fComp(t, n->fItem)) {
            n = n->fChildren[kLeft_Child];
        } else {
            if (!fComp(n->fItem, t)) {
                // found one. check if another in right subtree.
                rightMost = n;
            }
            n = n->fChildren[kRight_Child];
        }
    }
    return Iter(rightMost, this);
}

template <typename T, typename C>
int GrRedBlackTree<T,C>::countOf(const T& t) const {
    return onCountOf(fRoot, t);
}

template <typename T, typename C>
int GrRedBlackTree<T,C>::onCountOf(const Node* n, const T& t) const {
    // this is count*log(n) :(
    while (NULL != n) {
        if (fComp(t, n->fItem)) {
            n = n->fChildren[kLeft_Child];
        } else {
            if (!fComp(n->fItem, t)) {
                int count = 1;
                count += onCountOf(n->fChildren[kLeft_Child], t);
                count += onCountOf(n->fChildren[kRight_Child], t);
                return count;
            }
            n = n->fChildren[kRight_Child];
        }
    }
    return 0;

}

template <typename T, typename C>
void GrRedBlackTree<T,C>::reset() {
    RecursiveDelete(fRoot);
    fRoot = NULL;
    fFirst = NULL;
    fLast = NULL;
    fCount = 0;
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Iter GrRedBlackTree<T,C>::insert(const T& t) {
    validate();

    ++fCount;

    Node* x = new Node;
    x->fChildren[kLeft_Child] = NULL;
    x->fChildren[kRight_Child] = NULL;
    x->fItem = t;

    Node* returnNode = x;

    Node* gp = NULL;
    Node* p = NULL;
    Node* n = fRoot;
    Child pc = kLeft_Child; // suppress uninit warning
    Child gpc;

    bool first = true;
    bool last = true;
    while (NULL != n) {
        gpc = pc;
        pc = fComp(x->fItem, n->fItem) ? kLeft_Child : kRight_Child;
        first = first && kLeft_Child == pc;
        last = last && kRight_Child == pc;
        gp = p;
        p = n;
        n = p->fChildren[pc];
    }
    if (last) {
        fLast = x;
    }
    if (first) {
        fFirst = x;
    }

    if (NULL == p) {
        fRoot = x;
        x->fColor = kBlack_Color;
        x->fParent = NULL;
        GrAssert(1 == fCount);
        return Iter(returnNode, this);
    }
    p->fChildren[pc] = x;
    x->fColor = kRed_Color;
    x->fParent = p;

    do {
        // assumptions at loop start.
        GrAssert(NULL != x);
        GrAssert(kRed_Color == x->fColor);
        // can't have a grandparent but no parent.
        GrAssert(!(NULL != gp && NULL == p));
        // make sure pc and gpc are correct
        GrAssert(NULL == p  || p->fChildren[pc] == x);
        GrAssert(NULL == gp || gp->fChildren[gpc] == p);

        // if x's parent is black then we didn't violate any of the
        // red/black properties when we added x as red.
        if (kBlack_Color == p->fColor) {
            return Iter(returnNode, this);
        }
        // gp must be valid because if p was the root then it is black
        GrAssert(NULL != gp);
        // gp must be black since it's child, p, is red.
        GrAssert(kBlack_Color == gp->fColor);

        // x and its parent are red, violating red-black property.
        Node* u = gp->fChildren[1-gpc];
        // if x's uncle (p's sibling) is also red then we can flip
        // p and u to black and make gp red. But then we have to recurse
        // up to gp since it's parent may also be red.
        if (NULL != u && kRed_Color == u->fColor) {
            p->fColor = kBlack_Color;
            u->fColor = kBlack_Color;
            gp->fColor = kRed_Color;
            x = gp;
            p = x->fParent;
            if (NULL == p) {
                // x (prev gp) is the root, color it black and be done.
                GrAssert(fRoot == x);
                x->fColor = kBlack_Color;
                validate();
                return Iter(returnNode, this);
            }
            gp = p->fParent;
            pc = (p->fChildren[kLeft_Child] == x) ? kLeft_Child :
                                                    kRight_Child;
            if (NULL != gp) {
                gpc = (gp->fChildren[kLeft_Child] == p) ? kLeft_Child :
                                                          kRight_Child;
            }
            continue;
        } break;
    } while (true);
    // Here p is red but u is black and we still have to resolve the fact
    // that x and p are both red.
    GrAssert(NULL == gp->fChildren[1-gpc] || kBlack_Color == gp->fChildren[1-gpc]->fColor);
    GrAssert(kRed_Color == x->fColor);
    GrAssert(kRed_Color == p->fColor);
    GrAssert(kBlack_Color == gp->fColor);

    // make x be on the same side of p as p is of gp. If it isn't already
    // the case then rotate x up to p and swap their labels.
    if (pc != gpc) {
        if (kRight_Child == pc) {
            rotateLeft(p);
            Node* temp = p;
            p = x;
            x = temp;
            pc = kLeft_Child;
        } else {
            rotateRight(p);
            Node* temp = p;
            p = x;
            x = temp;
            pc = kRight_Child;
        }
    }
    // we now rotate gp down, pulling up p to be it's new parent.
    // gp's child, u, that is not affected we know to be black. gp's new
    // child is p's previous child (x's pre-rotation sibling) which must be
    // black since p is red.
    GrAssert(NULL == p->fChildren[1-pc] ||
             kBlack_Color == p->fChildren[1-pc]->fColor);
    // Since gp's two children are black it can become red if p is made
    // black. This leaves the black-height of both of p's new subtrees
    // preserved and removes the red/red parent child relationship.
    p->fColor = kBlack_Color;
    gp->fColor = kRed_Color;
    if (kLeft_Child == pc) {
        rotateRight(gp);
    } else {
        rotateLeft(gp);
    }
    validate();
    return Iter(returnNode, this);
}

template <typename T, typename C>
void GrRedBlackTree<T,C>::rotateRight(Node* n) {
    /*            d?              d?
     *           /               /
     *          n               s
     *         / \     --->    / \
     *        s   a?          c?  n
     *       / \                 / \
     *      c?  b?              b?  a?
     */
    Node* d = n->fParent;
    Node* s = n->fChildren[kLeft_Child];
    GrAssert(NULL != s);
    Node* b = s->fChildren[kRight_Child];

    if (NULL != d) {
        Child c = d->fChildren[kLeft_Child] == n ? kLeft_Child :
                                             kRight_Child;
        d->fChildren[c] = s;
    } else {
        GrAssert(fRoot == n);
        fRoot = s;
    }
    s->fParent = d;
    s->fChildren[kRight_Child] = n;
    n->fParent = s;
    n->fChildren[kLeft_Child] = b;
    if (NULL != b) {
        b->fParent = n;
    }

    GR_DEBUGASSERT(validateChildRelations(d, true));
    GR_DEBUGASSERT(validateChildRelations(s, true));
    GR_DEBUGASSERT(validateChildRelations(n, false));
    GR_DEBUGASSERT(validateChildRelations(n->fChildren[kRight_Child], true));
    GR_DEBUGASSERT(validateChildRelations(b, true));
    GR_DEBUGASSERT(validateChildRelations(s->fChildren[kLeft_Child], true));
}

template <typename T, typename C>
void GrRedBlackTree<T,C>::rotateLeft(Node* n) {

    Node* d = n->fParent;
    Node* s = n->fChildren[kRight_Child];
    GrAssert(NULL != s);
    Node* b = s->fChildren[kLeft_Child];

    if (NULL != d) {
        Child c = d->fChildren[kRight_Child] == n ? kRight_Child :
                                                   kLeft_Child;
        d->fChildren[c] = s;
    } else {
        GrAssert(fRoot == n);
        fRoot = s;
    }
    s->fParent = d;
    s->fChildren[kLeft_Child] = n;
    n->fParent = s;
    n->fChildren[kRight_Child] = b;
    if (NULL != b) {
        b->fParent = n;
    }

    GR_DEBUGASSERT(validateChildRelations(d, true));
    GR_DEBUGASSERT(validateChildRelations(s, true));
    GR_DEBUGASSERT(validateChildRelations(n, true));
    GR_DEBUGASSERT(validateChildRelations(n->fChildren[kLeft_Child], true));
    GR_DEBUGASSERT(validateChildRelations(b, true));
    GR_DEBUGASSERT(validateChildRelations(s->fChildren[kRight_Child], true));
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::SuccessorNode(Node* x) {
    GrAssert(NULL != x);
    if (NULL != x->fChildren[kRight_Child]) {
        x = x->fChildren[kRight_Child];
        while (NULL != x->fChildren[kLeft_Child]) {
            x = x->fChildren[kLeft_Child];
        }
        return x;
    }
    while (NULL != x->fParent && x == x->fParent->fChildren[kRight_Child]) {
        x = x->fParent;
    }
    return x->fParent;
}

template <typename T, typename C>
typename GrRedBlackTree<T,C>::Node* GrRedBlackTree<T,C>::PredecessorNode(Node* x) {
    GrAssert(NULL != x);
    if (NULL != x->fChildren[kLeft_Child]) {
        x = x->fChildren[kLeft_Child];
        while (NULL != x->fChildren[kRight_Child]) {
            x = x->fChildren[kRight_Child];
        }
        return x;
    }
    while (NULL != x->fParent && x == x->fParent->fChildren[kLeft_Child]) {
        x = x->fParent;
    }
    return x->fParent;
}

template <typename T, typename C>
void GrRedBlackTree<T,C>::deleteAtNode(Node* x) {
    GrAssert(NULL != x);
    validate();
    --fCount;

    bool hasLeft =  NULL != x->fChildren[kLeft_Child];
    bool hasRight = NULL != x->fChildren[kRight_Child];
    Child c = hasLeft ? kLeft_Child : kRight_Child;

    if (hasLeft && hasRight) {
        // first and last can't have two children.
        GrAssert(fFirst != x);
        GrAssert(fLast != x);
        // if x is an interior node then we find it's successor
        // and swap them.
        Node* s = x->fChildren[kRight_Child];
        while (NULL != s->fChildren[kLeft_Child]) {
            s = s->fChildren[kLeft_Child];
        }
        GrAssert(NULL != s);
        // this might be expensive relative to swapping node ptrs around.
        // depends on T.
        x->fItem = s->fItem;
        x = s;
        c = kRight_Child;
    } else if (NULL == x->fParent) {
        // if x was the root we just replace it with its child and make
        // the new root (if the tree is not empty) black.
        GrAssert(fRoot == x);
        fRoot = x->fChildren[c];
        if (NULL != fRoot) {
            fRoot->fParent = NULL;
            fRoot->fColor = kBlack_Color;
            if (x == fLast) {
                GrAssert(c == kLeft_Child);
                fLast = fRoot;
            } else if (x == fFirst) {
                GrAssert(c == kRight_Child);
                fFirst = fRoot;
            }
        } else {
            GrAssert(fFirst == fLast && x == fFirst);
            fFirst = NULL;
            fLast = NULL;
            GrAssert(0 == fCount);
        }
        delete x;
        validate();
        return;
    }

    Child pc;
    Node* p = x->fParent;
    pc = p->fChildren[kLeft_Child] == x ? kLeft_Child : kRight_Child;

    if (NULL == x->fChildren[c]) {
        if (fLast == x) {
            fLast = p;
            GrAssert(p == PredecessorNode(x));
        } else if (fFirst == x) {
            fFirst = p;
            GrAssert(p == SuccessorNode(x));
        }
        // x has two implicit black children.
        Color xcolor = x->fColor;
        p->fChildren[pc] = NULL;
        delete x;
        x = NULL;
        // when x is red it can be with an implicit black leaf without
        // violating any of the red-black tree properties.
        if (kRed_Color == xcolor) {
            validate();
            return;
        }
        // s is p's other child (x's sibling)
        Node* s = p->fChildren[1-pc];

        //s cannot be an implicit black node because the original
        // black-height at x was >= 2 and s's black-height must equal the
        // initial black height of x.
        GrAssert(NULL != s);
        GrAssert(p == s->fParent);

        // assigned in loop
        Node* sl;
        Node* sr;
        bool slRed;
        bool srRed;

        do {
            // When we start this loop x may already be deleted it is/was
            // p's child on its pc side. x's children are/were black. The
            // first time through the loop they are implict children.
            // On later passes we will be walking up the tree and they will
            // be real nodes.
            // The x side of p has a black-height that is one less than the
            // s side. It must be rebalanced.
            GrAssert(NULL != s);
            GrAssert(p == s->fParent);
            GrAssert(NULL == x || x->fParent == p);

            //sl and sr are s's children, which may be implicit.
            sl = s->fChildren[kLeft_Child];
            sr = s->fChildren[kRight_Child];

            // if the s is red we will rotate s and p, swap their colors so
            // that x's new sibling is black
            if (kRed_Color == s->fColor) {
                // if s is red then it's parent must be black.
                GrAssert(kBlack_Color == p->fColor);
                // s's children must also be black since s is red. They can't
                // be implicit since s is red and it's black-height is >= 2.
                GrAssert(NULL != sl && kBlack_Color == sl->fColor);
                GrAssert(NULL != sr && kBlack_Color == sr->fColor);
                p->fColor = kRed_Color;
                s->fColor = kBlack_Color;
                if (kLeft_Child == pc) {
                    rotateLeft(p);
                    s = sl;
                } else {
                    rotateRight(p);
                    s = sr;
                }
                sl = s->fChildren[kLeft_Child];
                sr = s->fChildren[kRight_Child];
            }
            // x and s are now both black.
            GrAssert(kBlack_Color == s->fColor);
            GrAssert(NULL == x || kBlack_Color == x->fColor);
            GrAssert(p == s->fParent);
            GrAssert(NULL == x || p == x->fParent);

            // when x is deleted its subtree will have reduced black-height.
            slRed = (NULL != sl && kRed_Color == sl->fColor);
            srRed = (NULL != sr && kRed_Color == sr->fColor);
            if (!slRed && !srRed) {
                // if s can be made red that will balance out x's removal
                // to make both subtrees of p have the same black-height.
                if (kBlack_Color == p->fColor) {
                    s->fColor = kRed_Color;
                    // now subtree at p has black-height of one less than
                    // p's parent's other child's subtree. We move x up to
                    // p and go through the loop again. At the top of loop
                    // we assumed x and x's children are black, which holds
                    // by above ifs.
                    // if p is the root there is no other subtree to balance
                    // against.
                    x = p;
                    p = x->fParent;
                    if (NULL == p) {
                        GrAssert(fRoot == x);
                        validate();
                        return;
                    } else {
                        pc = p->fChildren[kLeft_Child] == x ? kLeft_Child :
                                                              kRight_Child;

                    }
                    s = p->fChildren[1-pc];
                    GrAssert(NULL != s);
                    GrAssert(p == s->fParent);
                    continue;
                } else if (kRed_Color == p->fColor) {
                    // we can make p black and s red. This balance out p's
                    // two subtrees and keep the same black-height as it was
                    // before the delete.
                    s->fColor = kRed_Color;
                    p->fColor = kBlack_Color;
                    validate();
                    return;
                }
            }
            break;
        } while (true);
        // if we made it here one or both of sl and sr is red.
        // s and x are black. We make sure that a red child is on
        // the same side of s as s is of p.
        GrAssert(slRed || srRed);
        if (kLeft_Child == pc && !srRed) {
            s->fColor = kRed_Color;
            sl->fColor = kBlack_Color;
            rotateRight(s);
            sr = s;
            s = sl;
            //sl = s->fChildren[kLeft_Child]; don't need this
        } else if (kRight_Child == pc && !slRed) {
            s->fColor = kRed_Color;
            sr->fColor = kBlack_Color;
            rotateLeft(s);
            sl = s;
            s = sr;
            //sr = s->fChildren[kRight_Child]; don't need this
        }
        // now p is either red or black, x and s are red and s's 1-pc
        // child is red.
        // We rotate p towards x, pulling s up to replace p. We make
        // p be black and s takes p's old color.
        // Whether p was red or black, we've increased its pc subtree
        // rooted at x by 1 (balancing the imbalance at the start) and
        // we've also its subtree rooted at s's black-height by 1. This
        // can be balanced by making s's red child be black.
        s->fColor = p->fColor;
        p->fColor = kBlack_Color;
        if (kLeft_Child == pc) {
            GrAssert(NULL != sr && kRed_Color == sr->fColor);
            sr->fColor = kBlack_Color;
            rotateLeft(p);
        } else {
            GrAssert(NULL != sl && kRed_Color == sl->fColor);
            sl->fColor = kBlack_Color;
            rotateRight(p);
        }
    }
    else {
        // x has exactly one implicit black child. x cannot be red.
        // Proof by contradiction: Assume X is red. Let c0 be x's implicit
        // child and c1 be its non-implicit child. c1 must be black because
        // red nodes always have two black children. Then the two subtrees
        // of x rooted at c0 and c1 will have different black-heights.
        GrAssert(kBlack_Color == x->fColor);
        // So we know x is black and has one implicit black child, c0. c1
        // must be red, otherwise the subtree at c1 will have a different
        // black-height than the subtree rooted at c0.
        GrAssert(kRed_Color == x->fChildren[c]->fColor);
        // replace x with c1, making c1 black, preserves all red-black tree
        // props.
        Node* c1 = x->fChildren[c];
        if (x == fFirst) {
            GrAssert(c == kRight_Child);
            fFirst = c1;
            while (NULL != fFirst->fChildren[kLeft_Child]) {
                fFirst = fFirst->fChildren[kLeft_Child];
            }
            GrAssert(fFirst == SuccessorNode(x));
        } else if (x == fLast) {
            GrAssert(c == kLeft_Child);
            fLast = c1;
            while (NULL != fLast->fChildren[kRight_Child]) {
                fLast = fLast->fChildren[kRight_Child];
            }
            GrAssert(fLast == PredecessorNode(x));
        }
        c1->fParent = p;
        p->fChildren[pc] = c1;
        c1->fColor = kBlack_Color;
        delete x;
        validate();
    }
    validate();
}

template <typename T, typename C>
void GrRedBlackTree<T,C>::RecursiveDelete(Node* x) {
    if (NULL != x) {
        RecursiveDelete(x->fChildren[kLeft_Child]);
        RecursiveDelete(x->fChildren[kRight_Child]);
        delete x;
    }
}

#if GR_DEBUG
template <typename T, typename C>
void GrRedBlackTree<T,C>::validate() const {
    if (fCount) {
        GrAssert(NULL == fRoot->fParent);
        GrAssert(NULL != fFirst);
        GrAssert(NULL != fLast);

        GrAssert(kBlack_Color == fRoot->fColor);
        if (1 == fCount) {
            GrAssert(fFirst == fRoot);
            GrAssert(fLast == fRoot);
            GrAssert(0 == fRoot->fChildren[kLeft_Child]);
            GrAssert(0 == fRoot->fChildren[kRight_Child]);
        }
    } else {
        GrAssert(NULL == fRoot);
        GrAssert(NULL == fFirst);
        GrAssert(NULL == fLast);
    }
#if DEEP_VALIDATE
    int bh;
    int count = checkNode(fRoot, &bh);
    GrAssert(count == fCount);
#endif
}

template <typename T, typename C>
int GrRedBlackTree<T,C>::checkNode(Node* n, int* bh) const {
    if (NULL != n) {
        GrAssert(validateChildRelations(n, false));
        if (kBlack_Color == n->fColor) {
            *bh += 1;
        }
        GrAssert(!fComp(n->fItem, fFirst->fItem));
        GrAssert(!fComp(fLast->fItem, n->fItem));
        int leftBh = *bh;
        int rightBh = *bh;
        int cl = checkNode(n->fChildren[kLeft_Child], &leftBh);
        int cr = checkNode(n->fChildren[kRight_Child], &rightBh);
        GrAssert(leftBh == rightBh);
        *bh = leftBh;
        return 1 + cl + cr;
    }
    return 0;
}

template <typename T, typename C>
bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n,
                                                 bool allowRedRed) const {
    if (NULL != n) {
        if (NULL != n->fChildren[kLeft_Child] ||
            NULL != n->fChildren[kRight_Child]) {
            if (n->fChildren[kLeft_Child] == n->fChildren[kRight_Child]) {
                return validateChildRelationsFailed();
            }
            if (n->fChildren[kLeft_Child] == n->fParent &&
                NULL != n->fParent) {
                return validateChildRelationsFailed();
            }
            if (n->fChildren[kRight_Child] == n->fParent &&
                NULL != n->fParent) {
                return validateChildRelationsFailed();
            }
            if (NULL != n->fChildren[kLeft_Child]) {
                if (!allowRedRed &&
                    kRed_Color == n->fChildren[kLeft_Child]->fColor &&
                    kRed_Color == n->fColor) {
                    return validateChildRelationsFailed();
                }
                if (n->fChildren[kLeft_Child]->fParent != n) {
                    return validateChildRelationsFailed();
                }
                if (!(fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) ||
                      (!fComp(n->fChildren[kLeft_Child]->fItem, n->fItem) &&
                       !fComp(n->fItem, n->fChildren[kLeft_Child]->fItem)))) {
                    return validateChildRelationsFailed();
                }
            }
            if (NULL != n->fChildren[kRight_Child]) {
                if (!allowRedRed &&
                    kRed_Color == n->fChildren[kRight_Child]->fColor &&
                    kRed_Color == n->fColor) {
                    return validateChildRelationsFailed();
                }
                if (n->fChildren[kRight_Child]->fParent != n) {
                    return validateChildRelationsFailed();
                }
                if (!(fComp(n->fItem, n->fChildren[kRight_Child]->fItem) ||
                      (!fComp(n->fChildren[kRight_Child]->fItem, n->fItem) &&
                       !fComp(n->fItem, n->fChildren[kRight_Child]->fItem)))) {
                    return validateChildRelationsFailed();
                }
            }
        }
    }
    return true;
}
#endif

#include "GrRandom.h"

template <typename T, typename C>
void GrRedBlackTree<T,C>::UnitTest() {
    GrRedBlackTree<int> tree;
    typedef GrRedBlackTree<int>::Iter iter;

    GrRandom r;

    int count[100] = {0};
    // add 10K ints
    for (int i = 0; i < 10000; ++i) {
        int x = r.nextU()%100;
        Iter xi = tree.insert(x);
        GrAssert(*xi == x);
        ++count[x];
    }

    tree.insert(0);
    ++count[0];
    tree.insert(99);
    ++count[99];
    GrAssert(*tree.begin() == 0);
    GrAssert(*tree.last() == 99);
    GrAssert(--(++tree.begin()) == tree.begin());
    GrAssert(--tree.end() == tree.last());
    GrAssert(tree.count() == 10002);

    int c = 0;
    // check that we iterate through the correct number of
    // elements and they are properly sorted.
    for (Iter a = tree.begin(); tree.end() != a; ++a) {
        Iter b = a;
        ++b;
        ++c;
        GrAssert(b == tree.end() || *a <= *b);
    }
    GrAssert(c == tree.count());

    // check that the tree reports the correct number of each int
    // and that we can iterate through them correctly both forward
    // and backward.
    for (int i = 0; i < 100; ++i) {
        int c;
        c = tree.countOf(i);
        GrAssert(c == count[i]);
        c = 0;
        Iter iter = tree.findFirst(i);
        while (iter != tree.end() && *iter == i) {
            ++c;
            ++iter;
        }
        GrAssert(count[i] == c);
        c = 0;
        iter = tree.findLast(i);
        if (iter != tree.end()) {
            do {
                if (*iter == i) {
                    ++c;
                } else {
                    break;
                }
                if (iter != tree.begin()) {
                    --iter;
                } else {
                    break;
                }
            } while (true);
        }
        GrAssert(c == count[i]);
    }
    // remove all the ints between 25 and 74. Randomly chose to remove
    // the first, last, or any entry for each.
    for (int i = 25; i < 75; ++i) {
        while (0 != tree.countOf(i)) {
            --count[i];
            int x = r.nextU() % 3;
            Iter iter;
            switch (x) {
            case 0:
                iter = tree.findFirst(i);
                break;
            case 1:
                iter = tree.findLast(i);
                break;
            case 2:
            default:
                iter = tree.find(i);
                break;
            }
            tree.remove(iter);
        }
        GrAssert(0 == count[i]);
        GrAssert(tree.findFirst(i) == tree.end());
        GrAssert(tree.findLast(i) == tree.end());
        GrAssert(tree.find(i) == tree.end());
    }
    // remove all of the 0 entries. (tests removing begin())
    GrAssert(*tree.begin() == 0);
    GrAssert(*(--tree.end()) == 99);
    while (0 != tree.countOf(0)) {
        --count[0];
        tree.remove(tree.find(0));
    }
    GrAssert(0 == count[0]);
    GrAssert(tree.findFirst(0) == tree.end());
    GrAssert(tree.findLast(0) == tree.end());
    GrAssert(tree.find(0) == tree.end());
    GrAssert(0 < *tree.begin());

    // remove all the 99 entries (tests removing last()).
    while (0 != tree.countOf(99)) {
        --count[99];
        tree.remove(tree.find(99));
    }
    GrAssert(0 == count[99]);
    GrAssert(tree.findFirst(99) == tree.end());
    GrAssert(tree.findLast(99) == tree.end());
    GrAssert(tree.find(99) == tree.end());
    GrAssert(99 > *(--tree.end()));
    GrAssert(tree.last() == --tree.end());

    // Make sure iteration still goes through correct number of entries
    // and is still sorted correctly.
    c = 0;
    for (Iter a = tree.begin(); tree.end() != a; ++a) {
        Iter b = a;
        ++b;
        ++c;
        GrAssert(b == tree.end() || *a <= *b);
    }
    GrAssert(c == tree.count());

    // repeat check that correct number of each entry is in the tree
    // and iterates correctly both forward and backward.
    for (int i = 0; i < 100; ++i) {
        GrAssert(tree.countOf(i) == count[i]);
        int c = 0;
        Iter iter = tree.findFirst(i);
        while (iter != tree.end() && *iter == i) {
            ++c;
            ++iter;
        }
        GrAssert(count[i] == c);
        c = 0;
        iter = tree.findLast(i);
        if (iter != tree.end()) {
            do {
                if (*iter == i) {
                    ++c;
                } else {
                    break;
                }
                if (iter != tree.begin()) {
                    --iter;
                } else {
                    break;
                }
            } while (true);
        }
        GrAssert(count[i] == c);
    }

    // remove all entries
    while (!tree.empty()) {
        tree.remove(tree.begin());
    }

    // test reset on empty tree.
    tree.reset();
}

#endif


code:
/*
    Copyright 2010 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrRefCnt_DEFINED
#define GrRefCnt_DEFINED

#include "GrTypes.h"
#include "GrNoncopyable.h"

/**
 *  Base class for reference counting. When an object is first instantiated,
 *  its reference count is 1. If the object may be null, use GrSafeRef() and
 *  GrSafeUnref().
 *
 *  It is an error (though only checked for in the debug build) to call unref()
 *  such that the reference count becomes 0.
 */
class GR_API GrRefCnt : GrNoncopyable {
public:
            GrRefCnt() : fRefCnt(1) {}
    virtual ~GrRefCnt() {
        GrAssert(1 == fRefCnt);
#if GR_DEBUG
        fRefCnt = 0;    // force validate() to trigger if called afterwards
#endif
    }

    int32_t refcnt() const { return fRefCnt; }

    void ref() const {
        GrAssert(fRefCnt > 0);
        ++fRefCnt;
    }

    void unref() const {
        GrAssert(fRefCnt > 0);
        if (1 == fRefCnt) {
            delete this;
        } else {
            --fRefCnt;
        }
    }

#if GR_DEBUG
    void validate() const {
        GrAssert(fRefCnt > 0);
    }
#else
    void validate() const {}
#endif

private:
    mutable int32_t fRefCnt;
};

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

/**
 *  Call with instance/subclass of GrRefCnt. This does nothing if obj is null,
 *  but otherwise it calls ref().
 */
static inline void GrSafeRef(const GrRefCnt* obj) {
    if (obj) {
        obj->ref();
    }
}

/**
 *  Call with instance/subclass of GrRefCnt. This does nothing if obj is null,
 *  but otherwise it calls unref().
 */
static inline void GrSafeUnref(const GrRefCnt* obj) {
    if (obj) {
        obj->unref();
    }
}

/**
 *  Assigns src to dst, checking for NULLs in each, and correctly incrementing
 *  the reference count of src, and decrementing the reference count of dst
 */
template<typename T>
static inline void GrSafeAssign(T*& dst, T* src) {
    if (src) {
        src->ref();
    }
    if (dst) {
        dst->unref();
    }
    dst = src;
}

template<typename T>
static inline void GrSafeSetNull(T*& obj) {
    if (NULL != obj) {
        obj->unref();
        obj = NULL;
    }
}

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

class GrAutoRef : GrNoncopyable {
public:
    GrAutoRef(GrRefCnt* obj) : fObj(obj) { GrSafeRef(obj); }
    ~GrAutoRef() { GrSafeUnref(fObj); }
private:
    GrRefCnt* fObj;
};

class GrAutoUnref : GrNoncopyable {
public:
    GrAutoUnref(GrRefCnt* obj) : fObj(obj) {}
    ~GrAutoUnref() { GrSafeUnref(fObj); }
private:
    GrRefCnt* fObj;
};

#endif


code:
/*
    Copyright 2011 Google Inc.

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

         http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
 */

#ifndef GrResource_DEFINED
#define GrResource_DEFINED

#include "GrRefCnt.h"

class GrGpu;

class GrResource : public GrRefCnt {
public:
    explicit GrResource(GrGpu* gpu);

    virtual ~GrResource() {
        // subclass should have released this.
        GrAssert(!isValid());
    }

    /**
     * Frees the resource in the underlying 3D API. It must be safe to call this
     * when the resource has been previously abandoned.
     */
    void release();

    /**
     * Removes references to objects in the underlying 3D API without freeing
     * them. Used when the API context has been torn down before the GrContext.
     */
    void abandon();

    /**
     * Tests whether a resource has been abandoned or released. All resources
     * will be in this state after their creating GrContext is destroyed or has
     * contextLost called. It's up to the client to test isValid() before
     * attempting to use a resource if it holds refs on resources across
     * ~GrContext, freeResources with the force flag, or contextLost.
     *
     * @return true if the resource has been released or abandoned,
     *         false otherwise.
     */
    bool isValid() const { return NULL != fGpu; }

protected:

    virtual void onRelease() = 0;
    virtual void onAbandon() = 0;

    GrGpu* getGpu() const { return fGpu; }

private:
    GrResource(); // unimpl

    GrGpu* fGpu; // not reffed. This can outlive the GrGpu.

    friend class GrGpu; // GrGpu manages list of resources.

    GrResource* fNext;      // dl-list of resources per-GrGpu
    GrResource* fPrevious;

    typedef GrRefCnt INHERITED;
};

#endif