Debian Codegraph @

Source/Utilities/Container/CQtManagedRestrictedModificationMap.h

raw
1 /*
2 * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team.
3 *
4 * This file is part of the reasoning system Konclude.
5 * For details and support, see <http://konclude.com/>.
6 *
7 * Konclude is free software: you can redistribute it and/or modify
8 * it under the terms of version 3 of the GNU Lesser General Public
9 * License (LGPLv3) as published by the Free Software Foundation.
10 *
11 * Konclude is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU (Lesser) General Public License for more details.
15 *
16 * You should have received a copy of the GNU (Lesser) General Public
17 * License along with Konclude. If not, see <http://www.gnu.org/licenses/>.
18 *
19 * This file incorporates work covered by the following copyright and
20 * permission notice (to be compatible with LGPLv2.1,
21 * this code is available/released under GPLv3,
22 * see https://www.gnu.org/licenses/gpl-faq.html#AllCompatibility):
23 *
24 *
25 * Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
26 * Contact: http://www.qt-project.org/legal
27 *
28 * This file is part of the QtCore module of the Qt Toolkit.
29 *
30 * $QT_BEGIN_LICENSE:LGPL$
31 * Commercial License Usage
32 * Licensees holding valid commercial Qt licenses may use this file in
33 * accordance with the commercial license agreement provided with the
34 * Software or, alternatively, in accordance with the terms contained in
35 * a written agreement between you and Digia. For licensing terms and
36 * conditions see http://qt.digia.com/licensing. For further information
37 * use the contact form at http://qt.digia.com/contact-us.
38 *
39 * GNU Lesser General Public License Usage
40 * Alternatively, this file may be used under the terms of the GNU Lesser
41 * General Public License version 2.1 as published by the Free Software
42 * Foundation and appearing in the file LICENSE.LGPL included in the
43 * packaging of this file. Please review the following information to
44 * ensure the GNU Lesser General Public License version 2.1 requirements
45 * will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
46 *
47 * In addition, as a special exception, Digia gives you certain additional
48 * rights. These rights are described in the Digia Qt LGPL Exception
49 * version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
50 *
51 * GNU General Public License Usage
52 * Alternatively, this file may be used under the terms of the GNU
53 * General Public License version 3.0 as published by the Free Software
54 * Foundation and appearing in the file LICENSE.GPL included in the
55 * packaging of this file. Please review the following information to
56 * ensure the GNU General Public License version 3.0 requirements will be
57 * met: http://www.gnu.org/copyleft/gpl.html.
58 *
59 *
60 * $QT_END_LICENSE$
61 *
62 *
63 */
64
65 #ifndef KONCLUDE_UTILITIES_CONTAINER_CQTMANAGEDRESTRICTEDMODIFICATIONMAP_H
66 #define KONCLUDE_UTILITIES_CONTAINER_CQTMANAGEDRESTRICTEDMODIFICATIONMAP_H
67
68 // Namespace includes
69 #include "ContainerSettings.h"
70 #include "CQtManagedRestrictedModificationMapBase.h"
71 #include "CQtManagedRestrictedModificationMapData.h"
72 #include "CQtManagedRestrictedModificationList.h"
73
74 #ifdef KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_MAP_CONTAINER
75
76 // Library includes
77 #include <QHash>
78 #include <map>
79
80 // Other includes
81 #include "Context/CContext.h"
82
83 // Logger includes
84 #include "Logger/CLogger.h"
85
86
87 namespace Konclude {
88
89 using namespace Context;
90
91 namespace Utilities {
92
93 namespace Container {
94
95
96 /*!
97 *
98 * \class CQtManagedRestrictedModificationMap
99 * \author Andreas Steigmiller
100 * \version 0.1
101 * \brief TODO
102 *
103 */
104
105
106 /*
107 CQtManagedRestrictedModificationMap uses cMapLessThanKey() to compare keys. The default
108 implementation uses operator<(). For pointer types,
109 cMapLessThanKey() casts the pointers to integers before it
110 compares them, because operator<() is undefined on pointers
111 that come from different memory blocks. (In practice, this
112 is only a problem when running a program such as
113 BoundsChecker.)
114 */
115
116 template <class Key> inline bool cMapLessThanKey(const Key &key1, const Key &key2)
117 {
118 return key1 < key2;
119 }
120
121 #ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
122 template <class Ptr> inline bool cMapLessThanKey(Ptr *key1, Ptr *key2)
123 {
124 Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *));
125 return quintptr(key1) < quintptr(key2);
126 }
127
128 template <class Ptr> inline bool cMapLessThanKey(const Ptr *key1, const Ptr *key2)
129 {
130 Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
131 return quintptr(key1) < quintptr(key2);
132 }
133 #endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
134
135 template <class Key, class T>
136 struct CQtManagedRestrictedModificationMapNode {
137 Key key;
138 T value;
139
140 private:
141 // never access these members through this structure.
142 // see below
143 CQtManagedRestrictedModificationMapData::Node *backward;
144 CQtManagedRestrictedModificationMapData::Node *forward[1];
145 };
146
147 template <class Key, class T>
148 struct CQtManagedRestrictedModificationMapPayloadNode
149 {
150 Key key;
151 T value;
152
153 private:
154 // CQtManagedRestrictedModificationMap::e is a pointer to CQtManagedRestrictedModificationMapData::Node, which matches the member
155 // below. However, the memory allocation node in CQtManagedRestrictedModificationMapData::node_create
156 // allocates sizeof(CQtManagedRestrictedModificationMapPayloNode) and incorrectly calculates the offset
157 // of 'backward' below. If the alignment of CQtManagedRestrictedModificationMapPayloadNode is larger
158 // than the alignment of a pointer, the 'backward' member is aligned to
159 // the end of this structure, not to 'value' above, and will occupy the
160 // tail-padding area.
161 //
162 // e.g., on a 32-bit archictecture with Key = int and
163 // sizeof(T) = alignof(T) = 8
164 // 0 4 8 12 16 20 24 byte
165 // | key | PAD | value |backward| PAD | correct layout
166 // | key | PAD | value | |backward| how it's actually used
167 // |<----- value of CQtManagedRestrictedModificationMap::payload() = 20 ----->|
168 CQtManagedRestrictedModificationMapData::Node *backward;
169 };
170
171 template <class Key, class T>
172 class CQtManagedRestrictedModificationMap : public CQtManagedRestrictedModificationMapBase
173 {
174 typedef CQtManagedRestrictedModificationMapNode<Key, T> Node;
175 typedef CQtManagedRestrictedModificationMapPayloadNode<Key, T> PayloadNode;
176
177 union {
178 CQtManagedRestrictedModificationMapData *d;
179 CQtManagedRestrictedModificationMapData::Node *e;
180 };
181 CContext* mContext;
182 CMemoryAllocationManager* mMemMan;
183
184
185 static inline int payload() { return sizeof(PayloadNode) - sizeof(CQtManagedRestrictedModificationMapData::Node *); }
186 static inline int alignment() {
187 #ifdef Q_ALIGNOF
188 return int(qMax(sizeof(void*), Q_ALIGNOF(Node)));
189 #else
190 return 0;
191 #endif
192 }
193 static inline Node *concrete(CQtManagedRestrictedModificationMapData::Node *node) {
194 return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());
195 }
196
197 public:
198 inline CQtManagedRestrictedModificationMap() : d(&CQtManagedRestrictedModificationMapData::shared_null),mContext(nullptr) {
199 mMemMan = CContext::getMemoryAllocationManager(mContext);
200 /*d->ref.ref();*/
201 }
202 inline CQtManagedRestrictedModificationMap(CContext* context) : d(&CQtManagedRestrictedModificationMapData::shared_null),mContext(context) {
203 mMemMan = CContext::getMemoryAllocationManager(mContext);
204 /*d->ref.ref();*/
205 }
206 inline CQtManagedRestrictedModificationMap(const CQtManagedRestrictedModificationMap<Key, T> &other) : d(other.d),mContext(nullptr) {
207 mMemMan = CContext::getMemoryAllocationManager(mContext);
208 /*d->ref.ref();*/ if (!d->sharable) detach();
209 }
210 inline CQtManagedRestrictedModificationMap(const CQtManagedRestrictedModificationMap<Key, T> &other, CContext* context) : d(other.d),mContext(context) {
211 mMemMan = CContext::getMemoryAllocationManager(mContext);
212 /*d->ref.ref();*/ if (!d->sharable) detach();
213 }
214 inline ~CQtManagedRestrictedModificationMap() { if (!d) return; if (/*!d->ref.deref()*/ d->refMap == this) freeData(d); }
215
216 CQtManagedRestrictedModificationMap<Key, T> &operator=(const CQtManagedRestrictedModificationMap<Key, T> &other);
217
218 CQtManagedRestrictedModificationMap<Key, T>* init(CContext* context = nullptr);
219 CQtManagedRestrictedModificationMap<Key, T>* init(const CQtManagedRestrictedModificationMap<Key, T> &other, CContext* context = nullptr);
220 CQtManagedRestrictedModificationMap<Key, T>* init(const CQtManagedRestrictedModificationMap<Key, T>* other, CContext* context = nullptr);
221
222
223 bool isKeySubSetOf(const CQtManagedRestrictedModificationMap<Key, T>* other, cint64 testDirectSubSetFactorCount = 20);
224
225 #ifndef QT_NO_STL
226 explicit CQtManagedRestrictedModificationMap(const typename std::map<Key, T> &other);
227 std::map<Key, T> toStdMap() const;
228 #endif
229
230 bool operator==(const CQtManagedRestrictedModificationMap<Key, T> &other) const;
231 inline bool operator!=(const CQtManagedRestrictedModificationMap<Key, T> &other) const { return !(*this == other); }
232
233 inline int size() const { return d->size; }
234
235 inline bool isEmpty() const { return d->size == 0; }
236
237 inline void detach() { if (/*d->ref != 1*/ d->refMap != this) detach_helper(); }
238 inline bool isDetached() const { return /*d->ref == 1*/ d->refMap == this; }
239 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
240 inline bool isSharedWith(const CQtManagedRestrictedModificationMap<Key, T> &other) const { return d == other.d; }
241 inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }
242
243 void clear();
244
245 int remove(const Key &key);
246 T take(const Key &key);
247
248 bool contains(const Key &key) const;
249 const Key key(const T &value) const;
250 const Key key(const T &value, const Key &defaultKey) const;
251 const T value(const Key &key) const;
252 const T value(const Key &key, const T &defaultValue) const;
253 T &operator[](const Key &key);
254 const T operator[](const Key &key) const;
255
256 bool tryGetValue(const Key &key, T* value = nullptr) const;
257 bool tryGetValuePointer(const Key &key, T*& valuePointer) const;
258
259 QList<Key> uniqueKeys() const;
260 QList<Key> keys() const;
261 QList<Key> keys(const T &value) const;
262 QList<T> values() const;
263 QList<T> values(const Key &key) const;
264 int count(const Key &key) const;
265
266 class const_iterator;
267
268 class iterator
269 {
270 friend class const_iterator;
271 CQtManagedRestrictedModificationMapData::Node *i;
272
273 public:
274 typedef std::bidirectional_iterator_tag iterator_category;
275 typedef qptrdiff difference_type;
276 typedef T value_type;
277 typedef T *pointer;
278 typedef T &reference;
279
280 // ### Qt 5: get rid of 'operator Node *'
281 inline operator CQtManagedRestrictedModificationMapData::Node *() const { return i; }
282 inline iterator() : i(0) { }
283 inline iterator(CQtManagedRestrictedModificationMapData::Node *node) : i(node) { }
284
285 inline const Key &key() const { return concrete(i)->key; }
286 inline T &value() const { return concrete(i)->value; }
287
288 inline T &operator*() const { return concrete(i)->value; }
289 inline T *operator->() const { return &concrete(i)->value; }
290 inline bool operator==(const iterator &o) const { return i == o.i; }
291 inline bool operator!=(const iterator &o) const { return i != o.i; }
292
293 inline iterator &operator++() {
294 i = i->forward[0];
295 return *this;
296 }
297 inline iterator operator++(int) {
298 iterator r = *this;
299 i = i->forward[0];
300 return r;
301 }
302 inline iterator &operator--() {
303 i = i->backward;
304 return *this;
305 }
306 inline iterator operator--(int) {
307 iterator r = *this;
308 i = i->backward;
309 return r;
310 }
311 inline iterator operator+(int j) const
312 { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
313 inline iterator operator-(int j) const { return operator+(-j); }
314 inline iterator &operator+=(int j) { return *this = *this + j; }
315 inline iterator &operator-=(int j) { return *this = *this - j; }
316
317 // ### Qt 5: not sure this is necessary anymore
318 #ifdef QT_STRICT_ITERATORS
319 private:
320 #else
321 public:
322 #endif
323 inline bool operator==(const const_iterator &o) const
324 { return i == o.i; }
325 inline bool operator!=(const const_iterator &o) const
326 { return i != o.i; }
327
328 private:
329 // ### Qt 5: remove
330 inline operator bool() const { return false; }
331 };
332 friend class iterator;
333
334 class const_iterator
335 {
336 friend class iterator;
337 CQtManagedRestrictedModificationMapData::Node *i;
338
339 public:
340 typedef std::bidirectional_iterator_tag iterator_category;
341 typedef qptrdiff difference_type;
342 typedef T value_type;
343 typedef const T *pointer;
344 typedef const T &reference;
345
346 // ### Qt 5: get rid of 'operator Node *'
347 inline operator CQtManagedRestrictedModificationMapData::Node *() const { return i; }
348 inline const_iterator() : i(0) { }
349 inline const_iterator(CQtManagedRestrictedModificationMapData::Node *node) : i(node) { }
350 #ifdef QT_STRICT_ITERATORS
351 explicit inline const_iterator(const iterator &o)
352 #else
353 inline const_iterator(const iterator &o)
354 #endif
355 { i = o.i; }
356
357 inline const Key &key() const { return concrete(i)->key; }
358 inline const T &value() const { return concrete(i)->value; }
359 inline const T &operator*() const { return concrete(i)->value; }
360 inline const T *operator->() const { return &concrete(i)->value; }
361 inline bool operator==(const const_iterator &o) const { return i == o.i; }
362 inline bool operator!=(const const_iterator &o) const { return i != o.i; }
363
364 inline const_iterator &operator++() {
365 i = i->forward[0];
366 return *this;
367 }
368 inline const_iterator operator++(int) {
369 const_iterator r = *this;
370 i = i->forward[0];
371 return r;
372 }
373 inline const_iterator &operator--() {
374 i = i->backward;
375 return *this;
376 }
377 inline const_iterator operator--(int) {
378 const_iterator r = *this;
379 i = i->backward;
380 return r;
381 }
382 inline const_iterator operator+(int j) const
383 { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
384 inline const_iterator operator-(int j) const { return operator+(-j); }
385 inline const_iterator &operator+=(int j) { return *this = *this + j; }
386 inline const_iterator &operator-=(int j) { return *this = *this - j; }
387
388 // ### Qt 5: not sure this is necessary anymore
389 #ifdef QT_STRICT_ITERATORS
390 private:
391 inline bool operator==(const iterator &o) { return operator==(const_iterator(o)); }
392 inline bool operator!=(const iterator &o) { return operator!=(const_iterator(o)); }
393 #endif
394
395 private:
396 // ### Qt 5: remove
397 inline operator bool() const { return false; }
398 };
399 friend class const_iterator;
400
401 // STL style
402 inline iterator begin() { detach(); return iterator(e->forward[0]); }
403 inline iterator beginNoDetach() { return iterator(e->forward[0]); }
404 inline const_iterator begin() const { return const_iterator(e->forward[0]); }
405 inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }
406 inline iterator end() {
407 detach();
408 return iterator(e);
409 }
410 inline iterator endNoDetach() { return iterator(e); }
411 inline const_iterator end() const { return const_iterator(e); }
412 inline const_iterator constEnd() const { return const_iterator(e); }
413
414 iterator erase(iterator it);
415
416 // more Qt
417 typedef iterator Iterator;
418 typedef const_iterator ConstIterator;
419 inline int count() const { return d->size; }
420 iterator find(const Key &key);
421 const_iterator find(const Key &key) const;
422 const_iterator constFind(const Key &key) const;
423 iterator lowerBound(const Key &key);
424 const_iterator lowerBound(const Key &key) const;
425 iterator upperBound(const Key &key);
426 const_iterator upperBound(const Key &key) const;
427 iterator insert(const Key &key, const T &value);
428 iterator tryInsert(const Key &key, const T &value, bool* containsAlready = nullptr);
429 iterator tryInsert(const Key &key, const T &value, bool* containsAlready, T** containedValue);
430 iterator insertMulti(const Key &key, const T &value);
431 CQtManagedRestrictedModificationMap<Key, T> &unite(const CQtManagedRestrictedModificationMap<Key, T> &other);
432
433 // STL compatibility
434 typedef Key key_type;
435 typedef T mapped_type;
436 typedef qptrdiff difference_type;
437 typedef int size_type;
438 inline bool empty() const { return isEmpty(); }
439
440 #ifdef KONCLUDE_CQTMANAGEDRESTRICTEDMODIFICATIONMAP_DEBUG
441 inline void dump() const { d->dump(); }
442 #endif
443
444 private:
445 void detach_helper();
446 void freeData(CQtManagedRestrictedModificationMapData *d);
447 CQtManagedRestrictedModificationMapData::Node *findNode(const Key &key) const;
448 CQtManagedRestrictedModificationMapData::Node *mutableFindNode(CQtManagedRestrictedModificationMapData::Node *update[], const Key &key) const;
449 CQtManagedRestrictedModificationMapData::Node *node_create(CQtManagedRestrictedModificationMapData *d, CQtManagedRestrictedModificationMapData::Node *update[], const Key &key,
450 const T &value);
451 };
452
453
454
455 }; // end namespace Container
456
457 }; // end namespace Utilities
458
459 }; // end namespace Konclude
460
461 #include "CQtManagedRestrictedModificationMap.cpp"
462
463
464 #endif // KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_MAP_CONTAINER
465
466 #endif // KONCLUDE_UTILITIES_CONTAINER_CQTMANAGEDRESTRICTEDMODIFICATIONMAP_H