| 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 nullptr 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 nullptr 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) o
verride { | |
| 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 (nullptr == 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(GrGLuin
t* removedCount) override { | |
| 164 fLeft.reset(fLeft->removeLeftmostContiguousRange(removedCount)); | |
| 165 if (nullptr == fLeft) { | |
| 166 return fRight.detach(); | |
| 167 } | |
| 168 this->updateStats(); | |
| 169 return this->rebalance(); | |
| 170 } | |
| 171 | |
| 172 GrGLuint appendNames(GrGLuint count) 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) 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) override { | |
| 189 if (name < fLeft->end()) { | |
| 190 fLeft.reset(fLeft->free(name)); | |
| 191 if (nullptr == 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 (nullptr == 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 SparseNameRange* SK_WARN_UNUSED_RESULT internalAllocate(GrGLuint* outName) o
verride { | |
| 284 *outName = 0; // No internal gaps, we are contiguous. | |
| 285 return this->takeRef(); | |
| 286 } | |
| 287 | |
| 288 SparseNameRange* SK_WARN_UNUSED_RESULT removeLeftmostContiguousRange(GrGLuin
t* removedCount) override { | |
| 289 *removedCount = fEnd - fFirst; | |
| 290 return nullptr; | |
| 291 } | |
| 292 | |
| 293 GrGLuint appendNames(GrGLuint count) 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) 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) 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) ? nullptr : this->takeRef(); | |
| 315 } | |
| 316 | |
| 317 if (fEnd == name + 1) { | |
| 318 --fEnd; | |
| 319 return this->takeRef(); | |
| 320 } | |
| 321 | |
| 322 SparseNameRange* left = new ContiguousNameRange(fFirst, name); | |
| 323 SparseNameRange* right = this->takeRef(); | |
| 324 fFirst = name + 1; | |
| 325 return new 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 (nullptr == fAllocatedNames.get()) { | |
| 341 fAllocatedNames.reset(new 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 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1150243003:
Simplify path allocation, clean up resources correctly (Closed)
Base URL: https://skia.googlesource.com/skia.git@master