diff options
Diffstat (limited to 'chromium/third_party/skia/src/gpu/gl/GrGLNameAllocator.cpp')
| -rw-r--r-- | chromium/third_party/skia/src/gpu/gl/GrGLNameAllocator.cpp | 370 |
1 files changed, 370 insertions, 0 deletions
diff --git a/chromium/third_party/skia/src/gpu/gl/GrGLNameAllocator.cpp b/chromium/third_party/skia/src/gpu/gl/GrGLNameAllocator.cpp new file mode 100644 index 00000000000..f2c37edbeb2 --- /dev/null +++ b/chromium/third_party/skia/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)); +} |