45 #include <QtCore/qatomic.h> 46 #include <QtCore/qiterator.h> 47 #include <QtCore/qlist.h> 67 enum { LastLevel = 11, Sparseness = 3 };
82 void continueFreeData(
int offset);
83 Node *node_create(
Node *update[],
int offset);
84 Node *node_create(
Node *update[],
int offset,
int alignment);
85 void node_delete(
Node *update[],
int offset,
Node *node);
122 template <
class Key,
class T>
134 template <
class Key,
class T>
158 template <
class Key,
class T>
172 return int(
qMax(
sizeof(
void*), Q_ALIGNOF(Node)));
178 return reinterpret_cast<Node *
>(
reinterpret_cast<char *
>(node) - payload());
184 {
d->ref.ref();
if (!
d->sharable) detach(); }
185 inline ~QMap() {
if (!
d)
return;
if (!
d->ref.deref()) freeData(
d); }
188 #ifdef Q_COMPILER_RVALUE_REFS 190 {
qSwap(
d, other.
d);
return *
this; }
194 explicit QMap(
const typename std::map<Key, T> &other);
195 std::map<Key, T> toStdMap()
const;
201 inline int size()
const {
return d->size; }
203 inline bool isEmpty()
const {
return d->size == 0; }
205 inline void detach() {
if (
d->ref != 1) detach_helper(); }
207 inline void setSharable(
bool sharable) {
if (!sharable) detach();
d->sharable = sharable; }
213 int remove(
const Key &
key);
216 bool contains(
const Key &key)
const;
217 const Key key(
const T &value)
const;
218 const Key key(
const T &value,
const Key &defaultKey)
const;
219 const T value(
const Key &key)
const;
220 const T value(
const Key &key,
const T &defaultValue)
const;
221 T &operator[](
const Key &key);
222 const T operator[](
const Key &key)
const;
229 int count(
const Key &key)
const;
231 class const_iterator;
250 inline const Key &
key()
const {
return concrete(i)->key; }
251 inline T &
value()
const {
return concrete(i)->value; }
253 inline QT3_SUPPORT T &
data()
const {
return concrete(i)->value; }
255 inline T &
operator*()
const {
return concrete(i)->value; }
279 {
iterator r = *
this;
if (j > 0)
while (j--) ++r;
else while (j++) --r;
return r; }
285 #ifdef QT_STRICT_ITERATORS 297 inline operator bool()
const {
return false; }
299 friend class iterator;
317 #ifdef QT_STRICT_ITERATORS 324 inline const Key &
key()
const {
return concrete(i)->key; }
325 inline const T &
value()
const {
return concrete(i)->value; }
327 inline QT3_SUPPORT
const T &
data()
const {
return concrete(i)->value; }
329 inline const T &
operator*()
const {
return concrete(i)->value; }
330 inline const T *
operator->()
const {
return &concrete(i)->value; }
353 {
const_iterator r = *
this;
if (j > 0)
while (j--) ++r;
else while (j++) --r;
return r; }
359 #ifdef QT_STRICT_ITERATORS 367 inline operator bool()
const {
return false; }
369 friend class const_iterator;
372 inline iterator
begin() { detach();
return iterator(e->forward[0]); }
373 inline const_iterator
begin()
const {
return const_iterator(e->forward[0]); }
374 inline const_iterator
constBegin()
const {
return const_iterator(e->forward[0]); }
379 inline const_iterator
end()
const {
return const_iterator(e); }
380 inline const_iterator
constEnd()
const {
return const_iterator(e); }
381 iterator erase(iterator
it);
383 inline QT3_SUPPORT iterator
remove(iterator
it) {
return erase(it); }
384 inline QT3_SUPPORT
void erase(
const Key &aKey) {
remove(aKey); }
390 inline int count()
const {
return d->size; }
391 iterator find(
const Key &key);
392 const_iterator find(
const Key &key)
const;
393 const_iterator constFind(
const Key &key)
const;
394 iterator lowerBound(
const Key &key);
395 const_iterator lowerBound(
const Key &key)
const;
396 iterator upperBound(
const Key &key);
397 const_iterator upperBound(
const Key &key)
const;
398 iterator insert(
const Key &key,
const T &value);
400 QT3_SUPPORT iterator insert(
const Key &key,
const T &value,
bool overwrite);
402 iterator insertMulti(
const Key &key,
const T &value);
404 inline QT3_SUPPORT iterator replace(
const Key &aKey,
const T &aValue) {
return insert(aKey, aValue); }
416 inline void dump()
const {
d->dump(); }
420 void detach_helper();
428 template <
class Key,
class T>
443 template <
class Key,
class T>
449 template <
class Key,
class T>
455 Node *concreteNode = concrete(abstractNode);
456 new (&concreteNode->
key)
Key(akey);
458 new (&concreteNode->
value) T(avalue);
460 concreteNode->
key.~Key();
464 adt->
node_delete(aupdate, payload(), abstractNode);
480 template <
class Key,
class T>
486 for (
int i =
d->topLevel; i >= 0; i--) {
487 while ((next = cur->
forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
491 if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
498 template <
class Key,
class T>
502 if (
d->size == 0 || (node = findNode(akey)) == e) {
505 return concrete(node)->value;
509 template <
class Key,
class T>
513 if (
d->size == 0 || (node = findNode(akey)) == e) {
514 return adefaultValue;
516 return concrete(node)->value;
520 template <
class Key,
class T>
526 template <
class Key,
class T>
534 node = node_create(
d, update, akey, T());
535 return concrete(node)->value;
538 template <
class Key,
class T>
547 }
while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
552 template <
class Key,
class T>
555 return findNode(akey) != e;
558 template <
class Key,
class T>
567 node = node_create(
d, update, akey, avalue);
569 concrete(node)->value = avalue;
571 return iterator(node);
575 template <
class Key,
class T>
585 node = node_create(
d, update, akey, avalue);
588 concrete(node)->value = avalue;
590 return iterator(node);
594 template <
class Key,
class T>
601 mutableFindNode(update, akey);
602 return iterator(node_create(
d, update, akey, avalue));
605 template <
class Key,
class T>
608 return const_iterator(findNode(akey));
611 template <
class Key,
class T>
614 return const_iterator(findNode(akey));
617 template <
class Key,
class T>
621 return iterator(findNode(akey));
624 template <
class Key,
class T>
632 insertMulti(it.key(), it.value());
637 #if defined(_MSC_VER) 638 #pragma warning(push) 639 #pragma warning(disable:4189) 641 template <
class Key,
class T>
650 Node *concreteNode = concrete(reinterpret_cast<QMapData::Node *>(cur));
651 concreteNode->
key.~Key();
652 concreteNode->
value.~T();
657 #if defined(_MSC_VER) 661 template <
class Key,
class T>
669 int oldSize =
d->size;
671 for (
int i =
d->topLevel; i >= 0; i--) {
672 while ((next = cur->
forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
677 if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
678 bool deleteNext =
true;
682 deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
683 concrete(cur)->key.~Key();
684 concrete(cur)->value.~T();
685 d->node_delete(update, payload(), cur);
686 }
while (deleteNext);
688 return oldSize -
d->size;
691 template <
class Key,
class T>
700 for (
int i =
d->topLevel; i >= 0; i--) {
701 while ((next = cur->
forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
706 if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
707 T t = concrete(next)->value;
708 concrete(next)->key.~Key();
709 concrete(next)->value.~T();
710 d->node_delete(update, payload(), next);
716 template <
class Key,
class T>
723 if (it == iterator(e))
726 for (
int i =
d->topLevel; i >= 0; i--) {
727 while ((next = cur->
forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))
736 concrete(cur)->key.~Key();
737 concrete(cur)->value.~T();
738 d->node_delete(update, payload(), cur);
739 return iterator(next);
742 for (
int i = 0; i <=
d->topLevel; ++i) {
743 if (update[i]->forward[i] != cur)
751 template <
class Key,
class T>
757 x.d->insertInOrder =
true;
763 Node *concreteNode = concrete(cur);
764 node_create(x.d, update, concreteNode->
key, concreteNode->
value);
771 x.d->insertInOrder =
false;
778 template <
class Key,
class T>
780 const Key &akey)
const 785 for (
int i =
d->topLevel; i >= 0; i--) {
786 while ((next = cur->
forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
790 if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
797 template <
class Key,
class T>
802 const_iterator i = begin();
805 const Key &aKey = i.key();
809 goto break_out_of_outer_loop;
810 }
while (!(aKey < i.key()));
813 break_out_of_outer_loop:
817 template <
class Key,
class T>
822 const_iterator i = begin();
830 template <
class Key,
class T>
834 const_iterator i = begin();
836 if (i.value() == avalue)
843 template <
class Key,
class T>
846 return key(avalue,
Key());
849 template <
class Key,
class T>
852 const_iterator i = begin();
854 if (i.value() == avalue)
862 template <
class Key,
class T>
867 const_iterator i = begin();
875 template <
class Key,
class T>
882 res.
append(concrete(node)->value);
884 }
while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
889 template <
class Key,
class T>
894 mutableFindNode(update, akey);
895 return const_iterator(update[0]->forward[0]);
898 template <
class Key,
class T>
902 return static_cast<QMapData::Node *
>(
const_cast<const QMap *
>(
this)->lowerBound(akey));
905 template <
class Key,
class T>
910 mutableFindNode(update, akey);
912 while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))
914 return const_iterator(node);
917 template <
class Key,
class T>
921 return static_cast<QMapData::Node *
>(
const_cast<const QMap *
>(
this)->upperBound(akey));
924 template <
class Key,
class T>
927 if (size() != other.
size())
932 const_iterator it1 = begin();
933 const_iterator it2 = other.
begin();
935 while (it1 !=
end()) {
945 template <
class Key,
class T>
949 d->insertInOrder =
true;
950 typename std::map<Key,T>::const_iterator
it = other.end();
951 while (it != other.begin()) {
953 insert((*it).first, (*it).second);
955 d->insertInOrder =
false;
958 template <
class Key,
class T>
961 std::map<Key, T>
map;
962 const_iterator
it =
end();
963 while (it != begin()) {
965 map.insert(std::pair<Key, T>(it.key(), it.value()));
972 template <
class Key,
class T>
986 { this->unite(other);
return *
this; }
988 {
QMultiMap result = *
this; result += other;
return result; }
990 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT) 998 inline bool contains(
const Key &key)
const 1000 inline int remove(
const Key &
key)
1002 inline int count(
const Key &key)
const 1004 inline int count()
const 1014 bool contains(
const Key &key,
const T &value)
const;
1016 int remove(
const Key &
key,
const T &value);
1018 int count(
const Key &key,
const T &value)
const;
1023 while (i != end && !qMapLessThanKey<Key>(key, i.
key())) {
1024 if (i.
value() == value)
1033 while (i != end && !qMapLessThanKey<Key>(key, i.
key())) {
1034 if (i.
value() == value)
1041 {
return find(key, value); }
1043 T &operator[](
const Key &key);
1044 const T operator[](
const Key &key)
const;
1047 template <
class Key,
class T>
1053 template <
class Key,
class T>
1059 while (i != end && !qMapLessThanKey<Key>(key, i.
key())) {
1060 if (i.
value() == value) {
1070 template <
class Key,
class T>
1076 while (i != end && !qMapLessThanKey<Key>(key, i.
key())) {
1077 if (i.
value() == value)
The QMultiMap class is a convenience QMap subclass that provides multi-valued maps.
Key key_type
Typedef for Key.
void node_delete(Node *update[], int offset, Node *node)
const Key & key() const
Returns the current item's key as a const reference.
void setInsertInOrder(bool ordered)
qptrdiff difference_type
Typedef for ptrdiff_t.
QIntegerForSizeof< void * >::Unsigned quintptr
#define QT_END_NAMESPACE
This macro expands to.
const Key key(const T &value) const
Returns the first key with value value.
QMultiMap(const QMap< Key, T > &other)
Constructs a copy of other (which can be a QMap or a QMultiMap).
bool empty() const
This function is provided for STL compatibility.
#define it(className, varName)
std::bidirectional_iterator_tag iterator_category
A synonym for {std::bidirectional_iterator_tag} indicating this iterator is a bidirectional iterator...
QList< Key > uniqueKeys() const
Returns a list containing all the keys in the map in ascending order.
bool isDetached() const
Returns true if the map's internal data isn't shared with any other map object; otherwise returns fal...
QMap< Key, T >::iterator insert(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
QMultiMap & operator+=(const QMultiMap &other)
Inserts all the items in the other map into this map and returns a reference to this map...
iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
QList< T > values() const
Returns a list containing all the values in the map, in ascending order of their keys.
const_iterator & operator-=(int j)
Makes the iterator go back by j items.
const T * operator->() const
Returns a pointer to the current item's value.
bool operator!=(const iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
QMapPayloadNode< Key, T > PayloadNode
QMap< Key, T > & operator=(const QMap< Key, T > &other)
Assigns other to this map and returns a reference to this map.
const_iterator(const iterator &o)
Constructs a copy of other.
const_iterator begin() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
static void clear(QVariant::Private *d)
const_iterator & operator+=(int j)
Advances the iterator by j items.
int remove(const Key &key, const T &value)
Removes all the items that have the key key and the value value from the map.
int size() const
Returns the number of (key, value) pairs in the map.
Node * node_create(Node *update[], int offset)
QMapData::Node * mutableFindNode(QMapData::Node *update[], const Key &key) const
T & operator[](const Key &key)
Returns the value associated with the key key as a modifiable reference.
QMultiMap()
Constructs an empty map.
T mapped_type
Typedef for T.
const_iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
const_iterator(QMapData::Node *node)
QMapData::Node * node_create(QMapData *d, QMapData::Node *update[], const Key &key, const T &value)
const Key & key() const
Returns the current item's key.
void continueFreeData(int offset)
iterator find(const Key &key)
Returns an iterator pointing to the item with key key in the map.
bool operator!=(QBool b1, bool b2)
const_iterator & operator--()
The prefix – operator (–i) makes the preceding item current and returns an iterator pointing to the...
const_iterator operator++(int)
The postfix ++ operator (i++) advances the iterator to the next item in the map and returns an iterat...
void setSharable(bool sharable)
iterator operator++(int)
The postfix ++ operator (i++) advances the iterator to the next item in the map and returns an iterat...
T & operator*() const
Returns a modifiable reference to the current item's value.
QMap< Key, T >::const_iterator constFind(const Key &key, const T &value) const
Returns an iterator pointing to the item with key key and the value value in the map.
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
int size_type
Typedef for int.
static QTextFrameData * createData(QTextFrame *f)
#define Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(C)
QMap< Key, T > & unite(const QMap< Key, T > &other)
Inserts all the items in the other map into this map.
bool operator!=(const const_iterator &o) const
void freeData(QMapData *d)
T & value() const
Returns a modifiable reference to the current item's value.
iterator insertMulti(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
const_iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
void append(const T &t)
Inserts value at the end of the list.
static QMapData * createData()
QMultiMap operator+(const QMultiMap &other) const
Returns a map that contains all the items in this map in addition to all the items in other...
QFuture< void > map(Sequence &sequence, MapFunction function)
QMapData::Node * backward
#define QT_BEGIN_NAMESPACE
This macro expands to.
static bool isEmpty(const char *str)
const_iterator ConstIterator
Qt-style synonym for QMap::const_iterator.
QMap< Key, T >::iterator find(const Key &key, const T &value)
Returns an iterator pointing to the item with key key and value value in the map. ...
QIntegerForSizeof< void * >::Signed qptrdiff
bool operator==(const const_iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
const T value(const Key &key) const
Returns the value associated with the key key.
int count() const
Same as size().
iterator Iterator
Qt-style synonym for QMap::iterator.
iterator & operator--()
The prefix – operator (–i) makes the preceding item current and returns an iterator pointing to the...
#define Q_INLINE_TEMPLATE
static const char * data(const QByteArray &arr)
QMapData * forward[QMapData::LastLevel+1]
QMap()
Constructs an empty map.
QList< Key > keys() const
Returns a list containing all the keys in the map in ascending order.
QMap< Key, T >::iterator replace(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
void detach()
Detaches this map from any other maps with which it may share data.
T * operator->() const
Returns a pointer to the current item's value.
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the map.
iterator & operator++()
The prefix ++ operator (++i) advances the iterator to the next item in the map and returns an iterato...
std::map< Key, T > toStdMap() const
Returns an STL map equivalent to this QMap.
bool operator!=(const QMap< Key, T > &other) const
Returns true if other is not equal to this map; otherwise returns false.
iterator & operator+=(int j)
Advances the iterator by j items.
void qSwap(T &value1, T &value2)
iterator begin()
Returns an STL-style iterator pointing to the first item in the map.
bool operator==(const const_iterator &o) const
#define Q_DECLARE_ASSOCIATIVE_ITERATOR(C)
void swap(QMap< Key, T > &other)
Swaps map other with this map.
bool qMapLessThanKey(const Key &key1, const Key &key2)
int remove(const Key &key)
Removes all the items that have the key key from the map.
bool contains(const Key &key, const T &value) const
Returns true if the map contains an item with key key and value value; otherwise returns false...
The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap.
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the map...
const_iterator end() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap.
QMapData::Node * backward
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the map...
bool operator==(const iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
iterator insert(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
iterator(QMapData::Node *node)
bool operator==(const QMap< Key, T > &other) const
Returns true if other is equal to this map; otherwise returns false.
const T & operator*() const
Returns the current item's value.
iterator & operator-=(int j)
Makes the iterator go back by j items.
bool isEmpty() const
Returns true if the map contains no items; otherwise returns false.
const_iterator & operator++()
The prefix ++ operator (++i) advances the iterator to the next item in the map and returns an iterato...
Node & operator=(const Node &)
const_iterator()
Constructs an uninitialized iterator.
const_iterator operator--(int)
The postfix – operator (i–) makes the preceding item current and returns an iterator pointing to th...
const T & value() const
Returns the current item's value.
bool contains(const Key &key) const
Returns true if the map contains an item with key key; otherwise returns false.
QMap(const QMap< Key, T > &other)
Constructs a copy of other.
static QString dump(const QByteArray &)
const_iterator constFind(const Key &key) const
Returns an const iterator pointing to the item with key key in the map.
iterator()
Constructs an uninitialized iterator.
bool isSharedWith(const QMap< Key, T > &other) const
iterator erase(iterator it)
Removes the (key, value) pair pointed to by the iterator pos from the map, and returns an iterator to...
iterator upperBound(const Key &key)
Returns an iterator pointing to the item that immediately follows the last item with key key in the m...
T take(const Key &key)
Removes the item with the key key from the map and returns the value associated with it...
static Node * concrete(QMapData::Node *node)
iterator operator--(int)
The postfix – operator (i–) makes the preceding item current and returns an iterator pointing to th...
iterator lowerBound(const Key &key)
Returns an iterator pointing to the first item with key key in the map.
void swap(QMultiMap< Key, T > &other)
Swaps map other with this map.
static const KeyPair *const end
#define Q_OUTOFLINE_TEMPLATE
bool operator!=(const const_iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
bool operator==(QBool b1, bool b2)
std::bidirectional_iterator_tag iterator_category
A synonym for {std::bidirectional_iterator_tag} indicating this iterator is a bidirectional iterator...
QMap< Key, T >::const_iterator find(const Key &key, const T &value) const
Returns a const iterator pointing to the item with the given key and value in the map...
void clear()
Removes all items from the map.
iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
The QMap class is a template class that provides a skip-list-based dictionary.
void reserve(int size)
Reserve space for alloc elements.
QMapData::Node * findNode(const Key &key) const
The QList class is a template class that provides lists.
static QMapData shared_null
timeval operator+(const timeval &t1, const timeval &t2)