67 enum { LastLevel = 11, Sparseness = 3 };
75 uint insertInOrder : 1;
77 uint strictAlignment : 1;
80 static QMapData *createData();
81 static QMapData *createData(
int alignment);
82 void continueFreeData(
int offset);
87 uint adjust_ptr(
Node *node);
112 Q_ASSERT(
sizeof(quintptr) ==
sizeof(Ptr *));
113 return quintptr(key1) < quintptr(key2);
118 Q_ASSERT(
sizeof(quintptr) ==
sizeof(
const Ptr *));
119 return quintptr(key1) < quintptr(key2);
122 template <
class Key,
class T>
134 template <
class Key,
class T>
158 template <
class Key,
class T>
169 static inline int payload() {
return sizeof(PayloadNode) -
sizeof(
QMapData::Node *); }
170 static inline int alignment() {
172 return int(qMax(
sizeof(
void*), Q_ALIGNOF(Node)));
178 return reinterpret_cast<Node *
>(
reinterpret_cast<char *
>(node) - payload());
188 #ifdef Q_COMPILER_RVALUE_REFS
190 {
qSwap(
d, other.d);
return *
this; }
194 explicit QMap(
const typename std::map<Key, T> &other);
213 int remove(
const Key &
key);
220 const T
value(
const Key &
key,
const T &defaultValue)
const;
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; }
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; }
384 inline QT3_SUPPORT
void erase(
const Key &aKey) {
remove(aKey); }
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;
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>
611 template <
class Key,
class T>
617 template <
class Key,
class T>
624 template <
class Key,
class T>
637 #if defined(_MSC_VER)
638 #pragma warning(push)
639 #pragma warning(disable:4189)
641 template <
class Key,
class T>
644 if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
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>
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);
742 for (
int i = 0; i <= d->topLevel; ++i) {
743 if (update[i]->forward[i] != cur)
751 template <
class Key,
class T>
763 Node *concreteNode = concrete(cur);
764 node_create(x.d, update, concreteNode->key, concreteNode->value);
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>
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>
830 template <
class Key,
class T>
836 if (i.value() == avalue)
843 template <
class Key,
class T>
846 return key(avalue,
Key());
849 template <
class Key,
class T>
854 if (i.value() == avalue)
862 template <
class Key,
class T>
875 template <
class Key,
class T>
884 }
while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
889 template <
class Key,
class T>
894 mutableFindNode(update, akey);
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))
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>
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;
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)
1000 inline int remove(
const Key &
key)
1004 inline int count()
const
1023 while (i != end && !qMapLessThanKey<Key>(key, i.
key())) {
1033 while (i != end && !qMapLessThanKey<Key>(key, i.
key())) {
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())) {
1070 template <
class Key,
class T>
1076 while (i != end && !qMapLessThanKey<Key>(key, i.
key())) {
GLdouble GLdouble GLdouble r
unsigned int(APIENTRYP PFNGLXGETAGPOFFSETMESAPROC)(const void *pointer)
iterator erase(iterator it)
const_iterator(QMapData::Node *node)
const_iterator constEnd() const
iterator operator+(int j) const
const_iterator operator+(int j) const
const_iterator begin() const
const_iterator constBegin() const
QMap< Key, T >::const_iterator constFind(const Key &key, const T &value) const
friend class const_iterator
QMap< Key, T > & operator=(const QMap< Key, T > &other)
std::bidirectional_iterator_tag iterator_category
void swap(QMultiMap< Key, T > &other)
const_iterator end() const
Node * node_create(Node *update[], int offset)
QFuture< void > map(Sequence &sequence, MapFunctor map)
const_iterator operator++(int)
iterator insert(const Key &key, const T &value)
iterator lowerBound(const Key &key)
T & operator[](const Key &key)
QList< Key > keys() const
iterator & operator+=(int j)
const T value(const Key &key) const
bool isSharedWith(const QMap< Key, T > &other) const
QList< T > values() const
QMultiMap(const QMap< Key, T > &other)
static QMapData * createData()
const_iterator & operator-=(int j)
const_iterator & operator++()
const T * operator->() const
QMapData * forward[QMapData::LastLevel+1]
#define Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(C)
const_iterator operator-(int j) const
std::map< Key, T > toStdMap() const
iterator upperBound(const Key &key)
#define QT_BEGIN_NAMESPACE
iterator insertMulti(const Key &key, const T &value)
GLsizei GLsizei GLenum GLenum const GLvoid * data
void setSharable(bool sharable)
QMap< Key, T >::iterator replace(const Key &key, const T &value)
void swap(QMap< Key, T > &other)
const Key key(const T &value) const
Q_INLINE_TEMPLATE void qSwap(QScopedPointer< T, Cleanup > &p1, QScopedPointer< T, Cleanup > &p2)
bool contains(const Key &key, const T &value) const
QMap< Key, T >::iterator insert(const Key &key, const T &value)
QMultiMap operator+(const QMultiMap &other) const
iterator(QMapData::Node *node)
const_iterator operator--(int)
const_iterator ConstIterator
#define Q_DECLARE_ASSOCIATIVE_ITERATOR(C)
const_iterator & operator+=(int j)
bool qMapLessThanKey(const Key &key1, const Key &key2)
static QMapData shared_null
bool operator==(const const_iterator &o) const
int remove(const Key &key, const T &value)
QMap< Key, T >::iterator find(const Key &key, const T &value)
GLsizei const GLfloat * value
void node_delete(Node *update[], int offset, Node *node)
QMap< Key, T > & unite(const QMap< Key, T > &other)
void setInsertInOrder(bool ordered)
bool operator!=(const const_iterator &o) const
std::bidirectional_iterator_tag iterator_category
bool contains(const Key &key) const
bool operator==(const QMap< Key, T > &other) const
int remove(const Key &key)
QList< Key > uniqueKeys() const
bool operator!=(const QMap< Key, T > &other) const
bool operator==(const iterator &o) const
QMap(const QMap< Key, T > &other)
bool operator!=(const const_iterator &o) const
QMultiMap & operator+=(const QMultiMap &other)
const_iterator & operator--()
const T & operator*() const
const_iterator constFind(const Key &key) const
bool operator==(const const_iterator &o) const
iterator find(const Key &key)
void continueFreeData(int offset)
QMap< Key, T >::const_iterator find(const Key &key, const T &value) const
bool operator!=(const iterator &o) const
iterator & operator-=(int j)
const_iterator(const iterator &o)
iterator operator-(int j) const