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