diff -r 000000000000 -r 1918ee327afb src/corelib/tools/qcontiguouscache.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/corelib/tools/qcontiguouscache.h	Mon Jan 11 14:00:40 2010 +0000
@@ -0,0 +1,437 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QCONTIGUOUSCACHE_H
+#define QCONTIGUOUSCACHE_H
+
+#include <QtCore/qatomic.h>
+#include <limits.h>
+#include <new>
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+#undef QT_QCONTIGUOUSCACHE_DEBUG
+QT_MODULE(Core)
+
+
+struct Q_CORE_EXPORT QContiguousCacheData
+{
+    QBasicAtomicInt ref;
+    int alloc;
+    int count;
+    int start;
+    int offset;
+    uint sharable : 1;
+
+#ifdef QT_QCONTIGUOUSCACHE_DEBUG
+    void dump() const;
+#endif
+};
+
+template <typename T>
+struct QContiguousCacheTypedData
+{
+    QBasicAtomicInt ref;
+    int alloc;
+    int count;
+    int start;
+    int offset;
+    uint sharable : 1;
+    // uint unused : 31;
+
+    // total is 24 bytes (HP-UX aCC: 40 bytes)
+    // the next entry is already aligned to 8 bytes
+    // there will be an 8 byte gap here if T requires 16-byte alignment
+    //  (such as long double on 64-bit platforms, __int128, __float128)
+
+    T array[1];
+};
+
+template<typename T>
+class QContiguousCache {
+    typedef QContiguousCacheTypedData<T> Data;
+    union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; };
+public:
+    explicit QContiguousCache(int capacity = 0);
+    QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
+
+    inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(d); }
+
+    inline void detach() { if (d->ref != 1) detach_helper(); }
+    inline bool isDetached() const { return d->ref == 1; }
+    inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
+
+    QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
+    bool operator==(const QContiguousCache<T> &other) const;
+    inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); }
+
+    inline int capacity() const {return d->alloc; }
+    inline int count() const { return d->count; }
+    inline int size() const { return d->count; }
+
+    inline bool isEmpty() const { return d->count == 0; }
+    inline bool isFull() const { return d->count == d->alloc; }
+    inline int available() const { return d->alloc - d->count; }
+
+    void clear();
+    void setCapacity(int size);
+
+    const T &at(int pos) const;
+    T &operator[](int i);
+    const T &operator[](int i) const;
+
+    void append(const T &value);
+    void prepend(const T &value);
+    void insert(int pos, const T &value);
+
+    inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; }
+    inline int firstIndex() const { return d->offset; }
+    inline int lastIndex() const { return d->offset + d->count - 1; }
+
+    inline const T &first() const { Q_ASSERT(!isEmpty()); return d->array[d->start]; }
+    inline const T &last() const { Q_ASSERT(!isEmpty()); return d->array[(d->start + d->count -1) % d->alloc]; }
+    inline T &first() { Q_ASSERT(!isEmpty()); detach(); return d->array[d->start]; }
+    inline T &last() { Q_ASSERT(!isEmpty()); detach(); return d->array[(d->start + d->count -1) % d->alloc]; }
+
+    void removeFirst();
+    T takeFirst();
+    void removeLast();
+    T takeLast();
+
+    inline bool areIndexesValid() const
+    { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }
+
+    inline void normalizeIndexes() { d->offset = d->start; }
+
+#ifdef QT_QCONTIGUOUSCACHE_DEBUG
+    void dump() const { p->dump(); }
+#endif
+private:
+    void detach_helper();
+
+    QContiguousCacheData *malloc(int aalloc);
+    void free(Data *x);
+    int sizeOfTypedData() {
+        // this is more or less the same as sizeof(Data), except that it doesn't
+        // count the padding at the end
+        return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
+    }
+};
+
+template <typename T>
+void QContiguousCache<T>::detach_helper()
+{
+    union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+
+    x.p = malloc(d->alloc);
+    x.d->ref = 1;
+    x.d->count = d->count;
+    x.d->start = d->start;
+    x.d->offset = d->offset;
+    x.d->alloc = d->alloc;
+    x.d->sharable = true;
+
+    T *dest = x.d->array + x.d->start;
+    T *src = d->array + d->start;
+    int oldcount = x.d->count;
+    while (oldcount--) {
+        if (QTypeInfo<T>::isComplex) {
+            new (dest) T(*src);
+        } else {
+            *dest = *src;
+        }
+        dest++;
+        if (dest == x.d->array + x.d->alloc)
+            dest = x.d->array;
+        src++;
+        if (src == d->array + d->alloc)
+            src = d->array;
+    }
+
+    if (!d->ref.deref())
+        free(d);
+    d = x.d;
+}
+
+template <typename T>
+void QContiguousCache<T>::setCapacity(int asize)
+{
+    if (asize == d->alloc)
+        return;
+    detach();
+    union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+    x.p = malloc(asize);
+    x.d->alloc = asize;
+    x.d->count = qMin(d->count, asize);
+    x.d->offset = d->offset + d->count - x.d->count;
+    x.d->start = x.d->offset % x.d->alloc;
+    T *dest = x.d->array + (x.d->start + x.d->count-1) % x.d->alloc;
+    T *src = d->array + (d->start + d->count-1) % d->alloc;
+    int oldcount = x.d->count;
+    while (oldcount--) {
+        if (QTypeInfo<T>::isComplex) {
+            new (dest) T(*src);
+        } else {
+            *dest = *src;
+        }
+        if (dest == x.d->array)
+            dest = x.d->array + x.d->alloc;
+        dest--;
+        if (src == d->array)
+            src = d->array + d->alloc;
+        src--;
+    }
+    /* free old */
+    free(d);
+    d = x.d;
+}
+
+template <typename T>
+void QContiguousCache<T>::clear()
+{
+    if (d->ref == 1) {
+        if (QTypeInfo<T>::isComplex) {
+            int oldcount = d->count;
+            T * i = d->array + d->start;
+            T * e = d->array + d->alloc;
+            while (oldcount--) {
+                i->~T();
+                i++;
+                if (i == e)
+                    i = d->array;
+            }
+        }
+        d->count = d->start = d->offset = 0;
+    } else {
+        union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;
+        x.p = malloc(d->alloc);
+        x.d->ref = 1;
+        x.d->alloc = d->alloc;
+        x.d->count = x.d->start = x.d->offset = 0;
+        x.d->sharable = true;
+        if (!d->ref.deref()) free(d);
+        d = x.d;
+    }
+}
+
+template <typename T>
+inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)
+{
+    return static_cast<QContiguousCacheData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T)));
+}
+
+template <typename T>
+QContiguousCache<T>::QContiguousCache(int cap)
+{
+    p = malloc(cap);
+    d->ref = 1;
+    d->alloc = cap;
+    d->count = d->start = d->offset = 0;
+    d->sharable = true;
+}
+
+template <typename T>
+QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
+{
+    other.d->ref.ref();
+    if (!d->ref.deref())
+        free(d);
+    d = other.d;
+    if (!d->sharable)
+        detach_helper();
+    return *this;
+}
+
+template <typename T>
+bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
+{
+    if (other.d == d)
+        return true;
+    if (other.d->start != d->start
+            || other.d->count != d->count
+            || other.d->offset != d->offset
+            || other.d->alloc != d->alloc)
+        return false;
+    for (int i = firstIndex(); i <= lastIndex(); ++i)
+        if (!(at(i) == other.at(i)))
+            return false;
+    return true;
+}
+
+template <typename T>
+void QContiguousCache<T>::free(Data *x)
+{
+    if (QTypeInfo<T>::isComplex) {
+        int oldcount = d->count;
+        T * i = d->array + d->start;
+        T * e = d->array + d->alloc;
+        while (oldcount--) {
+            i->~T();
+            i++;
+            if (i == e)
+                i = d->array;
+        }
+    }
+    qFree(x);
+}
+template <typename T>
+void QContiguousCache<T>::append(const T &value)
+{
+    detach();
+    if (QTypeInfo<T>::isComplex) {
+        if (d->count == d->alloc)
+            (d->array + (d->start+d->count) % d->alloc)->~T();
+        new (d->array + (d->start+d->count) % d->alloc) T(value);
+    } else {
+        d->array[(d->start+d->count) % d->alloc] = value;
+    }
+
+    if (d->count == d->alloc) {
+        d->start++;
+        d->start %= d->alloc;
+        d->offset++;
+    } else {
+        d->count++;
+    }
+}
+
+template<typename T>
+void QContiguousCache<T>::prepend(const T &value)
+{
+    detach();
+    if (d->start)
+        d->start--;
+    else
+        d->start = d->alloc-1;
+    d->offset--;
+
+    if (d->count != d->alloc)
+        d->count++;
+    else
+        if (d->count == d->alloc)
+            (d->array + d->start)->~T();
+
+    if (QTypeInfo<T>::isComplex)
+        new (d->array + d->start) T(value);
+    else
+        d->array[d->start] = value;
+}
+
+template<typename T>
+void QContiguousCache<T>::insert(int pos, const T &value)
+{
+    Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");
+    detach();
+    if (containsIndex(pos)) {
+        if(QTypeInfo<T>::isComplex)
+            new (d->array + pos % d->alloc) T(value);
+        else
+            d->array[pos % d->alloc] = value;
+    } else if (pos == d->offset-1)
+        prepend(value);
+    else if (pos == d->offset+d->count)
+        append(value);
+    else {
+        // we don't leave gaps.
+        clear();
+        d->offset = pos;
+        d->start = pos % d->alloc;
+        d->count = 1;
+        if (QTypeInfo<T>::isComplex)
+            new (d->array + d->start) T(value);
+        else
+            d->array[d->start] = value;
+    }
+}
+
+template <typename T>
+inline const T &QContiguousCache<T>::at(int pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
+template <typename T>
+inline const T &QContiguousCache<T>::operator[](int pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
+
+template <typename T>
+inline T &QContiguousCache<T>::operator[](int pos)
+{
+    detach();
+    if (!containsIndex(pos))
+        insert(pos, T());
+    return d->array[pos % d->alloc];
+}
+
+template <typename T>
+inline void QContiguousCache<T>::removeFirst()
+{
+    Q_ASSERT(d->count > 0);
+    detach();
+    d->count--;
+    if (QTypeInfo<T>::isComplex)
+        (d->array + d->start)->~T();
+    d->start = (d->start + 1) % d->alloc;
+    d->offset++;
+}
+
+template <typename T>
+inline void QContiguousCache<T>::removeLast()
+{
+    Q_ASSERT(d->count > 0);
+    detach();
+    d->count--;
+    if (QTypeInfo<T>::isComplex)
+        (d->array + (d->start + d->count) % d->alloc)->~T();
+}
+
+template <typename T>
+inline T QContiguousCache<T>::takeFirst()
+{ T t = first(); removeFirst(); return t; }
+
+template <typename T>
+inline T QContiguousCache<T>::takeLast()
+{ T t = last(); removeLast(); return t; }
+
+QT_END_NAMESPACE
+
+QT_END_HEADER
+
+#endif