/*
* 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));
}