QListData Struct Reference

#include <qlist.h>

Collaboration diagram for QListData:

[legend]List of all members.

---

Detailed Description

Definition at line 45 of file qlist.h.

Public Types
enum
Public Member Functions
Data *	detach ()
void	realloc (int alloc)
void **	erase (void **xi)
void **	append ()
void **	append (const QListData &l)
void **	prepend ()
void **	insert (int i)
void	remove (int i)
void	remove (int i, int n)
void	move (int from, int to)
int	size () const
bool	isEmpty () const
void **	at (int i) const
void **	begin () const
void **	end () const
Public Attributes
Data *	d
Static Public Attributes
static Data	shared_null
Classes
struct	Data

---

Member Enumeration Documentation

anonymous enum

Definition at line 52 of file qlist.h.

{ DataHeaderSize = sizeof(Data) - sizeof(void *) };

---

Member Function Documentation

QListData::Data * QListData::detach

(

)

Definition at line 48 of file qlistdata.cpp.

References QListData::Data::alloc, d, DataHeaderSize, qAtomicSetPtr(), qMalloc(), QListData::Data::ref, and x.

Referenced by QList< T >::detach_helper().

{
    Q_ASSERT(d->ref != 1);
    Data *x = static_cast<Data *>(qMalloc(DataHeaderSize + d->alloc * sizeof(void *)));
    ::memcpy(x, d, DataHeaderSize + d->alloc * sizeof(void *));
    x->alloc = d->alloc;
    x->ref.init(1);
    x->sharable = true;
    if (!x->alloc)
        x->begin = x->end = 0;

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

Here is the call graph for this function:

void QListData::realloc

(

int

alloc

)

Definition at line 65 of file qlistdata.cpp.

References QListData::Data::alloc, QListData::Data::begin, d, DataHeaderSize, QListData::Data::end, qRealloc(), and QListData::Data::ref.

Referenced by append(), insert(), and prepend().

{
    Q_ASSERT(d->ref == 1);
    d = static_cast<Data *>(qRealloc(d, DataHeaderSize + alloc * sizeof(void *)));
    d->alloc = alloc;
    if (!alloc)
        d->begin = d->end = 0;
}

Here is the call graph for this function:

void ** QListData::erase

(

void **

xi

)

Definition at line 233 of file qlistdata.cpp.

References QListData::Data::array, QListData::Data::begin, d, i, QListData::Data::ref, and remove().

Referenced by QList< T >::erase().

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

Here is the call graph for this function:

void ** QListData::append

(

)

Definition at line 75 of file qlistdata.cpp.

References QListData::Data::alloc, QListData::Data::array, QListData::Data::begin, d, QListData::Data::end, grow(), n, realloc(), and QListData::Data::ref.

Referenced by QList< T >::append(), insert(), and QList< T >::operator+=().

{
    Q_ASSERT(d->ref == 1);
    if (d->end == d->alloc) {
        int n = d->end - d->begin;
        if (d->begin > 2 * d->alloc / 3) {
            ::memcpy(d->array + n, d->array + d->begin, n * sizeof(void *));
            d->begin = n;
            d->end = n * 2;
        } else {
            realloc(grow(d->alloc + 1));
        }
    }
    return d->array + d->end++;
}

Here is the call graph for this function:

void ** QListData::append

(

const QListData &

l

)

Definition at line 91 of file qlistdata.cpp.

References QListData::Data::alloc, QListData::Data::array, d, QListData::Data::end, grow(), l, n, realloc(), and QListData::Data::ref.

{
    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 + l.d->end - l.d->begin));
        ::memcpy(d->array + d->end, l.d->array + l.d->begin, n * sizeof(void*));
        d->end += n;
    }
    return d->array + e;
}

Here is the call graph for this function:

void ** QListData::prepend

(

)

Definition at line 105 of file qlistdata.cpp.

References QListData::Data::alloc, QListData::Data::array, QListData::Data::begin, d, QListData::Data::end, grow(), realloc(), and QListData::Data::ref.

