60 int alloc; |
60 int alloc; |
61 int count; |
61 int count; |
62 int start; |
62 int start; |
63 int offset; |
63 int offset; |
64 uint sharable : 1; |
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); |
65 |
74 |
66 #ifdef QT_QCONTIGUOUSCACHE_DEBUG |
75 #ifdef QT_QCONTIGUOUSCACHE_DEBUG |
67 void dump() const; |
76 void dump() const; |
68 #endif |
77 #endif |
69 }; |
78 }; |
70 |
79 |
71 template <typename T> |
80 template <typename T> |
72 struct QContiguousCacheTypedData |
81 struct QContiguousCacheTypedData: private QContiguousCacheData |
73 { |
82 { |
74 QBasicAtomicInt ref; |
83 // private inheritance to avoid aliasing warningss |
75 int alloc; |
|
76 int count; |
|
77 int start; |
|
78 int offset; |
|
79 uint sharable : 1; |
|
80 // uint unused : 31; |
|
81 |
|
82 // total is 24 bytes (HP-UX aCC: 40 bytes) |
|
83 // the next entry is already aligned to 8 bytes |
|
84 // there will be an 8 byte gap here if T requires 16-byte alignment |
|
85 // (such as long double on 64-bit platforms, __int128, __float128) |
|
86 |
|
87 T array[1]; |
84 T array[1]; |
|
85 |
|
86 static inline void free(QContiguousCacheTypedData *data) { QContiguousCacheData::free(data); } |
88 }; |
87 }; |
89 |
88 |
90 template<typename T> |
89 template<typename T> |
91 class QContiguousCache { |
90 class QContiguousCache { |
92 typedef QContiguousCacheTypedData<T> Data; |
91 typedef QContiguousCacheTypedData<T> Data; |
93 union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; }; |
92 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; }; |
94 public: |
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 ptrdiff_t difference_type; |
|
101 typedef int size_type; |
|
102 |
95 explicit QContiguousCache(int capacity = 0); |
103 explicit QContiguousCache(int capacity = 0); |
96 QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } |
104 QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } |
97 |
105 |
98 inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(d); } |
106 inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(p); } |
99 |
107 |
100 inline void detach() { if (d->ref != 1) detach_helper(); } |
108 inline void detach() { if (d->ref != 1) detach_helper(); } |
101 inline bool isDetached() const { return d->ref == 1; } |
109 inline bool isDetached() const { return d->ref == 1; } |
102 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
110 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
103 |
111 |
154 int sizeOfTypedData() { |
162 int sizeOfTypedData() { |
155 // this is more or less the same as sizeof(Data), except that it doesn't |
163 // this is more or less the same as sizeof(Data), except that it doesn't |
156 // count the padding at the end |
164 // count the padding at the end |
157 return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this); |
165 return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this); |
158 } |
166 } |
|
167 int alignOfTypedData() const |
|
168 { |
|
169 #ifdef Q_ALIGNOF |
|
170 return qMax<int>(sizeof(void*), Q_ALIGNOF(Data)); |
|
171 #else |
|
172 return 0; |
|
173 #endif |
|
174 } |
159 }; |
175 }; |
160 |
176 |
161 template <typename T> |
177 template <typename T> |
162 void QContiguousCache<T>::detach_helper() |
178 void QContiguousCache<T>::detach_helper() |
163 { |
179 { |
164 union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x; |
180 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
165 |
181 |
166 x.p = malloc(d->alloc); |
182 x.d = malloc(d->alloc); |
167 x.d->ref = 1; |
183 x.d->ref = 1; |
168 x.d->count = d->count; |
184 x.d->count = d->count; |
169 x.d->start = d->start; |
185 x.d->start = d->start; |
170 x.d->offset = d->offset; |
186 x.d->offset = d->offset; |
171 x.d->alloc = d->alloc; |
187 x.d->alloc = d->alloc; |
172 x.d->sharable = true; |
188 x.d->sharable = true; |
173 |
189 x.d->reserved = 0; |
174 T *dest = x.d->array + x.d->start; |
190 |
175 T *src = d->array + d->start; |
191 T *dest = x.p->array + x.d->start; |
|
192 T *src = p->array + d->start; |
176 int oldcount = x.d->count; |
193 int oldcount = x.d->count; |
177 while (oldcount--) { |
194 while (oldcount--) { |
178 if (QTypeInfo<T>::isComplex) { |
195 if (QTypeInfo<T>::isComplex) { |
179 new (dest) T(*src); |
196 new (dest) T(*src); |
180 } else { |
197 } else { |
181 *dest = *src; |
198 *dest = *src; |
182 } |
199 } |
183 dest++; |
200 dest++; |
184 if (dest == x.d->array + x.d->alloc) |
201 if (dest == x.p->array + x.d->alloc) |
185 dest = x.d->array; |
202 dest = x.p->array; |
186 src++; |
203 src++; |
187 if (src == d->array + d->alloc) |
204 if (src == p->array + d->alloc) |
188 src = d->array; |
205 src = p->array; |
189 } |
206 } |
190 |
207 |
191 if (!d->ref.deref()) |
208 if (!d->ref.deref()) |
192 free(d); |
209 free(p); |
193 d = x.d; |
210 d = x.d; |
194 } |
211 } |
195 |
212 |
196 template <typename T> |
213 template <typename T> |
197 void QContiguousCache<T>::setCapacity(int asize) |
214 void QContiguousCache<T>::setCapacity(int asize) |
198 { |
215 { |
199 if (asize == d->alloc) |
216 if (asize == d->alloc) |
200 return; |
217 return; |
201 detach(); |
218 detach(); |
202 union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x; |
219 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
203 x.p = malloc(asize); |
220 x.d = malloc(asize); |
204 x.d->alloc = asize; |
221 x.d->alloc = asize; |
205 x.d->count = qMin(d->count, asize); |
222 x.d->count = qMin(d->count, asize); |
206 x.d->offset = d->offset + d->count - x.d->count; |
223 x.d->offset = d->offset + d->count - x.d->count; |
207 x.d->start = x.d->offset % x.d->alloc; |
224 x.d->start = x.d->offset % x.d->alloc; |
208 T *dest = x.d->array + (x.d->start + x.d->count-1) % x.d->alloc; |
225 T *dest = x.p->array + (x.d->start + x.d->count-1) % x.d->alloc; |
209 T *src = d->array + (d->start + d->count-1) % d->alloc; |
226 T *src = p->array + (d->start + d->count-1) % d->alloc; |
210 int oldcount = x.d->count; |
227 int oldcount = x.d->count; |
211 while (oldcount--) { |
228 while (oldcount--) { |
212 if (QTypeInfo<T>::isComplex) { |
229 if (QTypeInfo<T>::isComplex) { |
213 new (dest) T(*src); |
230 new (dest) T(*src); |
214 } else { |
231 } else { |
215 *dest = *src; |
232 *dest = *src; |
216 } |
233 } |
217 if (dest == x.d->array) |
234 if (dest == x.p->array) |
218 dest = x.d->array + x.d->alloc; |
235 dest = x.p->array + x.d->alloc; |
219 dest--; |
236 dest--; |
220 if (src == d->array) |
237 if (src == p->array) |
221 src = d->array + d->alloc; |
238 src = p->array + d->alloc; |
222 src--; |
239 src--; |
223 } |
240 } |
224 /* free old */ |
241 /* free old */ |
225 free(d); |
242 free(p); |
226 d = x.d; |
243 d = x.d; |
227 } |
244 } |
228 |
245 |
229 template <typename T> |
246 template <typename T> |
230 void QContiguousCache<T>::clear() |
247 void QContiguousCache<T>::clear() |
231 { |
248 { |
232 if (d->ref == 1) { |
249 if (d->ref == 1) { |
233 if (QTypeInfo<T>::isComplex) { |
250 if (QTypeInfo<T>::isComplex) { |
234 int oldcount = d->count; |
251 int oldcount = d->count; |
235 T * i = d->array + d->start; |
252 T * i = p->array + d->start; |
236 T * e = d->array + d->alloc; |
253 T * e = p->array + d->alloc; |
237 while (oldcount--) { |
254 while (oldcount--) { |
238 i->~T(); |
255 i->~T(); |
239 i++; |
256 i++; |
240 if (i == e) |
257 if (i == e) |
241 i = d->array; |
258 i = p->array; |
242 } |
259 } |
243 } |
260 } |
244 d->count = d->start = d->offset = 0; |
261 d->count = d->start = d->offset = 0; |
245 } else { |
262 } else { |
246 union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x; |
263 union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
247 x.p = malloc(d->alloc); |
264 x.d = malloc(d->alloc); |
248 x.d->ref = 1; |
265 x.d->ref = 1; |
249 x.d->alloc = d->alloc; |
266 x.d->alloc = d->alloc; |
250 x.d->count = x.d->start = x.d->offset = 0; |
267 x.d->count = x.d->start = x.d->offset = 0; |
251 x.d->sharable = true; |
268 x.d->sharable = true; |
252 if (!d->ref.deref()) free(d); |
269 if (!d->ref.deref()) free(p); |
253 d = x.d; |
270 d = x.d; |
254 } |
271 } |
255 } |
272 } |
256 |
273 |
257 template <typename T> |
274 template <typename T> |
258 inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc) |
275 inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc) |
259 { |
276 { |
260 return static_cast<QContiguousCacheData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T))); |
277 return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); |
261 } |
278 } |
262 |
279 |
263 template <typename T> |
280 template <typename T> |
264 QContiguousCache<T>::QContiguousCache(int cap) |
281 QContiguousCache<T>::QContiguousCache(int cap) |
265 { |
282 { |
266 p = malloc(cap); |
283 d = malloc(cap); |
267 d->ref = 1; |
284 d->ref = 1; |
268 d->alloc = cap; |
285 d->alloc = cap; |
269 d->count = d->start = d->offset = 0; |
286 d->count = d->start = d->offset = 0; |
270 d->sharable = true; |
287 d->sharable = true; |
271 } |
288 } |
301 template <typename T> |
318 template <typename T> |
302 void QContiguousCache<T>::free(Data *x) |
319 void QContiguousCache<T>::free(Data *x) |
303 { |
320 { |
304 if (QTypeInfo<T>::isComplex) { |
321 if (QTypeInfo<T>::isComplex) { |
305 int oldcount = d->count; |
322 int oldcount = d->count; |
306 T * i = d->array + d->start; |
323 T * i = p->array + d->start; |
307 T * e = d->array + d->alloc; |
324 T * e = p->array + d->alloc; |
308 while (oldcount--) { |
325 while (oldcount--) { |
309 i->~T(); |
326 i->~T(); |
310 i++; |
327 i++; |
311 if (i == e) |
328 if (i == e) |
312 i = d->array; |
329 i = p->array; |
313 } |
330 } |
314 } |
331 } |
315 qFree(x); |
332 x->free(x); |
316 } |
333 } |
317 template <typename T> |
334 template <typename T> |
318 void QContiguousCache<T>::append(const T &value) |
335 void QContiguousCache<T>::append(const T &value) |
319 { |
336 { |
320 detach(); |
337 detach(); |
321 if (QTypeInfo<T>::isComplex) { |
338 if (QTypeInfo<T>::isComplex) { |
322 if (d->count == d->alloc) |
339 if (d->count == d->alloc) |
323 (d->array + (d->start+d->count) % d->alloc)->~T(); |
340 (p->array + (d->start+d->count) % d->alloc)->~T(); |
324 new (d->array + (d->start+d->count) % d->alloc) T(value); |
341 new (p->array + (d->start+d->count) % d->alloc) T(value); |
325 } else { |
342 } else { |
326 d->array[(d->start+d->count) % d->alloc] = value; |
343 p->array[(d->start+d->count) % d->alloc] = value; |
327 } |
344 } |
328 |
345 |
329 if (d->count == d->alloc) { |
346 if (d->count == d->alloc) { |
330 d->start++; |
347 d->start++; |
331 d->start %= d->alloc; |
348 d->start %= d->alloc; |
347 |
364 |
348 if (d->count != d->alloc) |
365 if (d->count != d->alloc) |
349 d->count++; |
366 d->count++; |
350 else |
367 else |
351 if (d->count == d->alloc) |
368 if (d->count == d->alloc) |
352 (d->array + d->start)->~T(); |
369 (p->array + d->start)->~T(); |
353 |
370 |
354 if (QTypeInfo<T>::isComplex) |
371 if (QTypeInfo<T>::isComplex) |
355 new (d->array + d->start) T(value); |
372 new (p->array + d->start) T(value); |
356 else |
373 else |
357 d->array[d->start] = value; |
374 p->array[d->start] = value; |
358 } |
375 } |
359 |
376 |
360 template<typename T> |
377 template<typename T> |
361 void QContiguousCache<T>::insert(int pos, const T &value) |
378 void QContiguousCache<T>::insert(int pos, const T &value) |
362 { |
379 { |
363 Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range"); |
380 Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range"); |
364 detach(); |
381 detach(); |
365 if (containsIndex(pos)) { |
382 if (containsIndex(pos)) { |
366 if(QTypeInfo<T>::isComplex) |
383 if(QTypeInfo<T>::isComplex) |
367 new (d->array + pos % d->alloc) T(value); |
384 new (p->array + pos % d->alloc) T(value); |
368 else |
385 else |
369 d->array[pos % d->alloc] = value; |
386 p->array[pos % d->alloc] = value; |
370 } else if (pos == d->offset-1) |
387 } else if (pos == d->offset-1) |
371 prepend(value); |
388 prepend(value); |
372 else if (pos == d->offset+d->count) |
389 else if (pos == d->offset+d->count) |
373 append(value); |
390 append(value); |
374 else { |
391 else { |
376 clear(); |
393 clear(); |
377 d->offset = pos; |
394 d->offset = pos; |
378 d->start = pos % d->alloc; |
395 d->start = pos % d->alloc; |
379 d->count = 1; |
396 d->count = 1; |
380 if (QTypeInfo<T>::isComplex) |
397 if (QTypeInfo<T>::isComplex) |
381 new (d->array + d->start) T(value); |
398 new (p->array + d->start) T(value); |
382 else |
399 else |
383 d->array[d->start] = value; |
400 p->array[d->start] = value; |
384 } |
401 } |
385 } |
402 } |
386 |
403 |
387 template <typename T> |
404 template <typename T> |
388 inline const T &QContiguousCache<T>::at(int pos) const |
405 inline const T &QContiguousCache<T>::at(int pos) const |
389 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; } |
406 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; } |
390 template <typename T> |
407 template <typename T> |
391 inline const T &QContiguousCache<T>::operator[](int pos) const |
408 inline const T &QContiguousCache<T>::operator[](int pos) const |
392 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; } |
409 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; } |
393 |
410 |
394 template <typename T> |
411 template <typename T> |
395 inline T &QContiguousCache<T>::operator[](int pos) |
412 inline T &QContiguousCache<T>::operator[](int pos) |
396 { |
413 { |
397 detach(); |
414 detach(); |
398 if (!containsIndex(pos)) |
415 if (!containsIndex(pos)) |
399 insert(pos, T()); |
416 insert(pos, T()); |
400 return d->array[pos % d->alloc]; |
417 return p->array[pos % d->alloc]; |
401 } |
418 } |
402 |
419 |
403 template <typename T> |
420 template <typename T> |
404 inline void QContiguousCache<T>::removeFirst() |
421 inline void QContiguousCache<T>::removeFirst() |
405 { |
422 { |
406 Q_ASSERT(d->count > 0); |
423 Q_ASSERT(d->count > 0); |
407 detach(); |
424 detach(); |
408 d->count--; |
425 d->count--; |
409 if (QTypeInfo<T>::isComplex) |
426 if (QTypeInfo<T>::isComplex) |
410 (d->array + d->start)->~T(); |
427 (p->array + d->start)->~T(); |
411 d->start = (d->start + 1) % d->alloc; |
428 d->start = (d->start + 1) % d->alloc; |
412 d->offset++; |
429 d->offset++; |
413 } |
430 } |
414 |
431 |
415 template <typename T> |
432 template <typename T> |