QListData Struct Reference

#include <qlist.h>

Classes
struct	Data

Public Types
enum	{ DataHeaderSize = sizeof(Data) - sizeof(void *) }

Public Functions
void **	append (int n)
void **	append ()
void **	append (const QListData &l)
void **	append2 (const QListData &l)
void **	at (int i) const
void **	begin () const
Data *	detach (int alloc)
	Detaches the QListData by allocating new memory for a list which possibly has a different size than the copied one. More...
Data *	detach ()
Data *	detach2 ()
	Detaches the QListData by reallocating new memory. More...
Data *	detach3 ()
	Detaches the QListData by reallocating new memory. More...
Data *	detach_grow (int *i, int n)
	Detaches the QListData by allocating new memory for a list which will be bigger than the copied one and is expected to grow further. More...
void **	end () const
void **	erase (void **xi)
void **	insert (int i)
bool	isEmpty () const
void	move (int from, int to)
void **	prepend ()
void	realloc (int alloc)
void	remove (int i)
void	remove (int i, int n)
int	size () const

Public Variables
Data *	d

Static Public Variables
static Data	shared_null = { Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, true, { 0 } }

Detailed Description

Definition at line 71 of file qlist.h.

Enumerations

anonymous enum

anonymous enum

Enumerator
DataHeaderSize

Definition at line 78 of file qlist.h.

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

Functions

append() [1/3]

void ** QListData::append

(

int

n

)

Definition at line 231 of file qlist.cpp.

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

append() [2/3]

void ** QListData::append

(

)

Definition at line 251 of file qlist.cpp.

Referenced by append2(), and insert().

{
    return append(1);
}

append() [3/3]

void ** QListData::append

(

const QListData &

l

)

Definition at line 260 of file qlist.cpp.

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

append2()

void ** QListData::append2

(

const QListData &

l

)

Definition at line 275 of file qlist.cpp.

{
    return append(l.d->end - l.d->begin);
}

at()

void** QListData::at ( int  i ) const

inline

Definition at line 100 of file qlist.h.

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

begin()

void** QListData::begin ( ) const

inline

Definition at line 101 of file qlist.h.

Referenced by QList< QPostEvent >::mid(), and QList< QPostEvent >::operator+=().

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

detach() [1/2]

QListData::Data * QListData::detach

(

int

alloc

)

Detaches the QListData by allocating new memory for a list which possibly has a different size than the copied one.

Returns the old (shared) data, it is up to the caller to deref() and free() For the new data node_copy needs to be called.

Warning

This function is not part of the public interface.

Definition at line 182 of file qlist.cpp.

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

detach() [2/2]

QListData::Data * QListData::detach

(

)

Definition at line 119 of file qlist.cpp.

Referenced by detach3().

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

detach2()

QListData::Data * QListData::detach2

(

)

Detaches the QListData by reallocating new memory.

Returns the old (shared) data, it is up to the caller to deref() and free() For the new data node_copy needs to be called.

Warning

This function is not part of the public interface.

Definition at line 151 of file qlist.cpp.

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

detach3()

QListData::Data * QListData::detach3

(

)

Detaches the QListData by reallocating new memory.

Returns the old (shared) data, it is up to the caller to deref() and free() For the new data node_copy needs to be called.

Warning

This function is not part of the public interface.

Definition at line 213 of file qlist.cpp.

{
    return detach(d->alloc);
}

detach_grow()

QListData::Data * QListData::detach_grow	(	int *	idx,
		int	num
	)

Detaches the QListData by allocating new memory for a list which will be bigger than the copied one and is expected to grow further.

*idx is the desired insertion point and is clamped to the actual size of the list. num is the number of new elements to insert at the insertion point. Returns the old (shared) data, it is up to the caller to deref() and free(). For the new data node_copy needs to be called.

Warning

This function is not part of the public interface.

Definition at line 79 of file qlist.cpp.

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

end()

void** QListData::end ( ) const

inline

Definition at line 102 of file qlist.h.

Referenced by QList< QPostEvent >::mid(), and QList< QPostEvent >::operator==().

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

erase()

void ** QListData::erase

(

void **

xi

)

Definition at line 408 of file qlist.cpp.

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

insert()

void ** QListData::insert

(

int

i

)

Definition at line 298 of file qlist.cpp.

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

isEmpty()

bool QListData::isEmpty ( ) const

inline

Definition at line 99 of file qlist.h.

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

move()

void QListData::move	(	int	from,
		int	to
	)

Definition at line 368 of file qlist.cpp.

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

prepend()

void ** QListData::prepend

(

)

Definition at line 280 of file qlist.cpp.

Referenced by insert().

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

realloc()

void QListData::realloc

(

int

alloc

)

Definition at line 218 of file qlist.cpp.

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

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

remove() [1/2]

void QListData::remove

(

int

i

)

Definition at line 337 of file qlist.cpp.

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

remove() [2/2]

void QListData::remove	(	int	i,
		int	n
	)

Definition at line 352 of file qlist.cpp.

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

size()

int QListData::size ( ) const

inline

Definition at line 98 of file qlist.h.

Referenced by insert(), and QList< QPostEvent >::operator==().

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

Properties

d

Data* QListData::d

Definition at line 87 of file qlist.h.

Referenced by append(), append2(), detach(), detach2(), detach3(), detach_grow(), erase(), insert(), move(), prepend(), realloc(), and remove().

shared_null

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

static

Definition at line 86 of file qlist.h.

Referenced by QList< QPostEvent >::detachShared(), and QList< QPostEvent >::swap().

---

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

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