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() { return fFront; } back()46 void* back() { return fBack; } 47 48 /** 49 * push_front and push_back return a pointer to the memory space 50 * for the new element 51 */ 52 void* push_front(); 53 void* push_back(); 54 55 void pop_front(); 56 void pop_back(); 57 58 private: 59 struct Block; 60 61 public: 62 class Iter { 63 public: 64 enum IterStart { 65 kFront_IterStart, 66 kBack_IterStart, 67 }; 68 69 /** 70 * Creates an uninitialized iterator. Must be reset() 71 */ 72 Iter(); 73 74 Iter(const SkDeque& d, IterStart startLoc); 75 void* next(); 76 void* prev(); 77 78 void reset(const SkDeque& d, IterStart startLoc); 79 80 private: 81 SkDeque::Block* fCurBlock; 82 char* fPos; 83 size_t fElemSize; 84 }; 85 86 // Inherit privately from Iter to prevent access to reverse iteration 87 class F2BIter : private Iter { 88 public: F2BIter()89 F2BIter() {} 90 91 /** 92 * Wrap Iter's 2 parameter ctor to force initialization to the 93 * beginning of the deque 94 */ F2BIter(const SkDeque & d)95 F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {} 96 97 using Iter::next; 98 99 /** 100 * Wrap Iter::reset to force initialization to the beginning of the 101 * deque 102 */ reset(const SkDeque & d)103 void reset(const SkDeque& d) { 104 this->INHERITED::reset(d, kFront_IterStart); 105 } 106 107 private: 108 using INHERITED = Iter; 109 }; 110 111 private: 112 // allow unit test to call numBlocksAllocated 113 friend class DequeUnitTestHelper; 114 115 void* fFront; 116 void* fBack; 117 118 Block* fFrontBlock; 119 Block* fBackBlock; 120 size_t fElemSize; 121 void* fInitialStorage; 122 int fCount; // number of elements in the deque 123 int fAllocCount; // number of elements to allocate per block 124 125 Block* allocateBlock(int allocCount); 126 void freeBlock(Block* block); 127 128 /** 129 * This returns the number of chunk blocks allocated by the deque. It 130 * can be used to gauge the effectiveness of the selected allocCount. 131 */ 132 int numBlocksAllocated() const; 133 134 SkDeque(const SkDeque&) = delete; 135 SkDeque& operator=(const SkDeque&) = delete; 136 }; 137 138 #endif 139