Generate path names on the client side

src/gpu/gl/GrGLNameAllocator.cpp

+
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.

[bsalomon, 2014/05/30 18:09:11]

This file could really use some documentation.

+ */
+
+#include "GrGLNameAllocator.h"
+
+class GrGLNameAllocator::SparseNameRange {
+public:
+    virtual ~SparseNameRange() {}
+
+    GrGLuint first() const { return fFirst; }
+    GrGLuint end() const { return fEnd; }
+    GrGLuint height() const { return fHeight; }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) = 0;
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) = 0;
+    virtual GrGLuint appendNames(GrGLuint count) = 0;
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) = 0;
+
+    // Implement ref/unref without atomics.
+    SparseNameRange* ref() {

[bsalomon, 2014/05/30 18:09:11]

Are these really frequently ref'ed and unref'ed?

[Chris Dalton, 2014/05/30 21:39:41]

In theory it could. In practice it might not. I can try using standard ref
counting at least for the initial commit. If it starts showing up in the
profiles we can always come back to it.

[bsalomon, 2014/06/02 15:14:43]

I'd prefer that. If we're going to tackle non-atomic refs for Gr code, I'd
rather do it separately and more comprehensively (i.e. for more than just one
type).

+        ++fRefCnt;
+        return this;
+    }
+    int unref() {
+        if (0 == --fRefCnt) {
+            SkDELETE(this);
+            return 0;
+        }
+        return fRefCnt;
+    }
+
+protected:
+    SparseNameRange() : fRefCnt(1) {}
+
+    GrGLuint fFirst;
+    GrGLuint fEnd;
+    GrGLuint fHeight;
+
+private:
+    int fRefCnt;
+};
+
+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();
+        }
+
+        *outName = fLeft->appendNames(1);
+        return this->ref();
+    }
+
+    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 SK_WARN_UNUSED_RESULT 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 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 {
+            SkASSERT(name >= fRight->first());
+            fRight.reset(fRight->free(name));
+            if (NULL == fRight) {
+                // fRight became empty after the free.
+                return fLeft.detach();
+            }
+            this->updateStats();
+            return this->rebalance();
+        }
+    }
+
+protected:
+    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->ref();
+    }
+
+    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());
+        SparseNameTree* tallChild = static_cast<SparseNameTree*>((this->*Tall).get());
+        if ((tallChild->*Tall)->height() < (tallChild->*Short)->height()) {
+            (this->*Tall).reset(tallChild->rotate<Short, Tall>());
+        }
+        return this->rotate<Tall, Short>();
+    }
+
+    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->ref());
+        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());
+    }
+
+private:
+    SkAutoTUnref<SparseNameRange> fLeft;
+    SkAutoTUnref<SparseNameRange> fRight;
+};
+
+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->ref();
+    }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) SK_OVERRIDE {
+        *removedCount = fEnd - fFirst;
+        return NULL;
+    }
+
+    virtual GrGLuint SK_WARN_UNUSED_RESULT appendNames(GrGLuint count) SK_OVERRIDE {
+        SkASSERT(fEnd + count > fEnd); // Check for integer wrap.
+        GrGLuint name = fEnd;
+        fEnd += count;
+        return name;
+    }
+
+    virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) SK_OVERRIDE {
+        SkASSERT(name >= fFirst);
+        SkASSERT(name < fEnd);
+
+        if (fFirst == name) {
+            ++fFirst;
+            return (fEnd == fFirst) ? NULL : this->ref();
+        }
+
+        if (fEnd == name + 1) {
+            --fEnd;
+            return this->ref();
+        }
+
+        SparseNameRange* left = SkNEW_ARGS(ContiguousNameRange, (fFirst, name));
+        SparseNameRange* right = this->ref();
+        fFirst = name + 1;
+        return SkNEW_ARGS(SparseNameTree, (left, right));
+    }
+};
+
+GrGLNameAllocator::GrGLNameAllocator(GrGLuint names, GrGLuint range)
+    : fNames(names),
+      fRange(range) {
+    SkASSERT(range > 0);
+}
+
+GrGLNameAllocator::~GrGLNameAllocator() {
+}
+
+GrGLuint GrGLNameAllocator::allocateName() {
+    if (NULL == fAllocatedNames.get()) {
+        fAllocatedNames.reset(SkNEW_ARGS(ContiguousNameRange, (fNames, fNames + 1)));
+        return fNames;
+    }
+
+    GrGLuint name;
+    fAllocatedNames.reset(fAllocatedNames->internalAllocate(&name));
+    if (0 != name) {
+        return name;
+    }
+
+    if (fAllocatedNames->end() >= fAllocatedNames->first() + fRange) {
+        // Out of names.
+        return 0;
+    }
+
+    return fAllocatedNames->appendNames(1);
+}
+
+void GrGLNameAllocator::freeName(GrGLuint name) {
+    SkASSERT(fAllocatedNames.get());
+    SkASSERT(name >= fAllocatedNames->first());
+    SkASSERT(name < fAllocatedNames->end()); // It is invalid to free not-allocated names.
+
+    fAllocatedNames.reset(fAllocatedNames->free(name));
+}