OLD | NEW |
(Empty) | |
| 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* ou
tName) = 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 virtual SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* ou
tName) 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 virtual 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 virtual 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 virtual 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 virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) SK_OVERRI
DE { |
| 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).g
et()); |
| 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).det
ach()); |
| 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 virtual SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* ou
tName) SK_OVERRIDE { |
| 284 *outName = 0; // No internal gaps, we are contiguous. |
| 285 return this->takeRef(); |
| 286 } |
| 287 |
| 288 virtual SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange
(GrGLuint* removedCount) SK_OVERRIDE { |
| 289 *removedCount = fEnd - fFirst; |
| 290 return NULL; |
| 291 } |
| 292 |
| 293 virtual 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 virtual 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 virtual SparseNameRange* SK_WARN_UNUSED_RESULT free(GrGLuint name) SK_OVERRI
DE { |
| 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, fFirs
tName + 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 } |
OLD | NEW |