1 2/* 3 * Copyright 2006 The Android Open Source Project 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 10#ifndef SkTDStack_DEFINED 11#define SkTDStack_DEFINED 12 13#include "SkTypes.h" 14 15template <typename T> class SkTDStack : SkNoncopyable { 16public: 17 SkTDStack() : fCount(0), fTotalCount(0) { 18 fInitialRec.fNext = NULL; 19 fRec = &fInitialRec; 20 21 // fCount = kSlotCount; 22 } 23 24 ~SkTDStack() { 25 Rec* rec = fRec; 26 while (rec != &fInitialRec) { 27 Rec* next = rec->fNext; 28 sk_free(rec); 29 rec = next; 30 } 31 } 32 33 int count() const { return fTotalCount; } 34 int depth() const { return fTotalCount; } 35 bool empty() const { return fTotalCount == 0; } 36 37 T* push() { 38 SkASSERT(fCount <= kSlotCount); 39 if (fCount == kSlotCount) { 40 Rec* rec = (Rec*)sk_malloc_throw(sizeof(Rec)); 41 rec->fNext = fRec; 42 fRec = rec; 43 fCount = 0; 44 } 45 ++fTotalCount; 46 return &fRec->fSlots[fCount++]; 47 } 48 49 void push(const T& elem) { *this->push() = elem; } 50 51 const T& index(int idx) const { 52 SkASSERT(fRec && fCount > idx); 53 return fRec->fSlots[fCount - idx - 1]; 54 } 55 56 T& index(int idx) { 57 SkASSERT(fRec && fCount > idx); 58 return fRec->fSlots[fCount - idx - 1]; 59 } 60 61 const T& top() const { 62 SkASSERT(fRec && fCount > 0); 63 return fRec->fSlots[fCount - 1]; 64 } 65 66 T& top() { 67 SkASSERT(fRec && fCount > 0); 68 return fRec->fSlots[fCount - 1]; 69 } 70 71 void pop(T* elem) { 72 if (elem) { 73 *elem = fRec->fSlots[fCount - 1]; 74 } 75 this->pop(); 76 } 77 78 void pop() { 79 SkASSERT(fCount > 0 && fRec); 80 --fTotalCount; 81 if (--fCount == 0) { 82 if (fRec != &fInitialRec) { 83 Rec* rec = fRec->fNext; 84 sk_free(fRec); 85 fCount = kSlotCount; 86 fRec = rec; 87 } else { 88 SkASSERT(fTotalCount == 0); 89 } 90 } 91 } 92 93private: 94 enum { 95 kSlotCount = 8 96 }; 97 98 struct Rec; 99 friend struct Rec; 100 101 struct Rec { 102 Rec* fNext; 103 T fSlots[kSlotCount]; 104 }; 105 Rec fInitialRec; 106 Rec* fRec; 107 int fCount, fTotalCount; 108}; 109 110#endif 111 112