180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SkDeque_DEFINED 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkDeque_DEFINED 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTypes.h" 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * The deque class works by blindly creating memory space of a specified element 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * size. It manages the memory as a doubly linked list of blocks each of which 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * can contain multiple elements. Pushes and pops add/remove blocks from the 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * beginning/end of the list as necessary while each block tracks the used 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * portion of its memory. 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * One behavior to be aware of is that the pops do not immediately remove an 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * empty block from the beginning/end of the list (Presumably so push/pop pairs 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * on the block boundaries don't cause thrashing). This can result in the first/ 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * last element not residing in the first/last block. 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SK_API SkDeque : SkNoncopyable { 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * elemSize specifies the size of each individual element in the deque 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * allocCount specifies how many elements are to be allocated as a block 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru explicit SkDeque(size_t elemSize, int allocCount = 1); 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1); 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru ~SkDeque(); 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool empty() const { return 0 == fCount; } 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count() const { return fCount; } 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t elemSize() const { return fElemSize; } 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const void* front() const { return fFront; } 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const void* back() const { return fBack; } 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* front() { 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (void*)((const SkDeque*)this)->front(); 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* back() { 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (void*)((const SkDeque*)this)->back(); 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * push_front and push_back return a pointer to the memory space 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * for the new element 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* push_front(); 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* push_back(); 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void pop_front(); 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void pop_back(); 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru struct Block; 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru class Iter { 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru public: 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru enum IterStart { 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru kFront_IterStart, 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru kBack_IterStart 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Creates an uninitialized iterator. Must be reset() 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Iter(); 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Iter(const SkDeque& d, IterStart startLoc); 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* next(); 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* prev(); 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void reset(const SkDeque& d, IterStart startLoc); 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru private: 840a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger SkDeque::Block* fCurBlock; 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* fPos; 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t fElemSize; 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Inherit privately from Iter to prevent access to reverse iteration 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru class F2BIter : private Iter { 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru public: 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru F2BIter() {} 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Wrap Iter's 2 parameter ctor to force initialization to the 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * beginning of the deque 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {} 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru using Iter::next; 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Wrap Iter::reset to force initialization to the beginning of the 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * deque 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void reset(const SkDeque& d) { 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->INHERITED::reset(d, kFront_IterStart); 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru private: 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru typedef Iter INHERITED; 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // allow unit test to call numBlocksAllocated 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru friend class DequeUnitTestHelper; 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* fFront; 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* fBack; 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* fFrontBlock; 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* fBackBlock; 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t fElemSize; 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void* fInitialStorage; 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int fCount; // number of elements in the deque 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int fAllocCount; // number of elements to allocate per block 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Block* allocateBlock(int allocCount); 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void freeBlock(Block* block); 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * This returns the number of chunk blocks allocated by the deque. It 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * can be used to gauge the effectiveness of the selected allocCount. 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int numBlocksAllocated() const; 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 139