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
15template <typename T> class SkTDStack : SkNoncopyable {
16public:
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
93private:
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