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 | |
36 | bool empty() const { return 0 == fCount; } |
37 | int count() const { return fCount; } |
38 | size_t elemSize() const { return fElemSize; } |
39 | |
40 | const void* front() const { return fFront; } |
41 | const void* back() const { return fBack; } |
42 | |
43 | void* front() { |
44 | return (void*)((const SkDeque*)this)->front(); |
45 | } |
46 | |
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: |
92 | F2BIter() {} |
93 | |
94 | /** |
95 | * Wrap Iter's 2 parameter ctor to force initialization to the |
96 | * beginning of the deque |
97 | */ |
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 | */ |
106 | void reset(const SkDeque& d) { |
107 | this->INHERITED::reset(d, kFront_IterStart); |
108 | } |
109 | |
110 | private: |
111 | typedef Iter INHERITED; |
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 | |