1 /* 2 * Copyright (C) 2006 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef SkTDStack_DEFINED 18 #define SkTDStack_DEFINED 19 20 #include "SkTypes.h" 21 22 template <typename T> class SkTDStack : SkNoncopyable { 23 public: SkTDStack()24 SkTDStack() : fCount(0), fTotalCount(0) 25 { 26 fInitialRec.fNext = NULL; 27 fRec = &fInitialRec; 28 29 // fCount = kSlotCount; 30 } ~SkTDStack()31 ~SkTDStack() 32 { 33 Rec* rec = fRec; 34 while (rec != &fInitialRec) 35 { 36 Rec* next = rec->fNext; 37 sk_free(rec); 38 rec = next; 39 } 40 } 41 count()42 int count() const { return fTotalCount; } depth()43 int depth() const { return fTotalCount; } empty()44 bool empty() const { return fTotalCount == 0; } 45 push()46 T* push() 47 { 48 SkASSERT(fCount <= kSlotCount); 49 if (fCount == kSlotCount) 50 { 51 Rec* rec = (Rec*)sk_malloc_throw(sizeof(Rec)); 52 rec->fNext = fRec; 53 fRec = rec; 54 fCount = 0; 55 } 56 ++fTotalCount; 57 return &fRec->fSlots[fCount++]; 58 } push(const T & elem)59 void push(const T& elem) { *this->push() = elem; } index(int idx)60 const T& index(int idx) const 61 { 62 SkASSERT(fRec && fCount > idx); 63 return fRec->fSlots[fCount - idx - 1]; 64 } index(int idx)65 T& index(int idx) 66 { 67 SkASSERT(fRec && fCount > idx); 68 return fRec->fSlots[fCount - idx - 1]; 69 } top()70 const T& top() const 71 { 72 SkASSERT(fRec && fCount > 0); 73 return fRec->fSlots[fCount - 1]; 74 } top()75 T& top() 76 { 77 SkASSERT(fRec && fCount > 0); 78 return fRec->fSlots[fCount - 1]; 79 } pop(T * elem)80 void pop(T* elem) 81 { 82 if (elem) 83 *elem = fRec->fSlots[fCount - 1]; 84 this->pop(); 85 } pop()86 void pop() 87 { 88 SkASSERT(fCount > 0 && fRec); 89 --fTotalCount; 90 if (--fCount == 0) 91 { 92 if (fRec != &fInitialRec) 93 { 94 Rec* rec = fRec->fNext; 95 sk_free(fRec); 96 fCount = kSlotCount; 97 fRec = rec; 98 } 99 else 100 SkASSERT(fTotalCount == 0); 101 } 102 } 103 104 private: 105 enum { 106 kSlotCount = 8 107 }; 108 109 struct Rec; 110 friend struct Rec; 111 112 struct Rec { 113 Rec* fNext; 114 T fSlots[kSlotCount]; 115 }; 116 Rec fInitialRec; 117 Rec* fRec; 118 int fCount, fTotalCount; 119 }; 120 121 #endif 122 123