1 2 /* 3 * Copyright 2006 The Android Open Source Project 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10 #ifndef SkDeque_DEFINED 11 #define SkDeque_DEFINED 12 13 #include "include/core/SkTypes.h" 14 15 /* 16 * The deque class works by blindly creating memory space of a specified element 17 * size. It manages the memory as a doubly linked list of blocks each of which 18 * can contain multiple elements. Pushes and pops add/remove blocks from the 19 * beginning/end of the list as necessary while each block tracks the used 20 * portion of its memory. 21 * One behavior to be aware of is that the pops do not immediately remove an 22 * empty block from the beginning/end of the list (Presumably so push/pop pairs 23 * on the block boundaries don't cause thrashing). This can result in the first/ 24 * last element not residing in the first/last block. 25 */ 26 class SK_API SkDeque { 27 public: 28 /** 29 * elemSize specifies the size of each individual element in the deque 30 * allocCount specifies how many elements are to be allocated as a block 31 */ 32 explicit SkDeque(size_t elemSize, int allocCount = 1); 33 SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1); 34 ~SkDeque(); 35 empty()36 bool empty() const { return 0 == fCount; } count()37 int count() const { return fCount; } elemSize()38 size_t elemSize() const { return fElemSize; } 39 front()40 const void* front() const { return fFront; } back()41 const void* back() const { return fBack; } 42 front()43 void* front() { 44 return (void*)((const SkDeque*)this)->front(); 45 } 46 back()47 void* back() { 48 return (void*)((const SkDeque*)this)->back(); 49 } 50 51 /** 52 * push_front and push_back return a pointer to the memory space 53 * for the new element 54 */ 55 void* push_front(); 56 void* push_back(); 57 58 void pop_front(); 59 void pop_back(); 60 61 private: 62 struct Block; 63 64 public: 65 class Iter { 66 public: 67 enum IterStart { 68 kFront_IterStart, 69 kBack_IterStart, 70 }; 71 72 /** 73 * Creates an uninitialized iterator. Must be reset() 74 */ 75 Iter(); 76 77 Iter(const SkDeque& d, IterStart startLoc); 78 void* next(); 79 void* prev(); 80 81 void reset(const SkDeque& d, IterStart startLoc); 82 83 private: 84 SkDeque::Block* fCurBlock; 85 char* fPos; 86 size_t fElemSize; 87 }; 88 89 // Inherit privately from Iter to prevent access to reverse iteration 90 class F2BIter : private Iter { 91 public: F2BIter()92 F2BIter() {} 93 94 /** 95 * Wrap Iter's 2 parameter ctor to force initialization to the 96 * beginning of the deque 97 */ F2BIter(const SkDeque & d)98 F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {} 99 100 using Iter::next; 101 102 /** 103 * Wrap Iter::reset to force initialization to the beginning of the 104 * deque 105 */ reset(const SkDeque & d)106 void reset(const SkDeque& d) { 107 this->INHERITED::reset(d, kFront_IterStart); 108 } 109 110 private: 111 using INHERITED = Iter; 112 }; 113 114 private: 115 // allow unit test to call numBlocksAllocated 116 friend class DequeUnitTestHelper; 117 118 void* fFront; 119 void* fBack; 120 121 Block* fFrontBlock; 122 Block* fBackBlock; 123 size_t fElemSize; 124 void* fInitialStorage; 125 int fCount; // number of elements in the deque 126 int fAllocCount; // number of elements to allocate per block 127 128 Block* allocateBlock(int allocCount); 129 void freeBlock(Block* block); 130 131 /** 132 * This returns the number of chunk blocks allocated by the deque. It 133 * can be used to gauge the effectiveness of the selected allocCount. 134 */ 135 int numBlocksAllocated() const; 136 137 SkDeque(const SkDeque&) = delete; 138 SkDeque& operator=(const SkDeque&) = delete; 139 }; 140 141 #endif 142