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