Generate path names on the client side
Pre-allocates a range of path names and manages allocations within
that range on the client side. This allows us to generate new path
objects in a feed-forward manner that doesn't require round trips to
the GL server.
BUG=skia:
R=bsalomon@google.com, markkilgard@gmail.com
Author: cdalton@nvidia.com
Review URL: https://codereview.chromium.org/304403003
diff --git a/gyp/gpu.gypi b/gyp/gpu.gypi
index 568bc0e..d336fa9 100644
--- a/gyp/gpu.gypi
+++ b/gyp/gpu.gypi
@@ -186,6 +186,8 @@
'<(skia_src_path)/gpu/gl/GrGLIndexBuffer.h',
'<(skia_src_path)/gpu/gl/GrGLInterface.cpp',
'<(skia_src_path)/gpu/gl/GrGLIRect.h',
+ '<(skia_src_path)/gpu/gl/GrGLNameAllocator.cpp',
+ '<(skia_src_path)/gpu/gl/GrGLNameAllocator.h',
'<(skia_src_path)/gpu/gl/GrGLNoOpInterface.cpp',
'<(skia_src_path)/gpu/gl/GrGLNoOpInterface.h',
'<(skia_src_path)/gpu/gl/GrGLPath.cpp',
diff --git a/gyp/tests.gypi b/gyp/tests.gypi
index 7a32da2..6af8e91 100644
--- a/gyp/tests.gypi
+++ b/gyp/tests.gypi
@@ -119,6 +119,7 @@
'../tests/MessageBusTest.cpp',
'../tests/MetaDataTest.cpp',
'../tests/MipMapTest.cpp',
+ '../tests/NameAllocatorTest.cpp',
'../tests/ObjectPoolTest.cpp',
'../tests/OSPathTest.cpp',
'../tests/OnceTest.cpp',
diff --git a/src/gpu/gl/GrGLNameAllocator.cpp b/src/gpu/gl/GrGLNameAllocator.cpp
new file mode 100644
index 0000000..f2c37ed
--- /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));
+}
diff --git a/src/gpu/gl/GrGLNameAllocator.h b/src/gpu/gl/GrGLNameAllocator.h
new file mode 100644
index 0000000..1c2c26e
--- /dev/null
+++ b/src/gpu/gl/GrGLNameAllocator.h
@@ -0,0 +1,86 @@
+
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef GrGLNameAllocator_DEFINED
+#define GrGLNameAllocator_DEFINED
+
+#include "SkRefCnt.h"
+#include "gl/GrGLFunctions.h"
+
+/**
+ * This class assumes ownership of an explicit range of OpenGL object names and
+ * manages allocations within that range. This allows the app to generate new
+ * objects on the client side without making round trips to the GL server.
+ */
+class GrGLNameAllocator {
+public:
+ /**
+ * Constructs a name allocator that produces names within the explicit
+ * half-open range [firstName, end). Note that the caller will most likely
+ * need to call glGen* beforehand to reserve a range within the GL driver,
+ * and then invoke this constructor with that range.
+ *
+ * @param firstName The first name in the range owned by this class. Must be
+ greater than zero.
+ * @param endName The first past-the-end name beyond the range owned by
+ this class. Must be >= firstName.
+ */
+ GrGLNameAllocator(GrGLuint firstName, GrGLuint endName);
+
+ /**
+ * Destructs the name allocator. The caller is responsible for calling the
+ * appropriate glDelete* on the range if necessary.
+ */
+ ~GrGLNameAllocator();
+
+ /**
+ * Return the beginning of this class's range.
+ *
+ * @return The first name in the range owned by this class.
+ */
+ GrGLuint firstName() const { return fFirstName; }
+
+ /**
+ * Return the end of this class's range. Note that endName() is not owned by
+ * this class.
+ *
+ * @return One plus the final name in the range owned by this class.
+ */
+ GrGLuint endName() const { return fEndName; }
+
+ /**
+ * Allocate an OpenGL object name from within this class's range.
+ *
+ * @return The name if one was available,
+ 0 if all the names in the range were already in use.
+ */
+ GrGLuint allocateName();
+
+ /**
+ * Free an OpenGL object name, allowing it to be returned by a future call
+ * to allocateName(). Note that the caller should most likely redefine the
+ * object as empty to deallocate any underlying GPU memory before calling
+ * this method (but not call glDelete*, since that would free up the name
+ * within the driver itself).
+ *
+ * @param name The object name to free. Not-allocated names are silently
+ * ignored the same way they are in the OpenGL spec.
+ */
+ void free(GrGLuint name);
+
+private:
+ class SparseNameRange;
+ class SparseNameTree;
+ class ContiguousNameRange;
+
+ const GrGLuint fFirstName;
+ const GrGLuint fEndName;
+ SkAutoTUnref<SparseNameRange> fAllocatedNames;
+};
+
+#endif
diff --git a/src/gpu/gl/GrGLPath.cpp b/src/gpu/gl/GrGLPath.cpp
index 879edd5..bb26b12 100644
--- a/src/gpu/gl/GrGLPath.cpp
+++ b/src/gpu/gl/GrGLPath.cpp
@@ -89,7 +89,7 @@
: INHERITED(gpu, kIsWrapped, path, stroke) {
SkASSERT(!path.isEmpty());
- GL_CALL_RET(fPathID, GenPaths(1));
+ fPathID = gpu->createGLPathObject();
SkSTArray<16, GrGLubyte, true> pathCommands;
SkSTArray<16, SkPoint, true> pathPoints;
@@ -135,7 +135,7 @@
void GrGLPath::onRelease() {
if (0 != fPathID && !this->isWrapped()) {
- GL_CALL(DeletePaths(fPathID, 1));
+ static_cast<GrGpuGL*>(this->getGpu())->deleteGLPathObject(fPathID);
fPathID = 0;
}
diff --git a/src/gpu/gl/GrGpuGL.cpp b/src/gpu/gl/GrGpuGL.cpp
index 7568ba3..12938f1 100644
--- a/src/gpu/gl/GrGpuGL.cpp
+++ b/src/gpu/gl/GrGpuGL.cpp
@@ -7,6 +7,7 @@
#include "GrGpuGL.h"
+#include "GrGLNameAllocator.h"
#include "GrGLStencilBuffer.h"
#include "GrGLPath.h"
#include "GrGLShaderBuilder.h"
@@ -2497,6 +2498,39 @@
}
}
+
+GrGLuint GrGpuGL::createGLPathObject() {
+ if (NULL == fPathNameAllocator.get()) {
+ static const int range = 65536;
+ GrGLuint firstName;
+ GL_CALL_RET(firstName, GenPaths(range));
+ fPathNameAllocator.reset(SkNEW_ARGS(GrGLNameAllocator, (firstName, firstName + range)));
+ }
+
+ GrGLuint name = fPathNameAllocator->allocateName();
+ if (0 == name) {
+ // Our reserved path names are all in use. Fall back on GenPaths.
+ GL_CALL_RET(name, GenPaths(1));
+ }
+
+ return name;
+}
+
+void GrGpuGL::deleteGLPathObject(GrGLuint name) {
+ if (NULL == fPathNameAllocator.get() ||
+ name < fPathNameAllocator->firstName() ||
+ name >= fPathNameAllocator->endName()) {
+ // If we aren't inside fPathNameAllocator's range then this name was
+ // generated by the GenPaths fallback (or else the name is unallocated).
+ GL_CALL(DeletePaths(name, 1));
+ return;
+ }
+
+ // Make the path empty to save memory, but don't free the name in the driver.
+ GL_CALL(PathCommands(name, 0, NULL, 0, GR_GL_FLOAT, NULL));
+ fPathNameAllocator->free(name);
+}
+
bool GrGpuGL::configToGLFormats(GrPixelConfig config,
bool getSizedInternalFormat,
GrGLenum* internalFormat,
diff --git a/src/gpu/gl/GrGpuGL.h b/src/gpu/gl/GrGpuGL.h
index cfb8b52..e50ff9b 100644
--- a/src/gpu/gl/GrGpuGL.h
+++ b/src/gpu/gl/GrGpuGL.h
@@ -26,6 +26,8 @@
#define PROGRAM_CACHE_STATS
#endif
+class GrGLNameAllocator;
+
class GrGpuGL : public GrGpu {
public:
GrGpuGL(const GrGLContext& ctx, GrContext* context);
@@ -106,6 +108,11 @@
void notifyTextureDelete(GrGLTexture* texture);
void notifyRenderTargetDelete(GrRenderTarget* renderTarget);
+ // These functions should be used to generate and delete GL path names. They have their own
+ // allocator that runs on the client side, so they are much faster than going through GenPaths.
+ GrGLuint createGLPathObject();
+ void deleteGLPathObject(GrGLuint);
+
protected:
virtual bool onCopySurface(GrSurface* dst,
GrSurface* src,
@@ -465,6 +472,8 @@
// from our loop that tries stencil formats and calls check fb status.
int fLastSuccessfulStencilFmtIdx;
+ SkAutoTDelete<GrGLNameAllocator> fPathNameAllocator;
+
typedef GrGpu INHERITED;
};
diff --git a/src/gpu/gl/GrGpuGL_program.cpp b/src/gpu/gl/GrGpuGL_program.cpp
index bc3a5b2..bd4758c 100644
--- a/src/gpu/gl/GrGpuGL_program.cpp
+++ b/src/gpu/gl/GrGpuGL_program.cpp
@@ -10,6 +10,7 @@
#include "GrEffect.h"
#include "GrGLEffect.h"
#include "SkRTConf.h"
+#include "GrGLNameAllocator.h"
#include "SkTSearch.h"
#ifdef PROGRAM_CACHE_STATS
@@ -202,6 +203,7 @@
INHERITED::abandonResources();
fProgramCache->abandon();
fHWProgramID = 0;
+ fPathNameAllocator.reset(NULL);
}
////////////////////////////////////////////////////////////////////////////////
diff --git a/tests/NameAllocatorTest.cpp b/tests/NameAllocatorTest.cpp
new file mode 100644
index 0000000..86efdb2
--- /dev/null
+++ b/tests/NameAllocatorTest.cpp
@@ -0,0 +1,169 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#if SK_SUPPORT_GPU
+
+#include "gl/GrGLNameAllocator.h"
+#include "Test.h"
+
+////////////////////////////////////////////////////////////////////////////////
+
+class NameLeakTest {
+ static const GrGLuint kFirstName = 101;
+ static const GrGLuint kRange = 1013;
+
+public:
+ NameLeakTest(skiatest::Reporter* reporter)
+ : fReporter(reporter),
+ fAllocator(kFirstName, kFirstName + kRange),
+ fAllocatedCount(0),
+ fRandomName(kFirstName + 4 * kRange / 7) {
+ memset(fAllocatedNames, 0, sizeof(fAllocatedNames));
+ }
+
+ bool run() {
+ if (!this->allocateAllRemaining()) {
+ return false;
+ }
+
+ for (GrGLuint freeCount = 1; freeCount <= kRange; ++freeCount) {
+ if (!this->freeRandomNames(freeCount)) {
+ return false;
+ }
+ if (!this->allocateAllRemaining()) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+private:
+ bool isAllocated(GrGLuint name) const {
+ return fAllocatedNames[name - kFirstName];
+ }
+
+ void setAllocated(GrGLuint name, bool allocated) {
+ fAllocatedNames[name - kFirstName] = allocated;
+ }
+
+ bool allocateAllRemaining() {
+ for (; fAllocatedCount < kRange; ++fAllocatedCount) {
+ GrGLuint name = fAllocator.allocateName();
+ if (0 == name) {
+ ERRORF(fReporter,
+ "Name allocate failed, but there should still be %u free names",
+ kRange - fAllocatedCount);
+ return false;
+ }
+ if (name < kFirstName || name >= kFirstName + kRange) {
+ ERRORF(fReporter,
+ "Name allocate returned name %u outside its bounds [%u, %u)",
+ name, kFirstName, kFirstName + kRange);
+ return false;
+ }
+ if (this->isAllocated(name)) {
+ ERRORF(fReporter, "Name allocate returned name that is already allocated");
+ return false;
+ }
+
+ this->setAllocated(name, true);
+ }
+
+ // Ensure it returns 0 once all the names are allocated.
+ GrGLuint name = fAllocator.allocateName();
+ if (0 != name) {
+ ERRORF(fReporter,
+ "Name allocate did not fail when all names were already in use");
+ return false;
+ }
+
+ // Ensure every unique name is allocated.
+ for (GrGLuint i = 0; i < kRange; ++i) {
+ if (!this->isAllocated(kFirstName + i)) {
+ ERRORF(fReporter, "Not all unique names are allocated after allocateAllRemaining()");
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ bool freeRandomNames(GrGLuint count) {
+ // The values a and c make up an LCG (pseudo-random generator). These
+ // values must satisfy the Hull-Dobell Theorem (with m=kRange):
+ // http://en.wikipedia.org/wiki/Linear_congruential_generator
+ // We use our own generator to guarantee it hits each unique value
+ // within kRange exactly once before repeating.
+ const GrGLuint seed = (count + fRandomName) / 2;
+ const GrGLuint a = seed * kRange + 1;
+ const GrGLuint c = (seed * 743) % kRange;
+
+ for (GrGLuint i = 0; i < count; ++i) {
+ fRandomName = (a * fRandomName + c) % kRange;
+ const GrGLuint name = kFirstName + fRandomName;
+ if (!this->isAllocated(name)) {
+ ERRORF(fReporter, "Test bug: Should not free a not-allocated name at this point (%u)", i);
+ return false;
+ }
+
+ fAllocator.free(name);
+ this->setAllocated(name, false);
+ --fAllocatedCount;
+ }
+
+ return true;
+ }
+
+ skiatest::Reporter* fReporter;
+ GrGLNameAllocator fAllocator;
+ bool fAllocatedNames[kRange];
+ GrGLuint fAllocatedCount;
+ GrGLuint fRandomName;
+};
+
+DEF_GPUTEST(NameAllocator, reporter, factory) {
+ // Ensure no names are leaked or double-allocated during heavy usage.
+ {
+ NameLeakTest nameLeakTest(reporter);
+ nameLeakTest.run();
+ }
+
+ static const GrGLuint range = 32;
+ GrGLNameAllocator allocator(1, 1 + range);
+ for (GrGLuint i = 1; i <= range; ++i) {
+ allocator.allocateName();
+ }
+ REPORTER_ASSERT(reporter, 0 == allocator.allocateName());
+
+ // Test freeing names out of range.
+ allocator.free(allocator.firstName() - 1);
+ allocator.free(allocator.endName());
+ REPORTER_ASSERT(reporter, 0 == allocator.allocateName());
+
+ // Test freeing not-allocated names.
+ for (GrGLuint i = 1; i <= range/2; i += 2) {
+ allocator.free(i);
+ }
+ for (GrGLuint i = 1; i <= range/2; i += 2) {
+ // None of these names will be allocated.
+ allocator.free(i);
+ }
+ for (GrGLuint i = 1; i <= range/2; ++i) {
+ // Every other name will not be be allocated.
+ allocator.free(i);
+ }
+ for (GrGLuint i = 1; i <= range/2; ++i) {
+ if (0 == allocator.allocateName()) {
+ ERRORF(reporter, "Name allocate failed when there should be free names");
+ break;
+ }
+ }
+ REPORTER_ASSERT(reporter, 0 == allocator.allocateName());
+}
+
+#endif
