180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SkTDStack_DEFINED 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkTDStack_DEFINED 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTypes.h" 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querutemplate <typename T> class SkTDStack : SkNoncopyable { 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTDStack() : fCount(0), fTotalCount(0) { 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fInitialRec.fNext = NULL; 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fRec = &fInitialRec; 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // fCount = kSlotCount; 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ~SkTDStack() { 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Rec* rec = fRec; 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (rec != &fInitialRec) { 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Rec* next = rec->fNext; 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru sk_free(rec); 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru rec = next; 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count() const { return fTotalCount; } 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int depth() const { return fTotalCount; } 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool empty() const { return fTotalCount == 0; } 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru T* push() { 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCount <= kSlotCount); 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fCount == kSlotCount) { 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Rec* rec = (Rec*)sk_malloc_throw(sizeof(Rec)); 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru rec->fNext = fRec; 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fRec = rec; 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCount = 0; 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ++fTotalCount; 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return &fRec->fSlots[fCount++]; 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void push(const T& elem) { *this->push() = elem; } 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const T& index(int idx) const { 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fRec && fCount > idx); 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return fRec->fSlots[fCount - idx - 1]; 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru T& index(int idx) { 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fRec && fCount > idx); 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return fRec->fSlots[fCount - idx - 1]; 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const T& top() const { 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fRec && fCount > 0); 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return fRec->fSlots[fCount - 1]; 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru T& top() { 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fRec && fCount > 0); 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return fRec->fSlots[fCount - 1]; 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void pop(T* elem) { 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (elem) { 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *elem = fRec->fSlots[fCount - 1]; 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->pop(); 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void pop() { 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCount > 0 && fRec); 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru --fTotalCount; 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (--fCount == 0) { 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fRec != &fInitialRec) { 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Rec* rec = fRec->fNext; 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru sk_free(fRec); 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCount = kSlotCount; 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fRec = rec; 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fTotalCount == 0); 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru enum { 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru kSlotCount = 8 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru struct Rec; 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru friend struct Rec; 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru struct Rec { 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Rec* fNext; 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru T fSlots[kSlotCount]; 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Rec fInitialRec; 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Rec* fRec; 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int fCount, fTotalCount; 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 111