123 |
123 |
124 template <class Key, class T> |
124 template <class Key, class T> |
125 struct QMapNode { |
125 struct QMapNode { |
126 Key key; |
126 Key key; |
127 T value; |
127 T value; |
|
128 |
|
129 private: |
|
130 // never access these members through this structure. |
|
131 // see below |
128 QMapData::Node *backward; |
132 QMapData::Node *backward; |
129 QMapData::Node *forward[1]; |
133 QMapData::Node *forward[1]; |
130 }; |
134 }; |
131 |
135 |
132 template <class Key, class T> |
136 template <class Key, class T> |
133 struct QMapPayloadNode |
137 struct QMapPayloadNode |
134 { |
138 { |
135 Key key; |
139 Key key; |
136 T value; |
140 T value; |
|
141 |
|
142 private: |
|
143 // QMap::e is a pointer to QMapData::Node, which matches the member |
|
144 // below. However, the memory allocation node in QMapData::node_create |
|
145 // allocates sizeof(QMapPayloNode) and incorrectly calculates the offset |
|
146 // of 'backward' below. If the alignment of QMapPayloadNode is larger |
|
147 // than the alignment of a pointer, the 'backward' member is aligned to |
|
148 // the end of this structure, not to 'value' above, and will occupy the |
|
149 // tail-padding area. |
|
150 // |
|
151 // e.g., on a 32-bit archictecture with Key = int and |
|
152 // sizeof(T) = alignof(T) = 8 |
|
153 // 0 4 8 12 16 20 24 byte |
|
154 // | key | PAD | value |backward| PAD | correct layout |
|
155 // | key | PAD | value | |backward| how it's actually used |
|
156 // |<----- value of QMap::payload() = 20 ----->| |
137 QMapData::Node *backward; |
157 QMapData::Node *backward; |
138 }; |
158 }; |
139 |
159 |
140 template <class Key, class T> |
160 template <class Key, class T> |
141 class QMap |
161 class QMap |
180 inline bool isEmpty() const { return d->size == 0; } |
200 inline bool isEmpty() const { return d->size == 0; } |
181 |
201 |
182 inline void detach() { if (d->ref != 1) detach_helper(); } |
202 inline void detach() { if (d->ref != 1) detach_helper(); } |
183 inline bool isDetached() const { return d->ref == 1; } |
203 inline bool isDetached() const { return d->ref == 1; } |
184 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
204 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
|
205 inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; } |
185 inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; } |
206 inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; } |
186 |
207 |
187 void clear(); |
208 void clear(); |
188 |
209 |
189 int remove(const Key &key); |
210 int remove(const Key &key); |
770 |
791 |
771 template <class Key, class T> |
792 template <class Key, class T> |
772 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const |
793 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const |
773 { |
794 { |
774 QList<Key> res; |
795 QList<Key> res; |
|
796 res.reserve(size()); // May be too much, but assume short lifetime |
775 const_iterator i = begin(); |
797 const_iterator i = begin(); |
776 if (i != end()) { |
798 if (i != end()) { |
777 for (;;) { |
799 for (;;) { |
778 const Key &aKey = i.key(); |
800 const Key &aKey = i.key(); |
779 res.append(aKey); |
801 res.append(aKey); |
951 { return QMap<Key, T>::insert(key, value); } |
975 { return QMap<Key, T>::insert(key, value); } |
952 inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value) |
976 inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value) |
953 { return QMap<Key, T>::insertMulti(key, value); } |
977 { return QMap<Key, T>::insertMulti(key, value); } |
954 |
978 |
955 inline QMultiMap &operator+=(const QMultiMap &other) |
979 inline QMultiMap &operator+=(const QMultiMap &other) |
956 { this->unite(other); return *this; } |
980 { unite(other); return *this; } |
957 inline QMultiMap operator+(const QMultiMap &other) const |
981 inline QMultiMap operator+(const QMultiMap &other) const |
958 { QMultiMap result = *this; result += other; return result; } |
982 { QMultiMap result = *this; result += other; return result; } |
959 |
983 |
960 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT) |
984 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT) |
961 // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class |
985 // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class |
1026 int n = 0; |
1050 int n = 0; |
1027 typename QMap<Key, T>::iterator i(find(key)); |
1051 typename QMap<Key, T>::iterator i(find(key)); |
1028 typename QMap<Key, T>::iterator end(QMap<Key, T>::end()); |
1052 typename QMap<Key, T>::iterator end(QMap<Key, T>::end()); |
1029 while (i != end && !qMapLessThanKey<Key>(key, i.key())) { |
1053 while (i != end && !qMapLessThanKey<Key>(key, i.key())) { |
1030 if (i.value() == value) { |
1054 if (i.value() == value) { |
1031 i = this->erase(i); |
1055 #if defined(Q_CC_RVCT) |
|
1056 // RVCT has problems with scoping, apparently. |
|
1057 i = QMap<Key, T>::erase(i); |
|
1058 #else |
|
1059 i = erase(i); |
|
1060 #endif |
1032 ++n; |
1061 ++n; |
1033 } else { |
1062 } else { |
1034 ++i; |
1063 ++i; |
1035 } |
1064 } |
1036 } |
1065 } |