michael@0: 
michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #ifndef SkDeque_DEFINED
michael@0: #define SkDeque_DEFINED
michael@0: 
michael@0: #include "SkTypes.h"
michael@0: 
michael@0: /*
michael@0:  * The deque class works by blindly creating memory space of a specified element
michael@0:  * size. It manages the memory as a doubly linked list of blocks each of which
michael@0:  * can contain multiple elements. Pushes and pops add/remove blocks from the
michael@0:  * beginning/end of the list as necessary while each block tracks the used
michael@0:  * portion of its memory.
michael@0:  * One behavior to be aware of is that the pops do not immediately remove an
michael@0:  * empty block from the beginning/end of the list (Presumably so push/pop pairs
michael@0:  * on the block boundaries don't cause thrashing). This can result in the first/
michael@0:  * last element not residing in the first/last block.
michael@0:  */
michael@0: class SK_API SkDeque : SkNoncopyable {
michael@0: public:
michael@0:     /**
michael@0:      * elemSize specifies the size of each individual element in the deque
michael@0:      * allocCount specifies how many elements are to be allocated as a block
michael@0:      */
michael@0:     explicit SkDeque(size_t elemSize, int allocCount = 1);
michael@0:     SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1);
michael@0:     ~SkDeque();
michael@0: 
michael@0:     bool    empty() const { return 0 == fCount; }
michael@0:     int     count() const { return fCount; }
michael@0:     size_t  elemSize() const { return fElemSize; }
michael@0: 
michael@0:     const void* front() const { return fFront; }
michael@0:     const void* back() const  { return fBack; }
michael@0: 
michael@0:     void* front() {
michael@0:         return (void*)((const SkDeque*)this)->front();
michael@0:     }
michael@0: 
michael@0:     void* back() {
michael@0:         return (void*)((const SkDeque*)this)->back();
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * push_front and push_back return a pointer to the memory space
michael@0:      * for the new element
michael@0:      */
michael@0:     void* push_front();
michael@0:     void* push_back();
michael@0: 
michael@0:     void pop_front();
michael@0:     void pop_back();
michael@0: 
michael@0: private:
michael@0:     struct Block;
michael@0: 
michael@0: public:
michael@0:     class Iter {
michael@0:     public:
michael@0:         enum IterStart {
michael@0:             kFront_IterStart,
michael@0:             kBack_IterStart
michael@0:         };
michael@0: 
michael@0:         /**
michael@0:          * Creates an uninitialized iterator. Must be reset()
michael@0:          */
michael@0:         Iter();
michael@0: 
michael@0:         Iter(const SkDeque& d, IterStart startLoc);
michael@0:         void* next();
michael@0:         void* prev();
michael@0: 
michael@0:         void reset(const SkDeque& d, IterStart startLoc);
michael@0: 
michael@0:     private:
michael@0:         SkDeque::Block* fCurBlock;
michael@0:         char*           fPos;
michael@0:         size_t          fElemSize;
michael@0:     };
michael@0: 
michael@0:     // Inherit privately from Iter to prevent access to reverse iteration
michael@0:     class F2BIter : private Iter {
michael@0:     public:
michael@0:         F2BIter() {}
michael@0: 
michael@0:         /**
michael@0:          * Wrap Iter's 2 parameter ctor to force initialization to the
michael@0:          * beginning of the deque
michael@0:          */
michael@0:         F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {}
michael@0: 
michael@0:         using Iter::next;
michael@0: 
michael@0:         /**
michael@0:          * Wrap Iter::reset to force initialization to the beginning of the
michael@0:          * deque
michael@0:          */
michael@0:         void reset(const SkDeque& d) {
michael@0:             this->INHERITED::reset(d, kFront_IterStart);
michael@0:         }
michael@0: 
michael@0:     private:
michael@0:         typedef Iter INHERITED;
michael@0:     };
michael@0: 
michael@0: private:
michael@0:     // allow unit test to call numBlocksAllocated
michael@0:     friend class DequeUnitTestHelper;
michael@0: 
michael@0:     void*   fFront;
michael@0:     void*   fBack;
michael@0: 
michael@0:     Block*  fFrontBlock;
michael@0:     Block*  fBackBlock;
michael@0:     size_t  fElemSize;
michael@0:     void*   fInitialStorage;
michael@0:     int     fCount;             // number of elements in the deque
michael@0:     int     fAllocCount;        // number of elements to allocate per block
michael@0: 
michael@0:     Block*  allocateBlock(int allocCount);
michael@0:     void    freeBlock(Block* block);
michael@0: 
michael@0:     /**
michael@0:      * This returns the number of chunk blocks allocated by the deque. It
michael@0:      * can be used to gauge the effectiveness of the selected allocCount.
michael@0:      */
michael@0:     int  numBlocksAllocated() const;
michael@0: };
michael@0: 
michael@0: #endif