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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
/**
@file SmallArray.h
@created 2009-04-26
@edited 2010-02-26
Copyright 2000-2010, Morgan McGuire, http://graphics.cs.williams.edu
All rights reserved.
*/
#ifndef G3D_SmallArray_h
#define G3D_SmallArray_h
#include "G3D/platform.h"
#include "G3D/Array.h"
#include "G3D/MemoryManager.h"
namespace G3D {
/** Embeds \a N elements to reduce allocation time and increase
memory coherence when working with arrays of arrays.
Offers a limited subset of the functionality of G3D::Array.*/
template<class T, int N>
class SmallArray {
private:
int m_size;
/** First N elements */
T m_embedded[N];
/** Remaining elements */
Array<T> m_rest;
public:
SmallArray() : m_size(0) {}
inline int size() const {
return m_size;
}
void resize(int n, bool shrinkIfNecessary = true) {
m_rest.resize(std::max(0, n - N), shrinkIfNecessary);
m_size = n;
}
void clear(bool shrinkIfNecessary = true) {
resize(0, shrinkIfNecessary);
}
void clearAndSetMemoryManager(MemoryManager::Ref& m) {
clear();
m_rest.clearAndSetMemoryManager(m);
}
inline T& operator[](int i) {
debugAssert(i < m_size && i >= 0);
if (i < N) {
return m_embedded[i];
} else {
return m_rest[i - N];
}
}
inline const T& operator[](int i) const {
debugAssert(i < m_size && i >= 0);
if (i < N) {
return m_embedded[i];
} else {
return m_rest[i - N];
}
}
inline void push(const T& v) {
++m_size;
if (m_size <= N) {
m_embedded[m_size - 1] = v;
} else {
m_rest.append(v);
}
}
inline void append(const T& v) {
push(v);
}
void fastRemove(int i, bool shrinkIfNecessary = false) {
debugAssert(i < m_size && i >= 0);
if (i < N) {
if (m_size <= N) {
// Exclusively embedded
m_embedded[i] = m_embedded[m_size - 1];
} else {
// Move one down from the rest array
m_embedded[i] = m_rest.pop();
}
} else {
// Removing from the rest array
m_rest.fastRemove(i - N, shrinkIfNecessary);
}
--m_size;
}
T pop() {
debugAssert(m_size > 0);
if (m_size <= N) {
// Popping from embedded, don't need a temporary
--m_size;
return m_embedded[m_size];
} else {
// Popping from rest
--m_size;
return m_rest.pop();
}
}
inline void popDiscard() {
debugAssert(m_size > 0);
if (m_size > N) {
m_rest.popDiscard();
}
--m_size;
}
inline T& next() {
++m_size;
if (m_size <= N) {
return m_embedded[m_size - 1];
} else {
return m_rest.next();
}
}
bool contains(const T& value) const {
for (int i = std::min(m_size, N) - 1; i >= 0; --i) {
if (m_embedded[i] == value) {
return true;
}
}
return m_rest.contains(value);
}
template<int MIN_ELEMENTS, int MIN_BYTES>
SmallArray<T, N>& operator=(const Array<T, MIN_ELEMENTS, MIN_BYTES>& src) {
resize(src.size());
for (int i = 0; i < src.size(); ++i) {
(*this)[i] = src[i];
}
return *this;
}
inline const T& last() const {
return (*this)[size() - 1];
}
inline T& last() {
return (*this)[size() - 1];
}
};
}
#endif
|
