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 
15 template <typename T> class SkTDStack : SkNoncopyable {
16 public:
SkTDStack()17     SkTDStack() : fCount(0), fTotalCount(0) {
18         fInitialRec.fNext = NULL;
19         fRec = &fInitialRec;
20 
21     //  fCount = kSlotCount;
22     }
23 
~SkTDStack()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 
count()33     int count() const { return fTotalCount; }
depth()34     int depth() const { return fTotalCount; }
empty()35     bool empty() const { return fTotalCount == 0; }
36 
push()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 
push(const T & elem)49     void push(const T& elem) { *this->push() = elem; }
50 
index(int idx)51     const T& index(int idx) const {
52         SkASSERT(fRec && fCount > idx);
53         return fRec->fSlots[fCount - idx - 1];
54     }
55 
index(int idx)56     T& index(int idx) {
57         SkASSERT(fRec && fCount > idx);
58         return fRec->fSlots[fCount - idx - 1];
59     }
60 
top()61     const T& top() const {
62         SkASSERT(fRec && fCount > 0);
63         return fRec->fSlots[fCount - 1];
64     }
65 
top()66     T& top() {
67         SkASSERT(fRec && fCount > 0);
68         return fRec->fSlots[fCount - 1];
69     }
70 
pop(T * elem)71     void pop(T* elem) {
72         if (elem) {
73             *elem = fRec->fSlots[fCount - 1];
74         }
75         this->pop();
76     }
77 
pop()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 
93 private:
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