src/gpu/gl/GrGLNameAllocator.cpp

   1
   2 /*
   3  * Copyright 2014 Google Inc.
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8
   9 #include "GrGLNameAllocator.h"
  10
  11 /**
  12  * This is the abstract base class for a nonempty AVL tree that tracks allocated
  13  * names within the half-open range [fFirst, fEnd). The inner nodes can be
  14  * sparse (meaning not every name within the range is necessarily allocated),
  15  * but the bounds are tight, so fFirst *is* guaranteed to be allocated, and so
  16  * is fEnd - 1.
  17  */
  18 class GrGLNameAllocator::SparseNameRange : public SkRefCnt {
  19 public:
  20     virtual ~SparseNameRange() {}
  21
  22     /**
  23      * Return the beginning of the range. first() is guaranteed to be allocated.
  24      *
  25      * @return The first name in the range.
  26      */
  27     GrGLuint first() const { return fFirst; }
  28
  29     /**
  30      * Return the end of the range. end() - 1 is guaranteed to be allocated.
  31      *
  32      * @return One plus the final name in the range.
  33      */
  34     GrGLuint end() const { return fEnd; }
  35
  36     /**
  37      * Return the height of the tree. This can only be nonzero at an inner node.
  38      *
  39      * @return 0 if the implementation is a leaf node,
  40      *         The nonzero height of the tree otherwise.
  41      */
  42     GrGLuint height() const { return fHeight; }
  43
  44     /**
  45      * Allocate a name from strictly inside this range. The call will fail if
  46      * there is not a free name within.
  47      *
  48      * @param outName A pointer that receives the allocated name. outName will
  49      *                be set to zero if there were no free names within the
  50      *                range [fFirst, fEnd).
  51      * @return The resulting SparseNameRange after the allocation. Note that
  52      *         this call is destructive, so the original SparseNameRange will no
  53      *         longer be valid afterward. The caller must always update its
  54      *         pointer with the new SparseNameRange.
  55      */
  56     virtual SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) = 0;
  57
  58     /**
  59      * Remove the leftmost leaf node from this range (or the entire thing if it
  60      * *is* a leaf node). This is an internal helper method that is used after
  61      * an allocation if one contiguous range became adjacent to another. (The
  62      * range gets removed so the one immediately before can be extended,
  63      * collapsing the two into one.)
  64      *
  65      * @param removedCount A pointer that receives the size of the contiguous
  66                            range that was removed.
  67      * @return The resulting SparseNameRange after the removal (or NULL if it
  68      *         became empty). Note that this call is destructive, so the
  69      *         original SparseNameRange will no longer be valid afterward. The
  70      *         caller must always update its pointer with the new
  71      *         SparseNameRange.
  72      */
  73     virtual SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) = 0;
  74
  75     /**
  76      * Append adjacent allocated names to the end of this range. This operation
  77      * does not affect the structure of the tree. The caller is responsible for
  78      * ensuring the new names won't overlap sibling ranges, if any.
  79      *
  80      * @param count The number of adjacent names to append.
  81      * @return The first name appended.
  82      */
  83     virtual GrGLuint appendNames(GrGLuint count) = 0;
  84
  85     /**
  86      * Prepend adjacent allocated names behind the beginning of this range. This
  87      * operation does not affect the structure of the tree. The caller is
  88      * responsible for ensuring the new names won't overlap sibling ranges, if
  89      * any.
  90      *
  91      * @param count The number of adjacent names to prepend.
  92      * @return The final name prepended (the one with the lowest value).
  93      */
  94     virtual GrGLuint prependNames(GrGLuint count) = 0;
  95
  96     /**
  97      * Free a name so it is no longer tracked as allocated. If the name is at
  98      * the very beginning or very end of the range, the boundaries [fFirst, fEnd)
  99      * will be tightened.
 100      *
 101      * @param name The name to free. Not-allocated names are silently ignored
 102      *             the same way they are in the OpenGL spec.
 103      * @return The resulting SparseNameRange after the free (or NULL if it
 104      *         became empty). Note that this call is destructive, so the
 105      *         original SparseNameRange will no longer be valid afterward. The
 106      *         caller must always update its pointer with the new
 107      *         SparseNameRange.
 108      */
 109     virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) = 0;
 110
 111 protected:
 112     SparseNameRange* takeRef() {
 113       this->ref();
 114       return this;
 115     }
 116
 117     GrGLuint fFirst;
 118     GrGLuint fEnd;
 119     GrGLuint fHeight;
 120 };
 121
 122 /**
 123  * This class is the SparseNameRange implementation for an inner node. It is an
 124  * AVL tree with non-null, non-adjacent left and right children.
 125  */
 126 class GrGLNameAllocator::SparseNameTree : public SparseNameRange {
 127 public:
 128     SparseNameTree(SparseNameRange* left, SparseNameRange* right)
 129         : fLeft(left),
 130           fRight(right) {
 131         SkASSERT(fLeft.get());
 132         SkASSERT(fRight.get());
 133         this->updateStats();
 134     }
 135
 136     SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) SK_OVERRIDE {
 137         // Try allocating the range inside fLeft's internal gaps.
 138         fLeft.reset(fLeft->internalAllocate(outName));
 139         if (0 != *outName) {
 140             this->updateStats();
 141             return this->rebalance();
 142         }
 143
 144         if (fLeft->end() + 1 == fRight->first()) {
 145             // It closed the gap between fLeft and fRight; merge.
 146             GrGLuint removedCount;
 147             fRight.reset(fRight->removeLeftmostContiguousRange(&removedCount));
 148             *outName = fLeft->appendNames(1 + removedCount);
 149             if (NULL == fRight.get()) {
 150                 return fLeft.detach();
 151             }
 152             this->updateStats();
 153             return this->rebalance();
 154         }
 155
 156         // There is guaranteed to be a gap between fLeft and fRight, and the
 157         // "size 1" case has already been covered.
 158         SkASSERT(fLeft->end() + 1 < fRight->first());
 159         *outName = fLeft->appendNames(1);
 160         return this->takeRef();
 161     }
 162
 163     SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) SK_OVERRIDE {
 164         fLeft.reset(fLeft->removeLeftmostContiguousRange(removedCount));
 165         if (NULL == fLeft) {
 166             return fRight.detach();
 167         }
 168         this->updateStats();
 169         return this->rebalance();
 170     }
 171
 172     GrGLuint appendNames(GrGLuint count) SK_OVERRIDE {
 173         SkASSERT(fEnd + count > fEnd); // Check for integer wrap.
 174         GrGLuint name = fRight->appendNames(count);
 175         SkASSERT(fRight->end() == fEnd + count);
 176         this->updateStats();
 177         return name;
 178     }
 179
 180     GrGLuint prependNames(GrGLuint count) SK_OVERRIDE {
 181         SkASSERT(fFirst > count); // We can't allocate at or below 0.
 182         GrGLuint name = fLeft->prependNames(count);
 183         SkASSERT(fLeft->first() == fFirst - count);
 184         this->updateStats();
 185         return name;
 186     }
 187
 188     SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) SK_OVERRIDE {
 189         if (name < fLeft->end()) {
 190             fLeft.reset(fLeft->free(name));
 191             if (NULL == fLeft) {
 192                 // fLeft became empty after the free.
 193                 return fRight.detach();
 194             }
 195             this->updateStats();
 196             return this->rebalance();
 197         } else {
 198             fRight.reset(fRight->free(name));
 199             if (NULL == fRight) {
 200                 // fRight became empty after the free.
 201                 return fLeft.detach();
 202             }
 203             this->updateStats();
 204             return this->rebalance();
 205         }
 206     }
 207
 208 private:
 209     typedef SkAutoTUnref<SparseNameRange> SparseNameTree::* ChildRange;
 210
 211     SparseNameRange* SK_WARN_UNUSED_RESULT rebalance() {
 212         if (fLeft->height() > fRight->height() + 1) {
 213             return this->rebalanceImpl<&SparseNameTree::fLeft, &SparseNameTree::fRight>();
 214         }
 215         if (fRight->height() > fLeft->height() + 1) {
 216             return this->rebalanceImpl<&SparseNameTree::fRight, &SparseNameTree::fLeft>();
 217         }
 218         return this->takeRef();
 219     }
 220
 221     /**
 222      * Rebalance the tree using rotations, as described in the AVL algorithm:
 223      * http://en.wikipedia.org/wiki/AVL_tree#Insertion
 224      */
 225     template<ChildRange Tall, ChildRange Short>
 226     SparseNameRange* SK_WARN_UNUSED_RESULT rebalanceImpl() {
 227         // We should be calling rebalance() enough that the tree never gets more
 228         // than one rotation off balance.
 229         SkASSERT(2 == (this->*Tall)->height() - (this->*Short)->height());
 230
 231         // Ensure we are in the 'Left Left' or 'Right Right' case:
 232         // http://en.wikipedia.org/wiki/AVL_tree#Insertion
 233         SparseNameTree* tallChild = static_cast<SparseNameTree*>((this->*Tall).get());
 234         if ((tallChild->*Tall)->height() < (tallChild->*Short)->height()) {
 235             (this->*Tall).reset(tallChild->rotate<Short, Tall>());
 236         }
 237
 238         // Perform a rotation to balance the tree.
 239         return this->rotate<Tall, Short>();
 240     }
 241
 242     /**
 243      * Perform a node rotation, as described in the AVL algorithm:
 244      * http://en.wikipedia.org/wiki/AVL_tree#Insertion
 245      */
 246     template<ChildRange Tall, ChildRange Short>
 247     SparseNameRange* SK_WARN_UNUSED_RESULT rotate() {
 248         SparseNameTree* newRoot = static_cast<SparseNameTree*>((this->*Tall).detach());
 249
 250         (this->*Tall).reset((newRoot->*Short).detach());
 251         this->updateStats();
 252
 253         (newRoot->*Short).reset(this->takeRef());
 254         newRoot->updateStats();
 255
 256         return newRoot;
 257     }
 258
 259     void updateStats() {
 260         SkASSERT(fLeft->end() < fRight->first()); // There must be a gap between left and right.
 261         fFirst = fLeft->first();
 262         fEnd = fRight->end();
 263         fHeight = 1 + SkMax32(fLeft->height(), fRight->height());
 264     }
 265
 266     SkAutoTUnref<SparseNameRange> fLeft;
 267     SkAutoTUnref<SparseNameRange> fRight;
 268 };
 269
 270 /**
 271  * This class is the SparseNameRange implementation for a leaf node. It just a
 272  * contiguous range of allocated names.
 273  */
 274 class GrGLNameAllocator::ContiguousNameRange : public SparseNameRange {
 275 public:
 276     ContiguousNameRange(GrGLuint first, GrGLuint end) {
 277         SkASSERT(first < end);
 278         fFirst = first;
 279         fEnd = end;
 280         fHeight = 0;
 281     }
 282
 283     SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) SK_OVERRIDE {
 284         *outName = 0; // No internal gaps, we are contiguous.
 285         return this->takeRef();
 286     }
 287
 288     SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuint* removedCount) SK_OVERRIDE {
 289         *removedCount = fEnd - fFirst;
 290         return NULL;
 291     }
 292
 293     GrGLuint appendNames(GrGLuint count) SK_OVERRIDE {
 294         SkASSERT(fEnd + count > fEnd); // Check for integer wrap.
 295         GrGLuint name = fEnd;
 296         fEnd += count;
 297         return name;
 298     }
 299
 300     GrGLuint prependNames(GrGLuint count) SK_OVERRIDE {
 301         SkASSERT(fFirst > count); // We can't allocate at or below 0.
 302         fFirst -= count;
 303         return fFirst;
 304     }
 305
 306     SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) SK_OVERRIDE {
 307         if (name < fFirst || name >= fEnd) {
 308           // Not-allocated names are silently ignored.
 309           return this->takeRef();
 310         }
 311
 312         if (fFirst == name) {
 313             ++fFirst;
 314             return (fEnd == fFirst) ? NULL : this->takeRef();
 315         }
 316
 317         if (fEnd == name + 1) {
 318             --fEnd;
 319             return this->takeRef();
 320         }
 321
 322         SparseNameRange* left = SkNEW_ARGS(ContiguousNameRange, (fFirst, name));
 323         SparseNameRange* right = this->takeRef();
 324         fFirst = name + 1;
 325         return SkNEW_ARGS(SparseNameTree, (left, right));
 326     }
 327 };
 328
 329 GrGLNameAllocator::GrGLNameAllocator(GrGLuint firstName, GrGLuint endName)
 330     : fFirstName(firstName),
 331       fEndName(endName) {
 332     SkASSERT(firstName > 0);
 333     SkASSERT(endName > firstName);
 334 }
 335
 336 GrGLNameAllocator::~GrGLNameAllocator() {
 337 }
 338
 339 GrGLuint GrGLNameAllocator::allocateName() {
 340     if (NULL == fAllocatedNames.get()) {
 341         fAllocatedNames.reset(SkNEW_ARGS(ContiguousNameRange, (fFirstName, fFirstName + 1)));
 342         return fFirstName;
 343     }
 344
 345     if (fAllocatedNames->first() > fFirstName) {
 346         return fAllocatedNames->prependNames(1);
 347     }
 348
 349     GrGLuint name;
 350     fAllocatedNames.reset(fAllocatedNames->internalAllocate(&name));
 351     if (0 != name) {
 352         return name;
 353     }
 354
 355     if (fAllocatedNames->end() < fEndName) {
 356         return fAllocatedNames->appendNames(1);
 357     }
 358
 359     // Out of names.
 360     return 0;
 361 }
 362
 363 void GrGLNameAllocator::free(GrGLuint name) {
 364     if (!fAllocatedNames.get()) {
 365       // Not-allocated names are silently ignored.
 366       return;
 367     }
 368
 369     fAllocatedNames.reset(fAllocatedNames->free(name));
 370 }