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 SkDeque_DEFINED 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkDeque_DEFINED 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTypes.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com/* 1663ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * The deque class works by blindly creating memory space of a specified element 17fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * size. It manages the memory as a doubly linked list of blocks each of which 18fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * can contain multiple elements. Pushes and pops add/remove blocks from the 1963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * beginning/end of the list as necessary while each block tracks the used 2063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * portion of its memory. 2163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * One behavior to be aware of is that the pops do not immediately remove an 2263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * empty block from the beginning/end of the list (Presumably so push/pop pairs 2363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * on the block boundaries don't cause thrashing). This can result in the first/ 2463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * last element not residing in the first/last block. 2563ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com */ 267ffb1b21abcc7bbed5a0fc711f6dd7b9dbb4f577ctguil@chromium.orgclass SK_API SkDeque : SkNoncopyable { 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.compublic: 280a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com /** 290a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com * elemSize specifies the size of each individual element in the deque 300a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com * allocCount specifies how many elements are to be allocated as a block 310a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com */ 320a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com explicit SkDeque(size_t elemSize, int allocCount = 1); 330a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1); 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ~SkDeque(); 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool empty() const { return 0 == fCount; } 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count() const { return fCount; } 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t elemSize() const { return fElemSize; } 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com const void* front() const { return fFront; } 4163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com const void* back() const { return fBack; } 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void* front() { 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (void*)((const SkDeque*)this)->front(); 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void* back() { 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (void*)((const SkDeque*)this)->back(); 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com /** 5263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * push_front and push_back return a pointer to the memory space 5363ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com * for the new element 5463ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com */ 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void* push_front(); 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void* push_back(); 574c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void pop_front(); 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void pop_back(); 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 620a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com struct Block; 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.compublic: 650a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com class Iter { 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com public: 670a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com enum IterStart { 680a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com kFront_IterStart, 690a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com kBack_IterStart 700a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com }; 710a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 72d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com /** 73d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com * Creates an uninitialized iterator. Must be reset() 74d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com */ 750a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Iter(); 76d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com 770a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Iter(const SkDeque& d, IterStart startLoc); 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void* next(); 790a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com void* prev(); 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 810a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com void reset(const SkDeque& d, IterStart startLoc); 82d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com private: 846c157640c27ee2ed6f9a484d21691b7b19dfecdecommit-bot@chromium.org SkDeque::Block* fCurBlock; 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* fPos; 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t fElemSize; 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 88fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 890a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com // Inherit privately from Iter to prevent access to reverse iteration 900a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com class F2BIter : private Iter { 910a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com public: 920a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com F2BIter() {} 930a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 940a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com /** 95fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * Wrap Iter's 2 parameter ctor to force initialization to the 960a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com * beginning of the deque 970a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com */ 980a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {} 990a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 1000a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com using Iter::next; 1010a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 102fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com /** 103fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * Wrap Iter::reset to force initialization to the beginning of the 1040a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com * deque 1050a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com */ 1060a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com void reset(const SkDeque& d) { 1070a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com this->INHERITED::reset(d, kFront_IterStart); 1080a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com } 1090a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 1100a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com private: 1110a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com typedef Iter INHERITED; 1120a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com }; 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 1150a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com // allow unit test to call numBlocksAllocated 116fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com friend class DequeUnitTestHelper; 1170a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 11863ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com void* fFront; 11963ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com void* fBack; 12063ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com 12163ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* fFrontBlock; 12263ae1cfb10d0d14722df59cba0012f8a4370c090robertphillips@google.com Block* fBackBlock; 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t fElemSize; 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void* fInitialStorage; 1250a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com int fCount; // number of elements in the deque 1260a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com int fAllocCount; // number of elements to allocate per block 1270a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com 1280a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com Block* allocateBlock(int allocCount); 1290a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com void freeBlock(Block* block); 1304c09d5cd4b9e6f0be1352f62288efdedc1bc3de3reed@google.com 1310a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com /** 1320a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com * This returns the number of chunk blocks allocated by the deque. It 1330a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com * can be used to gauge the effectiveness of the selected allocCount. 1340a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com */ 1350a78b0f4a2e1a3d7d1fbdb9b0b5dba5095db2e5arobertphillips@google.com int numBlocksAllocated() const; 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 139