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
31template <typename T> class SkTDStackNester : SkNoncopyable {
32public:
33    SkTDStackNester()
34        : fCount(0)
35        , fLocalCount(0)
36        , fNestingLevel(0) {
37        fInitialRec.fNext = NULL;
38        fRec = &fInitialRec;
39        SkDEBUGCODE(fTotalCount = 0;)
40    }
41
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     */
54    int count() const { return fLocalCount; }
55
56    /**
57     * Whether the current nesting level is empty.
58     */
59    bool empty() const { return fLocalCount == 0; }
60
61    /**
62     * The current nesting level.
63     */
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     */
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     */
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     */
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     */
134    void push(const T& elem) { *this->push() = elem; }
135
136    /**
137     * Return the top element.
138     */
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     */
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     */
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     */
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
183private:
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