Debian Codegraph @

include/private/base/SkDeque.h

raw
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
38 bool empty() const { return 0 == fCount; }
39 int count() const { return fCount; }
40 size_t elemSize() const { return fElemSize; }
41
42 const void* front() const { return fFront; }
43 const void* back() const { return fBack; }
44
45 void* front() { return fFront; }
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:
89 F2BIter() {}
90
91 /**
92 * Wrap Iter's 2 parameter ctor to force initialization to the
93 * beginning of the deque
94 */
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 */
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