10daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com/* 20daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * Copyright 2013 Google Inc. 30daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * 40daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * Use of this source code is governed by a BSD-style license that can be 50daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * found in the LICENSE file. 60daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com */ 70daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 80daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com#ifndef SkTDStackNester_DEFINED 90daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com#define SkTDStackNester_DEFINED 100daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 110daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com#include "SkTypes.h" 127d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com#include "SkPdfReporter.h" 130daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 147d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com// Adobe limits it to 28. Allow deeper nesting in case a file does not quite meet the 157d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com// spec. 256 should be more than enough. 160daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com#define MAX_NESTING 256 170daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 180daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com/** \class SkTDStackNester 190daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * 207d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Specialized version of SkTDStack which allows a stack of stacks. 217d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * FIXME (scroggo): Could this be a subclass of SkTDStack? Could it have-a SkTDStack? 220daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * The difference between SkTDStackNester and SkTDStack is that: 230daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * - SkTDStackNester uses new/delete to manage initializations 247d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * FIXME (scroggo): Why use new rather than malloc? 250daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * - Supports nest/unnest which simulates a stack of stack. unnest will pop all the 260daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com * objects pushed since the last nest 277d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * - kSlotCount is 64, instead of 8. 287d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * FIXME (scroggo): How did we arrive at this number? 290daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com */ 300daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 310daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.comtemplate <typename T> class SkTDStackNester : SkNoncopyable { 320daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.compublic: 337d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkTDStackNester() 347d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com : fCount(0) 357d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com , fLocalCount(0) 367d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com , fNestingLevel(0) { 370daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fInitialRec.fNext = NULL; 380daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fRec = &fInitialRec; 397d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkDEBUGCODE(fTotalCount = 0;) 400daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 410daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 420daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com ~SkTDStackNester() { 430daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com Rec* rec = fRec; 440daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com while (rec != &fInitialRec) { 450daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com Rec* next = rec->fNext; 460daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com delete rec; 470daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com rec = next; 480daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 490daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 500daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 517d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 527d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Return the number of objects in the current nesting level. 537d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 540daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com int count() const { return fLocalCount; } 557d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com 567d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 577d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Whether the current nesting level is empty. 587d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 590daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com bool empty() const { return fLocalCount == 0; } 600daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 617d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 627d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * The current nesting level. 637d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 647d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com int nestingLevel() const { 650daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com return fNestingLevel; 660daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 670daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 687d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 697d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Analogous to an SkCanvas::save(). When unnest() is called, the state of this SkTDStackNester 707d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * will return to its state when nest() was called. 717d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * 727d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * After a call to nest(), fLocalCount is reset to 0, since the stack is on a new nesting 737d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * level. 747d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 750daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com void nest() { 767d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkASSERT(fNestingLevel >= 0); 777d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com if (fNestingLevel < MAX_NESTING) { 780daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fNestings[fNestingLevel] = fLocalCount; 790daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fLocalCount = 0; 807d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com } else { 817d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // We are are past max nesting levels. We will still continue to work, but we might fail 827d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // to properly ignore errors. Ideally it should only mean poor rendering in exceptional 837d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // cases. 847d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkPdfReport(kWarning_SkPdfIssueSeverity, kStackNestingOverflow_SkPdfIssue, 857d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com "Past maximum nesting level", NULL, NULL); 860daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 870daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fNestingLevel++; 880daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 890daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 907d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 917d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Analagous to an SkCanvas::restore(). Will revert this stack to the state it was in the last 927d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * time nest() was called. It is an error to call unnest() more times than nest() has been 937d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * called. 947d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 950daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com void unnest() { 967d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkASSERT(fNestingLevel >= 0); 977d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com if (0 == fNestingLevel) { 987d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkPdfReport(kWarning_SkPdfIssueSeverity, kStackNestingOverflow_SkPdfIssue, 997d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com "Nesting underflow", NULL, NULL); 1007d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com return; 1017d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com } 1027d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com 1030daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fNestingLevel--; 1047d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com if (fNestingLevel < MAX_NESTING) { 1050daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com while (fLocalCount > 0) { 1067d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // FIXME (scroggo): Pass the object? 1077d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkPdfReport(kInfo_SkPdfIssueSeverity, kUnusedObject_SkPdfIssue, 1087d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com "Unused object when calling unnest!", NULL, NULL); 1097d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com this->pop(); 1100daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1110daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fLocalCount = fNestings[fNestingLevel]; 1120daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1130daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1140daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 1157d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 1167d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Add an object to the stack, and return a pointer to it for modification. 1177d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 1180daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com T* push() { 1190daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com SkASSERT(fCount <= kSlotCount); 1200daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com if (fCount == kSlotCount) { 1210daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com Rec* rec = new Rec(); 1220daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com rec->fNext = fRec; 1230daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fRec = rec; 1240daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fCount = 0; 1250daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1267d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkDEBUGCODE(++fTotalCount;) 1270daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com ++fLocalCount; 1280daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com return &fRec->fSlots[fCount++]; 1290daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1300daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 1317d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 1327d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Add an object to the stack, copied from elem. 1337d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 1340daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com void push(const T& elem) { *this->push() = elem; } 1350daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 1367d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 1377d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Return the top element. 1387d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 1390daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com const T& top() const { 1400daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com SkASSERT(fRec && fCount > 0); 1410daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com return fRec->fSlots[fCount - 1]; 1420daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1430daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 1447d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 1457d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Return the top element. 1467d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 1470daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com T& top() { 1480daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com SkASSERT(fRec && fCount > 0); 1490daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com return fRec->fSlots[fCount - 1]; 1500daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1510daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 1527d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 1537d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Pop an object off the stack (via pop()), and copy its members into elem. 1547d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 1550daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com void pop(T* elem) { 1560daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com if (elem) { 1570daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com *elem = fRec->fSlots[fCount - 1]; 1580daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1590daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com this->pop(); 1600daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1610daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 1627d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com /** 1637d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * Pop an object off the stack. It is an error to call pop() more times 1647d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com * than push() has been called in total or since the last call to nest(). 1657d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com */ 1660daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com void pop() { 1670daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com SkASSERT(fCount > 0 && fRec); 1687d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkASSERT(fLocalCount > 0); 1690daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com --fLocalCount; 1707d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkDEBUGCODE(--fTotalCount;) 1710daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com if (--fCount == 0) { 1720daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com if (fRec != &fInitialRec) { 1730daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com Rec* rec = fRec->fNext; 1740daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com delete fRec; 1750daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fCount = kSlotCount; 1760daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com fRec = rec; 1770daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } else { 1780daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com SkASSERT(fTotalCount == 0); 1790daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1800daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1810daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com } 1820daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 1830daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.comprivate: 1840daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com enum { 1857d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // Number of objects held per Rec. Storing multiple objects in one Rec 1867d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // means that we call new less often. 1870daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com kSlotCount = 64 1880daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com }; 1890daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com 1900daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com struct Rec { 1910daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com Rec* fNext; 1920daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com T fSlots[kSlotCount]; 1930daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com }; 1947d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com 1957d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // First Rec, requiring no allocation. 1960daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com Rec fInitialRec; 1977d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // The Rec on top of the stack. 1980daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com Rec* fRec; 1997d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // Number of objects in fRec. 2007d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com int fCount; 2017d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // Number of objects in the current nesting level. 2027d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com int fLocalCount; 2037d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // Array of counts of objects per nesting level. 2047d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // Only valid for fNestings[0] through fNestings[fNestingLevel-1]. 2050daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com int fNestings[MAX_NESTING]; 2067d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // Current nesting level. 2070daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com int fNestingLevel; 2087d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // Total number of objects in this SkTDStackNester. 2097d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com SkDEBUGCODE(int fTotalCount;) 2107d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com 2117d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com // For testing. 2127d8013f3064cd202f5a2344a1ab1860fd7511bb3scroggo@google.com friend class SkTDStackNesterTester; 2130daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com}; 2140daf00ccd742a84d73f370ced0f507f5094937b5scroggo@google.com#endif // SkTDStackNester_DEFINED 215