qlist.cpp

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
** Contact: http://www.qt-project.org/legal
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Digia.  For licensing terms and
** conditions see http://qt.digia.com/licensing.  For further information
** use the contact form at http://qt.digia.com/contact-us.
**
** 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, Digia gives you certain additional
** rights.  These rights are described in the Digia Qt LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3.0 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU General Public License version 3.0 requirements will be
** met: http://www.gnu.org/copyleft/gpl.html.
**
**
** $QT_END_LICENSE$
**
****************************************************************************/

#include <new>
#include "qlist.h"
#include "qtools_p.h"
#include <string.h>

QT_BEGIN_NAMESPACE

/*
    QList as an array-list combines the easy-of-use of a random
    access interface with fast list operations and the low memory
    management overhead of an array. Accessing elements by index,
    appending, prepending, and removing elements from both the front
    and the back all happen in constant time O(1). Inserting or
    removing elements at random index positions \ai happens in linear
    time, or more precisly in O(min{i,n-i}) <= O(n/2), with n being
    the number of elements in the list.
*/

QListData::Data QListData::shared_null = { Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, true, { 0 } };

static int grow(int size)
{
    // dear compiler: don't optimize me out.
    volatile int x = qAllocMore(size * sizeof(void *), QListData::DataHeaderSize) / sizeof(void *);
    return x;
}

QListData::Data *QListData::detach_grow(int *idx, int num)
{
    Data *x = d;
    int l = x->end - x->begin;
    int nl = l + num;
    int alloc = grow(nl);
    Data* t = static_cast<Data *>(qMalloc(DataHeaderSize + alloc * sizeof(void *)));
    Q_CHECK_PTR(t);

    t->ref = 1;
    t->sharable = true;
    t->alloc = alloc;
    // The space reservation algorithm's optimization is biased towards appending:
    // Something which looks like an append will put the data at the beginning,
    // while something which looks like a prepend will put it in the middle
    // instead of at the end. That's based on the assumption that prepending
    // is uncommon and even an initial prepend will eventually be followed by
    // at least some appends.
    int bg;
    if (*idx < 0) {
        *idx = 0;
        bg = (alloc - nl) >> 1;
    } else if (*idx > l) {
        *idx = l;
        bg = 0;
    } else if (*idx < (l >> 1)) {
        bg = (alloc - nl) >> 1;
    } else {
        bg = 0;
    }
    t->begin = bg;
    t->end = bg + nl;
    d = t;

    return x;
}

#if QT_VERSION >= 0x050000
#  error "Remove QListData::detach(), it is only required for binary compatibility for 4.0.x to 4.2.x"
#endif
QListData::Data *QListData::detach()
{
    Data *x = static_cast<Data *>(qMalloc(DataHeaderSize + d->alloc * sizeof(void *)));
    Q_CHECK_PTR(x);

    x->ref = 1;
    x->sharable = true;
    x->alloc = d->alloc;
    if (!x->alloc) {
        x->begin = 0;
        x->end = 0;
    } else {
        x->begin = d->begin;
        x->end   = d->end;
    }

    qSwap(d, x);
    if (!x->ref.deref())
        return x;
    return 0;
}

#if QT_VERSION >= 0x050000
#  error "Remove QListData::detach2(), it is only required for binary compatibility for 4.3.x to 4.5.x"
#endif
QListData::Data *QListData::detach2()
{
    Data *x = d;
    Data* t = static_cast<Data *>(qMalloc(DataHeaderSize + x->alloc * sizeof(void *)));
    Q_CHECK_PTR(t);

    ::memcpy(t, d, DataHeaderSize + d->alloc * sizeof(void *));

    t->ref = 1;
    t->sharable = true;
    t->alloc = x->alloc;
    if (!t->alloc) {
        t->begin = 0;
        t->end = 0;
    } else {
        t->begin = x->begin;
        t->end   = x->end;
    }
    d = t;

    return x;
}

QListData::Data *QListData::detach(int alloc)
{
    Data *x = d;
    Data* t = static_cast<Data *>(qMalloc(DataHeaderSize + alloc * sizeof(void *)));
    Q_CHECK_PTR(t);

    t->ref = 1;
    t->sharable = true;
    t->alloc = alloc;
    if (!alloc) {
        t->begin = 0;
        t->end = 0;
    } else {
        t->begin = x->begin;
        t->end   = x->end;
    }
    d = t;

    return x;
}

#if QT_VERSION >= 0x050000
#  error "Remove QListData::detach3(), it is only required for binary compatibility for 4.5.x to 4.6.x"
#endif
QListData::Data *QListData::detach3()
{
    return detach(d->alloc);
}

void QListData::realloc(int alloc)
{
    Q_ASSERT(d->ref == 1);
    Data *x = static_cast<Data *>(qRealloc(d, DataHeaderSize + alloc * sizeof(void *)));
    Q_CHECK_PTR(x);

    d = x;
    d->alloc = alloc;
    if (!alloc)
        d->begin = d->end = 0;
}

