Debian Codegraph @

Source/Utilities/Container/CQtManagedRestrictedModificationHashData.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 "CQtManagedRestrictedModificationHashData.h"
66
67
68 namespace Konclude {
69
70 namespace Utilities {
71
72 namespace Container {
73
74
75 #ifdef KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_HASH_CONTAINER
76
77 static const uchar prime_deltas[] = {
78 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3,
79 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0
80 };
81
82 static inline int primeForNumBits(int numBits)
83 {
84 return (1 << numBits) + prime_deltas[numBits];
85 }
86
87 /*
88 Returns the smallest integer n such that
89 primeForNumBits(n) >= hint.
90 */
91 static int countBits(int hint)
92 {
93 int numBits = 0;
94 int bits = hint;
95
96 while (bits > 1) {
97 bits >>= 1;
98 numBits++;
99 }
100
101 if (numBits >= (int)sizeof(prime_deltas)) {
102 numBits = sizeof(prime_deltas) - 1;
103 } else if (primeForNumBits(numBits) < hint) {
104 ++numBits;
105 }
106 return numBits;
107 }
108
109 const int MinNumBits = 4;
110
111 CQtManagedRestrictedModificationHashData CQtManagedRestrictedModificationHashData::shared_null = {
112 0, 0, /*Q_BASIC_ATOMIC_INITIALIZER(1)*/0, 0, 0, MinNumBits, 0, 0, true, false, 0
113 };
114
115 void *CQtManagedRestrictedModificationHashData::allocateNode(CMemoryAllocationManager* memMan)
116 {
117 return allocateNode(0,memMan);
118 }
119
120 void *CQtManagedRestrictedModificationHashData::allocateNode(int nodeAlign, CMemoryAllocationManager* memMan)
121 {
122 //void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : qMalloc(nodeSize);
123 //void *ptr = strictAlignment ? memMan->allocateAligned(nodeSize,nodeAlign) : memMan->allocate(nodeSize);
124 void *ptr = strictAlignment ? CMemoryAllocator::allocateAlignedMemory(memMan,nodeSize,nodeAlign) : CMemoryAllocator::allocateMemory(memMan,nodeSize);
125 Q_CHECK_PTR(ptr);
126 return ptr;
127 }
128
129 void CQtManagedRestrictedModificationHashData::freeNode(void *node, CMemoryAllocationManager* memMan)
130 {
131 if (strictAlignment)
132 //qFreeAligned(node);
133 CMemoryAllocator::releaseAlignedMemory(node,memMan);
134 else
135 //qFree(node);
136 CMemoryAllocator::releaseMemory(node,memMan);
137 }
138
139 CQtManagedRestrictedModificationHashData *CQtManagedRestrictedModificationHashData::detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize)
140 {
141 return detach_helper2( node_duplicate, 0, nodeSize, 0, 0, 0);
142 }
143
144 CQtManagedRestrictedModificationHashData *CQtManagedRestrictedModificationHashData::detach_helper2(void (*node_duplicate)(Node *, void *),
145 void (*node_delete)(Node *),
146 int nodeSize,
147 int nodeAlign, CQtManagedRestrictedModificationHashBase* referencedHash, CMemoryAllocationManager* memMan)
148 {
149 union {
150 CQtManagedRestrictedModificationHashData *d;
151 Node *e;
152 };
153 //d = new CQtManagedRestrictedModificationHashData;
154 d = CObjectAllocator<CQtManagedRestrictedModificationHashData>::allocate(memMan);
155 d->fakeNext = 0;
156 d->buckets = 0;
157 //d->ref = 1;
158 d->refHash = referencedHash;
159 d->size = size;
160 d->nodeSize = nodeSize;
161 d->userNumBits = userNumBits;
162 d->numBits = numBits;
163 d->numBuckets = numBuckets;
164 d->sharable = true;
165 d->strictAlignment = nodeAlign > 8;
166 d->reserved = 0;
167
168 if (numBuckets) {
169 QT_TRY {
170 //d->buckets = new Node *[numBuckets];
171 d->buckets = CObjectAllocator<Node*>::allocateArray(memMan,numBuckets);
172 } QT_CATCH(...) {
173 // restore a consistent state for d
174 d->numBuckets = 0;
175 // roll back
176 d->free_helper(node_delete,memMan);
177 QT_RETHROW;
178 }
179
180 Node *this_e = reinterpret_cast<Node *>(this);
181 for (int i = 0; i < numBuckets; ++i) {
182 Node **nextNode = &d->buckets[i];
183 Node *oldNode = buckets[i];
184 while (oldNode != this_e) {
185 QT_TRY {
186 Node *dup = static_cast<Node *>(allocateNode(nodeAlign,memMan));
187
188 QT_TRY {
189 node_duplicate(oldNode, dup);
190 } QT_CATCH(...) {
191 freeNode(dup,memMan);
192 QT_RETHROW;
193 }
194
195 dup->h = oldNode->h;
196 *nextNode = dup;
197 nextNode = &dup->next;
198 oldNode = oldNode->next;
199 } QT_CATCH(...) {
200 // restore a consistent state for d
201 *nextNode = e;
202 d->numBuckets = i+1;
203 // roll back
204 d->free_helper(node_delete,memMan);
205 QT_RETHROW;
206 }
207 }
208 *nextNode = e;
209 }
210 }
211 return d;
212 }
213
214 CQtManagedRestrictedModificationHashData *CQtManagedRestrictedModificationHashData::restricted_detach_helper2(bool (*copy_restricted)(Node *, void *),
215 void *assistValue, void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),
216 int nodeSize,
217 int nodeAlign, CQtManagedRestrictedModificationHashBase* referencedHash, CMemoryAllocationManager* memMan)
218 {
219 union {
220 CQtManagedRestrictedModificationHashData *d;
221 Node *e;
222 };
223 //d = new CQtManagedRestrictedModificationHashData;
224 d = CObjectAllocator<CQtManagedRestrictedModificationHashData>::allocate(memMan);
225 d->fakeNext = 0;
226 d->buckets = 0;
227 //d->ref = 1;
228 d->refHash = referencedHash;
229 d->size = size;
230 d->nodeSize = nodeSize;
231 d->userNumBits = userNumBits;
232 d->numBits = numBits;
233 d->numBuckets = numBuckets;
234 d->sharable = true;
235 d->strictAlignment = nodeAlign > 8;
236 d->reserved = 0;
237
238 if (numBuckets) {
239 QT_TRY {
240 //d->buckets = new Node *[numBuckets];
241 d->buckets = CObjectAllocator<Node*>::allocateArray(memMan,numBuckets);
242 } QT_CATCH(...) {
243 // restore a consistent state for d
244 d->numBuckets = 0;
245 // roll back
246 d->free_helper(node_delete,memMan);
247 QT_RETHROW;
248 }
249
250 Node *this_e = reinterpret_cast<Node *>(this);
251 for (int i = 0; i < numBuckets; ++i) {
252 Node **nextNode = &d->buckets[i];
253 Node *oldNode = buckets[i];
254 while (oldNode != this_e) {
255 if (copy_restricted(oldNode,assistValue)) {
256 QT_TRY {
257 Node *dup = static_cast<Node *>(allocateNode(nodeAlign,memMan));
258
259 QT_TRY {
260 node_duplicate(oldNode, dup);
261 } QT_CATCH(...) {
262 freeNode(dup,memMan);
263 QT_RETHROW;
264 }
265
266 dup->h = oldNode->h;
267 *nextNode = dup;
268 nextNode = &dup->next;
269 oldNode = oldNode->next;
270 } QT_CATCH(...) {
271 // restore a consistent state for d
272 *nextNode = e;
273 d->numBuckets = i+1;
274 // roll back
275 d->free_helper(node_delete,memMan);
276 QT_RETHROW;
277 }
278 } else {
279 d->size = d->size - 1;
280 oldNode = oldNode->next;
281 }
282 }
283 *nextNode = e;
284 }
285 }
286 return d;
287 }
288
289 void CQtManagedRestrictedModificationHashData::free_helper(void (*node_delete)(Node *), CMemoryAllocationManager* memMan)
290 {
291 if (node_delete) {
292 Node *this_e = reinterpret_cast<Node *>(this);
293 Node **bucket = reinterpret_cast<Node **>(this->buckets);
294
295 int n = numBuckets;
296 while (n--) {
297 Node *cur = *bucket++;
298 while (cur != this_e) {
299 Node *next = cur->next;
300 node_delete(cur);
301 freeNode(cur,memMan);
302 cur = next;
303 }
304 }
305 }
306 //delete [] buckets;
307 CObjectAllocator<Node*>::releaseArray(buckets,memMan);
308 //delete this;
309 CObjectAllocator<CQtManagedRestrictedModificationHashData>::release(this,memMan);
310 }
311
312 CQtManagedRestrictedModificationHashData::Node *CQtManagedRestrictedModificationHashData::nextNode(Node *node)
313 {
314 union {
315 Node *next;
316 Node *e;
317 CQtManagedRestrictedModificationHashData *d;
318 };
319 next = node->next;
320 Q_ASSERT_X(next, "QHash", "Iterating beyond end()");
321 if (next->next)
322 return next;
323
324 int start = (node->h % d->numBuckets) + 1;
325 Node **bucket = d->buckets + start;
326 int n = d->numBuckets - start;
327 while (n--) {
328 if (*bucket != e)
329 return *bucket;
330 ++bucket;
331 }
332 return e;
333 }
334
335 CQtManagedRestrictedModificationHashData::Node *CQtManagedRestrictedModificationHashData::previousNode(Node *node)
336 {
337 union {
338 Node *e;
339 CQtManagedRestrictedModificationHashData *d;
340 };
341
342 e = node;
343 while (e->next)
344 e = e->next;
345
346 int start;
347 if (node == e)
348 start = d->numBuckets - 1;
349 else
350 start = node->h % d->numBuckets;
351
352 Node *sentinel = node;
353 Node **bucket = d->buckets + start;
354 while (start >= 0) {
355 if (*bucket != sentinel) {
356 Node *prev = *bucket;
357 while (prev->next != sentinel)
358 prev = prev->next;
359 return prev;
360 }
361
362 sentinel = e;
363 --bucket;
364 --start;
365 }
366 Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()");
367 return e;
368 }
369
370 /*
371 If hint is negative, -hint gives the approximate number of
372 buckets that should be used for the hash table. If hint is
373 nonnegative, (1 << hint) gives the approximate number
374 of buckets that should be used.
375 */
376 void CQtManagedRestrictedModificationHashData::rehash(int hint, CMemoryAllocationManager* memMan)
377 {
378 if (hint < 0) {
379 hint = countBits(-hint);
380 if (hint < MinNumBits)
381 hint = MinNumBits;
382 userNumBits = hint;
383 while (primeForNumBits(hint) < (size >> 1))
384 ++hint;
385 } else if (hint < MinNumBits) {
386 hint = MinNumBits;
387 }
388
389 if (numBits != hint) {
390 Node *e = reinterpret_cast<Node *>(this);
391 Node **oldBuckets = buckets;
392 int oldNumBuckets = numBuckets;
393
394 int nb = primeForNumBits(hint);
395 //buckets = new Node *[nb];
396 buckets = CObjectAllocator<Node*>::allocateArray(memMan,nb);
397 numBits = hint;
398 numBuckets = nb;
399 for (int i = 0; i < numBuckets; ++i)
400 buckets[i] = e;
401
402 for (int i = 0; i < oldNumBuckets; ++i) {
403 Node *firstNode = oldBuckets[i];
404 while (firstNode != e) {
405 uint h = firstNode->h;
406 Node *lastNode = firstNode;
407 while (lastNode->next != e && lastNode->next->h == h)
408 lastNode = lastNode->next;
409
410 Node *afterLastNode = lastNode->next;
411 Node **beforeFirstNode = &buckets[h % numBuckets];
412 while (*beforeFirstNode != e)
413 beforeFirstNode = &(*beforeFirstNode)->next;
414 lastNode->next = *beforeFirstNode;
415 *beforeFirstNode = firstNode;
416 firstNode = afterLastNode;
417 }
418 }
419 //delete [] oldBuckets;
420 CObjectAllocator<Node*>::releaseArray(oldBuckets,memMan);
421 }
422 }
423
424 void CQtManagedRestrictedModificationHashData::destroyAndFree(CMemoryAllocationManager* memMan)
425 {
426 free_helper(0,memMan);
427 }
428
429 #ifdef KONCLUDE_CQTMANAGEDRESTRICTEDMODIFICATIONHASH_DEBUG
430
431 void CQtManagedRestrictedModificationHashData::dump()
432 {
433 qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)",
434 /*int(ref)*/(int)refHash, size, nodeSize, userNumBits, numBits,
435 numBuckets);
436 qDebug(" %p (fakeNode = %p)", this, fakeNext);
437 for (int i = 0; i < numBuckets; ++i) {
438 QString line;
439 Node *n = buckets[i];
440 if (n != reinterpret_cast<Node *>(this)) {
441 line.sprintf("%d:", i);
442 while (n != reinterpret_cast<Node *>(this)) {
443 line += QString().sprintf(" -> [%p]", n);
444 if (!n) {
445 line += " (CORRUPT)";
446 break;
447 }
448 n = n->next;
449 }
450 qDebug(qPrintable(line));
451 }
452 }
453 }
454
455 void CQtManagedRestrictedModificationHashData::checkSanity()
456 {
457 if (fakeNext)
458 qFatal("Fake next isn't 0");
459
460 for (int i = 0; i < numBuckets; ++i) {
461 Node *n = buckets[i];
462 Node *p = n;
463 if (!n)
464 qFatal("%d: Bucket entry is 0", i);
465 if (n != reinterpret_cast<Node *>(this)) {
466 while (n != reinterpret_cast<Node *>(this)) {
467 if (!n->next)
468 qFatal("%d: Next of %p is 0, should be %p", i, n, this);
469 n = n->next;
470 }
471 }
472 }
473 }
474 #endif
475
476 void CQtManagedRestrictedModificationHashData::mightGrow(CMemoryAllocationManager* memMan) // ### Qt 5: eliminate
477 {
478 if (size >= numBuckets)
479 rehash(numBits + 1,memMan);
480 }
481
482 //inline bool CQtManagedRestrictedModificationHashData::willGrow()
483 //{
484 // if (size >= numBuckets) {
485 // rehash(numBits + 1);
486 // return true;
487 // } else {
488 // return false;
489 // }
490 //}
491
492 void CQtManagedRestrictedModificationHashData::hasShrunk(CMemoryAllocationManager* memMan)
493 {
494 if (size <= (numBuckets >> 3) && numBits > userNumBits) {
495 QT_TRY {
496 rehash(qMax(int(numBits) - 2, int(userNumBits)),memMan);
497 } QT_CATCH(const std::bad_alloc &) {
498 // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
499 }
500 }
501 }
502
503 CQtManagedRestrictedModificationHashData::Node *CQtManagedRestrictedModificationHashData::firstNode()
504 {
505 Node *e = reinterpret_cast<Node *>(this);
506 Node **bucket = buckets;
507 int n = numBuckets;
508 while (n--) {
509 if (*bucket != e)
510 return *bucket;
511 ++bucket;
512 }
513 return e;
514 }
515
516
517 #endif // KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_HASH_CONTAINER
518
519
520 }; // end namespace Container
521
522 }; // end namespace Utilities
523
524 }; // end namespace Konclude
525