00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef SkTDStack_DEFINED
00018 #define SkTDStack_DEFINED
00019
00020 #include "SkTypes.h"
00021
00022 template <typename T> class SkTDStack : SkNoncopyable {
00023 public:
00024 SkTDStack() : fCount(0), fTotalCount(0)
00025 {
00026 fInitialRec.fNext = NULL;
00027 fRec = &fInitialRec;
00028
00029
00030 }
00031 ~SkTDStack()
00032 {
00033 Rec* rec = fRec;
00034 while (rec != &fInitialRec)
00035 {
00036 Rec* next = rec->fNext;
00037 sk_free(rec);
00038 rec = next;
00039 }
00040 }
00041
00042 int count() const { return fTotalCount; }
00043 int depth() const { return fTotalCount; }
00044 bool empty() const { return fTotalCount == 0; }
00045
00046 T* push()
00047 {
00048 SkASSERT(fCount <= kSlotCount);
00049 if (fCount == kSlotCount)
00050 {
00051 Rec* rec = (Rec*)sk_malloc_throw(sizeof(Rec));
00052 rec->fNext = fRec;
00053 fRec = rec;
00054 fCount = 0;
00055 }
00056 ++fTotalCount;
00057 return &fRec->fSlots[fCount++];
00058 }
00059 void push(const T& elem) { *this->push() = elem; }
00060 const T& index(int idx) const
00061 {
00062 SkASSERT(fRec && fCount > idx);
00063 return fRec->fSlots[fCount - idx - 1];
00064 }
00065 T& index(int idx)
00066 {
00067 SkASSERT(fRec && fCount > idx);
00068 return fRec->fSlots[fCount - idx - 1];
00069 }
00070 const T& top() const
00071 {
00072 SkASSERT(fRec && fCount > 0);
00073 return fRec->fSlots[fCount - 1];
00074 }
00075 T& top()
00076 {
00077 SkASSERT(fRec && fCount > 0);
00078 return fRec->fSlots[fCount - 1];
00079 }
00080 void pop(T* elem)
00081 {
00082 if (elem)
00083 *elem = fRec->fSlots[fCount - 1];
00084 this->pop();
00085 }
00086 void pop()
00087 {
00088 SkASSERT(fCount > 0 && fRec);
00089 --fTotalCount;
00090 if (--fCount == 0)
00091 {
00092 if (fRec != &fInitialRec)
00093 {
00094 Rec* rec = fRec->fNext;
00095 sk_free(fRec);
00096 fCount = kSlotCount;
00097 fRec = rec;
00098 }
00099 else
00100 SkASSERT(fTotalCount == 0);
00101 }
00102 }
00103
00104 private:
00105 enum {
00106 kSlotCount = 8
00107 };
00108
00109 struct Rec;
00110 friend struct Rec;
00111
00112 struct Rec {
00113 Rec* fNext;
00114 T fSlots[kSlotCount];
00115 };
00116 Rec fInitialRec;
00117 Rec* fRec;
00118 int fCount, fTotalCount;
00119 };
00120
00121 #endif
00122