45 #include <QtCore/qatomic.h> 46 #include <QtCore/qchar.h> 47 #include <QtCore/qiterator.h> 48 #include <QtCore/qlist.h> 49 #include <QtCore/qpair.h> 72 return uint(((key >> (8 *
sizeof(
uint) - 1)) ^ key) & (~0U));
74 return uint(key & (~0U));
81 return uint(((key >> (8 *
sizeof(
uint) - 1)) ^ key) & (~0U));
83 return uint(key & (~0U));
93 #if defined(Q_CC_MSVC) 94 #pragma warning( push ) 95 #pragma warning( disable : 4311 ) // disable pointer truncation warning 99 return qHash(reinterpret_cast<quintptr>(key));
101 #if defined(Q_CC_MSVC) 102 #pragma warning( pop ) 109 return ((h1 << 16) | (h1 >> 16)) ^ h2;
131 void *allocateNode();
132 void *allocateNode(
int nodeAlign);
133 void freeNode(
void *node);
134 QHashData *detach_helper(
void (*node_duplicate)(
Node *,
void *),
int nodeSize);
135 QHashData *detach_helper2(
void (*node_duplicate)(
Node *,
void *),
void (*node_delete)(
Node *),
136 int nodeSize,
int nodeAlign);
140 void rehash(
int hint);
141 void free_helper(
void (*node_delete)(
Node *));
142 void destroyAndFree();
144 #ifdef QT_QHASH_DEBUG 149 static Node *previousNode(
Node *node);
156 if (size >= numBuckets)
162 if (size >= numBuckets) {
172 if (size <= (numBuckets >> 3) && numBits > userNumBits) {
174 rehash(
qMax(
int(numBits) - 2,
int(userNumBits)));
175 }
QT_CATCH(
const std::bad_alloc &) {
183 Node *e =
reinterpret_cast<Node *
>(
this);
184 Node **bucket = buckets;
205 template <
class Key,
class T>
215 template <
class Key,
class T>
224 inline QHashNode(
const Key &key0,
const T &value0) : key(key0), value(value0) {}
229 #define Q_HASH_DECLARE_INT_NODES(key_type) \ 231 struct QHashDummyNode<key_type, T> { \ 232 QHashDummyNode *next; \ 233 union { uint h; key_type key; }; \ 235 inline QHashDummyNode(key_type ) {} \ 239 struct QHashNode<key_type, T> { \ 241 union { uint h; key_type key; }; \ 244 inline QHashNode(key_type ) {} \ 245 inline QHashNode(key_type , const T &value0) : value(value0) {} \ 246 inline bool same_key(uint h0, key_type) { return h0 == h; } \ 249 #if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN 255 #undef Q_HASH_DECLARE_INT_NODES 257 template <
class Key,
class T>
269 return reinterpret_cast<Node *
>(node);
273 static inline int alignOfNode() {
return qMax<int>(
sizeof(
void*), Q_ALIGNOF(Node)); }
274 static inline int alignOfDummyNode() {
return qMax<int>(
sizeof(
void*), Q_ALIGNOF(DummyNode)); }
283 inline ~QHash() {
if (!
d->ref.deref()) freeData(
d); }
286 #ifdef Q_COMPILER_RVALUE_REFS 288 {
qSwap(
d, other.
d);
return *
this; }
295 inline int size()
const {
return d->size; }
297 inline bool isEmpty()
const {
return d->size == 0; }
300 void reserve(
int size);
303 inline void detach() {
if (
d->ref != 1) detach_helper(); }
305 inline void setSharable(
bool sharable) {
if (!sharable) detach();
d->sharable = sharable; }
310 int remove(
const Key &
key);
311 T take(
const Key &key);
313 bool contains(
const Key &key)
const;
314 const Key key(
const T &value)
const;
315 const Key key(
const T &value,
const Key &defaultKey)
const;
316 const T value(
const Key &key)
const;
317 const T value(
const Key &key,
const T &defaultValue)
const;
318 T &operator[](
const Key &key);
319 const T operator[](
const Key &key)
const;
326 int count(
const Key &key)
const;
328 class const_iterator;
343 inline operator Node *()
const {
return concrete(i); }
347 inline const Key &
key()
const {
return concrete(i)->key; }
348 inline T &
value()
const {
return concrete(i)->value; }
349 inline T &
operator*()
const {
return concrete(i)->value; }
373 {
iterator r = *
this;
if (j > 0)
while (j--) ++r;
else while (j++) --r;
return r; }
379 #ifdef QT_STRICT_ITERATORS 391 inline operator bool()
const {
return false; }
393 friend class iterator;
408 inline operator Node *()
const {
return concrete(i); }
411 : i(reinterpret_cast<
QHashData::Node *>(node)) { }
412 #ifdef QT_STRICT_ITERATORS 419 inline const Key &
key()
const {
return concrete(i)->key; }
420 inline const T &
value()
const {
return concrete(i)->value; }
421 inline const T &
operator*()
const {
return concrete(i)->value; }
422 inline const T *
operator->()
const {
return &concrete(i)->value; }
445 {
const_iterator r = *
this;
if (j > 0)
while (j--) ++r;
else while (j++) --r;
return r; }
451 #ifdef QT_STRICT_ITERATORS 459 inline operator bool()
const {
return false; }
461 friend class const_iterator;
464 inline iterator
begin() { detach();
return iterator(
d->firstNode()); }
465 inline const_iterator
begin()
const {
return const_iterator(
d->firstNode()); }
466 inline const_iterator
constBegin()
const {
return const_iterator(
d->firstNode()); }
467 inline iterator
end() { detach();
return iterator(e); }
468 inline const_iterator
end()
const {
return const_iterator(e); }
469 inline const_iterator
constEnd()
const {
return const_iterator(e); }
470 iterator erase(iterator
it);
475 inline int count()
const {
return d->size; }
476 iterator find(
const Key &key);
477 const_iterator find(
const Key &key)
const;
478 const_iterator constFind(
const Key &key)
const;
479 iterator insert(
const Key &key,
const T &value);
480 iterator insertMulti(
const Key &key,
const T &value);
491 #ifdef QT_QHASH_DEBUG 492 inline void dump()
const {
d->dump(); }
493 inline void checkSanity()
const {
d->checkSanity(); }
497 void detach_helper();
499 Node **findNode(
const Key &key,
uint *hp = 0)
const;
500 Node *createNode(
uint h,
const Key &key,
const T &value, Node **nextNode);
501 void deleteNode(Node *node);
504 static void duplicateNode(
QHashData::Node *originalNode,
void *newNode);
508 template <
class Key,
class T>
511 deleteNode2(reinterpret_cast<QHashData::Node*>(node));
515 template <
class Key,
class T>
519 concrete(node)->~QHashNode<
Key, T>();
521 concrete(node)->~Node();
525 template <
class Key,
class T>
528 Node *concreteNode = concrete(node);
530 (void)
new (newNode) DummyNode(concreteNode->
key);
532 (void)
new (newNode) Node(concreteNode->
key, concreteNode->
value);
536 template <
class Key,
class T>
543 node =
reinterpret_cast<Node *
>(
new (
d->allocateNode(alignOfDummyNode())) DummyNode(akey));
545 node =
new (
d->allocateNode(alignOfNode())) Node(akey, avalue);
549 node->
next = *anextNode;
555 template <
class Key,
class T>
562 insertMulti(it.key(), it.value());
567 template <
class Key,
class T>
573 template <
class Key,
class T>
579 template <
class Key,
class T>
582 QHashData *x =
d->detach_helper2(duplicateNode, deleteNode2,
590 template <
class Key,
class T>
605 template <
class Key,
class T>
609 if (
d->size == 0 || (node = *findNode(akey)) == e) {
616 template <
class Key,
class T>
620 if (
d->size == 0 || (node = *findNode(akey)) == e) {
621 return adefaultValue;
627 template <
class Key,
class T>
632 const_iterator i = begin();
635 const Key &aKey = i.key();
639 goto break_out_of_outer_loop;
640 }
while (aKey == i.key());
643 break_out_of_outer_loop:
647 template <
class Key,
class T>
652 const_iterator i = begin();
660 template <
class Key,
class T>
664 const_iterator i = begin();
666 if (i.value() == avalue)
673 template <
class Key,
class T>
676 return key(avalue,
Key());
679 template <
class Key,
class T>
682 const_iterator i = begin();
684 if (i.value() == avalue)
692 template <
class Key,
class T>
697 const_iterator i = begin();
705 template <
class Key,
class T>
709 Node *node = *findNode(akey);
713 }
while ((node = node->
next) != e && node->
key == akey);
718 template <
class Key,
class T>
722 Node *node = *findNode(akey);
726 }
while ((node = node->
next) != e && node->
key == akey);
731 template <
class Key,
class T>
737 template <
class Key,
class T>
743 Node **node = findNode(akey, &h);
746 node = findNode(akey, &h);
747 return createNode(h, akey, T(), node)->
value;
749 return (*node)->
value;
752 template <
class Key,
class T>
759 Node **node = findNode(akey, &h);
762 node = findNode(akey, &h);
763 return iterator(createNode(h, akey, avalue, node));
767 (*node)->value = avalue;
768 return iterator(*node);
771 template <
class Key,
class T>
779 Node **nextNode = findNode(akey, &h);
780 return iterator(createNode(h, akey, avalue, nextNode));
783 template <
class Key,
class T>
790 int oldSize =
d->size;
791 Node **node = findNode(akey);
793 bool deleteNext =
true;
795 Node *next = (*node)->next;
796 deleteNext = (next != e && next->
key == (*node)->key);
800 }
while (deleteNext);
803 return oldSize -
d->size;
806 template <
class Key,
class T>
813 Node **node = findNode(akey);
815 T t = (*node)->value;
816 Node *next = (*node)->next;
826 template <
class Key,
class T>
829 if (it == iterator(e))
836 Node **node_ptr =
reinterpret_cast<Node **
>(&
d->buckets[node->
h %
d->numBuckets]);
837 while (*node_ptr != node)
838 node_ptr = &(*node_ptr)->
next;
839 *node_ptr = node->
next;
845 template <
class Key,
class T>
849 d->rehash(-
qMax(asize, 1));
852 template <
class Key,
class T>
855 return const_iterator(*findNode(akey));
858 template <
class Key,
class T>
861 return const_iterator(*findNode(akey));
864 template <
class Key,
class T>
868 return iterator(*findNode(akey));
871 template <
class Key,
class T>
874 return *findNode(akey) != e;
877 template <
class Key,
class T>
885 node =
reinterpret_cast<Node **
>(&
d->buckets[h %
d->numBuckets]);
887 while (*node != e && !(*node)->
same_key(h, akey))
888 node = &(*node)->
next;
890 node =
const_cast<Node **
>(
reinterpret_cast<const Node *
const *
>(&e));
897 template <
class Key,
class T>
900 if (size() != other.
size())
905 const_iterator
it = begin();
907 while (it !=
end()) {
908 const Key &akey = it.key();
910 const_iterator it2 = other.
find(akey);
912 if (it2 == other.
end() || !(it2.key() == akey))
918 }
while (it !=
end() && it.key() == akey);
923 template <
class Key,
class T>
938 { this->unite(other);
return *
this; }
940 {
QMultiHash result = *
this; result += other;
return result; }
942 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT) 950 inline bool contains(
const Key &key)
const 952 inline int remove(
const Key &
key)
954 inline int count(
const Key &key)
const 956 inline int count()
const 966 bool contains(
const Key &key,
const T &value)
const;
968 int remove(
const Key &
key,
const T &value);
970 int count(
const Key &key,
const T &value)
const;
975 while (i != end && i.
key() ==
key) {
976 if (i.
value() == value)
985 while (i != end && i.
key() ==
key) {
986 if (i.
value() == value)
993 {
return find(key, value); }
995 T &operator[](
const Key &key);
996 const T operator[](
const Key &key)
const;
999 template <
class Key,
class T>
1005 template <
class Key,
class T>
1011 while (i != end && i.
key() ==
key) {
1012 if (i.
value() == value) {
1022 template <
class Key,
class T>
1028 while (i != end && i.
key() ==
key) {
1029 if (i.
value() == value)
The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes.
iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
iterator & operator-=(int j)
Makes the iterator go back by j items.
iterator & operator++()
The prefix ++ operator (++i) advances the iterator to the next item in the hash and returns an iterat...
void setSharable(bool sharable)
The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash...
const_iterator begin() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
bool isDetached() const
Returns true if the hash's internal data isn't shared with any other hash object; otherwise returns f...
#define QT_END_NAMESPACE
This macro expands to.
bool operator!=(const iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
void clear()
Removes all items from the hash.
QHash< Key, T >::const_iterator constFind(const Key &key, const T &value) const
Returns an iterator pointing to the item with the key and the value in the hash.
int remove(const Key &key)
Removes all the items that have the key from the hash.
int size_type
Typedef for int.
ushort unicode() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
#define it(className, varName)
iterator & operator--()
The prefix – operator (–i) makes the preceding item current and returns an iterator pointing to the...
static Node * previousNode(Node *node)
void swap(QMultiHash< Key, T > &other)
Swaps hash other with this hash.
The QByteArray class provides an array of bytes.
bool operator==(const const_iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
const_iterator ConstIterator
Qt-style synonym for QHash::const_iterator.
static void clear(QVariant::Private *d)
bool operator==(const QHashDummyValue &, const QHashDummyValue &)
T mapped_type
Typedef for T.
void squeeze()
Reduces the size of the QHash's internal hash table to save memory.
static Node * nextNode(Node *node)
bool operator!=(QBool b1, bool b2)
T & value() const
Returns a modifiable reference to the current item's value.
The QString class provides a Unicode character string.
void swap(QHash< Key, T > &other)
Swaps hash other with this hash.
T take(const Key &key)
Removes the item with the key from the hash and returns the value associated with it...
The QHash class is a template class that provides a hash-table-based dictionary.
QHash< Key, T > & operator=(const QHash< Key, T > &other)
Assigns other to this hash and returns a reference to this hash.
const_iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
iterator & operator+=(int j)
Advances the iterator by j items.
~QHash()
Destroys the hash.
bool contains(const Key &key) const
Returns true if the hash contains an item with the key; otherwise returns false.
iterator()
Constructs an uninitialized iterator.
std::bidirectional_iterator_tag iterator_category
QHash< Key, T >::iterator find(const Key &key, const T &value)
Returns an iterator pointing to the item with the key and value.
The QChar class provides a 16-bit Unicode character.
bool same_key(uint h0, const Key &key0)
QHashNode(const Key &key0, const T &value0)
const T value(const Key &key) const
Returns the value associated with the key.
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
QHashDummyNode(const Key &key0)
Key key_type
Typedef for Key.
void reserve(int size)
Ensures that the QHash's internal hash table consists of at least size buckets.
#define Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(C)
iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
Node ** findNode(const Key &key, uint *hp=0) const
bool operator!=(const QHash< Key, T > &other) const
Returns true if other is not equal to this hash; otherwise returns false.
const_iterator & operator-=(int j)
Makes the iterator go back by j items.
const Key & key() const
Returns the current item's key.
const_iterator & operator+=(int j)
Advances the iterator by j items.
void append(const T &t)
Inserts value at the end of the list.
Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE|Q_DUMMY_TYPE)
#define QT_BEGIN_NAMESPACE
This macro expands to.
qptrdiff difference_type
Typedef for ptrdiff_t.
QHash< Key, T >::const_iterator find(const Key &key, const T &value) const
static bool isEmpty(const char *str)
QIntegerForSizeof< void * >::Signed qptrdiff
bool contains(const Key &key, const T &value) const
Returns true if the hash contains an item with the key and value; otherwise returns false...
QMultiHash(const QHash< Key, T > &other)
Constructs a copy of other (which can be a QHash or a QMultiHash).
const_iterator()
Constructs an uninitialized iterator.
bool isEmpty() const
Returns true if the hash contains no items; otherwise returns false.
const T & value() const
Returns the current item's value.
#define Q_INLINE_TEMPLATE
const T & operator*() const
Returns the current item's value.
const_iterator constFind(const Key &key) const
Returns an iterator pointing to the item with the key in the hash.
const_iterator end() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
QMultiHash operator+(const QMultiHash &other) const
Returns a hash that contains all the items in this hash in addition to all the items in other...
bool operator==(const QHash< Key, T > &other) const
Returns true if other is equal to this hash; otherwise returns false.
const_iterator operator++(int)
The postfix ++ operator (i++) advances the iterator to the next item in the hash and returns an itera...
#define Q_HASH_DECLARE_INT_NODES(key_type)
void free_helper(void(*node_delete)(Node *))
const Key & key() const
Returns the current item's key as a const reference.
const_iterator & operator++()
The prefix ++ operator (++i) advances the iterator to the next item in the hash and returns an iterat...
static QHashData shared_null
bool operator==(const const_iterator &o) const
const_iterator(const iterator &o)
Constructs a copy of other.
The QStringRef class provides a thin wrapper around QString substrings.
void qSwap(T &value1, T &value2)
QHash(const QHash< Key, T > &other)
Constructs a copy of other.
QMultiHash & operator+=(const QMultiHash &other)
Inserts all the items in the other hash into this hash and returns a reference to this hash...
The QBitArray class provides an array of bits.
#define Q_DECLARE_ASSOCIATIVE_ITERATOR(C)
const_iterator(void *node)
QHash< Key, T >::iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the hash.
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the hash...
uint qHash(const QUrl &url)
int remove(const Key &key, const T &value)
Removes all the items that have the key and the value value from the hash.
int size() const
Returns the number of items in the hash.
const T * operator->() const
Returns a pointer to the current item's value.
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the hash...
static Node * concrete(QHashData::Node *node)
Node * createNode(uint h, const Key &key, const T &value, Node **nextNode)
bool operator!=(const const_iterator &o) const
std::bidirectional_iterator_tag iterator_category
void detach()
Detaches this hash from any other hashes with which it may share data.
const Key key(const T &value) const
Returns the first key mapped to value.
QList< T > values() const
Returns a list containing all the values in the hash, in an arbitrary order.
iterator operator++(int)
The postfix ++ operator (i++) advances the iterator to the next item in the hash and returns an itera...
bool operator==(const iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash.
QHash< Key, T >::iterator replace(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
bool empty() const
This function is provided for STL compatibility.
bool operator!=(const const_iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
QHashDummyNode< Key, T > DummyNode
QList< Key > uniqueKeys() const
Returns a list containing all the keys in the map.
iterator begin()
Returns an STL-style iterator pointing to the first item in the hash.
static void deleteNode2(QHashData::Node *node)
static QString dump(const QByteArray &)
void deleteNode(Node *node)
const_iterator & operator--()
The prefix – operator (–i) makes the preceding item current and returns an iterator pointing to the...
static int alignOfDummyNode()
bool isSharedWith(const QHash< Key, T > &other) const
QMultiHash()
Constructs an empty hash.
int capacity() const
Returns the number of buckets in the QHash's internal hash table.
QHashNode(const Key &key0)
T * operator->() const
Returns a pointer to the current item's value.
iterator find(const Key &key)
Returns an iterator pointing to the item with the key in the hash.
iterator insertMulti(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
T & operator*() const
Returns a modifiable reference to the current item's value.
static void duplicateNode(QHashData::Node *originalNode, void *newNode)
static const KeyPair *const end
#define Q_OUTOFLINE_TEMPLATE
int count() const
Same as size().
const_iterator operator--(int)
The postfix – operator (i–) makes the preceding item current and returns an iterator pointing to th...
T & operator[](const Key &key)
Returns the value associated with the key as a modifiable reference.
QList< Key > keys() const
Returns a list containing all the keys in the hash, in an arbitrary order.
const_iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
iterator erase(iterator it)
Removes the (key, value) pair associated with the iterator pos from the hash, and returns an iterator...
iterator Iterator
Qt-style synonym for QHash::iterator.
QHash< Key, T > & unite(const QHash< Key, T > &other)
Inserts all the items in the other hash into this hash.
void reserve(int size)
Reserve space for alloc elements.
QHash()
Constructs an empty hash.
The QList class is a template class that provides lists.
iterator operator--(int)
The postfix – operator (i–) makes the preceding item current and returns an iterator pointing to th...
void freeData(QHashData *d)
timeval operator+(const timeval &t1, const timeval &t2)
iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.