// ensures that enough space is available to append n elements
void **QListData::append(int n)
{
    Q_ASSERT(d->ref == 1);
    int e = d->end;
    if (e + n > d->alloc) {
        int b = d->begin;
        if (b - n >= 2 * d->alloc / 3) {
            // we have enough space. Just not at the end -> move it.
            e -= b;
            ::memmove(d->array, d->array + b, e * sizeof(void *));
            d->begin = 0;
        } else {
            realloc(grow(d->alloc + n));
        }
    }
    d->end = e + n;
    return d->array + e;
}

// ensures that enough space is available to append one element
void **QListData::append()
{
    return append(1);
}

// ensures that enough space is available to append the list
#if QT_VERSION >= 0x050000
#  error "Remove QListData::append(), it is only required for binary compatibility up to 4.5.x"
#endif
void **QListData::append(const QListData& l)
{
    Q_ASSERT(d->ref == 1);
    int e = d->end;
    int n = l.d->end - l.d->begin;
    if (n) {
        if (e + n > d->alloc)
            realloc(grow(e + n));
        ::memcpy(d->array + d->end, l.d->array + l.d->begin, n*sizeof(void*));
        d->end += n;
    }
    return d->array + e;
}

// ensures that enough space is available to append the list
void **QListData::append2(const QListData& l)
{
    return append(l.d->end - l.d->begin);
}

void **QListData::prepend()
{
    Q_ASSERT(d->ref == 1);
    if (d->begin == 0) {
        if (d->end >= d->alloc / 3)
            realloc(grow(d->alloc + 1));

        if (d->end < d->alloc / 3)
            d->begin = d->alloc - 2 * d->end;
        else
            d->begin = d->alloc - d->end;

        ::memmove(d->array + d->begin, d->array, d->end * sizeof(void *));
        d->end += d->begin;
    }
    return d->array + --d->begin;
}

void **QListData::insert(int i)
{
    Q_ASSERT(d->ref == 1);
    if (i <= 0)
        return prepend();
    int size = d->end - d->begin;
    if (i >= size)
        return append();

    bool leftward = false;

    if (d->begin == 0) {
        if (d->end == d->alloc) {
            // If the array is full, we expand it and move some items rightward
            realloc(grow(d->alloc + 1));
        } else {
            // If there is free space at the end of the array, we move some items rightward
        }
    } else {
        if (d->end == d->alloc) {
            // If there is free space at the beginning of the array, we move some items leftward
            leftward = true;
        } else {
            // If there is free space at both ends, we move as few items as possible
            leftward = (i < size - i);
        }
    }

    if (leftward) {
        --d->begin;
        ::memmove(d->array + d->begin, d->array + d->begin + 1, i * sizeof(void *));
    } else {
        ::memmove(d->array + d->begin + i + 1, d->array + d->begin + i,
                  (size - i) * sizeof(void *));
        ++d->end;
    }
    return d->array + d->begin + i;
}

void QListData::remove(int i)
{
    Q_ASSERT(d->ref == 1);
    i += d->begin;
    if (i - d->begin < d->end - i) {
        if (int offset = i - d->begin)
            ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
        d->begin++;
    } else {
        if (int offset = d->end - i - 1)
            ::memmove(d->array + i, d->array + i + 1, offset * sizeof(void *));
        d->end--;
    }
}

void QListData::remove(int i, int n)
{
    Q_ASSERT(d->ref == 1);
    i += d->begin;
    int middle = i + n/2;
    if (middle - d->begin < d->end - middle) {
        ::memmove(d->array + d->begin + n, d->array + d->begin,
                   (i - d->begin) * sizeof(void*));
        d->begin += n;
    } else {
        ::memmove(d->array + i, d->array + i + n,
                   (d->end - i - n) * sizeof(void*));
        d->end -= n;
    }
}

void QListData::move(int from, int to)
{
    Q_ASSERT(d->ref == 1);
    if (from == to)
        return;

    from += d->begin;
    to += d->begin;
    void *t = d->array[from];

    if (from < to) {
        if (d->end == d->alloc || 3 * (to - from) < 2 * (d->end - d->begin)) {
            ::memmove(d->array + from, d->array + from + 1, (to - from) * sizeof(void *));
        } else {
            // optimization
            if (int offset = from - d->begin)
                ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
            if (int offset = d->end - (to + 1))
                ::memmove(d->array + to + 2, d->array + to + 1, offset * sizeof(void *));
            ++d->begin;
            ++d->end;
            ++to;
        }
    } else {
        if (d->begin == 0 || 3 * (from - to) < 2 * (d->end - d->begin)) {
            ::memmove(d->array + to + 1, d->array + to, (from - to) * sizeof(void *));
        } else {
            // optimization
            if (int offset = to - d->begin)
                ::memmove(d->array + d->begin - 1, d->array + d->begin, offset * sizeof(void *));
            if (int offset = d->end - (from + 1))
                ::memmove(d->array + from, d->array + from + 1, offset * sizeof(void *));
            --d->begin;
            --d->end;
            --to;
        }
    }
    d->array[to] = t;
}

void **QListData::erase(void **xi)
{
    Q_ASSERT(d->ref == 1);
    int i = xi - (d->array + d->begin);
    remove(i);
    return d->array + d->begin + i;
}

QT_END_NAMESPACE