Qt4-preview-feedback Archive, March 2007
Qt 4.3 and VS 2005 SP 1
Message 1 in thread
Hi,
I know that Microsoft broke the template handling in VS 2005 SP1 which
causes Qmap.h and qhash.h to give compile errors. (I just ordered the
hotfix from Microsoft)
It is simply annoying to manually update the headers and move the
functions find, findConst, replace back into the classes each time I
update (I am trying to test the snapshots).
Is there any reason for not moving the functions back into the classes?
(other compilers? code bloat?). Would it be possible to update this in
the upcoming 4.3 release?
It would save me and probably other a lot of hassle.
Thanks,
Robert
To unsubscribe - send "unsubscribe" in the subject to qt4-preview-feedback-request@xxxxxxxxxxxxx
Message 2 in thread
Hi Robert,
> I know that Microsoft broke the template handling in VS 2005 SP1 which
> causes Qmap.h and qhash.h to give compile errors. (I just ordered the
> hotfix from Microsoft)
>
> It is simply annoying to manually update the headers and move the
> functions find, findConst, replace back into the classes each time I
> update (I am trying to test the snapshots).
>
> Is there any reason for not moving the functions back into the classes?
> (other compilers? code bloat?). Would it be possible to update this in
> the upcoming 4.3 release?
I'm sure it should be possible. Could you send me a more precise
description of the problem, i.e. exactly which functions in QMap and
which functions in QHash should be implemented inside the class instead
of out-of-line? If you could send me your modified .h files or (even
better) a patch, I'm sure I could apply it before 4.3 is released.
Thanks!
Jasmin
To unsubscribe - send "unsubscribe" in the subject to qt4-preview-feedback-request@xxxxxxxxxxxxx
Message 3 in thread
Hi Jasmin,
these are the files. They are based on today's snapshot.
All I did was move the offending functions back into the class.
Thanks,
Robert
Jasmin Blanchette wrote:
> Hi Robert,
>
>> I know that Microsoft broke the template handling in VS 2005 SP1 which
>> causes Qmap.h and qhash.h to give compile errors. (I just ordered the
>> hotfix from Microsoft)
>>
>> It is simply annoying to manually update the headers and move the
>> functions find, findConst, replace back into the classes each time I
>> update (I am trying to test the snapshots).
>>
>> Is there any reason for not moving the functions back into the classes?
>> (other compilers? code bloat?). Would it be possible to update this in
>> the upcoming 4.3 release?
>
> I'm sure it should be possible. Could you send me a more precise
> description of the problem, i.e. exactly which functions in QMap and
> which functions in QHash should be implemented inside the class instead
> of out-of-line? If you could send me your modified .h files or (even
> better) a patch, I'm sure I could apply it before 4.3 is released.
>
> Thanks!
>
> Jasmin
>
> To unsubscribe - send "unsubscribe" in the subject to
> qt4-preview-feedback-request@xxxxxxxxxxxxx
/****************************************************************************
/****************************************************************************
**
** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** Licensees holding a valid Qt License Agreement may use this file in
** accordance with the rights, responsibilities and obligations
** contained therein. Please consult your licensing agreement or
** contact sales@xxxxxxxxxxxxx if any conditions of this licensing
** agreement are not clear to you.
**
** Further information about Qt licensing is available at:
** http://www.trolltech.com/products/qt/licensing.html or by
** contacting info@xxxxxxxxxxxxxx
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
****************************************************************************/
#ifndef QMAP_H
#define QMAP_H
#include <QtCore/qatomic.h>
#include <QtCore/qiterator.h>
#include <QtCore/qlist.h>
#ifndef QT_NO_STL
#include <map>
#endif
#include <new>
#undef QT_MAP_DEBUG
QT_BEGIN_HEADER
QT_MODULE(Core)
struct Q_CORE_EXPORT QMapData
{
struct Node {
Node *backward;
Node *forward[1];
};
enum { LastLevel = 11, Sparseness = 3 };
QMapData *backward;
QMapData *forward[QMapData::LastLevel + 1];
QBasicAtomic ref;
int topLevel;
int size;
uint randomBits;
uint insertInOrder : 1;
uint sharable : 1;
static QMapData *createData();
void continueFreeData(int offset);
Node *node_create(Node *update[], int offset);
void node_delete(Node *update[], int offset, Node *node);
#ifdef QT_QMAP_DEBUG
uint adjust_ptr(Node *node);
void dump();
#endif
static QMapData shared_null;
};
/*
QMap uses qMapLessThanKey() to compare keys. The default
implementation uses operator<(). For pointer types,
qMapLessThanKey() casts the pointers to integers before it
compares them, because operator<() is undefined on pointers
that come from different memory blocks. (In practice, this
is only a problem when running a program such as
BoundsChecker.)
*/
template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
{
return key1 < key2;
}
#ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
{
Q_ASSERT(sizeof(ulong) == sizeof(Ptr *));
return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);
}
template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
{
Q_ASSERT(sizeof(ulong) == sizeof(const Ptr *));
return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);
}
#endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
template <class Key, class T>
class QMap
{
struct Node {
Key key;
T value;
QMapData::Node *backward;
QMapData::Node *forward[1];
};
union {
QMapData *d;
QMapData::Node *e;
};
struct PayloadNode
{
Key key;
T value;
QMapData::Node *backward;
};
static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }
static inline Node *concrete(QMapData::Node *node) {
return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());
}
public:
inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }
inline QMap(const QMap<Key, T> &other) : d(other.d)
{ d->ref.ref(); if (!d->sharable) detach(); }
inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }
QMap<Key, T> &operator=(const QMap<Key, T> &other);
#ifndef QT_NO_STL
explicit QMap(const typename std::map<Key, T> &other);
std::map<Key, T> toStdMap() const;
#endif
bool operator==(const QMap<Key, T> &other) const;
inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
inline int size() const { return d->size; }
inline bool isEmpty() const { return d->size == 0; }
inline void detach() { if (d->ref != 1) detach_helper(); }
inline bool isDetached() const { return d->ref == 1; }
inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }
void clear();
int remove(const Key &key);
T take(const Key &key);
bool contains(const Key &key) const;
const Key key(const T &value) const;
const Key key(const T &value, const Key &defaultKey) const;
const T value(const Key &key) const;
const T value(const Key &key, const T &defaultValue) const;
T &operator[](const Key &key);
const T operator[](const Key &key) const;
QList<Key> uniqueKeys() const;
QList<Key> keys() const;
QList<Key> keys(const T &value) const;
QList<T> values() const;
QList<T> values(const Key &key) const;
int count(const Key &key) const;
class const_iterator;
class iterator
{
QMapData::Node *i;
public:
typedef std::bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
// ### Qt 5: get rid of 'operator Node *'
inline operator QMapData::Node *() const { return i; }
inline iterator() : i(0) { }
inline iterator(QMapData::Node *node) : i(node) { }
inline const Key &key() const { return concrete(i)->key; }
inline T &value() const { return concrete(i)->value; }
#ifdef QT3_SUPPORT
inline QT3_SUPPORT T &data() const { return concrete(i)->value; }
#endif
inline T &operator*() const { return concrete(i)->value; }
inline T *operator->() const { return &concrete(i)->value; }
inline bool operator==(const iterator &o) const { return i == o.i; }
inline bool operator!=(const iterator &o) const { return i != o.i; }
inline iterator &operator++() {
i = i->forward[0];
return *this;
}
inline iterator operator++(int) {
iterator r = *this;
i = i->forward[0];
return r;
}
inline iterator &operator--() {
i = i->backward;
return *this;
}
inline iterator operator--(int) {
iterator r = *this;
i = i->backward;
return r;
}
inline iterator operator+(int j) const
{ iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
inline iterator operator-(int j) const { return operator+(-j); }
inline iterator &operator+=(int j) { return *this = *this + j; }
inline iterator &operator-=(int j) { return *this = *this - j; }
// ### Qt 5: not sure this is necessary anymore
#ifdef QT_STRICT_ITERATORS
private:
#else
public:
#endif
inline bool operator==(const const_iterator &o) const
{ return i == reinterpret_cast<const iterator &>(o).i; }
inline bool operator!=(const const_iterator &o) const
{ return i != reinterpret_cast<const iterator &>(o).i; }
private:
// ### Qt 5: remove
inline operator bool() const { return false; }
};
friend class iterator;
class const_iterator
{
QMapData::Node *i;
public:
typedef std::bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef const T *pointer;
typedef const T &reference;
// ### Qt 5: get rid of 'operator Node *'
inline operator QMapData::Node *() const { return i; }
inline const_iterator() : i(0) { }
inline const_iterator(QMapData::Node *node) : i(node) { }
#ifdef QT_STRICT_ITERATORS
explicit inline const_iterator(const iterator &o)
#else
inline const_iterator(const iterator &o)
#endif
{ i = reinterpret_cast<const const_iterator &>(o).i; }
inline const Key &key() const { return concrete(i)->key; }
inline const T &value() const { return concrete(i)->value; }
#ifdef QT3_SUPPORT
inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }
#endif
inline const T &operator*() const { return concrete(i)->value; }
inline const T *operator->() const { return &concrete(i)->value; }
inline bool operator==(const const_iterator &o) const { return i == o.i; }
inline bool operator!=(const const_iterator &o) const { return i != o.i; }
inline const_iterator &operator++() {
i = i->forward[0];
return *this;
}
inline const_iterator operator++(int) {
const_iterator r = *this;
i = i->forward[0];
return r;
}
inline const_iterator &operator--() {
i = i->backward;
return *this;
}
inline const_iterator operator--(int) {
const_iterator r = *this;
i = i->backward;
return r;
}
inline const_iterator operator+(int j) const
{ const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
inline const_iterator operator-(int j) const { return operator+(-j); }
inline const_iterator &operator+=(int j) { return *this = *this + j; }
inline const_iterator &operator-=(int j) { return *this = *this - j; }
// ### Qt 5: not sure this is necessary anymore
#ifdef QT_STRICT_ITERATORS
private:
inline bool operator==(const iterator &o) { return operator==(const_iterator(o)); }
inline bool operator!=(const iterator &o) { return operator!=(const_iterator(o)); }
#endif
private:
// ### Qt 5: remove
inline operator bool() const { return false; }
};
friend class const_iterator;
// STL style
inline iterator begin() { detach(); return iterator(e->forward[0]); }
inline const_iterator begin() const { return const_iterator(e->forward[0]); }
inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }
inline iterator end() {
detach();
return iterator(e);
}
inline const_iterator end() const { return const_iterator(e); }
inline const_iterator constEnd() const { return const_iterator(e); }
iterator erase(iterator it);
#ifdef QT3_SUPPORT
inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }
inline QT3_SUPPORT void erase(const Key &key) { remove(key); }
#endif
// more Qt
typedef iterator Iterator;
typedef const_iterator ConstIterator;
inline int count() const { return d->size; }
iterator find(const Key &key);
const_iterator find(const Key &key) const;
const_iterator constFind(const Key &key) const;
iterator lowerBound(const Key &key);
const_iterator lowerBound(const Key &key) const;
iterator upperBound(const Key &key);
const_iterator upperBound(const Key &key) const;
iterator insert(const Key &key, const T &value);
#ifdef QT3_SUPPORT
QT3_SUPPORT iterator insert(const Key &key, const T &value, bool overwrite);
#endif
iterator insertMulti(const Key &key, const T &value);
#ifdef QT3_SUPPORT
inline QT3_SUPPORT iterator replace(const Key &key, const T &value) { return insert(key, value); }
#endif
QMap<Key, T> &unite(const QMap<Key, T> &other);
// STL compatibility
typedef Key key_type;
typedef T mapped_type;
typedef ptrdiff_t difference_type;
typedef int size_type;
inline bool empty() const { return isEmpty(); }
#ifdef QT_QMAP_DEBUG
inline void dump() const { d->dump(); }
#endif
private:
void detach_helper();
void freeData(QMapData *d);
QMapData::Node *findNode(const Key &key) const;
QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const;
QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key,
const T &value);
};
template <class Key, class T>
Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
{
if (d != other.d) {
QMapData *x = other.d;
x->ref.ref();
x = qAtomicSetPtr(&d, x);
if (!x->ref.deref())
freeData(x);
if (!d->sharable)
detach_helper();
}
return *this;
}
template <class Key, class T>
Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
{
*this = QMap<Key, T>();
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMapData::Node *
QMap<Key, T>::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue)
{
QMapData::Node *abstractNode = adt->node_create(aupdate, payload());
Node *concreteNode = concrete(abstractNode);
new (&concreteNode->key) Key(akey);
new (&concreteNode->value) T(avalue);
return abstractNode;
}
template <class Key, class T>
Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const
{
QMapData::Node *cur = e;
QMapData::Node *next = e;
for (int i = d->topLevel; i >= 0; i--) {
while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
cur = next;
}
if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
return next;
} else {
return e;
}
}
template <class Key, class T>
Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const
{
QMapData::Node *node = findNode(akey);
if (node == e) {
return T();
} else {
return concrete(node)->value;
}
}
template <class Key, class T>
Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
{
QMapData::Node *node = findNode(akey);
if (node == e) {
return adefaultValue;
} else {
return concrete(node)->value;
}
}
template <class Key, class T>
Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
{
return value(akey);
}
template <class Key, class T>
Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
{
detach();
QMapData::Node *update[QMapData::LastLevel + 1];
QMapData::Node *node = mutableFindNode(update, akey);
if (node == e)
node = node_create(d, update, akey, T());
return concrete(node)->value;
}
template <class Key, class T>
Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
{
int cnt = 0;
QMapData::Node *node = findNode(akey);
if (node != e) {
do {
++cnt;
node = node->forward[0];
} while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
}
return cnt;
}
template <class Key, class T>
Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
{
return findNode(akey) != e;
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
const T &avalue)
{
detach();
QMapData::Node *update[QMapData::LastLevel + 1];
QMapData::Node *node = mutableFindNode(update, akey);
if (node == e) {
node = node_create(d, update, akey, avalue);
} else {
concrete(node)->value = avalue;
}
return iterator(node);
}
#ifdef QT3_SUPPORT
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
const T &avalue,
bool aoverwrite)
{
detach();
QMapData::Node *update[QMapData::LastLevel + 1];
QMapData::Node *node = mutableFindNode(update, akey);
if (node == e) {
node = node_create(d, update, akey, avalue);
} else {
if (aoverwrite)
concrete(node)->value = avalue;
}
return iterator(node);
}
#endif
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
const T &avalue)
{
detach();
QMapData::Node *update[QMapData::LastLevel + 1];
mutableFindNode(update, akey);
return iterator(node_create(d, update, akey, avalue));
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
{
return const_iterator(findNode(akey));
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
{
return const_iterator(findNode(akey));
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
{
detach();
return iterator(findNode(akey));
}
template <class Key, class T>
Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
{
QMap<Key, T> copy(other);
const_iterator it = copy.constEnd();
const const_iterator b = copy.constBegin();
while (it != b) {
--it;
insertMulti(it.key(), it.value());
}
return *this;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)
{
if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
QMapData::Node *y = reinterpret_cast<QMapData::Node *>(x);
QMapData::Node *cur = y;
QMapData::Node *next = cur->forward[0];
while (next != y) {
cur = next;
next = cur->forward[0];
Node *concreteNode = concrete(cur);
concreteNode->key.~Key();
concreteNode->value.~T();
}
}
x->continueFreeData(payload());
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
{
detach();
QMapData::Node *update[QMapData::LastLevel + 1];
QMapData::Node *cur = e;
QMapData::Node *next = e;
int oldSize = d->size;
for (int i = d->topLevel; i >= 0; i--) {
while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
cur = next;
update[i] = cur;
}
if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
bool deleteNext = true;
do {
cur = next;
next = cur->forward[0];
deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
concrete(cur)->key.~Key();
concrete(cur)->value.~T();
d->node_delete(update, payload(), cur);
} while (deleteNext);
}
return oldSize - d->size;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
{
detach();
QMapData::Node *update[QMapData::LastLevel + 1];
QMapData::Node *cur = e;
QMapData::Node *next = e;
for (int i = d->topLevel; i >= 0; i--) {
while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
cur = next;
update[i] = cur;
}
if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
T t = concrete(next)->value;
concrete(next)->key.~Key();
concrete(next)->value.~T();
d->node_delete(update, payload(), next);
return t;
}
return T();
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
{
QMapData::Node *update[QMapData::LastLevel + 1];
QMapData::Node *cur = e;
QMapData::Node *next = e;
if (it == iterator(e))
return it;
for (int i = d->topLevel; i >= 0; i--) {
while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))
cur = next;
update[i] = cur;
}
while (next != e) {
cur = next;
next = cur->forward[0];
if (cur == it) {
concrete(cur)->key.~Key();
concrete(cur)->value.~T();
d->node_delete(update, payload(), cur);
return iterator(next);
}
for (int i = 0; i <= d->topLevel; ++i) {
if (update[i]->forward[i] != cur)
break;
update[i] = cur;
}
}
return end();
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
{
union { QMapData *d; QMapData::Node *e; } x;
x.d = QMapData::createData();
if (d->size) {
x.d->insertInOrder = true;
QMapData::Node *update[QMapData::LastLevel + 1];
QMapData::Node *cur = e->forward[0];
update[0] = x.e;
while (cur != e) {
Node *concreteNode = concrete(cur);
node_create(x.d, update, concreteNode->key, concreteNode->value);
cur = cur->forward[0];
}
x.d->insertInOrder = false;
}
x.d = qAtomicSetPtr(&d, x.d);
if (!x.d->ref.deref())
freeData(x.d);
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindNode(QMapData::Node *aupdate[],
const Key &akey) const
{
QMapData::Node *cur = e;
QMapData::Node *next = e;
for (int i = d->topLevel; i >= 0; i--) {
while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
cur = next;
aupdate[i] = cur;
}
if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
return next;
} else {
return e;
}
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
{
QList<Key> res;
const_iterator i = begin();
if (i != end()) {
for (;;) {
const Key &aKey = i.key();
res.append(aKey);
do {
if (++i == end())
goto break_out_of_outer_loop;
} while (!(aKey < i.key())); // loop while (key == i.key())
}
}
break_out_of_outer_loop:
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
{
QList<Key> res;
const_iterator i = begin();
while (i != end()) {
res.append(i.key());
++i;
}
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
{
QList<Key> res;
const_iterator i = begin();
while (i != end()) {
if (i.value() == avalue)
res.append(i.key());
++i;
}
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const
{
return key(avalue, Key());
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
{
const_iterator i = begin();
while (i != end()) {
if (i.value() == avalue)
return i.key();
++i;
}
return defaultKey;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
{
QList<T> res;
const_iterator i = begin();
while (i != end()) {
res.append(i.value());
++i;
}
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
{
QList<T> res;
QMapData::Node *node = findNode(akey);
if (node != e) {
do {
res.append(concrete(node)->value);
node = node->forward[0];
} while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
}
return res;
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
QMap<Key, T>::lowerBound(const Key &akey) const
{
QMapData::Node *update[QMapData::LastLevel + 1];
mutableFindNode(update, akey);
return const_iterator(update[0]->forward[0]);
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
{
detach();
return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
QMap<Key, T>::upperBound(const Key &akey) const
{
QMapData::Node *update[QMapData::LastLevel + 1];
mutableFindNode(update, akey);
QMapData::Node *node = update[0]->forward[0];
while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))
node = node->forward[0];
return const_iterator(node);
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
{
detach();
return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
{
if (size() != other.size())
return false;
if (d == other.d)
return true;
const_iterator it1 = begin();
const_iterator it2 = other.begin();
while (it1 != end()) {
if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
return false;
++it2;
++it1;
}
return true;
}
#ifndef QT_NO_STL
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
{
d = QMapData::createData();
d->insertInOrder = true;
typename std::map<Key,T>::const_iterator it = other.end();
while (it != other.begin()) {
--it;
insert((*it).first, (*it).second);
}
d->insertInOrder = false;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
{
std::map<Key, T> map;
const_iterator it = end();
while (it != begin()) {
--it;
map.insert(std::pair<Key, T>(it.key(), it.value()));
}
return map;
}
#endif // QT_NO_STL
template <class Key, class T>
class QMultiMap : public QMap<Key, T>
{
public:
QMultiMap() {}
QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
{ return QMap<Key, T>::insert(key, value); }
inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
{ return QMap<Key, T>::insertMulti(key, value); }
inline QMultiMap &operator+=(const QMultiMap &other)
{ unite(other); return *this; }
inline QMultiMap operator+(const QMultiMap &other) const
{ QMultiMap result = *this; result += other; return result; }
#ifndef Q_NO_USING_KEYWORD
using QMap<Key, T>::contains;
using QMap<Key, T>::remove;
using QMap<Key, T>::count;
using QMap<Key, T>::find;
using QMap<Key, T>::constFind;
#else
inline bool contains(const Key &key) const
{ return QMap<Key, T>::contains(key); }
inline int remove(const Key &key)
{ return QMap<Key, T>::remove(key); }
inline int count(const Key &key) const
{ return QMap<Key, T>::count(key); }
inline int count() const
{ return QMap<Key, T>::count(); }
inline typename QMap<Key, T>::iterator find(const Key &key)
{ return QMap<Key, T>::find(key); }
inline typename QMap<Key, T>::const_iterator find(const Key &key) const
{ return QMap<Key, T>::find(key); }
inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const
{ return QMap<Key, T>::constFind(key); }
#endif
bool contains(const Key &key, const T &value) const;
int remove(const Key &key, const T &value);
int count(const Key &key, const T &value) const;
typename QMap<Key, T>::iterator find(const Key &key, const T &value)
{
typename QMap<Key, T>::iterator i(find(key));
typename QMap<Key, T>::iterator end(this->end());
while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
if (i.value() == value)
return i;
++i;
}
return end;
}
typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const
{
typename QMap<Key, T>::const_iterator i(constFind(key));
typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
if (i.value() == value)
return i;
++i;
}
return end;
}
typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
{
return find(key, value);
}
private:
T &operator[](const Key &key);
const T operator[](const Key &key) const;
};
template <class Key, class T>
Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
{
return constFind(key, value) != QMap<Key, T>::constEnd();
}
template <class Key, class T>
Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
{
int n = 0;
typename QMap<Key, T>::iterator i(find(key));
typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
if (i.value() == value) {
i = erase(i);
++n;
} else {
++i;
}
}
return n;
}
template <class Key, class T>
Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
{
int n = 0;
typename QMap<Key, T>::const_iterator i(constFind(key));
typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
if (i.value() == value)
++n;
++i;
}
return n;
}
Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
QT_END_HEADER
#endif // QMAP_H
/****************************************************************************
/****************************************************************************
**
** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** Licensees holding a valid Qt License Agreement may use this file in
** accordance with the rights, responsibilities and obligations
** contained therein. Please consult your licensing agreement or
** contact sales@xxxxxxxxxxxxx if any conditions of this licensing
** agreement are not clear to you.
**
** Further information about Qt licensing is available at:
** http://www.trolltech.com/products/qt/licensing.html or by
** contacting info@xxxxxxxxxxxxxx
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
****************************************************************************/
#ifndef QHASH_H
#define QHASH_H
#include <QtCore/qatomic.h>
#include <QtCore/qchar.h>
#include <QtCore/qiterator.h>
#include <QtCore/qlist.h>
#include <QtCore/qpair.h>
QT_BEGIN_HEADER
#undef QT_QHASH_DEBUG
QT_MODULE(Core)
class QBitArray;
class QByteArray;
class QString;
class QStringRef;
inline uint qHash(char key) { return uint(key); }
inline uint qHash(uchar key) { return uint(key); }
inline uint qHash(signed char key) { return uint(key); }
inline uint qHash(ushort key) { return uint(key); }
inline uint qHash(short key) { return uint(key); }
inline uint qHash(uint key) { return key; }
inline uint qHash(int key) { return uint(key); }
inline uint qHash(ulong key)
{
if (sizeof(ulong) > sizeof(uint)) {
return uint((key >> (8 * sizeof(uint) - 1)) ^ key);
} else {
return uint(key);
}
}
inline uint qHash(long key) { return qHash(ulong(key)); }
inline uint qHash(quint64 key)
{
if (sizeof(quint64) > sizeof(uint)) {
return uint((key >> (8 * sizeof(uint) - 1)) ^ key);
} else {
return uint(key);
}
}
inline uint qHash(qint64 key) { return qHash(quint64(key)); }
inline uint qHash(QChar key) { return qHash(key.unicode()); }
Q_CORE_EXPORT uint qHash(const QByteArray &key);
Q_CORE_EXPORT uint qHash(const QString &key);
Q_CORE_EXPORT uint qHash(const QStringRef &key);
Q_CORE_EXPORT uint qHash(const QBitArray &key);
#if defined(Q_CC_MSVC)
#pragma warning( push )
#pragma warning( disable : 4311 ) // disable pointer truncation warning
#endif
template <class T> inline uint qHash(const T *key)
{
if (sizeof(const T *) > sizeof(uint))
return qHash(reinterpret_cast<quint64>(key));
else
return uint(reinterpret_cast<ulong>(key));
}
#if defined(Q_CC_MSVC)
#pragma warning( pop )
#endif
template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key)
{
uint h1 = qHash(key.first);
uint h2 = qHash(key.second);
return ((h1 << 16) | (h1 >> 16)) ^ h2;
}
struct Q_CORE_EXPORT QHashData
{
struct Node {
Node *next;
uint h;
};
Node *fakeNext;
Node **buckets;
QBasicAtomic ref;
int size;
int nodeSize;
short userNumBits;
short numBits;
int numBuckets;
uint sharable : 1;
void *allocateNode();
void freeNode(void *node);
QHashData *detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize);
void mightGrow();
void hasShrunk();
void rehash(int hint);
void destroyAndFree();
Node *firstNode();
#ifdef QT_QHASH_DEBUG
void dump();
void checkSanity();
#endif
static Node *nextNode(Node *node);
static Node *previousNode(Node *node);
static QHashData shared_null;
};
inline void QHashData::mightGrow()
{
if (size >= numBuckets)
rehash(numBits + 1);
}
inline void QHashData::hasShrunk()
{
if (size <= (numBuckets >> 3) && numBits > userNumBits)
rehash(qMax(int(numBits) - 2, int(userNumBits)));
}
inline QHashData::Node *QHashData::firstNode()
{
Node *e = reinterpret_cast<Node *>(this);
Node **bucket = buckets;
int n = numBuckets;
while (n--) {
if (*bucket != e)
return *bucket;
++bucket;
}
return e;
}
struct QHashDummyValue
{
};
inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
{
return true;
}
Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
template <class Key, class T>
struct QHashDummyNode
{
QHashDummyNode *next;
uint h;
Key key;
inline QHashDummyNode(const Key &key0) : key(key0) {}
};
template <class Key, class T>
struct QHashNode
{
QHashNode *next;
uint h;
Key key;
T value;
inline QHashNode(const Key &key0) : key(key0) {} // ### remove in 5.0
inline QHashNode(const Key &key0, const T &value0) : key(key0), value(value0) {}
inline bool same_key(uint h0, const Key &key0) { return h0 == h && key0 == key; }
};
#ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
#define Q_HASH_DECLARE_INT_NODES(key_type) \
template <class T> \
struct QHashDummyNode<key_type, T> { \
QHashDummyNode *next; \
union { uint h; key_type key; }; \
\
inline QHashDummyNode(key_type /* key0 */) {} \
}; \
\
template <class T> \
struct QHashNode<key_type, T> { \
QHashNode *next; \
union { uint h; key_type key; }; \
T value; \
\
inline QHashNode(key_type /* key0 */) {} \
inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \
inline bool same_key(uint h0, key_type) { return h0 == h; } \
}
#if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
Q_HASH_DECLARE_INT_NODES(short);
Q_HASH_DECLARE_INT_NODES(ushort);
#endif
Q_HASH_DECLARE_INT_NODES(int);
Q_HASH_DECLARE_INT_NODES(uint);
#undef Q_HASH_DECLARE_INT_NODES
#endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
template <class Key, class T>
class QHash
{
typedef QHashDummyNode<Key, T> DummyNode;
typedef QHashNode<Key, T> Node;
union {
QHashData *d;
QHashNode<Key, T> *e;
};
static inline Node *concrete(QHashData::Node *node) {
return reinterpret_cast<Node *>(node);
}
public:
inline QHash() : d(&QHashData::shared_null) { d->ref.ref(); }
inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
inline ~QHash() { if (!d->ref.deref()) freeData(d); }
QHash<Key, T> &operator=(const QHash<Key, T> &other);
bool operator==(const QHash<Key, T> &other) const;
inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }
inline int size() const { return d->size; }
inline bool isEmpty() const { return d->size == 0; }
inline int capacity() const { return d->numBuckets; }
void reserve(int size);
inline void squeeze() { reserve(1); }
inline void detach() { if (d->ref != 1) detach_helper(); }
inline bool isDetached() const { return d->ref == 1; }
inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
void clear();
int remove(const Key &key);
T take(const Key &key);
bool contains(const Key &key) const;
const Key key(const T &value) const;
const Key key(const T &value, const Key &defaultKey) const;
const T value(const Key &key) const;
const T value(const Key &key, const T &defaultValue) const;
T &operator[](const Key &key);
const T operator[](const Key &key) const;
QList<Key> uniqueKeys() const;
QList<Key> keys() const;
QList<Key> keys(const T &value) const;
QList<T> values() const;
QList<T> values(const Key &key) const;
int count(const Key &key) const;
class const_iterator;
class iterator
{
QHashData::Node *i;
public:
typedef std::bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
// ### Qt 5: get rid of 'operator Node *'
inline operator Node *() const { return concrete(i); }
inline iterator() : i(0) { }
explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
inline const Key &key() const { return concrete(i)->key; }
inline T &value() const { return concrete(i)->value; }
inline T &operator*() const { return concrete(i)->value; }
inline T *operator->() const { return &concrete(i)->value; }
inline bool operator==(const iterator &o) const { return i == o.i; }
inline bool operator!=(const iterator &o) const { return i != o.i; }
inline iterator &operator++() {
i = QHashData::nextNode(i);
return *this;
}
inline iterator operator++(int) {
iterator r = *this;
i = QHashData::nextNode(i);
return r;
}
inline iterator &operator--() {
i = QHashData::previousNode(i);
return *this;
}
inline iterator operator--(int) {
iterator r = *this;
i = QHashData::previousNode(i);
return r;
}
inline iterator operator+(int j) const
{ iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
inline iterator operator-(int j) const { return operator+(-j); }
inline iterator &operator+=(int j) { return *this = *this + j; }
inline iterator &operator-=(int j) { return *this = *this - j; }
// ### Qt 5: not sure this is necessary anymore
#ifdef QT_STRICT_ITERATORS
private:
#else
public:
#endif
inline bool operator==(const const_iterator &o) const
{ return i == reinterpret_cast<const iterator &>(o).i; }
inline bool operator!=(const const_iterator &o) const
{ return i != reinterpret_cast<const iterator &>(o).i; }
private:
// ### Qt 5: remove
inline operator bool() const { return false; }
};
friend class iterator;
class const_iterator
{
QHashData::Node *i;
public:
typedef std::bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef const T *pointer;
typedef const T &reference;
// ### Qt 5: get rid of 'operator Node *'
inline operator Node *() const { return concrete(i); }
inline const_iterator() : i(0) { }
explicit inline const_iterator(void *node)
: i(reinterpret_cast<QHashData::Node *>(node)) { }
#ifdef QT_STRICT_ITERATORS
explicit inline const_iterator(const iterator &o)
#else
inline const_iterator(const iterator &o)
#endif
{ i = reinterpret_cast<const const_iterator &>(o).i; }
inline const Key &key() const { return concrete(i)->key; }
inline const T &value() const { return concrete(i)->value; }
inline const T &operator*() const { return concrete(i)->value; }
inline const T *operator->() const { return &concrete(i)->value; }
inline bool operator==(const const_iterator &o) const { return i == o.i; }
inline bool operator!=(const const_iterator &o) const { return i != o.i; }
inline const_iterator &operator++() {
i = QHashData::nextNode(i);
return *this;
}
inline const_iterator operator++(int) {
const_iterator r = *this;
i = QHashData::nextNode(i);
return r;
}
inline const_iterator &operator--() {
i = QHashData::previousNode(i);
return *this;
}
inline const_iterator operator--(int) {
const_iterator r = *this;
i = QHashData::previousNode(i);
return r;
}
inline const_iterator operator+(int j) const
{ const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
inline const_iterator operator-(int j) const { return operator+(-j); }
inline const_iterator &operator+=(int j) { return *this = *this + j; }
inline const_iterator &operator-=(int j) { return *this = *this - j; }
// ### Qt 5: not sure this is necessary anymore
#ifdef QT_STRICT_ITERATORS
private:
inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
#endif
private:
// ### Qt 5: remove
inline operator bool() const { return false; }
};
friend class const_iterator;
// STL style
inline iterator begin() { detach(); return iterator(d->firstNode()); }
inline const_iterator begin() const { return const_iterator(d->firstNode()); }
inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
inline iterator end() { detach(); return iterator(e); }
inline const_iterator end() const { return const_iterator(e); }
inline const_iterator constEnd() const { return const_iterator(e); }
iterator erase(iterator it);
// more Qt
typedef iterator Iterator;
typedef const_iterator ConstIterator;
inline int count() const { return d->size; }
iterator find(const Key &key);
const_iterator find(const Key &key) const;
const_iterator constFind(const Key &key) const;
iterator insert(const Key &key, const T &value);
iterator insertMulti(const Key &key, const T &value);
QHash<Key, T> &unite(const QHash<Key, T> &other);
// STL compatibility
typedef T mapped_type;
typedef Key key_type;
typedef ptrdiff_t difference_type;
typedef int size_type;
inline bool empty() const { return isEmpty(); }
#ifdef QT_QHASH_DEBUG
inline void dump() const { d->dump(); }
inline void checkSanity() const { d->checkSanity(); }
#endif
private:
void detach_helper();
void freeData(QHashData *d);
Node **findNode(const Key &key, uint *hp = 0) const;
Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
void deleteNode(Node *node);
static void duplicateNode(QHashData::Node *originalNode, void *newNode);
};
template <class Key, class T>
Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
{
#ifdef Q_CC_BOR
node->~QHashNode<Key, T>();
#elif defined(QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION)
node->~QHashNode();
#else
node->~Node();
#endif
d->freeNode(node);
}
template <class Key, class T>
Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
{
Node *concreteNode = concrete(node);
if (QTypeInfo<T>::isDummy) {
(void) new (newNode) DummyNode(concreteNode->key);
} else {
(void) new (newNode) Node(concreteNode->key, concreteNode->value);
}
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
{
Node *node;
if (QTypeInfo<T>::isDummy) {
node = reinterpret_cast<Node *>(new (d->allocateNode()) DummyNode(akey));
} else {
node = new (d->allocateNode()) Node(akey, avalue);
}
node->h = ah;
node->next = *anextNode;
*anextNode = node;
++d->size;
return node;
}
template <class Key, class T>
Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)
{
QHash<Key, T> copy(other);
const_iterator it = copy.constEnd();
while (it != copy.constBegin()) {
--it;
insertMulti(it.key(), it.value());
}
return *this;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
{
Node *e_for_x = reinterpret_cast<Node *>(x);
Node **bucket = reinterpret_cast<Node **>(x->buckets);
int n = x->numBuckets;
while (n--) {
Node *cur = *bucket++;
while (cur != e_for_x) {
Node *next = cur->next;
deleteNode(cur);
cur = next;
}
}
x->destroyAndFree();
}
template <class Key, class T>
Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
{
*this = QHash<Key,T>();
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
{
QHashData *x = d->detach_helper(duplicateNode,
QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node));
x = qAtomicSetPtr(&d, x);
if (!x->ref.deref())
freeData(x);
}
template <class Key, class T>
Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)
{
if (d != other.d) {
QHashData *x = other.d;
x->ref.ref();
x = qAtomicSetPtr(&d, x);
if (!x->ref.deref())
freeData(x);
if (!d->sharable)
detach_helper();
}
return *this;
}
template <class Key, class T>
Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
{
Node *node = *findNode(akey);
if (node == e) {
return T();
} else {
return node->value;
}
}
template <class Key, class T>
Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
{
Node *node = *findNode(akey);
if (node == e) {
return adefaultValue;
} else {
return node->value;
}
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
{
QList<Key> res;
const_iterator i = begin();
if (i != end()) {
for (;;) {
const Key &aKey = i.key();
res.append(aKey);
do {
if (++i == end())
goto break_out_of_outer_loop;
} while (aKey == i.key());
}
}
break_out_of_outer_loop:
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
{
QList<Key> res;
const_iterator i = begin();
while (i != end()) {
res.append(i.key());
++i;
}
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
{
QList<Key> res;
const_iterator i = begin();
while (i != end()) {
if (i.value() == avalue)
res.append(i.key());
++i;
}
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
{
return key(avalue, Key());
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
{
const_iterator i = begin();
while (i != end()) {
if (i.value() == avalue)
return i.key();
++i;
}
return defaultValue;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
{
QList<T> res;
const_iterator i = begin();
while (i != end()) {
res.append(i.value());
++i;
}
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
{
QList<T> res;
Node *node = *findNode(akey);
if (node != e) {
do {
res.append(node->value);
} while ((node = node->next) != e && node->key == akey);
}
return res;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
{
int cnt = 0;
Node *node = *findNode(akey);
if (node != e) {
do {
++cnt;
} while ((node = node->next) != e && node->key == akey);
}
return cnt;
}
template <class Key, class T>
Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
{
return value(akey);
}
template <class Key, class T>
Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
{
detach();
d->mightGrow();
uint h;
Node **node = findNode(akey, &h);
if (*node == e)
return createNode(h, akey, T(), node)->value;
return (*node)->value;
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
const T &avalue)
{
detach();
d->mightGrow();
uint h;
Node **node = findNode(akey, &h);
if (*node == e)
return iterator(createNode(h, akey, avalue, node));
if (!QTypeInfo<T>::isDummy)
(*node)->value = avalue;
return iterator(*node);
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,
const T &avalue)
{
detach();
d->mightGrow();
uint h;
Node **nextNode = findNode(akey, &h);
return iterator(createNode(h, akey, avalue, nextNode));
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
{
detach();
int oldSize = d->size;
Node **node = findNode(akey);
if (*node != e) {
bool deleteNext = true;
do {
Node *next = (*node)->next;
deleteNext = (next != e && next->key == (*node)->key);
deleteNode(*node);
*node = next;
--d->size;
} while (deleteNext);
d->hasShrunk();
}
return oldSize - d->size;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
{
detach();
Node **node = findNode(akey);
if (*node != e) {
T t = (*node)->value;
Node *next = (*node)->next;
deleteNode(*node);
*node = next;
--d->size;
d->hasShrunk();
return t;
}
return T();
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it)
{
if (it == iterator(e))
return it;
iterator ret = it;
++ret;
Node *node = it;
Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
while (*node_ptr != node)
node_ptr = &(*node_ptr)->next;
*node_ptr = node->next;
deleteNode(node);
--d->size;
return ret;
}
template <class Key, class T>
Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
{
detach();
d->rehash(-qMax(asize, 1));
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
{
return const_iterator(*findNode(akey));
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
{
return const_iterator(*findNode(akey));
}
template <class Key, class T>
Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
{
detach();
return iterator(*findNode(akey));
}
template <class Key, class T>
Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
{
return *findNode(akey) != e;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
uint *ahp) const
{
Node **node;
uint h = qHash(akey);
if (d->numBuckets) {
node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
Q_ASSERT(*node == e || (*node)->next);
while (*node != e && !(*node)->same_key(h, akey))
node = &(*node)->next;
} else {
node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
}
if (ahp)
*ahp = h;
return node;
}
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash<Key, T> &other) const
{
if (size() != other.size())
return false;
if (d == other.d)
return true;
const_iterator it = begin();
while (it != end()) {
const Key &akey = it.key();
const_iterator it2 = other.find(akey);
do {
if (it2 == other.end() || !(it2.key() == akey))
return false;
if (!QTypeInfo<T>::isDummy && !(it.value() == it2.value()))
return false;
++it;
++it2;
} while (it != end() && it.key() == akey);
}
return true;
}
template <class Key, class T>
class QMultiHash : public QHash<Key, T>
{
public:
QMultiHash() {}
QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
{ return QHash<Key, T>::insert(key, value); }
inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)
{ return QHash<Key, T>::insertMulti(key, value); }
inline QMultiHash &operator+=(const QMultiHash &other)
{ unite(other); return *this; }
inline QMultiHash operator+(const QMultiHash &other) const
{ QMultiHash result = *this; result += other; return result; }
#ifndef Q_NO_USING_KEYWORD
using QHash<Key, T>::contains;
using QHash<Key, T>::remove;
using QHash<Key, T>::count;
using QHash<Key, T>::find;
using QHash<Key, T>::constFind;
#else
inline bool contains(const Key &key) const
{ return QHash<Key, T>::contains(key); }
inline int remove(const Key &key)
{ return QHash<Key, T>::remove(key); }
inline int count(const Key &key) const
{ return QHash<Key, T>::count(key); }
inline int count() const
{ return QHash<Key, T>::count(); }
inline typename QHash<Key, T>::iterator find(const Key &key)
{ return QHash<Key, T>::find(key); }
inline typename QHash<Key, T>::const_iterator find(const Key &key) const
{ return QHash<Key, T>::find(key); }
inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const
{ return QHash<Key, T>::constFind(key); }
#endif
bool contains(const Key &key, const T &value) const;
int remove(const Key &key, const T &value);
int count(const Key &key, const T &value) const;
typename QHash<Key, T>::iterator find(const Key &key, const T &value)
{
typename QHash<Key, T>::iterator i(find(key));
typename QHash<Key, T>::iterator end(this->end());
while (i != end && i.key() == key) {
if (i.value() == value)
return i;
++i;
}
return end;
}
typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const
{
typename QHash<Key, T>::const_iterator i(constFind(key));
typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
while (i != end && i.key() == key) {
if (i.value() == value)
return i;
++i;
}
return end;
}
typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
{
return find(key, value);
}
private:
T &operator[](const Key &key);
const T operator[](const Key &key) const;
};
template <class Key, class T>
Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
{
return constFind(key, value) != QHash<Key, T>::constEnd();
}
template <class Key, class T>
Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
{
int n = 0;
typename QHash<Key, T>::iterator i(find(key));
typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
while (i != end && i.key() == key) {
if (i.value() == value) {
i = erase(i);
++n;
} else {
++i;
}
}
return n;
}
template <class Key, class T>
Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
{
int n = 0;
typename QHash<Key, T>::const_iterator i(constFind(key));
typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
while (i != end && i.key() == key) {
if (i.value() == value)
++n;
++i;
}
return n;
}
Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
QT_END_HEADER
#endif // QHASH_H
