QMapData Struct Reference

#include <qmap.h>

Classes
struct	Node

Public Types
enum	{ LastLevel = 11, Sparseness = 3 }

Public Functions
void	continueFreeData (int offset)
Node *	node_create (Node *update[], int offset)
Node *	node_create (Node *update[], int offset, int alignment)
	Creates a new node inside the data structure. More...
void	node_delete (Node *update[], int offset, Node *node)

Static Public Functions
static QMapData *	createData ()
static QMapData *	createData (int alignment)

Public Variables
QMapData *	backward
QMapData *	forward [QMapData::LastLevel+1]
uint	insertInOrder: 1
uint	randomBits
QBasicAtomicInt	ref
uint	reserved: 29
uint	sharable: 1
int	size
uint	strictAlignment: 1
int	topLevel

Static Public Variables
static QMapData	shared_null

Detailed Description

Definition at line 61 of file qmap.h.

Enumerations

anonymous enum

anonymous enum

Enumerator
LastLevel
Sparseness

Definition at line 67 of file qmap.h.

{ LastLevel = 11, Sparseness = 3 };

Functions

continueFreeData()

void QMapData::continueFreeData

(

int

offset

)

Definition at line 82 of file qmap.cpp.

Referenced by QMap< int, QFrameInfo >::freeData().

{
    Node *e = reinterpret_cast<Node *>(this);
    Node *cur = e->forward[0];
    Node *prev;
    while (cur != e) {
        prev = cur;
        cur = cur->forward[0];
        if (strictAlignment)
            qFreeAligned(reinterpret_cast<char *>(prev) - offset);
        else
            qFree(reinterpret_cast<char *>(prev) - offset);
    }
    delete this;
}

createData() [1/2]

QMapData * QMapData::createData ( )

static

Definition at line 59 of file qmap.cpp.

Referenced by QMap< int, QFrameInfo >::detach_helper(), and QMap< int, QFrameInfo >::operator==().

{
    return createData(0);
}

createData() [2/2]

QMapData * QMapData::createData ( int  alignment )

static

Definition at line 64 of file qmap.cpp.

{
    QMapData *d = new QMapData;
    Q_CHECK_PTR(d);
    Node *e = reinterpret_cast<Node *>(d);
    e->backward = e;
    e->forward[0] = e;
    d->ref = 1;
    d->topLevel = 0;
    d->size = 0;
    d->randomBits = 0;
    d->insertInOrder = false;
    d->sharable = true;
    d->strictAlignment = alignment > 8;
    d->reserved = 0;
    return d;
}

node_create() [1/2]

QMapData::Node * QMapData::node_create	(	Node *	update[],
		int	offset
	)

Definition at line 98 of file qmap.cpp.

Referenced by QMap< int, QFrameInfo >::node_create().

{
    return node_create(update, offset, 0);
}

node_create() [2/2]

QMapData::Node * QMapData::node_create	(	Node *	update[],
		int	offset,
		int	alignment
	)

Creates a new node inside the data structure.

update is an array with pointers to the node after which the new node should be inserted. Because of the strange skip list data structure there could be several pointers to this node on different levels. offset is an amount of bytes that needs to reserved just before the QMapData::Node structure.

alignment dictates the alignment for the data.

Warning

This function is not part of the public interface.

Since

4.6

Definition at line 117 of file qmap.cpp.

{
    int level = 0;
    uint mask = (1 << Sparseness) - 1;

    while ((randomBits & mask) == mask && level < LastLevel) {
        ++level;
        mask <<= Sparseness;
    }

    if (level > topLevel) {
        Node *e = reinterpret_cast<Node *>(this);
        level = ++topLevel;
        e->forward[level] = e;
        update[level] = e;
    }

    ++randomBits;
    if (level == 3 && !insertInOrder)
        randomBits = qrand();

    void *concreteNode = strictAlignment ?
                         qMallocAligned(offset + sizeof(Node) + level * sizeof(Node *), alignment) :
                         qMalloc(offset + sizeof(Node) + level * sizeof(Node *));
    Q_CHECK_PTR(concreteNode);

    Node *abstractNode = reinterpret_cast<Node *>(reinterpret_cast<char *>(concreteNode) + offset);

    abstractNode->backward = update[0];
    update[0]->forward[0]->backward = abstractNode;

    for (int i = level; i >= 0; i--) {
        abstractNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = abstractNode;
        update[i] = abstractNode;
    }
    ++size;
    return abstractNode;
}

node_delete()

void QMapData::node_delete	(	Node *	update[],
		int	offset,
		Node *	node
	)

Definition at line 157 of file qmap.cpp.

Referenced by QMap< int, QFrameInfo >::node_create().

{
    node->forward[0]->backward = node->backward;

    for (int i = 0; i <= topLevel; ++i) {
        if (update[i]->forward[i] != node)
            break;
        update[i]->forward[i] = node->forward[i];
    }
    --size;
    if (strictAlignment)
        qFreeAligned(reinterpret_cast<char *>(node) - offset);
    else
        qFree(reinterpret_cast<char *>(node) - offset);
}

Properties

backward

QMapData* QMapData::backward

Definition at line 69 of file qmap.h.

forward

QMapData* QMapData::forward[QMapData::LastLevel+1]

Definition at line 70 of file qmap.h.

Referenced by QMap< int, QFrameInfo >::freeData(), and node_delete().

insertInOrder

uint QMapData::insertInOrder

Definition at line 75 of file qmap.h.

Referenced by createData(), and node_create().

randomBits

uint QMapData::randomBits

Definition at line 74 of file qmap.h.

Referenced by createData(), node_create(), and node_delete().

ref

QBasicAtomicInt QMapData::ref

Definition at line 71 of file qmap.h.

Referenced by createData(), node_delete(), and QMap< int, QFrameInfo >::operator=().

reserved

uint QMapData::reserved

Definition at line 78 of file qmap.h.

Referenced by createData().

sharable

uint QMapData::sharable

Definition at line 76 of file qmap.h.

Referenced by createData().

shared_null

QMapData QMapData::shared_null

static

Initial value:

= {
    &shared_null,
    { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, false, true, false, 0
}

Definition at line 91 of file qmap.h.

size

int QMapData::size

Definition at line 73 of file qmap.h.

Referenced by createData(), node_create(), and node_delete().

strictAlignment

uint QMapData::strictAlignment

Definition at line 77 of file qmap.h.

Referenced by continueFreeData(), createData(), node_create(), and node_delete().

topLevel

int QMapData::topLevel

Definition at line 72 of file qmap.h.

Referenced by createData(), node_create(), and node_delete().

---

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

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