1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies). |
4 | ** Contact: http://www.qt-project.org/legal |
5 | ** |
6 | ** This file is part of the QtCore module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and Digia. For licensing terms and |
14 | ** conditions see http://qt.digia.com/licensing. For further information |
15 | ** use the contact form at http://qt.digia.com/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 2.1 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 2.1 requirements |
23 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
24 | ** |
25 | ** In addition, as a special exception, Digia gives you certain additional |
26 | ** rights. These rights are described in the Digia Qt LGPL Exception |
27 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
28 | ** |
29 | ** GNU General Public License Usage |
30 | ** Alternatively, this file may be used under the terms of the GNU |
31 | ** General Public License version 3.0 as published by the Free Software |
32 | ** Foundation and appearing in the file LICENSE.GPL included in the |
33 | ** packaging of this file. Please review the following information to |
34 | ** ensure the GNU General Public License version 3.0 requirements will be |
35 | ** met: http://www.gnu.org/copyleft/gpl.html. |
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 | if (!d->alloc) |
350 | return; // zero capacity |
351 | detach(); |
352 | if (QTypeInfo<T>::isComplex) { |
353 | if (d->count == d->alloc) |
354 | (p->array + (d->start+d->count) % d->alloc)->~T(); |
355 | new (p->array + (d->start+d->count) % d->alloc) T(value); |
356 | } else { |
357 | p->array[(d->start+d->count) % d->alloc] = value; |
358 | } |
359 | |
360 | if (d->count == d->alloc) { |
361 | d->start++; |
362 | d->start %= d->alloc; |
363 | d->offset++; |
364 | } else { |
365 | d->count++; |
366 | } |
367 | } |
368 | |
369 | template<typename T> |
370 | void QContiguousCache<T>::prepend(const T &value) |
371 | { |
372 | if (!d->alloc) |
373 | return; // zero capacity |
374 | detach(); |
375 | if (d->start) |
376 | d->start--; |
377 | else |
378 | d->start = d->alloc-1; |
379 | d->offset--; |
380 | |
381 | if (d->count != d->alloc) |
382 | d->count++; |
383 | else |
384 | if (d->count == d->alloc) |
385 | (p->array + d->start)->~T(); |
386 | |
387 | if (QTypeInfo<T>::isComplex) |
388 | new (p->array + d->start) T(value); |
389 | else |
390 | p->array[d->start] = value; |
391 | } |
392 | |
393 | template<typename T> |
394 | void QContiguousCache<T>::insert(int pos, const T &value) |
395 | { |
396 | Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert" , "index out of range" ); |
397 | if (!d->alloc) |
398 | return; // zero capacity |
399 | detach(); |
400 | if (containsIndex(pos)) { |
401 | if (QTypeInfo<T>::isComplex) { |
402 | (p->array + pos % d->alloc)->~T(); |
403 | new (p->array + pos % d->alloc) T(value); |
404 | } else { |
405 | p->array[pos % d->alloc] = value; |
406 | } |
407 | } else if (pos == d->offset-1) |
408 | prepend(value); |
409 | else if (pos == d->offset+d->count) |
410 | append(value); |
411 | else { |
412 | // we don't leave gaps. |
413 | clear(); |
414 | d->offset = pos; |
415 | d->start = pos % d->alloc; |
416 | d->count = 1; |
417 | if (QTypeInfo<T>::isComplex) |
418 | new (p->array + d->start) T(value); |
419 | else |
420 | p->array[d->start] = value; |
421 | } |
422 | } |
423 | |
424 | template <typename T> |
425 | inline const T &QContiguousCache<T>::at(int pos) const |
426 | { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at" , "index out of range" ); return p->array[pos % d->alloc]; } |
427 | template <typename T> |
428 | inline const T &QContiguousCache<T>::operator[](int pos) const |
429 | { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at" , "index out of range" ); return p->array[pos % d->alloc]; } |
430 | |
431 | template <typename T> |
432 | inline T &QContiguousCache<T>::operator[](int pos) |
433 | { |
434 | detach(); |
435 | if (!containsIndex(pos)) |
436 | insert(pos, T()); |
437 | return p->array[pos % d->alloc]; |
438 | } |
439 | |
440 | template <typename T> |
441 | inline void QContiguousCache<T>::removeFirst() |
442 | { |
443 | Q_ASSERT(d->count > 0); |
444 | detach(); |
445 | d->count--; |
446 | if (QTypeInfo<T>::isComplex) |
447 | (p->array + d->start)->~T(); |
448 | d->start = (d->start + 1) % d->alloc; |
449 | d->offset++; |
450 | } |
451 | |
452 | template <typename T> |
453 | inline void QContiguousCache<T>::removeLast() |
454 | { |
455 | Q_ASSERT(d->count > 0); |
456 | detach(); |
457 | d->count--; |
458 | if (QTypeInfo<T>::isComplex) |
459 | (p->array + (d->start + d->count) % d->alloc)->~T(); |
460 | } |
461 | |
462 | template <typename T> |
463 | inline T QContiguousCache<T>::takeFirst() |
464 | { T t = first(); removeFirst(); return t; } |
465 | |
466 | template <typename T> |
467 | inline T QContiguousCache<T>::takeLast() |
468 | { T t = last(); removeLast(); return t; } |
469 | |
470 | QT_END_NAMESPACE |
471 | |
472 | QT_END_HEADER |
473 | |
474 | #endif |
475 | |