1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies). |
4 | ** Contact: http://www.qt-project.org/ |
5 | ** |
6 | ** This file is part of the QtCore module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** GNU Lesser General Public License Usage |
10 | ** This file may be used under the terms of the GNU Lesser General Public |
11 | ** License version 2.1 as published by the Free Software Foundation and |
12 | ** appearing in the file LICENSE.LGPL included in the packaging of this |
13 | ** file. Please review the following information to ensure the GNU Lesser |
14 | ** General Public License version 2.1 requirements will be met: |
15 | ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
16 | ** |
17 | ** In addition, as a special exception, Nokia gives you certain additional |
18 | ** rights. These rights are described in the Nokia Qt LGPL Exception |
19 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
20 | ** |
21 | ** GNU General Public License Usage |
22 | ** Alternatively, this file may be used under the terms of the GNU General |
23 | ** Public License version 3.0 as published by the Free Software Foundation |
24 | ** and appearing in the file LICENSE.GPL included in the packaging of this |
25 | ** file. Please review the following information to ensure the GNU General |
26 | ** Public License version 3.0 requirements will be met: |
27 | ** http://www.gnu.org/copyleft/gpl.html. |
28 | ** |
29 | ** Other Usage |
30 | ** Alternatively, this file may be used in accordance with the terms and |
31 | ** conditions contained in a signed written agreement between you and Nokia. |
32 | ** |
33 | ** |
34 | ** |
35 | ** |
36 | ** |
37 | ** |
38 | ** $QT_END_LICENSE$ |
39 | ** |
40 | ****************************************************************************/ |
41 | |
42 | #ifndef QCONTIGUOUSCACHE_H |
43 | #define QCONTIGUOUSCACHE_H |
44 | |
45 | #include <QtCore/qatomic.h> |
46 | #include <limits.h> |
47 | #include <new> |
48 | |
49 | QT_BEGIN_HEADER |
50 | |
51 | QT_BEGIN_NAMESPACE |
52 | |
53 | #undef QT_QCONTIGUOUSCACHE_DEBUG |
54 | QT_MODULE(Core) |
55 | |
56 | |
57 | struct Q_CORE_EXPORT QContiguousCacheData |
58 | { |
59 | QBasicAtomicInt ref; |
60 | int alloc; |
61 | int count; |
62 | int start; |
63 | int offset; |
64 | uint sharable : 1; |
65 | uint reserved : 31; |
66 | |
67 | // total is 24 bytes (HP-UX aCC: 40 bytes) |
68 | // the next entry is already aligned to 8 bytes |
69 | // there will be an 8 byte gap here if T requires 16-byte alignment |
70 | // (such as long double on 64-bit platforms, __int128, __float128) |
71 | |
72 | static QContiguousCacheData *allocate(int size, int alignment); |
73 | static void free(QContiguousCacheData *data); |
74 | |
75 | #ifdef QT_QCONTIGUOUSCACHE_DEBUG |
76 | void dump() const; |
77 | #endif |
78 | }; |
79 | |
80 | template <typename T> |
81 | struct QContiguousCacheTypedData: private QContiguousCacheData |
82 | { |
83 | // private inheritance to avoid aliasing warningss |
84 | T array[1]; |
85 | |
86 | static inline void free(QContiguousCacheTypedData *data) { QContiguousCacheData::free(data); } |
87 | }; |
88 | |
89 | template<typename T> |
90 | class QContiguousCache { |
91 | typedef QContiguousCacheTypedData<T> Data; |
92 | union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; }; |
93 | public: |
94 | // STL compatibility |
95 | typedef T value_type; |
96 | typedef value_type* pointer; |
97 | typedef const value_type* const_pointer; |
98 | typedef value_type& reference; |
99 | typedef const value_type& const_reference; |
100 | typedef qptrdiff difference_type; |
101 | typedef int size_type; |
102 | |
103 | explicit QContiguousCache(int capacity = 0); |
104 | QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } |
105 | |
106 | inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(p); } |
107 | |
108 | inline void detach() { if (d->ref != 1) detach_helper(); } |
109 | inline bool isDetached() const { return d->ref == 1; } |
110 | inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
111 | |
112 | QContiguousCache<T> &operator=(const QContiguousCache<T> &other); |
113 | #ifdef Q_COMPILER_RVALUE_REFS |
114 | inline QContiguousCache<T> &operator=(QContiguousCache<T> &&other) |
115 | { qSwap(d, other.d); return *this; } |
116 | #endif |
117 | inline void swap(QContiguousCache<T> &other) { qSwap(d, other.d); } |
118 | bool operator==(const QContiguousCache<T> &other) const; |
119 | inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); } |
120 | |
121 | inline int capacity() const {return d->alloc; } |
122 | inline int count() const { return d->count; } |
123 | inline int size() const { return d->count; } |
124 | |
125 | inline bool isEmpty() const { return d->count == 0; } |
126 | inline bool isFull() const { return d->count == d->alloc; } |
127 | inline int available() const { return d->alloc - d->count; } |
128 | |
129 | void clear(); |
130 | void setCapacity(int size); |
131 | |
132 | const T &at(int pos) const; |
133 | T &operator[](int i); |
134 | const T &operator[](int i) const; |
135 | |
136 | void append(const T &value); |
137 | void prepend(const T &value); |
138 | void insert(int pos, const T &value); |
139 | |
140 | inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; } |
141 | inline int firstIndex() const { return d->offset; } |
142 | inline int lastIndex() const { return d->offset + d->count - 1; } |
143 | |
144 | inline const T &first() const { Q_ASSERT(!isEmpty()); return p->array[d->start]; } |
145 | inline const T &last() const { Q_ASSERT(!isEmpty()); return p->array[(d->start + d->count -1) % d->alloc]; } |
146 | inline T &first() { Q_ASSERT(!isEmpty()); detach(); return p->array[d->start]; } |
147 | inline T &last() { Q_ASSERT(!isEmpty()); detach(); return p->array[(d->start + d->count -1) % d->alloc]; } |
148 | |
149 | void removeFirst(); |
150 | T takeFirst(); |
151 | void removeLast(); |
152 | T takeLast(); |
153 | |
154 | inline bool areIndexesValid() const |
155 | { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; } |
156 | |
157 | inline void normalizeIndexes() { d->offset = d->start; } |
158 | |
159 | #ifdef QT_QCONTIGUOUSCACHE_DEBUG |
160 | void dump() const { p->dump(); } |
161 | #endif |
162 | private: |
163 | void detach_helper(); |
164 | |
165 | QContiguousCacheData *malloc(int aalloc); |
166 | void free(Data *x); |
167 | int sizeOfTypedData() { |
168 | // this is more or less the same as sizeof(Data), except that it doesn't |
169 | // count the padding at the end |
170 | return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this); |
171 | } |
172 | int alignOfTypedData() const |
173 | { |
174 | #ifdef Q_ALIGNOF |
175 | return qMax<int>(sizeof(void*), Q_ALIGNOF(Data)); |
176 | #else |
177 | return 0; |
178 | #endif |
179 | } |
180 | }; |
181 | |
182 | template <typename T> |
183 | void QContiguousCache<T>::detach_helper() |
184 | { |
185 | union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
186 | |
187 | x.d = malloc(d->alloc); |
188 | x.d->ref = 1; |
189 | x.d->count = d->count; |
190 | x.d->start = d->start; |
191 | x.d->offset = d->offset; |
192 | x.d->alloc = d->alloc; |
193 | x.d->sharable = true; |
194 | x.d->reserved = 0; |
195 | |
196 | T *dest = x.p->array + x.d->start; |
197 | T *src = p->array + d->start; |
198 | int oldcount = x.d->count; |
199 | while (oldcount--) { |
200 | if (QTypeInfo<T>::isComplex) { |
201 | new (dest) T(*src); |
202 | } else { |
203 | *dest = *src; |
204 | } |
205 | dest++; |
206 | if (dest == x.p->array + x.d->alloc) |
207 | dest = x.p->array; |
208 | src++; |
209 | if (src == p->array + d->alloc) |
210 | src = p->array; |
211 | } |
212 | |
213 | if (!d->ref.deref()) |
214 | free(p); |
215 | d = x.d; |
216 | } |
217 | |
218 | template <typename T> |
219 | void QContiguousCache<T>::setCapacity(int asize) |
220 | { |
221 | if (asize == d->alloc) |
222 | return; |
223 | detach(); |
224 | union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
225 | x.d = malloc(asize); |
226 | x.d->alloc = asize; |
227 | x.d->count = qMin(d->count, asize); |
228 | x.d->offset = d->offset + d->count - x.d->count; |
229 | if(asize) |
230 | x.d->start = x.d->offset % x.d->alloc; |
231 | else |
232 | x.d->start = 0; |
233 | |
234 | int oldcount = x.d->count; |
235 | if(oldcount) |
236 | { |
237 | T *dest = x.p->array + (x.d->start + x.d->count-1) % x.d->alloc; |
238 | T *src = p->array + (d->start + d->count-1) % d->alloc; |
239 | while (oldcount--) { |
240 | if (QTypeInfo<T>::isComplex) { |
241 | new (dest) T(*src); |
242 | } else { |
243 | *dest = *src; |
244 | } |
245 | if (dest == x.p->array) |
246 | dest = x.p->array + x.d->alloc; |
247 | dest--; |
248 | if (src == p->array) |
249 | src = p->array + d->alloc; |
250 | src--; |
251 | } |
252 | } |
253 | /* free old */ |
254 | free(p); |
255 | d = x.d; |
256 | } |
257 | |
258 | template <typename T> |
259 | void QContiguousCache<T>::clear() |
260 | { |
261 | if (d->ref == 1) { |
262 | if (QTypeInfo<T>::isComplex) { |
263 | int oldcount = d->count; |
264 | T * i = p->array + d->start; |
265 | T * e = p->array + d->alloc; |
266 | while (oldcount--) { |
267 | i->~T(); |
268 | i++; |
269 | if (i == e) |
270 | i = p->array; |
271 | } |
272 | } |
273 | d->count = d->start = d->offset = 0; |
274 | } else { |
275 | union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
276 | x.d = malloc(d->alloc); |
277 | x.d->ref = 1; |
278 | x.d->alloc = d->alloc; |
279 | x.d->count = x.d->start = x.d->offset = 0; |
280 | x.d->sharable = true; |
281 | if (!d->ref.deref()) free(p); |
282 | d = x.d; |
283 | } |
284 | } |
285 | |
286 | template <typename T> |
287 | inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc) |
288 | { |
289 | return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); |
290 | } |
291 | |
292 | template <typename T> |
293 | QContiguousCache<T>::QContiguousCache(int cap) |
294 | { |
295 | d = malloc(cap); |
296 | d->ref = 1; |
297 | d->alloc = cap; |
298 | d->count = d->start = d->offset = 0; |
299 | d->sharable = true; |
300 | } |
301 | |
302 | template <typename T> |
303 | QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other) |
304 | { |
305 | other.d->ref.ref(); |
306 | if (!d->ref.deref()) |
307 | free(d); |
308 | d = other.d; |
309 | if (!d->sharable) |
310 | detach_helper(); |
311 | return *this; |
312 | } |
313 | |
314 | template <typename T> |
315 | bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const |
316 | { |
317 | if (other.d == d) |
318 | return true; |
319 | if (other.d->start != d->start |
320 | || other.d->count != d->count |
321 | || other.d->offset != d->offset |
322 | || other.d->alloc != d->alloc) |
323 | return false; |
324 | for (int i = firstIndex(); i <= lastIndex(); ++i) |
325 | if (!(at(i) == other.at(i))) |
326 | return false; |
327 | return true; |
328 | } |
329 | |
330 | template <typename T> |
331 | void QContiguousCache<T>::free(Data *x) |
332 | { |
333 | if (QTypeInfo<T>::isComplex) { |
334 | int oldcount = d->count; |
335 | T * i = p->array + d->start; |
336 | T * e = p->array + d->alloc; |
337 | while (oldcount--) { |
338 | i->~T(); |
339 | i++; |
340 | if (i == e) |
341 | i = p->array; |
342 | } |
343 | } |
344 | x->free(x); |
345 | } |
346 | template <typename T> |
347 | void QContiguousCache<T>::append(const T &value) |
348 | { |
349 | detach(); |
350 | if (QTypeInfo<T>::isComplex) { |
351 | if (d->count == d->alloc) |
352 | (p->array + (d->start+d->count) % d->alloc)->~T(); |
353 | new (p->array + (d->start+d->count) % d->alloc) T(value); |
354 | } else { |
355 | p->array[(d->start+d->count) % d->alloc] = value; |
356 | } |
357 | |
358 | if (d->count == d->alloc) { |
359 | d->start++; |
360 | d->start %= d->alloc; |
361 | d->offset++; |
362 | } else { |
363 | d->count++; |
364 | } |
365 | } |
366 | |
367 | template<typename T> |
368 | void QContiguousCache<T>::prepend(const T &value) |
369 | { |
370 | detach(); |
371 | if (d->start) |
372 | d->start--; |
373 | else |
374 | d->start = d->alloc-1; |
375 | d->offset--; |
376 | |
377 | if (d->count != d->alloc) |
378 | d->count++; |
379 | else |
380 | if (d->count == d->alloc) |
381 | (p->array + d->start)->~T(); |
382 | |
383 | if (QTypeInfo<T>::isComplex) |
384 | new (p->array + d->start) T(value); |
385 | else |
386 | p->array[d->start] = value; |
387 | } |
388 | |
389 | template<typename T> |
390 | void QContiguousCache<T>::insert(int pos, const T &value) |
391 | { |
392 | Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert" , "index out of range" ); |
393 | detach(); |
394 | if (containsIndex(pos)) { |
395 | if (QTypeInfo<T>::isComplex) { |
396 | (p->array + pos % d->alloc)->~T(); |
397 | new (p->array + pos % d->alloc) T(value); |
398 | } else { |
399 | p->array[pos % d->alloc] = value; |
400 | } |
401 | } else if (pos == d->offset-1) |
402 | prepend(value); |
403 | else if (pos == d->offset+d->count) |
404 | append(value); |
405 | else { |
406 | // we don't leave gaps. |
407 | clear(); |
408 | d->offset = pos; |
409 | d->start = pos % d->alloc; |
410 | d->count = 1; |
411 | if (QTypeInfo<T>::isComplex) |
412 | new (p->array + d->start) T(value); |
413 | else |
414 | p->array[d->start] = value; |
415 | } |
416 | } |
417 | |
418 | template <typename T> |
419 | inline const T &QContiguousCache<T>::at(int pos) const |
420 | { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at" , "index out of range" ); return p->array[pos % d->alloc]; } |
421 | template <typename T> |
422 | inline const T &QContiguousCache<T>::operator[](int pos) const |
423 | { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at" , "index out of range" ); return p->array[pos % d->alloc]; } |
424 | |
425 | template <typename T> |
426 | inline T &QContiguousCache<T>::operator[](int pos) |
427 | { |
428 | detach(); |
429 | if (!containsIndex(pos)) |
430 | insert(pos, T()); |
431 | return p->array[pos % d->alloc]; |
432 | } |
433 | |
434 | template <typename T> |
435 | inline void QContiguousCache<T>::removeFirst() |
436 | { |
437 | Q_ASSERT(d->count > 0); |
438 | detach(); |
439 | d->count--; |
440 | if (QTypeInfo<T>::isComplex) |
441 | (p->array + d->start)->~T(); |
442 | d->start = (d->start + 1) % d->alloc; |
443 | d->offset++; |
444 | } |
445 | |
446 | template <typename T> |
447 | inline void QContiguousCache<T>::removeLast() |
448 | { |
449 | Q_ASSERT(d->count > 0); |
450 | detach(); |
451 | d->count--; |
452 | if (QTypeInfo<T>::isComplex) |
453 | (p->array + (d->start + d->count) % d->alloc)->~T(); |
454 | } |
455 | |
456 | template <typename T> |
457 | inline T QContiguousCache<T>::takeFirst() |
458 | { T t = first(); removeFirst(); return t; } |
459 | |
460 | template <typename T> |
461 | inline T QContiguousCache<T>::takeLast() |
462 | { T t = last(); removeLast(); return t; } |
463 | |
464 | QT_END_NAMESPACE |
465 | |
466 | QT_END_HEADER |
467 | |
468 | #endif |
469 | |