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