1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SkTDStack_DEFINED 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkTDStack_DEFINED 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTypes.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comtemplate <typename T> class SkTDStack : SkNoncopyable { 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.compublic: 17ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com SkTDStack() : fCount(0), fTotalCount(0) { 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fInitialRec.fNext = NULL; 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fRec = &fInitialRec; 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // fCount = kSlotCount; 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 23ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com 24ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com ~SkTDStack() { 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Rec* rec = fRec; 26ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com while (rec != &fInitialRec) { 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Rec* next = rec->fNext; 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(rec); 298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com rec = next; 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count() const { return fTotalCount; } 3419a89f287f3af6fd34470a7aab92a989109d513freed@android.com int depth() const { return fTotalCount; } 3519a89f287f3af6fd34470a7aab92a989109d513freed@android.com bool empty() const { return fTotalCount == 0; } 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 37ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com T* push() { 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCount <= kSlotCount); 39ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com if (fCount == kSlotCount) { 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Rec* rec = (Rec*)sk_malloc_throw(sizeof(Rec)); 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com rec->fNext = fRec; 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fRec = rec; 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = 0; 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ++fTotalCount; 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return &fRec->fSlots[fCount++]; 478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 48ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void push(const T& elem) { *this->push() = elem; } 50ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com 51ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com const T& index(int idx) const { 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fRec && fCount > idx); 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fRec->fSlots[fCount - idx - 1]; 54ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com } 55ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com 56ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com T& index(int idx) { 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fRec && fCount > idx); 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fRec->fSlots[fCount - idx - 1]; 59ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com } 60ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com 61ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com const T& top() const { 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fRec && fCount > 0); 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fRec->fSlots[fCount - 1]; 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 65ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com 66ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com T& top() { 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fRec && fCount > 0); 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fRec->fSlots[fCount - 1]; 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 70ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com 71ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com void pop(T* elem) { 72ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com if (elem) { 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *elem = fRec->fSlots[fCount - 1]; 74ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com } 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->pop(); 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 77ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com 78ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com void pop() { 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCount > 0 && fRec); 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com --fTotalCount; 81ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com if (--fCount == 0) { 82ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com if (fRec != &fInitialRec) { 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Rec* rec = fRec->fNext; 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(fRec); 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = kSlotCount; 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fRec = rec; 87ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com } else { 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fTotalCount == 0); 89ca1f5e2a5db1d061f795aeb42acde6eba9e471e7reed@google.com } 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com enum { 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kSlotCount = 8 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com struct Rec; 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com friend struct Rec; 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com struct Rec { 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Rec* fNext; 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T fSlots[kSlotCount]; 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Rec fInitialRec; 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Rec* fRec; 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int fCount, fTotalCount; 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 111