michael@0: 
michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #ifndef SkTDStack_DEFINED
michael@0: #define SkTDStack_DEFINED
michael@0: 
michael@0: #include "SkTypes.h"
michael@0: 
michael@0: template <typename T> class SkTDStack : SkNoncopyable {
michael@0: public:
michael@0:     SkTDStack() : fCount(0), fTotalCount(0) {
michael@0:         fInitialRec.fNext = NULL;
michael@0:         fRec = &fInitialRec;
michael@0: 
michael@0:     //  fCount = kSlotCount;
michael@0:     }
michael@0: 
michael@0:     ~SkTDStack() {
michael@0:         Rec* rec = fRec;
michael@0:         while (rec != &fInitialRec) {
michael@0:             Rec* next = rec->fNext;
michael@0:             sk_free(rec);
michael@0:             rec = next;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     int count() const { return fTotalCount; }
michael@0:     int depth() const { return fTotalCount; }
michael@0:     bool empty() const { return fTotalCount == 0; }
michael@0: 
michael@0:     T* push() {
michael@0:         SkASSERT(fCount <= kSlotCount);
michael@0:         if (fCount == kSlotCount) {
michael@0:             Rec* rec = (Rec*)sk_malloc_throw(sizeof(Rec));
michael@0:             rec->fNext = fRec;
michael@0:             fRec = rec;
michael@0:             fCount = 0;
michael@0:         }
michael@0:         ++fTotalCount;
michael@0:         return &fRec->fSlots[fCount++];
michael@0:     }
michael@0: 
michael@0:     void push(const T& elem) { *this->push() = elem; }
michael@0: 
michael@0:     const T& index(int idx) const {
michael@0:         SkASSERT(fRec && fCount > idx);
michael@0:         return fRec->fSlots[fCount - idx - 1];
michael@0:     }
michael@0: 
michael@0:     T& index(int idx) {
michael@0:         SkASSERT(fRec && fCount > idx);
michael@0:         return fRec->fSlots[fCount - idx - 1];
michael@0:     }
michael@0: 
michael@0:     const T& top() const {
michael@0:         SkASSERT(fRec && fCount > 0);
michael@0:         return fRec->fSlots[fCount - 1];
michael@0:     }
michael@0: 
michael@0:     T& top() {
michael@0:         SkASSERT(fRec && fCount > 0);
michael@0:         return fRec->fSlots[fCount - 1];
michael@0:     }
michael@0: 
michael@0:     void pop(T* elem) {
michael@0:         if (elem) {
michael@0:             *elem = fRec->fSlots[fCount - 1];
michael@0:         }
michael@0:         this->pop();
michael@0:     }
michael@0: 
michael@0:     void pop() {
michael@0:         SkASSERT(fCount > 0 && fRec);
michael@0:         --fTotalCount;
michael@0:         if (--fCount == 0) {
michael@0:             if (fRec != &fInitialRec) {
michael@0:                 Rec* rec = fRec->fNext;
michael@0:                 sk_free(fRec);
michael@0:                 fCount = kSlotCount;
michael@0:                 fRec = rec;
michael@0:             } else {
michael@0:                 SkASSERT(fTotalCount == 0);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     enum {
michael@0:         kSlotCount  = 8
michael@0:     };
michael@0: 
michael@0:     struct Rec;
michael@0:     friend struct Rec;
michael@0: 
michael@0:     struct Rec {
michael@0:         Rec* fNext;
michael@0:         T    fSlots[kSlotCount];
michael@0:     };
michael@0:     Rec     fInitialRec;
michael@0:     Rec*    fRec;
michael@0:     int     fCount, fTotalCount;
michael@0: };
michael@0: 
michael@0: #endif