QHashData Struct Reference

#include <qhash.h>

Classes
struct	Node

Public Functions
void *	allocateNode ()
void *	allocateNode (int nodeAlign)
void	destroyAndFree ()
QHashData *	detach_helper (void(*node_duplicate)(Node *, void *), int nodeSize)
QHashData *	detach_helper2 (void(*node_duplicate)(Node *, void *), void(*node_delete)(Node *), int nodeSize, int nodeAlign)
Node *	firstNode ()
void	free_helper (void(*node_delete)(Node *))
void	freeNode (void *node)
void	hasShrunk ()
void	mightGrow ()
void	rehash (int hint)
bool	willGrow ()

Static Public Functions
static Node *	nextNode (Node *node)
static Node *	previousNode (Node *node)

Public Variables
Node **	buckets
Node *	fakeNext
int	nodeSize
short	numBits
int	numBuckets
QBasicAtomicInt	ref
uint	reserved: 30
uint	sharable: 1
int	size
uint	strictAlignment: 1
short	userNumBits

Static Public Variables
static QHashData	shared_null

Detailed Description

Definition at line 112 of file qhash.h.

Functions

allocateNode() [1/2]

void * QHashData::allocateNode

(

)

Definition at line 172 of file qhash.cpp.

Referenced by detach_helper2().

{
    return allocateNode(0);
}

allocateNode() [2/2]

void * QHashData::allocateNode

(

int

nodeAlign

)

Definition at line 177 of file qhash.cpp.

{
    void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : qMalloc(nodeSize);
    Q_CHECK_PTR(ptr);
    return ptr;
}

destroyAndFree()

void QHashData::destroyAndFree

(

)

Definition at line 395 of file qhash.cpp.

{
    free_helper(0);
}

detach_helper()

QHashData * QHashData::detach_helper	(	void(*)(Node *, void *)	node_duplicate,
		int	nodeSize
	)

Definition at line 192 of file qhash.cpp.

{
    return detach_helper2( node_duplicate, 0, nodeSize, 0 );
}

detach_helper2()

QHashData * QHashData::detach_helper2	(	void(*)(Node *, void *)	node_duplicate,
		void(*)(Node *)	node_delete,
		int	nodeSize,
		int	nodeAlign
	)

Definition at line 197 of file qhash.cpp.

Referenced by detach_helper().

{
    union {
        QHashData *d;
        Node *e;
    };
    d = new QHashData;
    d->fakeNext = 0;
    d->buckets = 0;
    d->ref = 1;
    d->size = size;
    d->nodeSize = nodeSize;
    d->userNumBits = userNumBits;
    d->numBits = numBits;
    d->numBuckets = numBuckets;
    d->sharable = true;
    d->strictAlignment = nodeAlign > 8;
    d->reserved = 0;

    if (numBuckets) {
        QT_TRY {
            d->buckets = new Node *[numBuckets];
        } QT_CATCH(...) {
            // restore a consistent state for d
            d->numBuckets = 0;
            // roll back
            d->free_helper(node_delete);
            QT_RETHROW;
        }

        Node *this_e = reinterpret_cast<Node *>(this);
        for (int i = 0; i < numBuckets; ++i) {
            Node **nextNode = &d->buckets[i];
            Node *oldNode = buckets[i];
            while (oldNode != this_e) {
                QT_TRY {
                    Node *dup = static_cast<Node *>(allocateNode(nodeAlign));

                    QT_TRY {
                        node_duplicate(oldNode, dup);
                    } QT_CATCH(...) {
                        freeNode( dup );
                        QT_RETHROW;
                    }

                    dup->h = oldNode->h;
                    *nextNode = dup;
                    nextNode = &dup->next;
                    oldNode = oldNode->next;
                } QT_CATCH(...) {
                    // restore a consistent state for d
                    *nextNode = e;
                    d->numBuckets = i+1;
                    // roll back
                    d->free_helper(node_delete);
                    QT_RETHROW;
                }
            }
            *nextNode = e;
        }
    }
    return d;
}

firstNode()

QHashData::Node * QHashData::firstNode ( )

inline

Definition at line 181 of file qhash.h.

Referenced by rehash().

{
    Node *e = reinterpret_cast<Node *>(this);
    Node **bucket = buckets;
    int n = numBuckets;
    while (n--) {
        if (*bucket != e)
            return *bucket;
        ++bucket;
    }
    return e;
}

free_helper()

void QHashData::free_helper

(

void(*)(Node *)

node_delete

)

Definition at line 264 of file qhash.cpp.

Referenced by destroyAndFree(), and QHash< QExplicitlySharedDataPointer, QHash >::freeData().

{
    if (node_delete) {
        Node *this_e = reinterpret_cast<Node *>(this);
        Node **bucket = reinterpret_cast<Node **>(this->buckets);

        int n = numBuckets;
        while (n--) {
            Node *cur = *bucket++;
            while (cur != this_e) {
                Node *next = cur->next;
                node_delete(cur);
                freeNode(cur);
                cur = next;
            }
        }
    }
    delete [] buckets;
    delete this;
}

freeNode()

void QHashData::freeNode

(

void *

node

)

Definition at line 184 of file qhash.cpp.

Referenced by detach_helper2(), and free_helper().

{
    if (strictAlignment)
        qFreeAligned(node);
    else
        qFree(node);
}

hasShrunk()

void QHashData::hasShrunk ( )

inline

Definition at line 170 of file qhash.h.

