10910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/* 20910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Copyright (C) 2006 The Android Open Source Project 30910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * 40910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 50910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * you may not use this file except in compliance with the License. 60910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * You may obtain a copy of the License at 70910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * 80910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 90910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * 100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * See the License for the specific language governing permissions and 140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * limitations under the License. 150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project */ 160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifndef SkTDStack_DEFINED 180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#define SkTDStack_DEFINED 190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#include "SkTypes.h" 210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projecttemplate <typename T> class SkTDStack : SkNoncopyable { 230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectpublic: 240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkTDStack() : fCount(0), fTotalCount(0) 250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fInitialRec.fNext = NULL; 270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fRec = &fInitialRec; 280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // fCount = kSlotCount; 300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project ~SkTDStack() 320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Rec* rec = fRec; 340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project while (rec != &fInitialRec) 350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Rec* next = rec->fNext; 370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project sk_free(rec); 380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project rec = next; 390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int count() const { return fTotalCount; } 4357382d688c1d6928b1d9bbbaf27188d54dd9e002Mike Reed int depth() const { return fTotalCount; } 4457382d688c1d6928b1d9bbbaf27188d54dd9e002Mike Reed bool empty() const { return fTotalCount == 0; } 450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project T* push() 470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fCount <= kSlotCount); 490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (fCount == kSlotCount) 500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Rec* rec = (Rec*)sk_malloc_throw(sizeof(Rec)); 520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project rec->fNext = fRec; 530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fRec = rec; 540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fCount = 0; 550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project ++fTotalCount; 570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return &fRec->fSlots[fCount++]; 580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project void push(const T& elem) { *this->push() = elem; } 600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const T& index(int idx) const 610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fRec && fCount > idx); 630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return fRec->fSlots[fCount - idx - 1]; 640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project T& index(int idx) 660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fRec && fCount > idx); 680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return fRec->fSlots[fCount - idx - 1]; 690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project const T& top() const 710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fRec && fCount > 0); 730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return fRec->fSlots[fCount - 1]; 740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project T& top() 760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fRec && fCount > 0); 780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return fRec->fSlots[fCount - 1]; 790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project void pop(T* elem) 810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (elem) 830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project *elem = fRec->fSlots[fCount - 1]; 840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project this->pop(); 850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project void pop() 870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fCount > 0 && fRec); 890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project --fTotalCount; 900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (--fCount == 0) 910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (fRec != &fInitialRec) 930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Rec* rec = fRec->fNext; 950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project sk_free(fRec); 960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fCount = kSlotCount; 970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fRec = rec; 980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project else 1000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(fTotalCount == 0); 1010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectprivate: 1050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project enum { 1060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project kSlotCount = 8 1070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project }; 1080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project struct Rec; 1100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project friend struct Rec; 1110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project struct Rec { 1130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Rec* fNext; 1140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project T fSlots[kSlotCount]; 1150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project }; 1160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Rec fInitialRec; 1170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Rec* fRec; 1180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int fCount, fTotalCount; 1190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}; 1200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif 1220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 123