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 */
26class SK_API SkDeque {
27public:
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
61private:
62 struct Block;
63
64public:
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
114private:
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