{
    if (size <= (numBuckets >> 3) && numBits > userNumBits) {
        QT_TRY {
            rehash(qMax(int(numBits) - 2, int(userNumBits)));
        } QT_CATCH(const std::bad_alloc &) {
            // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
        }
    }
}

mightGrow()

void QHashData::mightGrow ( )

inline

Definition at line 154 of file qhash.h.

{
    if (size >= numBuckets)
        rehash(numBits + 1);
}

nextNode()

QHashData::Node * QHashData::nextNode ( Node *  node )

static

Definition at line 285 of file qhash.cpp.

Referenced by detach_helper2(), QHash< Key, T >::iterator::operator++(), and QHash< Key, T >::const_iterator::operator++().

{
    union {
        Node *next;
        Node *e;
        QHashData *d;
    };
    next = node->next;
    Q_ASSERT_X(next, "QHash", "Iterating beyond end()");
    if (next->next)
        return next;

    int start = (node->h % d->numBuckets) + 1;
    Node **bucket = d->buckets + start;
    int n = d->numBuckets - start;
    while (n--) {
        if (*bucket != e)
            return *bucket;
        ++bucket;
    }
    return e;
}

previousNode()

QHashData::Node * QHashData::previousNode ( Node *  node )

static

Definition at line 308 of file qhash.cpp.

Referenced by QHash< Key, T >::iterator::operator--(), and QHash< Key, T >::const_iterator::operator--().

{
    union {
        Node *e;
        QHashData *d;
    };

    e = node;
    while (e->next)
        e = e->next;

    int start;
    if (node == e)
        start = d->numBuckets - 1;
    else
        start = node->h % d->numBuckets;

    Node *sentinel = node;
    Node **bucket = d->buckets + start;
    while (start >= 0) {
        if (*bucket != sentinel) {
            Node *prev = *bucket;
            while (prev->next != sentinel)
                prev = prev->next;
            return prev;
        }

        sentinel = e;
        --bucket;
        --start;
    }
    Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()");
    return e;
}

rehash()

void QHashData::rehash

(

int

hint

)

Definition at line 349 of file qhash.cpp.

{
    if (hint < 0) {
        hint = countBits(-hint);
        if (hint < MinNumBits)
            hint = MinNumBits;
        userNumBits = hint;
        while (primeForNumBits(hint) < (size >> 1))
            ++hint;
    } else if (hint < MinNumBits) {
        hint = MinNumBits;
    }

    if (numBits != hint) {
        Node *e = reinterpret_cast<Node *>(this);
        Node **oldBuckets = buckets;
        int oldNumBuckets = numBuckets;

        int nb = primeForNumBits(hint);
        buckets = new Node *[nb];
        numBits = hint;
        numBuckets = nb;
        for (int i = 0; i < numBuckets; ++i)
            buckets[i] = e;

        for (int i = 0; i < oldNumBuckets; ++i) {
            Node *firstNode = oldBuckets[i];
            while (firstNode != e) {
                uint h = firstNode->h;
                Node *lastNode = firstNode;
                while (lastNode->next != e && lastNode->next->h == h)
                    lastNode = lastNode->next;

                Node *afterLastNode = lastNode->next;
                Node **beforeFirstNode = &buckets[h % numBuckets];
                while (*beforeFirstNode != e)
                    beforeFirstNode = &(*beforeFirstNode)->next;
                lastNode->next = *beforeFirstNode;
                *beforeFirstNode = firstNode;
                firstNode = afterLastNode;
            }
        }
        delete [] oldBuckets;
    }
}

willGrow()

bool QHashData::willGrow ( )

inline

Definition at line 160 of file qhash.h.

{
    if (size >= numBuckets) {
        rehash(numBits + 1);
        return true;
    } else {
        return false;
    }
}

Properties

buckets

Node** QHashData::buckets

Definition at line 120 of file qhash.h.

Referenced by destroyAndFree(), detach_helper2(), free_helper(), and rehash().

fakeNext

Node* QHashData::fakeNext

Definition at line 119 of file qhash.h.

Referenced by destroyAndFree().

nodeSize

int QHashData::nodeSize

Definition at line 123 of file qhash.h.

Referenced by allocateNode(), destroyAndFree(), and detach_helper2().

numBits

short QHashData::numBits

Definition at line 125 of file qhash.h.

Referenced by destroyAndFree(), detach_helper2(), and rehash().

numBuckets

int QHashData::numBuckets

Definition at line 126 of file qhash.h.

Referenced by destroyAndFree(), detach_helper2(), free_helper(), and rehash().

ref

QBasicAtomicInt QHashData::ref

Definition at line 121 of file qhash.h.

Referenced by destroyAndFree(), QHash< QExplicitlySharedDataPointer, QHash >::operator=(), QSqlDatabase::QSqlDatabase(), and QSqlDatabase::~QSqlDatabase().

reserved

uint QHashData::reserved

Definition at line 129 of file qhash.h.

sharable

uint QHashData::sharable

Definition at line 127 of file qhash.h.

shared_null

QHashData QHashData::shared_null

static

Initial value:

= {
    0, 0, Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, MinNumBits, 0, 0, true, false, 0
}

Definition at line 151 of file qhash.h.

Referenced by QSqlDatabase::isValid().

size

int QHashData::size

Definition at line 122 of file qhash.h.

Referenced by destroyAndFree(), detach_helper2(), and rehash().

strictAlignment

uint QHashData::strictAlignment

Definition at line 128 of file qhash.h.

Referenced by allocateNode(), and freeNode().

userNumBits

short QHashData::userNumBits

Definition at line 124 of file qhash.h.

Referenced by destroyAndFree(), detach_helper2(), and rehash().

---

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

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