• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2     Copyright 2010 Google Inc.
3 
4     Licensed under the Apache License, Version 2.0 (the "License");
5     you may not use this file except in compliance with the License.
6     You may obtain a copy of the License at
7 
8          http://www.apache.org/licenses/LICENSE-2.0
9 
10     Unless required by applicable law or agreed to in writing, software
11     distributed under the License is distributed on an "AS IS" BASIS,
12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13     See the License for the specific language governing permissions and
14     limitations under the License.
15  */
16 
17 
18 #ifndef GrTArray_DEFINED
19 #define GrTArray_DEFINED
20 
21 #include <new>
22 #include "GrTypes.h"
23 #include "GrTemplates.h"
24 
25 // DATA_TYPE indicates that T has a trivial cons, destructor
26 // and can be shallow-copied
27 template <typename T, bool DATA_TYPE = false> class GrTArray {
28 public:
GrTArray()29     GrTArray() {
30         fCount = 0;
31         fReserveCount = MIN_ALLOC_COUNT;
32         fAllocCount = 0;
33         fMemArray = NULL;
34         fPreAllocMemArray = NULL;
35     }
36 
GrTArray(int reserveCount)37     explicit GrTArray(int reserveCount) {
38         GrAssert(reserveCount >= 0);
39         fCount = 0;
40         fReserveCount = reserveCount > MIN_ALLOC_COUNT ? reserveCount :
41                                                          MIN_ALLOC_COUNT;
42         fAllocCount = fReserveCount;
43         fMemArray = GrMalloc(sizeof(T) * fReserveCount);
44         fPreAllocMemArray = NULL;
45     }
46 
47     template <int N>
GrTArray(GrAlignedSTStorage<N,T> * storage)48     GrTArray(GrAlignedSTStorage<N,T>* storage) {
49         GrAssert(N > 0);
50         fCount              = 0;
51         fReserveCount       = N;
52         fAllocCount         = N;
53         fMemArray           = storage->get();
54         fPreAllocMemArray   = storage->get();
55     }
56 
GrTArray(void * preAllocStorage,int preAllocCount)57     GrTArray(void* preAllocStorage, int preAllocCount) {
58         GrAssert(preAllocCount >= 0);
59         // we allow NULL,0 args and revert to the default cons. behavior
60         // this makes it possible for a owner-object to use same constructor
61         // to get either prealloc or nonprealloc behavior based using same line
62         GrAssert((NULL == preAllocStorage) == !preAllocCount);
63 
64         fCount              = 0;
65         fReserveCount       = preAllocCount > 0 ? preAllocCount :
66                                                   MIN_ALLOC_COUNT;
67         fAllocCount         = preAllocCount;
68         fMemArray           = preAllocStorage;
69         fPreAllocMemArray   = preAllocStorage;
70     }
71 
GrTArray(const GrTArray & array)72     explicit GrTArray(const GrTArray& array) {
73         fCount              = array.count();
74         fReserveCount       = MIN_ALLOC_COUNT;
75         fAllocCount         = GrMax(fReserveCount, fCount);
76         fMemArray           = GrMalloc(sizeof(T) * fAllocCount);
77         fPreAllocMemArray   = NULL;
78 
79         if (DATA_TYPE) {
80             memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount);
81         } else {
82             for (int i = 0; i < fCount; ++i) {
83                 new (fItemArray + i) T(array[i]);
84             }
85         }
86     }
87 
GrTArray(const T * array,int count)88     GrTArray(const T* array, int count) {
89         GrAssert(count >= 0);
90         fCount              = count;
91         fReserveCount       = MIN_ALLOC_COUNT;
92         fAllocCount         = GrMax(fReserveCount, fCount);
93         fMemArray           = GrMalloc(sizeof(T) * fAllocCount);
94         fPreAllocMemArray   = NULL;
95         if (DATA_TYPE) {
96             memcpy(fMemArray, array, sizeof(T) * fCount);
97         } else {
98             for (int i = 0; i < fCount; ++i) {
99                 new (fItemArray + i) T(array[i]);
100             }
101         }
102     }
103 
GrTArray(const GrTArray & array,void * preAllocStorage,int preAllocCount)104     GrTArray(const GrTArray& array,
105              void* preAllocStorage, int preAllocCount) {
106 
107         GrAssert(preAllocCount >= 0);
108 
109         // for same reason as non-copying cons we allow NULL, 0 for prealloc
110         GrAssert((NULL == preAllocStorage) == !preAllocCount);
111 
112         fCount              = array.count();
113         fReserveCount       = preAllocCount > 0 ? preAllocCount :
114                                                   MIN_ALLOC_COUNT;
115         fPreAllocMemArray   = preAllocStorage;
116 
117         if (fReserveCount >= fCount && preAllocCount) {
118             fAllocCount = fReserveCount;
119             fMemArray = preAllocStorage;
120         } else {
121             fAllocCount = GrMax(fCount, fReserveCount);
122             fMemArray = GrMalloc(fAllocCount * sizeof(T));
123         }
124 
125         if (DATA_TYPE) {
126             memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount);
127         } else {
128             for (int i = 0; i < fCount; ++i) {
129                 new (fItemArray + i) T(array[i]);
130             }
131         }
132     }
133 
GrTArray(const T * array,int count,void * preAllocStorage,int preAllocCount)134     GrTArray(const T* array, int count,
135              void* preAllocStorage, int preAllocCount) {
136 
137         GrAssert(count >= 0);
138         GrAssert(preAllocCount >= 0);
139 
140         // for same reason as non-copying cons we allow NULL, 0 for prealloc
141         GrAssert((NULL == preAllocStorage) == !preAllocCount);
142 
143         fCount              = count;
144         fReserveCount       = (preAllocCount > 0) ? preAllocCount :
145                                                     MIN_ALLOC_COUNT;
146         fPreAllocMemArray   = preAllocStorage;
147 
148         if (fReserveCount >= fCount && preAllocCount) {
149             fAllocCount = fReserveCount;
150             fMemArray = preAllocStorage;
151         } else {
152             fAllocCount = GrMax(fCount, fReserveCount);
153             fMemArray = GrMalloc(fAllocCount * sizeof(T));
154         }
155 
156         if (DATA_TYPE) {
157             memcpy(fMemArray, array, sizeof(T) * fCount);
158         } else {
159             for (int i = 0; i < fCount; ++i) {
160                 new (fItemArray + i) T(array[i]);
161             }
162         }
163     }
164 
165     GrTArray& operator =(const GrTArray& array) {
166         for (int i = 0; i < fCount; ++i) {
167             fItemArray[i].~T();
168         }
169         fCount = 0;
170         checkRealloc((int)array.count());
171         fCount = array.count();
172         if (DATA_TYPE) {
173             memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount);
174         } else {
175             for (int i = 0; i < fCount; ++i) {
176                 new (fItemArray + i) T(array[i]);
177             }
178         }
179         return *this;
180     }
181 
~GrTArray()182     ~GrTArray() {
183         for (int i = 0; i < fCount; ++i) {
184             fItemArray[i].~T();
185         }
186         if (fMemArray != fPreAllocMemArray) {
187             GrFree(fMemArray);
188         }
189     }
190 
reset()191     void reset() { this->pop_back_n(fCount); }
192 
count()193     int count() const { return fCount; }
194 
empty()195     bool empty() const { return !fCount; }
196 
push_back()197     T& push_back() {
198         checkRealloc(1);
199         new ((char*)fMemArray+sizeof(T)*fCount) T;
200         ++fCount;
201         return fItemArray[fCount-1];
202     }
203 
push_back_n(int n)204     void push_back_n(int n) {
205         GrAssert(n >= 0);
206         checkRealloc(n);
207         for (int i = 0; i < n; ++i) {
208             new (fItemArray + fCount + i) T;
209         }
210         fCount += n;
211     }
212 
pop_back()213     void pop_back() {
214         GrAssert(fCount > 0);
215         --fCount;
216         fItemArray[fCount].~T();
217         checkRealloc(0);
218     }
219 
pop_back_n(int n)220     void pop_back_n(int n) {
221         GrAssert(n >= 0);
222         GrAssert(fCount >= n);
223         fCount -= n;
224         for (int i = 0; i < n; ++i) {
225             fItemArray[i].~T();
226         }
227         checkRealloc(0);
228     }
229 
230     // pushes or pops from the back to resize
resize_back(int newCount)231     void resize_back(int newCount) {
232         GrAssert(newCount >= 0);
233 
234         if (newCount > fCount) {
235             push_back_n(newCount - fCount);
236         } else if (newCount < fCount) {
237             pop_back_n(fCount - newCount);
238         }
239     }
240 
241     T& operator[] (int i) {
242         GrAssert(i < fCount);
243         GrAssert(i >= 0);
244         return fItemArray[i];
245     }
246 
247     const T& operator[] (int i) const {
248         GrAssert(i < fCount);
249         GrAssert(i >= 0);
250         return fItemArray[i];
251     }
252 
front()253     T& front() { GrAssert(fCount > 0); return fItemArray[0];}
254 
front()255     const T& front() const { GrAssert(fCount > 0); return fItemArray[0];}
256 
back()257     T& back() { GrAssert(fCount); return fItemArray[fCount - 1];}
258 
back()259     const T& back() const { GrAssert(fCount > 0); return fItemArray[fCount - 1];}
260 
fromBack(int i)261     T& fromBack(int i) {
262         GrAssert(i >= 0);
263         GrAssert(i < fCount);
264         return fItemArray[fCount - i - 1];
265     }
266 
fromBack(int i)267     const T& fromBack(int i) const {
268         GrAssert(i >= 0);
269         GrAssert(i < fCount);
270         return fItemArray[fCount - i - 1];
271     }
272 
273 private:
274 
275     static const int MIN_ALLOC_COUNT = 8;
276 
checkRealloc(int delta)277     inline void checkRealloc(int delta) {
278         GrAssert(fCount >= 0);
279         GrAssert(fAllocCount >= 0);
280 
281         GrAssert(-delta <= fCount);
282 
283         int newCount = fCount + delta;
284         int fNewAllocCount = fAllocCount;
285 
286         if (newCount > fAllocCount) {
287             fNewAllocCount = GrMax(newCount + ((newCount + 1) >> 1),
288                                    fReserveCount);
289         } else if (newCount < fAllocCount / 3) {
290             fNewAllocCount = GrMax(fAllocCount / 2, fReserveCount);
291         }
292 
293         if (fNewAllocCount != fAllocCount) {
294 
295             fAllocCount = fNewAllocCount;
296             char* fNewMemArray;
297 
298             if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) {
299                 fNewMemArray = (char*) fPreAllocMemArray;
300             } else {
301                 fNewMemArray = (char*) GrMalloc(fAllocCount*sizeof(T));
302             }
303 
304             if (DATA_TYPE) {
305                 memcpy(fNewMemArray, fMemArray, fCount * sizeof(T));
306             } else {
307                 for (int i = 0; i < fCount; ++i) {
308                     new (fNewMemArray + sizeof(T) * i) T(fItemArray[i]);
309                     fItemArray[i].~T();
310                 }
311             }
312 
313             if (fMemArray != fPreAllocMemArray) {
314                 GrFree(fMemArray);
315             }
316             fMemArray = fNewMemArray;
317         }
318     }
319 
320     int fReserveCount;
321     int fCount;
322     int fAllocCount;
323     void*    fPreAllocMemArray;
324     union {
325         T*       fItemArray;
326         void*    fMemArray;
327     };
328 };
329 
330 #endif
331 
332