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