Generate path names on the client side

src/gpu/gl/GrGLNameAllocator.cpp

Index: src/gpu/gl/GrGLNameAllocator.cpp
diff --git a/src/gpu/gl/GrGLNameAllocator.cpp b/src/gpu/gl/GrGLNameAllocator.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..f2c37edbeb20377b2207453b15df14e26c6b175e
--- /dev/null
+++ b/src/gpu/gl/GrGLNameAllocator.cpp
@@ -0,0 +1,370 @@
+
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "GrGLNameAllocator.h"
+
+/**
+ * This is the abstract base class for a nonempty AVL tree that tracks allocated
+ * names within the half-open range [fFirst, fEnd). The inner nodes can be
+ * sparse (meaning not every name within the range is necessarily allocated),
+ * but the bounds are tight, so fFirst *is* guaranteed to be allocated, and so
+ * is fEnd - 1.
+ */
+class GrGLNameAllocator::SparseNameRange : public SkRefCnt {
+public:
+    virtual ~SparseNameRange() {}
+
+    /**
+     * Return the beginning of the range. first() is guaranteed to be allocated.
+     *
+     * @return The first name in the range.
+     */
+    GrGLuint first() const { return fFirst; }
+
+    /**
+     * Return the end of the range. end() - 1 is guaranteed to be allocated.
+     *
+     * @return One plus the final name in the range.
+     */
+    GrGLuint end() const { return fEnd; }
+
+    /**
+     * Return the height of the tree. This can only be nonzero at an inner node.
+     *
+     * @return 0 if the implementation is a leaf node,
+     *         The nonzero height of the tree otherwise.
+     */
+    GrGLuint height() const { return fHeight; }
+
+    /**
+     * Allocate a name from strictly inside this range. The call will fail if
+     * there is not a free name within.
+     *
+     * @param outName A pointer that receives the allocated name. outName will
+     *                be set to zero if there were no free names within the
+     *                range [fFirst, fEnd).
+     * @return The resulting SparseNameRange after the allocation. Note that
+     *         this call is destructive, so the original SparseNameRange will no
+     *         longer be valid afterward. The caller must always update its
+     *         pointer with the new SparseNameRange.
+     */
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) = 0;
+
+    /**
+     * Remove the leftmost leaf node from this range (or the entire thing if it
+     * *is* a leaf node). This is an internal helper method that is used after
+     * an allocation if one contiguous range became adjacent to another. (The
+     * range gets removed so the one immediately before can be extended,
+     * collapsing the two into one.)
+     *
+     * @param removedCount A pointer that receives the size of the contiguous
+                           range that was removed.
+     * @return The resulting SparseNameRange after the removal (or NULL if it
+     *         became empty). Note that this call is destructive, so the
+     *         original SparseNameRange will no longer be valid afterward. The
+     *         caller must always update its pointer with the new
+     *         SparseNameRange.
+     */
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) = 0;
+
+    /**
+     * Append adjacent allocated names to the end of this range. This operation
+     * does not affect the structure of the tree. The caller is responsible for
+     * ensuring the new names won't overlap sibling ranges, if any.
+     *
+     * @param count The number of adjacent names to append.
+     * @return The first name appended.
+     */
+    virtual GrGLuint appendNames(GrGLuint count) = 0;
+
+    /**
+     * Prepend adjacent allocated names behind the beginning of this range. This
+     * operation does not affect the structure of the tree. The caller is
+     * responsible for ensuring the new names won't overlap sibling ranges, if
+     * any.
+     *
+     * @param count The number of adjacent names to prepend.
+     * @return The final name prepended (the one with the lowest value).
+     */
+    virtual GrGLuint prependNames(GrGLuint count) = 0;
+
+    /**
+     * Free a name so it is no longer tracked as allocated. If the name is at
+     * the very beginning or very end of the range, the boundaries [fFirst, fEnd)
+     * will be tightened.
+     *
+     * @param name The name to free. Not-allocated names are silently ignored
+     *             the same way they are in the OpenGL spec.
+     * @return The resulting SparseNameRange after the free (or NULL if it
+     *         became empty). Note that this call is destructive, so the
+     *         original SparseNameRange will no longer be valid afterward. The
+     *         caller must always update its pointer with the new
+     *         SparseNameRange.
+     */
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) = 0;
+
+protected:
+    SparseNameRange* takeRef() {
+      this->ref();
+      return this;
+    }
+
+    GrGLuint fFirst;
+    GrGLuint fEnd;
+    GrGLuint fHeight;
+};
+
+/**
+ * This class is the SparseNameRange implementation for an inner node. It is an
+ * AVL tree with non-null, non-adjacent left and right children.
+ */
+class GrGLNameAllocator::SparseNameTree : public SparseNameRange {
+public:
+    SparseNameTree(SparseNameRange* left, SparseNameRange* right)
+        : fLeft(left),
+          fRight(right) {
+        SkASSERT(fLeft.get());
+        SkASSERT(fRight.get());
+        this->updateStats();
+    }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) SK_OVERRIDE {
+        // Try allocating the range inside fLeft's internal gaps.
+        fLeft.reset(fLeft->internalAllocate(outName));
+        if (0 != *outName) {
+            this->updateStats();
+            return this->rebalance();
+        }
+
+        if (fLeft->end() + 1 == fRight->first()) {
+            // It closed the gap between fLeft and fRight; merge.
+            GrGLuint removedCount;
+            fRight.reset(fRight->removeLeftmostContiguousRange(&removedCount));
+            *outName = fLeft->appendNames(1 + removedCount);
+            if (NULL == fRight.get()) {
+                return fLeft.detach();
+            }
+            this->updateStats();
+            return this->rebalance();
+        }
+
+        // There is guaranteed to be a gap between fLeft and fRight, and the
+        // "size 1" case has already been covered.
+        SkASSERT(fLeft->end() + 1 < fRight->first());
+        *outName = fLeft->appendNames(1);
+        return this->takeRef();
+    }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) SK_OVERRIDE {
+        fLeft.reset(fLeft->removeLeftmostContiguousRange(removedCount));
+        if (NULL == fLeft) {
+            return fRight.detach();
+        }
+        this->updateStats();
+        return this->rebalance();
+    }
+
+    virtual GrGLuint appendNames(GrGLuint count) SK_OVERRIDE {
+        SkASSERT(fEnd + count > fEnd); // Check for integer wrap.
+        GrGLuint name = fRight->appendNames(count);
+        SkASSERT(fRight->end() == fEnd + count);
+        this->updateStats();
+        return name;
+    }
+
+    virtual GrGLuint prependNames(GrGLuint count) SK_OVERRIDE {
+        SkASSERT(fFirst > count); // We can't allocate at or below 0.
+        GrGLuint name = fLeft->prependNames(count);
+        SkASSERT(fLeft->first() == fFirst - count);
+        this->updateStats();
+        return name;
+    }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) SK_OVERRIDE {
+        if (name < fLeft->end()) {
+            fLeft.reset(fLeft->free(name));
+            if (NULL == fLeft) {
+                // fLeft became empty after the free.
+                return fRight.detach();
+            }
+            this->updateStats();
+            return this->rebalance();
+        } else {
+            fRight.reset(fRight->free(name));
+            if (NULL == fRight) {
+                // fRight became empty after the free.
+                return fLeft.detach();
+            }
+            this->updateStats();
+            return this->rebalance();
+        }
+    }
+
+private:
+    typedef SkAutoTUnref<SparseNameRange> SparseNameTree::* ChildRange;
+
+    SparseNameRange* SK_WARN_UNUSED_RESULT rebalance() {
+        if (fLeft->height() > fRight->height() + 1) {
+            return this->rebalanceImpl<&SparseNameTree::fLeft, &SparseNameTree::fRight>();
+        }
+        if (fRight->height() > fLeft->height() + 1) {
+            return this->rebalanceImpl<&SparseNameTree::fRight, &SparseNameTree::fLeft>();
+        }
+        return this->takeRef();
+    }
+
+    /**
+     * Rebalance the tree using rotations, as described in the AVL algorithm:
+     * http://en.wikipedia.org/wiki/AVL_tree#Insertion
+     */
+    template<ChildRange Tall, ChildRange Short>
+    SparseNameRange* SK_WARN_UNUSED_RESULT rebalanceImpl() {
+        // We should be calling rebalance() enough that the tree never gets more
+        // than one rotation off balance.
+        SkASSERT(2 == (this->*Tall)->height() - (this->*Short)->height());
+
+        // Ensure we are in the 'Left Left' or 'Right Right' case:
+        // http://en.wikipedia.org/wiki/AVL_tree#Insertion
+        SparseNameTree* tallChild = static_cast<SparseNameTree*>((this->*Tall).get());
+        if ((tallChild->*Tall)->height() < (tallChild->*Short)->height()) {
+            (this->*Tall).reset(tallChild->rotate<Short, Tall>());
+        }
+
+        // Perform a rotation to balance the tree.
+        return this->rotate<Tall, Short>();
+    }
+
+    /**
+     * Perform a node rotation, as described in the AVL algorithm:
+     * http://en.wikipedia.org/wiki/AVL_tree#Insertion
+     */
+    template<ChildRange Tall, ChildRange Short>
+    SparseNameRange* SK_WARN_UNUSED_RESULT rotate() {
+        SparseNameTree* newRoot = static_cast<SparseNameTree*>((this->*Tall).detach());
+
+        (this->*Tall).reset((newRoot->*Short).detach());
+        this->updateStats();
+
+        (newRoot->*Short).reset(this->takeRef());
+        newRoot->updateStats();
+
+        return newRoot;
+    }
+
+    void updateStats() {
+        SkASSERT(fLeft->end() < fRight->first()); // There must be a gap between left and right.
+        fFirst = fLeft->first();
+        fEnd = fRight->end();
+        fHeight = 1 + SkMax32(fLeft->height(), fRight->height());
+    }
+
+    SkAutoTUnref<SparseNameRange> fLeft;
+    SkAutoTUnref<SparseNameRange> fRight;
+};
+
+/**
+ * This class is the SparseNameRange implementation for a leaf node. It just a
+ * contiguous range of allocated names.
+ */
+class GrGLNameAllocator::ContiguousNameRange : public SparseNameRange {
+public:
+    ContiguousNameRange(GrGLuint first, GrGLuint end) {
+        SkASSERT(first < end);
+        fFirst = first;
+        fEnd = end;
+        fHeight = 0;
+    }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) SK_OVERRIDE {
+        *outName = 0; // No internal gaps, we are contiguous.
+        return this->takeRef();
+    }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) SK_OVERRIDE {
+        *removedCount = fEnd - fFirst;
+        return NULL;
+    }
+
+    virtual GrGLuint appendNames(GrGLuint count) SK_OVERRIDE {
+        SkASSERT(fEnd + count > fEnd); // Check for integer wrap.
+        GrGLuint name = fEnd;
+        fEnd += count;
+        return name;
+    }
+
+    virtual GrGLuint prependNames(GrGLuint count) SK_OVERRIDE {
+        SkASSERT(fFirst > count); // We can't allocate at or below 0.
+        fFirst -= count;
+        return fFirst;
+    }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) SK_OVERRIDE {
+        if (name < fFirst || name >= fEnd) {
+          // Not-allocated names are silently ignored.
+          return this->takeRef();
+        }
+
+        if (fFirst == name) {
+            ++fFirst;
+            return (fEnd == fFirst) ? NULL : this->takeRef();
+        }
+
+        if (fEnd == name + 1) {
+            --fEnd;
+            return this->takeRef();
+        }
+
+        SparseNameRange* left = SkNEW_ARGS(ContiguousNameRange, (fFirst, name));
+        SparseNameRange* right = this->takeRef();
+        fFirst = name + 1;
+        return SkNEW_ARGS(SparseNameTree, (left, right));
+    }
+};
+
+GrGLNameAllocator::GrGLNameAllocator(GrGLuint firstName, GrGLuint endName)
+    : fFirstName(firstName),
+      fEndName(endName) {
+    SkASSERT(firstName > 0);
+    SkASSERT(endName > firstName);
+}
+
+GrGLNameAllocator::~GrGLNameAllocator() {
+}
+
+GrGLuint GrGLNameAllocator::allocateName() {
+    if (NULL == fAllocatedNames.get()) {
+        fAllocatedNames.reset(SkNEW_ARGS(ContiguousNameRange, (fFirstName, fFirstName + 1)));
+        return fFirstName;
+    }
+
+    if (fAllocatedNames->first() > fFirstName) {
+        return fAllocatedNames->prependNames(1);
+    }
+
+    GrGLuint name;
+    fAllocatedNames.reset(fAllocatedNames->internalAllocate(&name));
+    if (0 != name) {
+        return name;
+    }
+
+    if (fAllocatedNames->end() < fEndName) {
+        return fAllocatedNames->appendNames(1);
+    }
+
+    // Out of names.
+    return 0;
+}
+
+void GrGLNameAllocator::free(GrGLuint name) {
+    if (!fAllocatedNames.get()) {
+      // Not-allocated names are silently ignored.
+      return;
+    }
+
+    fAllocatedNames.reset(fAllocatedNames->free(name));
+}