Debian Codegraph @

Source/Utilities/Container/CQtManagedRestrictedModificationMapData.cpp

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 #include "CQtManagedRestrictedModificationMapData.h"
66
67
68 namespace Konclude {
69
70 namespace Utilities {
71
72 namespace Container {
73
74
75 #ifdef KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_MAP_CONTAINER
76
77
78
79 CQtManagedRestrictedModificationMapData CQtManagedRestrictedModificationMapData::shared_null = {
80 &shared_null,
81 { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
82 /*Q_BASIC_ATOMIC_INITIALIZER(1)*/nullptr, 0, 0, 0, false, true, false, 0
83 };
84
85 CQtManagedRestrictedModificationMapData *CQtManagedRestrictedModificationMapData::createData(CQtManagedRestrictedModificationMapBase* referenceMap, CMemoryAllocationManager* memMan)
86 {
87 return createData(0,referenceMap,memMan);
88 }
89
90 CQtManagedRestrictedModificationMapData *CQtManagedRestrictedModificationMapData::createData(int alignment, CQtManagedRestrictedModificationMapBase* referenceMap, CMemoryAllocationManager* memMan)
91 {
92
93 CQtManagedRestrictedModificationMapData *d = CObjectAllocator<CQtManagedRestrictedModificationMapData>::allocateAndConstruct(memMan);
94
95 //CMemoryAllocator::allocateMemory(memMan,sizeof(CQtManagedRestrictedModificationMapData));
96 //CQtManagedRestrictedModificationMapData *d = CMemoryAllocator::allocateMemory(memMan,sizeof(CQtManagedRestrictedModificationMapData));
97 //CQtManagedRestrictedModificationMapData *d = new CQtManagedRestrictedModificationMapData;
98 Q_CHECK_PTR(d);
99 Node *e = reinterpret_cast<Node *>(d);
100 e->backward = e;
101 e->forward[0] = e;
102 //d->ref = 1;
103 d->refMap = referenceMap;
104 d->topLevel = 0;
105 d->size = 0;
106 d->randomBits = 0;
107 d->insertInOrder = false;
108 d->sharable = true;
109 d->strictAlignment = alignment > 8;
110 d->reserved = 0;
111 return d;
112 }
113
114 void CQtManagedRestrictedModificationMapData::continueFreeData(int offset, CMemoryAllocationManager* memMan)
115 {
116 Node *e = reinterpret_cast<Node *>(this);
117 Node *cur = e->forward[0];
118 Node *prev;
119 while (cur != e) {
120 prev = cur;
121 cur = cur->forward[0];
122 if (strictAlignment)
123 //qFreeAligned(reinterpret_cast<char *>(prev) - offset);
124 CMemoryAllocator::releaseAlignedMemory(reinterpret_cast<char *>(prev) - offset,memMan);
125 else
126 //qFree(reinterpret_cast<char *>(prev) - offset);
127 CMemoryAllocator::releaseMemory(reinterpret_cast<char *>(prev) - offset,memMan);
128 }
129 CObjectAllocator<CQtManagedRestrictedModificationMapData>::release(this,memMan);
130 //delete this;
131 }
132
133 CQtManagedRestrictedModificationMapData::Node *CQtManagedRestrictedModificationMapData::node_create(Node *update[], int offset, CMemoryAllocationManager* memMan)
134 {
135 return node_create(update, offset, 0, memMan);
136 }
137
138 /*!
139 Creates a new node inside the data structure.
140
141 \a update is an array with pointers to the node after which the new node
142 should be inserted. Because of the strange skip list data structure there
143 could be several pointers to this node on different levels.
144 \a offset is an amount of bytes that needs to reserved just before the
145 CQtManagedRestrictedModificationMapData::Node structure.
146
147 \a alignment dictates the alignment for the data.
148
149 \internal
150 \since 4.6
151 */
152 CQtManagedRestrictedModificationMapData::Node *CQtManagedRestrictedModificationMapData::node_create(Node *update[], int offset, int alignment, CMemoryAllocationManager* memMan)
153 {
154 int level = 0;
155 uint mask = (1 << Sparseness) - 1;
156
157 while ((randomBits & mask) == mask && level < LastLevel) {
158 ++level;
159 mask <<= Sparseness;
160 }
161
162 if (level > topLevel) {
163 Node *e = reinterpret_cast<Node *>(this);
164 level = ++topLevel;
165 e->forward[level] = e;
166 update[level] = e;
167 }
168
169 ++randomBits;
170 if (level == 3 && !insertInOrder)
171 randomBits = qrand();
172
173 //void *concreteNode = strictAlignment ?
174 // qMallocAligned(offset + sizeof(Node) + level * sizeof(Node *), alignment) :
175 // qMalloc(offset + sizeof(Node) + level * sizeof(Node *));
176 void *concreteNode = strictAlignment ?
177 CMemoryAllocator::allocateAlignedMemory(memMan,offset + sizeof(Node) + level * sizeof(Node *), alignment) :
178 CMemoryAllocator::allocateMemory(memMan,offset + sizeof(Node) + level * sizeof(Node *));
179 Q_CHECK_PTR(concreteNode);
180
181 Node *abstractNode = reinterpret_cast<Node *>(reinterpret_cast<char *>(concreteNode) + offset);
182
183 abstractNode->backward = update[0];
184 update[0]->forward[0]->backward = abstractNode;
185
186 for (int i = level; i >= 0; i--) {
187 abstractNode->forward[i] = update[i]->forward[i];
188 update[i]->forward[i] = abstractNode;
189 update[i] = abstractNode;
190 }
191 ++size;
192 return abstractNode;
193 }
194
195 void CQtManagedRestrictedModificationMapData::node_delete(Node *update[], int offset, Node *node, CMemoryAllocationManager* memMan)
196 {
197 node->forward[0]->backward = node->backward;
198
199 for (int i = 0; i <= topLevel; ++i) {
200 if (update[i]->forward[i] != node)
201 break;
202 update[i]->forward[i] = node->forward[i];
203 }
204 --size;
205 if (strictAlignment)
206 //qFreeAligned(reinterpret_cast<char *>(node) - offset);
207 CMemoryAllocator::releaseAlignedMemory(reinterpret_cast<char *>(node) - offset,memMan);
208 else
209 //qFree(reinterpret_cast<char *>(node) - offset);
210 CMemoryAllocator::releaseMemory(reinterpret_cast<char *>(node) - offset,memMan);
211 }
212
213 #ifdef KONCLUDE_CQTMANAGEDRESTRICTEDMODIFICATIONMAP_DEBUG
214
215 uint CQtManagedRestrictedModificationMapData::adjust_ptr(Node *node)
216 {
217 if (node == reinterpret_cast<Node *>(this)) {
218 return (uint)0xDEADBEEF;
219 } else {
220 return (uint)node;
221 }
222 }
223
224 void CQtManagedRestrictedModificationMapData::dump()
225 {
226 qDebug("Map data (ref = %d, size = %d, randomBits = %#.8x)", int(ref), size, randomBits);
227
228 QString preOutput;
229 QVector<QString> output(topLevel + 1);
230 Node *e = reinterpret_cast<Node *>(this);
231
232 QString str;
233 str.sprintf(" %.8x", adjust_ptr(reinterpret_cast<Node *>(this)));
234 preOutput += str;
235
236 Node *update[LastLevel + 1];
237 for (int i = 0; i <= topLevel; ++i) {
238 str.sprintf("%d: [%.8x] -", i, adjust_ptr(reinterpret_cast<Node *>(forward[i])));
239 output[i] += str;
240 update[i] = reinterpret_cast<Node *>(forward[i]);
241 }
242
243 Node *node = reinterpret_cast<Node *>(forward[0]);
244 while (node != e) {
245 int level = 0;
246 while (level < topLevel && update[level + 1] == node)
247 ++level;
248
249 str.sprintf(" %.8x", adjust_ptr(node));
250 preOutput += str;
251
252 for (int i = 0; i <= level; ++i) {
253 str.sprintf("-> [%.8x] -", adjust_ptr(node->forward[i]));
254 output[i] += str;
255 update[i] = node->forward[i];
256 }
257 for (int j = level + 1; j <= topLevel; ++j)
258 output[j] += QLatin1String("---------------");
259 node = node->forward[0];
260 }
261
262 qDebug("%s", preOutput.ascii());
263 for (int i = 0; i <= topLevel; ++i)
264 qDebug("%s", output[i].ascii());
265 }
266 #endif
267
268
269 #endif // KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_MAP_CONTAINER
270
271
272 }; // end namespace Container
273
274 }; // end namespace Utilities
275
276 }; // end namespace Konclude
277