OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2013 Google Inc. | 2 * Copyright 2013 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #ifndef SkTDStackNester_DEFINED | 8 #ifndef SkTDStackNester_DEFINED |
9 #define SkTDStackNester_DEFINED | 9 #define SkTDStackNester_DEFINED |
10 | 10 |
11 #include "SkTypes.h" | 11 #include "SkTypes.h" |
| 12 #include "SkPdfReporter.h" |
12 | 13 |
13 // Adobe limits it to 28, so 256 should be more than enough | 14 // Adobe limits it to 28. Allow deeper nesting in case a file does not quite mee
t the |
| 15 // spec. 256 should be more than enough. |
14 #define MAX_NESTING 256 | 16 #define MAX_NESTING 256 |
15 | 17 |
16 /** \class SkTDStackNester | 18 /** \class SkTDStackNester |
17 * | 19 * |
| 20 * Specialized version of SkTDStack which allows a stack of stacks. |
| 21 * FIXME (scroggo): Could this be a subclass of SkTDStack? Could it have-a SkTDS
tack? |
18 * The difference between SkTDStackNester and SkTDStack is that: | 22 * The difference between SkTDStackNester and SkTDStack is that: |
19 * - SkTDStackNester uses new/delete to manage initializations | 23 * - SkTDStackNester uses new/delete to manage initializations |
| 24 * FIXME (scroggo): Why use new rather than malloc? |
20 * - Supports nest/unnest which simulates a stack of stack. unnest will pop al
l the | 25 * - Supports nest/unnest which simulates a stack of stack. unnest will pop al
l the |
21 * objects pushed since the last nest | 26 * objects pushed since the last nest |
| 27 * - kSlotCount is 64, instead of 8. |
| 28 * FIXME (scroggo): How did we arrive at this number? |
22 */ | 29 */ |
23 | 30 |
24 template <typename T> class SkTDStackNester : SkNoncopyable { | 31 template <typename T> class SkTDStackNester : SkNoncopyable { |
25 public: | 32 public: |
26 SkTDStackNester() : fCount(0), fTotalCount(0), fLocalCount(0) { | 33 SkTDStackNester() |
| 34 : fCount(0) |
| 35 , fLocalCount(0) |
| 36 , fNestingLevel(0) { |
27 fInitialRec.fNext = NULL; | 37 fInitialRec.fNext = NULL; |
28 fRec = &fInitialRec; | 38 fRec = &fInitialRec; |
29 | 39 SkDEBUGCODE(fTotalCount = 0;) |
30 // fCount = kSlotCount; | |
31 } | 40 } |
32 | 41 |
33 ~SkTDStackNester() { | 42 ~SkTDStackNester() { |
34 Rec* rec = fRec; | 43 Rec* rec = fRec; |
35 while (rec != &fInitialRec) { | 44 while (rec != &fInitialRec) { |
36 Rec* next = rec->fNext; | 45 Rec* next = rec->fNext; |
37 delete rec; | 46 delete rec; |
38 rec = next; | 47 rec = next; |
39 } | 48 } |
40 } | 49 } |
41 | 50 |
| 51 /** |
| 52 * Return the number of objects in the current nesting level. |
| 53 */ |
42 int count() const { return fLocalCount; } | 54 int count() const { return fLocalCount; } |
| 55 |
| 56 /** |
| 57 * Whether the current nesting level is empty. |
| 58 */ |
43 bool empty() const { return fLocalCount == 0; } | 59 bool empty() const { return fLocalCount == 0; } |
44 | 60 |
45 int nests() { | 61 /** |
| 62 * The current nesting level. |
| 63 */ |
| 64 int nestingLevel() const { |
46 return fNestingLevel; | 65 return fNestingLevel; |
47 } | 66 } |
48 | 67 |
| 68 /** |
| 69 * Analogous to an SkCanvas::save(). When unnest() is called, the state of t
his SkTDStackNester |
| 70 * will return to its state when nest() was called. |
| 71 * |
| 72 * After a call to nest(), fLocalCount is reset to 0, since the stack is on
a new nesting |
| 73 * level. |
| 74 */ |
49 void nest() { | 75 void nest() { |
50 // We are are past max nesting levels, we will still continue to work, b
ut we might fail | 76 SkASSERT(fNestingLevel >= 0); |
51 // to properly ignore errors. Ideally it should only mean poor rendering
in exceptional | 77 if (fNestingLevel < MAX_NESTING) { |
52 // cases | |
53 if (fNestingLevel >= 0 && fNestingLevel < MAX_NESTING) { | |
54 fNestings[fNestingLevel] = fLocalCount; | 78 fNestings[fNestingLevel] = fLocalCount; |
55 fLocalCount = 0; | 79 fLocalCount = 0; |
| 80 } else { |
| 81 // We are are past max nesting levels. We will still continue to wor
k, but we might fail |
| 82 // to properly ignore errors. Ideally it should only mean poor rende
ring in exceptional |
| 83 // cases. |
| 84 SkPdfReport(kWarning_SkPdfIssueSeverity, kStackNestingOverflow_SkPdf
Issue, |
| 85 "Past maximum nesting level", NULL, NULL); |
56 } | 86 } |
57 fNestingLevel++; | 87 fNestingLevel++; |
58 } | 88 } |
59 | 89 |
| 90 /** |
| 91 * Analagous to an SkCanvas::restore(). Will revert this stack to the state
it was in the last |
| 92 * time nest() was called. It is an error to call unnest() more times than n
est() has been |
| 93 * called. |
| 94 */ |
60 void unnest() { | 95 void unnest() { |
61 SkASSERT(fNestingLevel > 0); | 96 SkASSERT(fNestingLevel >= 0); |
| 97 if (0 == fNestingLevel) { |
| 98 SkPdfReport(kWarning_SkPdfIssueSeverity, kStackNestingOverflow_SkPdf
Issue, |
| 99 "Nesting underflow", NULL, NULL); |
| 100 return; |
| 101 } |
| 102 |
62 fNestingLevel--; | 103 fNestingLevel--; |
63 if (fNestingLevel >= 0 && fNestingLevel < MAX_NESTING) { | 104 if (fNestingLevel < MAX_NESTING) { |
64 // TODO(edisonn): warn if fLocal > 0 | |
65 while (fLocalCount > 0) { | 105 while (fLocalCount > 0) { |
66 pop(); | 106 // FIXME (scroggo): Pass the object? |
| 107 SkPdfReport(kInfo_SkPdfIssueSeverity, kUnusedObject_SkPdfIssue, |
| 108 "Unused object when calling unnest!", NULL, NULL); |
| 109 this->pop(); |
67 } | 110 } |
68 fLocalCount = fNestings[fNestingLevel]; | 111 fLocalCount = fNestings[fNestingLevel]; |
69 } | 112 } |
70 } | 113 } |
71 | 114 |
| 115 /** |
| 116 * Add an object to the stack, and return a pointer to it for modification. |
| 117 */ |
72 T* push() { | 118 T* push() { |
73 SkASSERT(fCount <= kSlotCount); | 119 SkASSERT(fCount <= kSlotCount); |
74 if (fCount == kSlotCount) { | 120 if (fCount == kSlotCount) { |
75 Rec* rec = new Rec(); | 121 Rec* rec = new Rec(); |
76 rec->fNext = fRec; | 122 rec->fNext = fRec; |
77 fRec = rec; | 123 fRec = rec; |
78 fCount = 0; | 124 fCount = 0; |
79 } | 125 } |
80 ++fTotalCount; | 126 SkDEBUGCODE(++fTotalCount;) |
81 ++fLocalCount; | 127 ++fLocalCount; |
82 return &fRec->fSlots[fCount++]; | 128 return &fRec->fSlots[fCount++]; |
83 } | 129 } |
84 | 130 |
| 131 /** |
| 132 * Add an object to the stack, copied from elem. |
| 133 */ |
85 void push(const T& elem) { *this->push() = elem; } | 134 void push(const T& elem) { *this->push() = elem; } |
86 | 135 |
87 const T& index(int idx) const { | 136 /** |
88 SkASSERT(fRec && fCount > idx); | 137 * Return the top element. |
89 return fRec->fSlots[fCount - idx - 1]; | 138 */ |
90 } | |
91 | |
92 T& index(int idx) { | |
93 SkASSERT(fRec && fCount > idx); | |
94 return fRec->fSlots[fCount - idx - 1]; | |
95 } | |
96 | |
97 const T& top() const { | 139 const T& top() const { |
98 SkASSERT(fRec && fCount > 0); | 140 SkASSERT(fRec && fCount > 0); |
99 return fRec->fSlots[fCount - 1]; | 141 return fRec->fSlots[fCount - 1]; |
100 } | 142 } |
101 | 143 |
| 144 /** |
| 145 * Return the top element. |
| 146 */ |
102 T& top() { | 147 T& top() { |
103 SkASSERT(fRec && fCount > 0); | 148 SkASSERT(fRec && fCount > 0); |
104 return fRec->fSlots[fCount - 1]; | 149 return fRec->fSlots[fCount - 1]; |
105 } | 150 } |
106 | 151 |
| 152 /** |
| 153 * Pop an object off the stack (via pop()), and copy its members into elem. |
| 154 */ |
107 void pop(T* elem) { | 155 void pop(T* elem) { |
108 if (elem) { | 156 if (elem) { |
109 *elem = fRec->fSlots[fCount - 1]; | 157 *elem = fRec->fSlots[fCount - 1]; |
110 } | 158 } |
111 this->pop(); | 159 this->pop(); |
112 } | 160 } |
113 | 161 |
| 162 /** |
| 163 * Pop an object off the stack. It is an error to call pop() more times |
| 164 * than push() has been called in total or since the last call to nest(). |
| 165 */ |
114 void pop() { | 166 void pop() { |
115 SkASSERT(fCount > 0 && fRec); | 167 SkASSERT(fCount > 0 && fRec); |
| 168 SkASSERT(fLocalCount > 0); |
116 --fLocalCount; | 169 --fLocalCount; |
117 --fTotalCount; | 170 SkDEBUGCODE(--fTotalCount;) |
118 if (--fCount == 0) { | 171 if (--fCount == 0) { |
119 if (fRec != &fInitialRec) { | 172 if (fRec != &fInitialRec) { |
120 Rec* rec = fRec->fNext; | 173 Rec* rec = fRec->fNext; |
121 delete fRec; | 174 delete fRec; |
122 fCount = kSlotCount; | 175 fCount = kSlotCount; |
123 fRec = rec; | 176 fRec = rec; |
124 } else { | 177 } else { |
125 SkASSERT(fTotalCount == 0); | 178 SkASSERT(fTotalCount == 0); |
126 } | 179 } |
127 } | 180 } |
128 } | 181 } |
129 | 182 |
130 private: | 183 private: |
131 enum { | 184 enum { |
| 185 // Number of objects held per Rec. Storing multiple objects in one Rec |
| 186 // means that we call new less often. |
132 kSlotCount = 64 | 187 kSlotCount = 64 |
133 }; | 188 }; |
134 | 189 |
135 struct Rec; | |
136 friend struct Rec; | |
137 | |
138 struct Rec { | 190 struct Rec { |
139 Rec* fNext; | 191 Rec* fNext; |
140 T fSlots[kSlotCount]; | 192 T fSlots[kSlotCount]; |
141 }; | 193 }; |
| 194 |
| 195 // First Rec, requiring no allocation. |
142 Rec fInitialRec; | 196 Rec fInitialRec; |
| 197 // The Rec on top of the stack. |
143 Rec* fRec; | 198 Rec* fRec; |
144 int fCount, fTotalCount, fLocalCount; | 199 // Number of objects in fRec. |
| 200 int fCount; |
| 201 // Number of objects in the current nesting level. |
| 202 int fLocalCount; |
| 203 // Array of counts of objects per nesting level. |
| 204 // Only valid for fNestings[0] through fNestings[fNestingLevel-1]. |
145 int fNestings[MAX_NESTING]; | 205 int fNestings[MAX_NESTING]; |
| 206 // Current nesting level. |
146 int fNestingLevel; | 207 int fNestingLevel; |
| 208 // Total number of objects in this SkTDStackNester. |
| 209 SkDEBUGCODE(int fTotalCount;) |
| 210 |
| 211 // For testing. |
| 212 friend class SkTDStackNesterTester; |
147 }; | 213 }; |
148 #endif // SkTDStackNester_DEFINED | 214 #endif // SkTDStackNester_DEFINED |
OLD | NEW |