Home | History | Annotate | Download | only in core 
      1 
      2 /*
      3  * Copyright 2006 The Android Open Source Project
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 
     10 #ifndef SkTDStack_DEFINED
     11 #define SkTDStack_DEFINED
     12 
     13 #include "SkTypes.h"
     14 
     15 template <typename T> class SkTDStack : SkNoncopyable {
     16 public:
     17     SkTDStack() : fCount(0), fTotalCount(0) {
     18         fInitialRec.fNext = NULL;
     19         fRec = &fInitialRec;
     20 
     21     //  fCount = kSlotCount;
     22     }
     23 
     24     ~SkTDStack() {
     25         Rec* rec = fRec;
     26         while (rec != &fInitialRec) {
     27             Rec* next = rec->fNext;
     28             sk_free(rec);
     29             rec = next;
     30         }
     31     }
     32 
     33     int count() const { return fTotalCount; }
     34     int depth() const { return fTotalCount; }
     35     bool empty() const { return fTotalCount == 0; }
     36 
     37     T* push() {
     38         SkASSERT(fCount <= kSlotCount);
     39         if (fCount == kSlotCount) {
     40             Rec* rec = (Rec*)sk_malloc_throw(sizeof(Rec));
     41             rec->fNext = fRec;
     42             fRec = rec;
     43             fCount = 0;
     44         }
     45         ++fTotalCount;
     46         return &fRec->fSlots[fCount++];
     47     }
     48 
     49     void push(const T& elem) { *this->push() = elem; }
     50 
     51     const T& index(int idx) const {
     52         SkASSERT(fRec && fCount > idx);
     53         return fRec->fSlots[fCount - idx - 1];
     54     }
     55 
     56     T& index(int idx) {
     57         SkASSERT(fRec && fCount > idx);
     58         return fRec->fSlots[fCount - idx - 1];
     59     }
     60 
     61     const T& top() const {
     62         SkASSERT(fRec && fCount > 0);
     63         return fRec->fSlots[fCount - 1];
     64     }
     65 
     66     T& top() {
     67         SkASSERT(fRec && fCount > 0);
     68         return fRec->fSlots[fCount - 1];
     69     }
     70 
     71     void pop(T* elem) {
     72         if (elem) {
     73             *elem = fRec->fSlots[fCount - 1];
     74         }
     75         this->pop();
     76     }
     77 
     78     void pop() {
     79         SkASSERT(fCount > 0 && fRec);
     80         --fTotalCount;
     81         if (--fCount == 0) {
     82             if (fRec != &fInitialRec) {
     83                 Rec* rec = fRec->fNext;
     84                 sk_free(fRec);
     85                 fCount = kSlotCount;
     86                 fRec = rec;
     87             } else {
     88                 SkASSERT(fTotalCount == 0);
     89             }
     90         }
     91     }
     92 
     93 private:
     94     enum {
     95         kSlotCount  = 8
     96     };
     97 
     98     struct Rec;
     99     friend struct Rec;
    100 
    101     struct Rec {
    102         Rec* fNext;
    103         T    fSlots[kSlotCount];
    104     };
    105     Rec     fInitialRec;
    106     Rec*    fRec;
    107     int     fCount, fTotalCount;
    108 };
    109 
    110 #endif
    111