Referenced by insert(), and QList< T >::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;
}

Here is the call graph for this function:

void ** QListData::insert

(

int

i

)

Definition at line 123 of file qlistdata.cpp.

References QListData::Data::alloc, append(), QListData::Data::array, QListData::Data::begin, d, QListData::Data::end, grow(), prepend(), realloc(), QListData::Data::ref, and size().

Referenced by QList< T >::insert().

{
    Q_ASSERT(d->ref == 1);
    if (i <= 0)
        return prepend();
    if (i >= d->end - d->begin)
        return append();

    bool leftward = false;
    int size = d->end - d->begin;

    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;
}

Here is the call graph for this function:

void QListData::remove

(

int

i

)

Definition at line 162 of file qlistdata.cpp.

References QListData::Data::array, QListData::Data::begin, d, QListData::Data::end, and QListData::Data::ref.

Referenced by erase(), QList< T >::removeAll(), QList< T >::removeAt(), and QList< T >::takeAt().

{
    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
	)

Definition at line 177 of file qlistdata.cpp.

References QListData::Data::array, QListData::Data::begin, d, QListData::Data::end, and QListData::Data::ref.

{
    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
	)

Definition at line 193 of file qlistdata.cpp.

References QListData::Data::alloc, QListData::Data::array, QListData::Data::begin, d, QListData::Data::end, QListData::Data::ref, and t.

Referenced by QList< T >::move().

{
    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;
}

int QListData::size

(

)

const [inline]

Definition at line 66 of file qlist.h.

References d.

Referenced by QList< T >::at(), QList< QPostEvent >::count(), QList< T >::indexOf(), insert(), QList< T >::lastIndexOf(), QList< T >::move(), QList< T >::operator==(), QList< T >::operator[](), QList< T >::removeAll(), QList< T >::removeAt(), QList< T >::replace(), QList< QPostEvent >::size(), QList< T >::swap(), QList< T >::takeAt(), and QList< T >::value().

{ return d->end - d->begin; }

bool QListData::isEmpty

(

)

const [inline]

Definition at line 67 of file qlist.h.

References d.

Referenced by QList< QPostEvent >::isEmpty().

{ return d->end  == d->begin; }

void** QListData::at

(

int

i

)

const [inline]

Definition at line 68 of file qlist.h.

References d.

Referenced by QList< T >::at(), QList< T >::indexOf(), QList< T >::lastIndexOf(), QList< T >::operator[](), QList< T >::removeAll(), QList< T >::removeAt(), QList< T >::replace(), QList< T >::takeAt(), and QList< T >::value().

{ return d->array + d->begin + i; }

void** QListData::begin

(

)

const [inline]

Definition at line 69 of file qlist.h.

References d.

Referenced by QList< QPostEvent >::begin(), QList< QPostEvent >::constBegin(), QList< T >::contains(), QList< T >::count(), QList< T >::detach_helper(), QList< T >::indexOf(), QList< T >::insert(), QList< T >::lastIndexOf(), and QList< T >::operator==().

{ return d->array + d->begin; }

void** QListData::end

(

)

const [inline]

Definition at line 70 of file qlist.h.

References d.

Referenced by QList< QPostEvent >::constEnd(), QList< T >::contains(), QList< T >::count(), QList< T >::detach_helper(), QList< QPostEvent >::end(), QList< T >::indexOf(), QList< T >::operator+=(), and QList< T >::operator==().

{ return d->array + d->end; }

---

Member Data Documentation

QListData::Data QListData::shared_null [static]

Definition at line 56 of file qlist.h.

Referenced by Q3CleanupHandler< T >::add(), and QList< T >::~QList().

Data* QListData::d

Definition at line 57 of file qlist.h.

Referenced by append(), detach(), erase(), insert(), move(), prepend(), realloc(), and remove().

---

The documentation for this struct was generated from the following files:

• src/corelib/tools/qlist.h
• src/corelib/tools/qlistdata.cpp

---