1511923443facc611b3735b4688342c12071feaa0cdalton 2511923443facc611b3735b4688342c12071feaa0cdalton/* 3511923443facc611b3735b4688342c12071feaa0cdalton * Copyright 2014 Google Inc. 4511923443facc611b3735b4688342c12071feaa0cdalton * 5511923443facc611b3735b4688342c12071feaa0cdalton * Use of this source code is governed by a BSD-style license that can be 6511923443facc611b3735b4688342c12071feaa0cdalton * found in the LICENSE file. 7511923443facc611b3735b4688342c12071feaa0cdalton */ 8511923443facc611b3735b4688342c12071feaa0cdalton 9511923443facc611b3735b4688342c12071feaa0cdalton#include "GrGLNameAllocator.h" 10511923443facc611b3735b4688342c12071feaa0cdalton 11511923443facc611b3735b4688342c12071feaa0cdalton/** 12511923443facc611b3735b4688342c12071feaa0cdalton * This is the abstract base class for a nonempty AVL tree that tracks allocated 13511923443facc611b3735b4688342c12071feaa0cdalton * names within the half-open range [fFirst, fEnd). The inner nodes can be 14511923443facc611b3735b4688342c12071feaa0cdalton * sparse (meaning not every name within the range is necessarily allocated), 15511923443facc611b3735b4688342c12071feaa0cdalton * but the bounds are tight, so fFirst *is* guaranteed to be allocated, and so 16511923443facc611b3735b4688342c12071feaa0cdalton * is fEnd - 1. 17511923443facc611b3735b4688342c12071feaa0cdalton */ 18511923443facc611b3735b4688342c12071feaa0cdaltonclass GrGLNameAllocator::SparseNameRange : public SkRefCnt { 19511923443facc611b3735b4688342c12071feaa0cdaltonpublic: 20511923443facc611b3735b4688342c12071feaa0cdalton virtual ~SparseNameRange() {} 21511923443facc611b3735b4688342c12071feaa0cdalton 22511923443facc611b3735b4688342c12071feaa0cdalton /** 23511923443facc611b3735b4688342c12071feaa0cdalton * Return the beginning of the range. first() is guaranteed to be allocated. 24511923443facc611b3735b4688342c12071feaa0cdalton * 25511923443facc611b3735b4688342c12071feaa0cdalton * @return The first name in the range. 26511923443facc611b3735b4688342c12071feaa0cdalton */ 27511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint first() const { return fFirst; } 28511923443facc611b3735b4688342c12071feaa0cdalton 29511923443facc611b3735b4688342c12071feaa0cdalton /** 30511923443facc611b3735b4688342c12071feaa0cdalton * Return the end of the range. end() - 1 is guaranteed to be allocated. 31511923443facc611b3735b4688342c12071feaa0cdalton * 32511923443facc611b3735b4688342c12071feaa0cdalton * @return One plus the final name in the range. 33511923443facc611b3735b4688342c12071feaa0cdalton */ 34511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint end() const { return fEnd; } 35511923443facc611b3735b4688342c12071feaa0cdalton 36511923443facc611b3735b4688342c12071feaa0cdalton /** 37511923443facc611b3735b4688342c12071feaa0cdalton * Return the height of the tree. This can only be nonzero at an inner node. 38511923443facc611b3735b4688342c12071feaa0cdalton * 39511923443facc611b3735b4688342c12071feaa0cdalton * @return 0 if the implementation is a leaf node, 40511923443facc611b3735b4688342c12071feaa0cdalton * The nonzero height of the tree otherwise. 41511923443facc611b3735b4688342c12071feaa0cdalton */ 42511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint height() const { return fHeight; } 43511923443facc611b3735b4688342c12071feaa0cdalton 44511923443facc611b3735b4688342c12071feaa0cdalton /** 45511923443facc611b3735b4688342c12071feaa0cdalton * Allocate a name from strictly inside this range. The call will fail if 46511923443facc611b3735b4688342c12071feaa0cdalton * there is not a free name within. 47511923443facc611b3735b4688342c12071feaa0cdalton * 48511923443facc611b3735b4688342c12071feaa0cdalton * @param outName A pointer that receives the allocated name. outName will 49511923443facc611b3735b4688342c12071feaa0cdalton * be set to zero if there were no free names within the 50511923443facc611b3735b4688342c12071feaa0cdalton * range [fFirst, fEnd). 51511923443facc611b3735b4688342c12071feaa0cdalton * @return The resulting SparseNameRange after the allocation. Note that 52511923443facc611b3735b4688342c12071feaa0cdalton * this call is destructive, so the original SparseNameRange will no 53511923443facc611b3735b4688342c12071feaa0cdalton * longer be valid afterward. The caller must always update its 54511923443facc611b3735b4688342c12071feaa0cdalton * pointer with the new SparseNameRange. 55511923443facc611b3735b4688342c12071feaa0cdalton */ 56511923443facc611b3735b4688342c12071feaa0cdalton virtual SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) = 0; 57511923443facc611b3735b4688342c12071feaa0cdalton 58511923443facc611b3735b4688342c12071feaa0cdalton /** 59511923443facc611b3735b4688342c12071feaa0cdalton * Remove the leftmost leaf node from this range (or the entire thing if it 60511923443facc611b3735b4688342c12071feaa0cdalton * *is* a leaf node). This is an internal helper method that is used after 61511923443facc611b3735b4688342c12071feaa0cdalton * an allocation if one contiguous range became adjacent to another. (The 62511923443facc611b3735b4688342c12071feaa0cdalton * range gets removed so the one immediately before can be extended, 63511923443facc611b3735b4688342c12071feaa0cdalton * collapsing the two into one.) 64511923443facc611b3735b4688342c12071feaa0cdalton * 65511923443facc611b3735b4688342c12071feaa0cdalton * @param removedCount A pointer that receives the size of the contiguous 66511923443facc611b3735b4688342c12071feaa0cdalton range that was removed. 67511923443facc611b3735b4688342c12071feaa0cdalton * @return The resulting SparseNameRange after the removal (or NULL if it 68511923443facc611b3735b4688342c12071feaa0cdalton * became empty). Note that this call is destructive, so the 69511923443facc611b3735b4688342c12071feaa0cdalton * original SparseNameRange will no longer be valid afterward. The 70511923443facc611b3735b4688342c12071feaa0cdalton * caller must always update its pointer with the new 71511923443facc611b3735b4688342c12071feaa0cdalton * SparseNameRange. 72511923443facc611b3735b4688342c12071feaa0cdalton */ 73511923443facc611b3735b4688342c12071feaa0cdalton virtual SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) = 0; 74511923443facc611b3735b4688342c12071feaa0cdalton 75511923443facc611b3735b4688342c12071feaa0cdalton /** 76511923443facc611b3735b4688342c12071feaa0cdalton * Append adjacent allocated names to the end of this range. This operation 77511923443facc611b3735b4688342c12071feaa0cdalton * does not affect the structure of the tree. The caller is responsible for 78511923443facc611b3735b4688342c12071feaa0cdalton * ensuring the new names won't overlap sibling ranges, if any. 79511923443facc611b3735b4688342c12071feaa0cdalton * 80511923443facc611b3735b4688342c12071feaa0cdalton * @param count The number of adjacent names to append. 81511923443facc611b3735b4688342c12071feaa0cdalton * @return The first name appended. 82511923443facc611b3735b4688342c12071feaa0cdalton */ 83511923443facc611b3735b4688342c12071feaa0cdalton virtual GrGLuint appendNames(GrGLuint count) = 0; 84511923443facc611b3735b4688342c12071feaa0cdalton 85511923443facc611b3735b4688342c12071feaa0cdalton /** 86511923443facc611b3735b4688342c12071feaa0cdalton * Prepend adjacent allocated names behind the beginning of this range. This 87511923443facc611b3735b4688342c12071feaa0cdalton * operation does not affect the structure of the tree. The caller is 88511923443facc611b3735b4688342c12071feaa0cdalton * responsible for ensuring the new names won't overlap sibling ranges, if 89511923443facc611b3735b4688342c12071feaa0cdalton * any. 90511923443facc611b3735b4688342c12071feaa0cdalton * 91511923443facc611b3735b4688342c12071feaa0cdalton * @param count The number of adjacent names to prepend. 92511923443facc611b3735b4688342c12071feaa0cdalton * @return The final name prepended (the one with the lowest value). 93511923443facc611b3735b4688342c12071feaa0cdalton */ 94511923443facc611b3735b4688342c12071feaa0cdalton virtual GrGLuint prependNames(GrGLuint count) = 0; 95511923443facc611b3735b4688342c12071feaa0cdalton 96511923443facc611b3735b4688342c12071feaa0cdalton /** 97511923443facc611b3735b4688342c12071feaa0cdalton * Free a name so it is no longer tracked as allocated. If the name is at 98511923443facc611b3735b4688342c12071feaa0cdalton * the very beginning or very end of the range, the boundaries [fFirst, fEnd) 99511923443facc611b3735b4688342c12071feaa0cdalton * will be tightened. 100511923443facc611b3735b4688342c12071feaa0cdalton * 101511923443facc611b3735b4688342c12071feaa0cdalton * @param name The name to free. Not-allocated names are silently ignored 102511923443facc611b3735b4688342c12071feaa0cdalton * the same way they are in the OpenGL spec. 103511923443facc611b3735b4688342c12071feaa0cdalton * @return The resulting SparseNameRange after the free (or NULL if it 104511923443facc611b3735b4688342c12071feaa0cdalton * became empty). Note that this call is destructive, so the 105511923443facc611b3735b4688342c12071feaa0cdalton * original SparseNameRange will no longer be valid afterward. The 106511923443facc611b3735b4688342c12071feaa0cdalton * caller must always update its pointer with the new 107511923443facc611b3735b4688342c12071feaa0cdalton * SparseNameRange. 108511923443facc611b3735b4688342c12071feaa0cdalton */ 109511923443facc611b3735b4688342c12071feaa0cdalton virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) = 0; 110511923443facc611b3735b4688342c12071feaa0cdalton 111511923443facc611b3735b4688342c12071feaa0cdaltonprotected: 112511923443facc611b3735b4688342c12071feaa0cdalton SparseNameRange* takeRef() { 113511923443facc611b3735b4688342c12071feaa0cdalton this->ref(); 114511923443facc611b3735b4688342c12071feaa0cdalton return this; 115511923443facc611b3735b4688342c12071feaa0cdalton } 116511923443facc611b3735b4688342c12071feaa0cdalton 117511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint fFirst; 118511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint fEnd; 119511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint fHeight; 120511923443facc611b3735b4688342c12071feaa0cdalton}; 121511923443facc611b3735b4688342c12071feaa0cdalton 122511923443facc611b3735b4688342c12071feaa0cdalton/** 123511923443facc611b3735b4688342c12071feaa0cdalton * This class is the SparseNameRange implementation for an inner node. It is an 124511923443facc611b3735b4688342c12071feaa0cdalton * AVL tree with non-null, non-adjacent left and right children. 125511923443facc611b3735b4688342c12071feaa0cdalton */ 126511923443facc611b3735b4688342c12071feaa0cdaltonclass GrGLNameAllocator::SparseNameTree : public SparseNameRange { 127511923443facc611b3735b4688342c12071feaa0cdaltonpublic: 128511923443facc611b3735b4688342c12071feaa0cdalton SparseNameTree(SparseNameRange* left, SparseNameRange* right) 129511923443facc611b3735b4688342c12071feaa0cdalton : fLeft(left), 130511923443facc611b3735b4688342c12071feaa0cdalton fRight(right) { 131511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fLeft.get()); 132511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fRight.get()); 133511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 134511923443facc611b3735b4688342c12071feaa0cdalton } 135511923443facc611b3735b4688342c12071feaa0cdalton 13636352bf5e38f45a70ee4f4fc132a38048d38206dmtklein SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) override { 137511923443facc611b3735b4688342c12071feaa0cdalton // Try allocating the range inside fLeft's internal gaps. 138511923443facc611b3735b4688342c12071feaa0cdalton fLeft.reset(fLeft->internalAllocate(outName)); 139511923443facc611b3735b4688342c12071feaa0cdalton if (0 != *outName) { 140511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 141511923443facc611b3735b4688342c12071feaa0cdalton return this->rebalance(); 142511923443facc611b3735b4688342c12071feaa0cdalton } 143511923443facc611b3735b4688342c12071feaa0cdalton 144511923443facc611b3735b4688342c12071feaa0cdalton if (fLeft->end() + 1 == fRight->first()) { 145511923443facc611b3735b4688342c12071feaa0cdalton // It closed the gap between fLeft and fRight; merge. 146511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint removedCount; 147511923443facc611b3735b4688342c12071feaa0cdalton fRight.reset(fRight->removeLeftmostContiguousRange(&removedCount)); 148511923443facc611b3735b4688342c12071feaa0cdalton *outName = fLeft->appendNames(1 + removedCount); 149511923443facc611b3735b4688342c12071feaa0cdalton if (NULL == fRight.get()) { 150511923443facc611b3735b4688342c12071feaa0cdalton return fLeft.detach(); 151511923443facc611b3735b4688342c12071feaa0cdalton } 152511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 153511923443facc611b3735b4688342c12071feaa0cdalton return this->rebalance(); 154511923443facc611b3735b4688342c12071feaa0cdalton } 155511923443facc611b3735b4688342c12071feaa0cdalton 156511923443facc611b3735b4688342c12071feaa0cdalton // There is guaranteed to be a gap between fLeft and fRight, and the 157511923443facc611b3735b4688342c12071feaa0cdalton // "size 1" case has already been covered. 158511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fLeft->end() + 1 < fRight->first()); 159511923443facc611b3735b4688342c12071feaa0cdalton *outName = fLeft->appendNames(1); 160511923443facc611b3735b4688342c12071feaa0cdalton return this->takeRef(); 161511923443facc611b3735b4688342c12071feaa0cdalton } 162511923443facc611b3735b4688342c12071feaa0cdalton 16336352bf5e38f45a70ee4f4fc132a38048d38206dmtklein SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) override { 164511923443facc611b3735b4688342c12071feaa0cdalton fLeft.reset(fLeft->removeLeftmostContiguousRange(removedCount)); 165511923443facc611b3735b4688342c12071feaa0cdalton if (NULL == fLeft) { 166511923443facc611b3735b4688342c12071feaa0cdalton return fRight.detach(); 167511923443facc611b3735b4688342c12071feaa0cdalton } 168511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 169511923443facc611b3735b4688342c12071feaa0cdalton return this->rebalance(); 170511923443facc611b3735b4688342c12071feaa0cdalton } 171511923443facc611b3735b4688342c12071feaa0cdalton 17236352bf5e38f45a70ee4f4fc132a38048d38206dmtklein GrGLuint appendNames(GrGLuint count) override { 173511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fEnd + count > fEnd); // Check for integer wrap. 174511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint name = fRight->appendNames(count); 175511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fRight->end() == fEnd + count); 176511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 177511923443facc611b3735b4688342c12071feaa0cdalton return name; 178511923443facc611b3735b4688342c12071feaa0cdalton } 179511923443facc611b3735b4688342c12071feaa0cdalton 18036352bf5e38f45a70ee4f4fc132a38048d38206dmtklein GrGLuint prependNames(GrGLuint count) override { 181511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fFirst > count); // We can't allocate at or below 0. 182511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint name = fLeft->prependNames(count); 183511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fLeft->first() == fFirst - count); 184511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 185511923443facc611b3735b4688342c12071feaa0cdalton return name; 186511923443facc611b3735b4688342c12071feaa0cdalton } 187511923443facc611b3735b4688342c12071feaa0cdalton 18836352bf5e38f45a70ee4f4fc132a38048d38206dmtklein SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) override { 189511923443facc611b3735b4688342c12071feaa0cdalton if (name < fLeft->end()) { 190511923443facc611b3735b4688342c12071feaa0cdalton fLeft.reset(fLeft->free(name)); 191511923443facc611b3735b4688342c12071feaa0cdalton if (NULL == fLeft) { 192511923443facc611b3735b4688342c12071feaa0cdalton // fLeft became empty after the free. 193511923443facc611b3735b4688342c12071feaa0cdalton return fRight.detach(); 194511923443facc611b3735b4688342c12071feaa0cdalton } 195511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 196511923443facc611b3735b4688342c12071feaa0cdalton return this->rebalance(); 197511923443facc611b3735b4688342c12071feaa0cdalton } else { 198511923443facc611b3735b4688342c12071feaa0cdalton fRight.reset(fRight->free(name)); 199511923443facc611b3735b4688342c12071feaa0cdalton if (NULL == fRight) { 200511923443facc611b3735b4688342c12071feaa0cdalton // fRight became empty after the free. 201511923443facc611b3735b4688342c12071feaa0cdalton return fLeft.detach(); 202511923443facc611b3735b4688342c12071feaa0cdalton } 203511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 204511923443facc611b3735b4688342c12071feaa0cdalton return this->rebalance(); 205511923443facc611b3735b4688342c12071feaa0cdalton } 206511923443facc611b3735b4688342c12071feaa0cdalton } 207511923443facc611b3735b4688342c12071feaa0cdalton 208511923443facc611b3735b4688342c12071feaa0cdaltonprivate: 209511923443facc611b3735b4688342c12071feaa0cdalton typedef SkAutoTUnref<SparseNameRange> SparseNameTree::* ChildRange; 210511923443facc611b3735b4688342c12071feaa0cdalton 211511923443facc611b3735b4688342c12071feaa0cdalton SparseNameRange* SK_WARN_UNUSED_RESULT rebalance() { 212511923443facc611b3735b4688342c12071feaa0cdalton if (fLeft->height() > fRight->height() + 1) { 213511923443facc611b3735b4688342c12071feaa0cdalton return this->rebalanceImpl<&SparseNameTree::fLeft, &SparseNameTree::fRight>(); 214511923443facc611b3735b4688342c12071feaa0cdalton } 215511923443facc611b3735b4688342c12071feaa0cdalton if (fRight->height() > fLeft->height() + 1) { 216511923443facc611b3735b4688342c12071feaa0cdalton return this->rebalanceImpl<&SparseNameTree::fRight, &SparseNameTree::fLeft>(); 217511923443facc611b3735b4688342c12071feaa0cdalton } 218511923443facc611b3735b4688342c12071feaa0cdalton return this->takeRef(); 219511923443facc611b3735b4688342c12071feaa0cdalton } 220511923443facc611b3735b4688342c12071feaa0cdalton 221511923443facc611b3735b4688342c12071feaa0cdalton /** 222511923443facc611b3735b4688342c12071feaa0cdalton * Rebalance the tree using rotations, as described in the AVL algorithm: 223511923443facc611b3735b4688342c12071feaa0cdalton * http://en.wikipedia.org/wiki/AVL_tree#Insertion 224511923443facc611b3735b4688342c12071feaa0cdalton */ 225511923443facc611b3735b4688342c12071feaa0cdalton template<ChildRange Tall, ChildRange Short> 226511923443facc611b3735b4688342c12071feaa0cdalton SparseNameRange* SK_WARN_UNUSED_RESULT rebalanceImpl() { 227511923443facc611b3735b4688342c12071feaa0cdalton // We should be calling rebalance() enough that the tree never gets more 228511923443facc611b3735b4688342c12071feaa0cdalton // than one rotation off balance. 229511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(2 == (this->*Tall)->height() - (this->*Short)->height()); 230511923443facc611b3735b4688342c12071feaa0cdalton 231511923443facc611b3735b4688342c12071feaa0cdalton // Ensure we are in the 'Left Left' or 'Right Right' case: 232511923443facc611b3735b4688342c12071feaa0cdalton // http://en.wikipedia.org/wiki/AVL_tree#Insertion 233511923443facc611b3735b4688342c12071feaa0cdalton SparseNameTree* tallChild = static_cast<SparseNameTree*>((this->*Tall).get()); 234511923443facc611b3735b4688342c12071feaa0cdalton if ((tallChild->*Tall)->height() < (tallChild->*Short)->height()) { 235511923443facc611b3735b4688342c12071feaa0cdalton (this->*Tall).reset(tallChild->rotate<Short, Tall>()); 236511923443facc611b3735b4688342c12071feaa0cdalton } 237511923443facc611b3735b4688342c12071feaa0cdalton 238511923443facc611b3735b4688342c12071feaa0cdalton // Perform a rotation to balance the tree. 239511923443facc611b3735b4688342c12071feaa0cdalton return this->rotate<Tall, Short>(); 240511923443facc611b3735b4688342c12071feaa0cdalton } 241511923443facc611b3735b4688342c12071feaa0cdalton 242511923443facc611b3735b4688342c12071feaa0cdalton /** 243511923443facc611b3735b4688342c12071feaa0cdalton * Perform a node rotation, as described in the AVL algorithm: 244511923443facc611b3735b4688342c12071feaa0cdalton * http://en.wikipedia.org/wiki/AVL_tree#Insertion 245511923443facc611b3735b4688342c12071feaa0cdalton */ 246511923443facc611b3735b4688342c12071feaa0cdalton template<ChildRange Tall, ChildRange Short> 247511923443facc611b3735b4688342c12071feaa0cdalton SparseNameRange* SK_WARN_UNUSED_RESULT rotate() { 248511923443facc611b3735b4688342c12071feaa0cdalton SparseNameTree* newRoot = static_cast<SparseNameTree*>((this->*Tall).detach()); 249511923443facc611b3735b4688342c12071feaa0cdalton 250511923443facc611b3735b4688342c12071feaa0cdalton (this->*Tall).reset((newRoot->*Short).detach()); 251511923443facc611b3735b4688342c12071feaa0cdalton this->updateStats(); 252511923443facc611b3735b4688342c12071feaa0cdalton 253511923443facc611b3735b4688342c12071feaa0cdalton (newRoot->*Short).reset(this->takeRef()); 254511923443facc611b3735b4688342c12071feaa0cdalton newRoot->updateStats(); 255511923443facc611b3735b4688342c12071feaa0cdalton 256511923443facc611b3735b4688342c12071feaa0cdalton return newRoot; 257511923443facc611b3735b4688342c12071feaa0cdalton } 258511923443facc611b3735b4688342c12071feaa0cdalton 259511923443facc611b3735b4688342c12071feaa0cdalton void updateStats() { 260511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fLeft->end() < fRight->first()); // There must be a gap between left and right. 261511923443facc611b3735b4688342c12071feaa0cdalton fFirst = fLeft->first(); 262511923443facc611b3735b4688342c12071feaa0cdalton fEnd = fRight->end(); 263511923443facc611b3735b4688342c12071feaa0cdalton fHeight = 1 + SkMax32(fLeft->height(), fRight->height()); 264511923443facc611b3735b4688342c12071feaa0cdalton } 265511923443facc611b3735b4688342c12071feaa0cdalton 266511923443facc611b3735b4688342c12071feaa0cdalton SkAutoTUnref<SparseNameRange> fLeft; 267511923443facc611b3735b4688342c12071feaa0cdalton SkAutoTUnref<SparseNameRange> fRight; 268511923443facc611b3735b4688342c12071feaa0cdalton}; 269511923443facc611b3735b4688342c12071feaa0cdalton 270511923443facc611b3735b4688342c12071feaa0cdalton/** 271511923443facc611b3735b4688342c12071feaa0cdalton * This class is the SparseNameRange implementation for a leaf node. It just a 272511923443facc611b3735b4688342c12071feaa0cdalton * contiguous range of allocated names. 273511923443facc611b3735b4688342c12071feaa0cdalton */ 274511923443facc611b3735b4688342c12071feaa0cdaltonclass GrGLNameAllocator::ContiguousNameRange : public SparseNameRange { 275511923443facc611b3735b4688342c12071feaa0cdaltonpublic: 276511923443facc611b3735b4688342c12071feaa0cdalton ContiguousNameRange(GrGLuint first, GrGLuint end) { 277511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(first < end); 278511923443facc611b3735b4688342c12071feaa0cdalton fFirst = first; 279511923443facc611b3735b4688342c12071feaa0cdalton fEnd = end; 280511923443facc611b3735b4688342c12071feaa0cdalton fHeight = 0; 281511923443facc611b3735b4688342c12071feaa0cdalton } 282511923443facc611b3735b4688342c12071feaa0cdalton 28336352bf5e38f45a70ee4f4fc132a38048d38206dmtklein SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) override { 284511923443facc611b3735b4688342c12071feaa0cdalton *outName = 0; // No internal gaps, we are contiguous. 285511923443facc611b3735b4688342c12071feaa0cdalton return this->takeRef(); 286511923443facc611b3735b4688342c12071feaa0cdalton } 287511923443facc611b3735b4688342c12071feaa0cdalton 28836352bf5e38f45a70ee4f4fc132a38048d38206dmtklein SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) override { 289511923443facc611b3735b4688342c12071feaa0cdalton *removedCount = fEnd - fFirst; 290511923443facc611b3735b4688342c12071feaa0cdalton return NULL; 291511923443facc611b3735b4688342c12071feaa0cdalton } 292511923443facc611b3735b4688342c12071feaa0cdalton 29336352bf5e38f45a70ee4f4fc132a38048d38206dmtklein GrGLuint appendNames(GrGLuint count) override { 294511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fEnd + count > fEnd); // Check for integer wrap. 295511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint name = fEnd; 296511923443facc611b3735b4688342c12071feaa0cdalton fEnd += count; 297511923443facc611b3735b4688342c12071feaa0cdalton return name; 298511923443facc611b3735b4688342c12071feaa0cdalton } 299511923443facc611b3735b4688342c12071feaa0cdalton 30036352bf5e38f45a70ee4f4fc132a38048d38206dmtklein GrGLuint prependNames(GrGLuint count) override { 301511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(fFirst > count); // We can't allocate at or below 0. 302511923443facc611b3735b4688342c12071feaa0cdalton fFirst -= count; 303511923443facc611b3735b4688342c12071feaa0cdalton return fFirst; 304511923443facc611b3735b4688342c12071feaa0cdalton } 305511923443facc611b3735b4688342c12071feaa0cdalton 30636352bf5e38f45a70ee4f4fc132a38048d38206dmtklein SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) override { 307511923443facc611b3735b4688342c12071feaa0cdalton if (name < fFirst || name >= fEnd) { 308511923443facc611b3735b4688342c12071feaa0cdalton // Not-allocated names are silently ignored. 309511923443facc611b3735b4688342c12071feaa0cdalton return this->takeRef(); 310511923443facc611b3735b4688342c12071feaa0cdalton } 311511923443facc611b3735b4688342c12071feaa0cdalton 312511923443facc611b3735b4688342c12071feaa0cdalton if (fFirst == name) { 313511923443facc611b3735b4688342c12071feaa0cdalton ++fFirst; 314511923443facc611b3735b4688342c12071feaa0cdalton return (fEnd == fFirst) ? NULL : this->takeRef(); 315511923443facc611b3735b4688342c12071feaa0cdalton } 316511923443facc611b3735b4688342c12071feaa0cdalton 317511923443facc611b3735b4688342c12071feaa0cdalton if (fEnd == name + 1) { 318511923443facc611b3735b4688342c12071feaa0cdalton --fEnd; 319511923443facc611b3735b4688342c12071feaa0cdalton return this->takeRef(); 320511923443facc611b3735b4688342c12071feaa0cdalton } 321511923443facc611b3735b4688342c12071feaa0cdalton 322511923443facc611b3735b4688342c12071feaa0cdalton SparseNameRange* left = SkNEW_ARGS(ContiguousNameRange, (fFirst, name)); 323511923443facc611b3735b4688342c12071feaa0cdalton SparseNameRange* right = this->takeRef(); 324511923443facc611b3735b4688342c12071feaa0cdalton fFirst = name + 1; 325511923443facc611b3735b4688342c12071feaa0cdalton return SkNEW_ARGS(SparseNameTree, (left, right)); 326511923443facc611b3735b4688342c12071feaa0cdalton } 327511923443facc611b3735b4688342c12071feaa0cdalton}; 328511923443facc611b3735b4688342c12071feaa0cdalton 329511923443facc611b3735b4688342c12071feaa0cdaltonGrGLNameAllocator::GrGLNameAllocator(GrGLuint firstName, GrGLuint endName) 330511923443facc611b3735b4688342c12071feaa0cdalton : fFirstName(firstName), 331511923443facc611b3735b4688342c12071feaa0cdalton fEndName(endName) { 332511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(firstName > 0); 333511923443facc611b3735b4688342c12071feaa0cdalton SkASSERT(endName > firstName); 334511923443facc611b3735b4688342c12071feaa0cdalton} 335511923443facc611b3735b4688342c12071feaa0cdalton 336511923443facc611b3735b4688342c12071feaa0cdaltonGrGLNameAllocator::~GrGLNameAllocator() { 337511923443facc611b3735b4688342c12071feaa0cdalton} 338511923443facc611b3735b4688342c12071feaa0cdalton 339511923443facc611b3735b4688342c12071feaa0cdaltonGrGLuint GrGLNameAllocator::allocateName() { 340511923443facc611b3735b4688342c12071feaa0cdalton if (NULL == fAllocatedNames.get()) { 341511923443facc611b3735b4688342c12071feaa0cdalton fAllocatedNames.reset(SkNEW_ARGS(ContiguousNameRange, (fFirstName, fFirstName + 1))); 342511923443facc611b3735b4688342c12071feaa0cdalton return fFirstName; 343511923443facc611b3735b4688342c12071feaa0cdalton } 344511923443facc611b3735b4688342c12071feaa0cdalton 345511923443facc611b3735b4688342c12071feaa0cdalton if (fAllocatedNames->first() > fFirstName) { 346511923443facc611b3735b4688342c12071feaa0cdalton return fAllocatedNames->prependNames(1); 347511923443facc611b3735b4688342c12071feaa0cdalton } 348511923443facc611b3735b4688342c12071feaa0cdalton 349511923443facc611b3735b4688342c12071feaa0cdalton GrGLuint name; 350511923443facc611b3735b4688342c12071feaa0cdalton fAllocatedNames.reset(fAllocatedNames->internalAllocate(&name)); 351511923443facc611b3735b4688342c12071feaa0cdalton if (0 != name) { 352511923443facc611b3735b4688342c12071feaa0cdalton return name; 353511923443facc611b3735b4688342c12071feaa0cdalton } 354511923443facc611b3735b4688342c12071feaa0cdalton 355511923443facc611b3735b4688342c12071feaa0cdalton if (fAllocatedNames->end() < fEndName) { 356511923443facc611b3735b4688342c12071feaa0cdalton return fAllocatedNames->appendNames(1); 357511923443facc611b3735b4688342c12071feaa0cdalton } 358511923443facc611b3735b4688342c12071feaa0cdalton 359511923443facc611b3735b4688342c12071feaa0cdalton // Out of names. 360511923443facc611b3735b4688342c12071feaa0cdalton return 0; 361511923443facc611b3735b4688342c12071feaa0cdalton} 362511923443facc611b3735b4688342c12071feaa0cdalton 363511923443facc611b3735b4688342c12071feaa0cdaltonvoid GrGLNameAllocator::free(GrGLuint name) { 364511923443facc611b3735b4688342c12071feaa0cdalton if (!fAllocatedNames.get()) { 365511923443facc611b3735b4688342c12071feaa0cdalton // Not-allocated names are silently ignored. 366511923443facc611b3735b4688342c12071feaa0cdalton return; 367511923443facc611b3735b4688342c12071feaa0cdalton } 368511923443facc611b3735b4688342c12071feaa0cdalton 369511923443facc611b3735b4688342c12071feaa0cdalton fAllocatedNames.reset(fAllocatedNames->free(name)); 370511923443facc611b3735b4688342c12071feaa0cdalton} 371