/* * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team. * * This file is part of the reasoning system Konclude. * For details and support, see . * * Konclude is free software: you can redistribute it and/or modify * it under the terms of version 3 of the GNU Lesser General Public * License (LGPLv3) as published by the Free Software Foundation. * * Konclude is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU (Lesser) General Public License for more details. * * You should have received a copy of the GNU (Lesser) General Public * License along with Konclude. If not, see . * * This file incorporates work covered by the following copyright and * permission notice (to be compatible with LGPLv2.1, * this code is available/released under GPLv3, * see https://www.gnu.org/licenses/gpl-faq.html#AllCompatibility): * * * Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). * Contact: http://www.qt-project.org/legal * * This file is part of the QtCore module of the Qt Toolkit. * * $QT_BEGIN_LICENSE:LGPL$ * Commercial License Usage * Licensees holding valid commercial Qt licenses may use this file in * accordance with the commercial license agreement provided with the * Software or, alternatively, in accordance with the terms contained in * a written agreement between you and Digia. For licensing terms and * conditions see http://qt.digia.com/licensing. For further information * use the contact form at http://qt.digia.com/contact-us. * * GNU Lesser General Public License Usage * Alternatively, this file may be used under the terms of the GNU Lesser * General Public License version 2.1 as published by the Free Software * Foundation and appearing in the file LICENSE.LGPL included in the * packaging of this file. Please review the following information to * ensure the GNU Lesser General Public License version 2.1 requirements * will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. * * In addition, as a special exception, Digia gives you certain additional * rights. These rights are described in the Digia Qt LGPL Exception * version 1.1, included in the file LGPL_EXCEPTION.txt in this package. * * GNU General Public License Usage * Alternatively, this file may be used under the terms of the GNU * General Public License version 3.0 as published by the Free Software * Foundation and appearing in the file LICENSE.GPL included in the * packaging of this file. Please review the following information to * ensure the GNU General Public License version 3.0 requirements will be * met: http://www.gnu.org/copyleft/gpl.html. * * * $QT_END_LICENSE$ * * */ #include "CQtManagedRestrictedModificationHashData.h" namespace Konclude { namespace Utilities { namespace Container { #ifdef KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_HASH_CONTAINER static const uchar prime_deltas[] = { 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 }; static inline int primeForNumBits(int numBits) { return (1 << numBits) + prime_deltas[numBits]; } /* Returns the smallest integer n such that primeForNumBits(n) >= hint. */ static int countBits(int hint) { int numBits = 0; int bits = hint; while (bits > 1) { bits >>= 1; numBits++; } if (numBits >= (int)sizeof(prime_deltas)) { numBits = sizeof(prime_deltas) - 1; } else if (primeForNumBits(numBits) < hint) { ++numBits; } return numBits; } const int MinNumBits = 4; CQtManagedRestrictedModificationHashData CQtManagedRestrictedModificationHashData::shared_null = { 0, 0, /*Q_BASIC_ATOMIC_INITIALIZER(1)*/0, 0, 0, MinNumBits, 0, 0, true, false, 0 }; void *CQtManagedRestrictedModificationHashData::allocateNode(CMemoryAllocationManager* memMan) { return allocateNode(0,memMan); } void *CQtManagedRestrictedModificationHashData::allocateNode(int nodeAlign, CMemoryAllocationManager* memMan) { //void *ptr = strictAlignment ? qMallocAligned(nodeSize, nodeAlign) : qMalloc(nodeSize); //void *ptr = strictAlignment ? memMan->allocateAligned(nodeSize,nodeAlign) : memMan->allocate(nodeSize); void *ptr = strictAlignment ? CMemoryAllocator::allocateAlignedMemory(memMan,nodeSize,nodeAlign) : CMemoryAllocator::allocateMemory(memMan,nodeSize); Q_CHECK_PTR(ptr); return ptr; } void CQtManagedRestrictedModificationHashData::freeNode(void *node, CMemoryAllocationManager* memMan) { if (strictAlignment) //qFreeAligned(node); CMemoryAllocator::releaseAlignedMemory(node,memMan); else //qFree(node); CMemoryAllocator::releaseMemory(node,memMan); } CQtManagedRestrictedModificationHashData *CQtManagedRestrictedModificationHashData::detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize) { return detach_helper2( node_duplicate, 0, nodeSize, 0, 0, 0); } CQtManagedRestrictedModificationHashData *CQtManagedRestrictedModificationHashData::detach_helper2(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *), int nodeSize, int nodeAlign, CQtManagedRestrictedModificationHashBase* referencedHash, CMemoryAllocationManager* memMan) { union { CQtManagedRestrictedModificationHashData *d; Node *e; }; //d = new CQtManagedRestrictedModificationHashData; d = CObjectAllocator::allocate(memMan); d->fakeNext = 0; d->buckets = 0; //d->ref = 1; d->refHash = referencedHash; d->size = size; d->nodeSize = nodeSize; d->userNumBits = userNumBits; d->numBits = numBits; d->numBuckets = numBuckets; d->sharable = true; d->strictAlignment = nodeAlign > 8; d->reserved = 0; if (numBuckets) { QT_TRY { //d->buckets = new Node *[numBuckets]; d->buckets = CObjectAllocator::allocateArray(memMan,numBuckets); } QT_CATCH(...) { // restore a consistent state for d d->numBuckets = 0; // roll back d->free_helper(node_delete,memMan); QT_RETHROW; } Node *this_e = reinterpret_cast(this); for (int i = 0; i < numBuckets; ++i) { Node **nextNode = &d->buckets[i]; Node *oldNode = buckets[i]; while (oldNode != this_e) { QT_TRY { Node *dup = static_cast(allocateNode(nodeAlign,memMan)); QT_TRY { node_duplicate(oldNode, dup); } QT_CATCH(...) { freeNode(dup,memMan); QT_RETHROW; } dup->h = oldNode->h; *nextNode = dup; nextNode = &dup->next; oldNode = oldNode->next; } QT_CATCH(...) { // restore a consistent state for d *nextNode = e; d->numBuckets = i+1; // roll back d->free_helper(node_delete,memMan); QT_RETHROW; } } *nextNode = e; } } return d; } CQtManagedRestrictedModificationHashData *CQtManagedRestrictedModificationHashData::restricted_detach_helper2(bool (*copy_restricted)(Node *, void *), void *assistValue, void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *), int nodeSize, int nodeAlign, CQtManagedRestrictedModificationHashBase* referencedHash, CMemoryAllocationManager* memMan) { union { CQtManagedRestrictedModificationHashData *d; Node *e; }; //d = new CQtManagedRestrictedModificationHashData; d = CObjectAllocator::allocate(memMan); d->fakeNext = 0; d->buckets = 0; //d->ref = 1; d->refHash = referencedHash; d->size = size; d->nodeSize = nodeSize; d->userNumBits = userNumBits; d->numBits = numBits; d->numBuckets = numBuckets; d->sharable = true; d->strictAlignment = nodeAlign > 8; d->reserved = 0; if (numBuckets) { QT_TRY { //d->buckets = new Node *[numBuckets]; d->buckets = CObjectAllocator::allocateArray(memMan,numBuckets); } QT_CATCH(...) { // restore a consistent state for d d->numBuckets = 0; // roll back d->free_helper(node_delete,memMan); QT_RETHROW; } Node *this_e = reinterpret_cast(this); for (int i = 0; i < numBuckets; ++i) { Node **nextNode = &d->buckets[i]; Node *oldNode = buckets[i]; while (oldNode != this_e) { if (copy_restricted(oldNode,assistValue)) { QT_TRY { Node *dup = static_cast(allocateNode(nodeAlign,memMan)); QT_TRY { node_duplicate(oldNode, dup); } QT_CATCH(...) { freeNode(dup,memMan); QT_RETHROW; } dup->h = oldNode->h; *nextNode = dup; nextNode = &dup->next; oldNode = oldNode->next; } QT_CATCH(...) { // restore a consistent state for d *nextNode = e; d->numBuckets = i+1; // roll back d->free_helper(node_delete,memMan); QT_RETHROW; } } else { d->size = d->size - 1; oldNode = oldNode->next; } } *nextNode = e; } } return d; } void CQtManagedRestrictedModificationHashData::free_helper(void (*node_delete)(Node *), CMemoryAllocationManager* memMan) { if (node_delete) { Node *this_e = reinterpret_cast(this); Node **bucket = reinterpret_cast(this->buckets); int n = numBuckets; while (n--) { Node *cur = *bucket++; while (cur != this_e) { Node *next = cur->next; node_delete(cur); freeNode(cur,memMan); cur = next; } } } //delete [] buckets; CObjectAllocator::releaseArray(buckets,memMan); //delete this; CObjectAllocator::release(this,memMan); } CQtManagedRestrictedModificationHashData::Node *CQtManagedRestrictedModificationHashData::nextNode(Node *node) { union { Node *next; Node *e; CQtManagedRestrictedModificationHashData *d; }; next = node->next; Q_ASSERT_X(next, "QHash", "Iterating beyond end()"); if (next->next) return next; int start = (node->h % d->numBuckets) + 1; Node **bucket = d->buckets + start; int n = d->numBuckets - start; while (n--) { if (*bucket != e) return *bucket; ++bucket; } return e; } CQtManagedRestrictedModificationHashData::Node *CQtManagedRestrictedModificationHashData::previousNode(Node *node) { union { Node *e; CQtManagedRestrictedModificationHashData *d; }; e = node; while (e->next) e = e->next; int start; if (node == e) start = d->numBuckets - 1; else start = node->h % d->numBuckets; Node *sentinel = node; Node **bucket = d->buckets + start; while (start >= 0) { if (*bucket != sentinel) { Node *prev = *bucket; while (prev->next != sentinel) prev = prev->next; return prev; } sentinel = e; --bucket; --start; } Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()"); return e; } /* If hint is negative, -hint gives the approximate number of buckets that should be used for the hash table. If hint is nonnegative, (1 << hint) gives the approximate number of buckets that should be used. */ void CQtManagedRestrictedModificationHashData::rehash(int hint, CMemoryAllocationManager* memMan) { if (hint < 0) { hint = countBits(-hint); if (hint < MinNumBits) hint = MinNumBits; userNumBits = hint; while (primeForNumBits(hint) < (size >> 1)) ++hint; } else if (hint < MinNumBits) { hint = MinNumBits; } if (numBits != hint) { Node *e = reinterpret_cast(this); Node **oldBuckets = buckets; int oldNumBuckets = numBuckets; int nb = primeForNumBits(hint); //buckets = new Node *[nb]; buckets = CObjectAllocator::allocateArray(memMan,nb); numBits = hint; numBuckets = nb; for (int i = 0; i < numBuckets; ++i) buckets[i] = e; for (int i = 0; i < oldNumBuckets; ++i) { Node *firstNode = oldBuckets[i]; while (firstNode != e) { uint h = firstNode->h; Node *lastNode = firstNode; while (lastNode->next != e && lastNode->next->h == h) lastNode = lastNode->next; Node *afterLastNode = lastNode->next; Node **beforeFirstNode = &buckets[h % numBuckets]; while (*beforeFirstNode != e) beforeFirstNode = &(*beforeFirstNode)->next; lastNode->next = *beforeFirstNode; *beforeFirstNode = firstNode; firstNode = afterLastNode; } } //delete [] oldBuckets; CObjectAllocator::releaseArray(oldBuckets,memMan); } } void CQtManagedRestrictedModificationHashData::destroyAndFree(CMemoryAllocationManager* memMan) { free_helper(0,memMan); } #ifdef KONCLUDE_CQTMANAGEDRESTRICTEDMODIFICATIONHASH_DEBUG void CQtManagedRestrictedModificationHashData::dump() { qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)", /*int(ref)*/(int)refHash, size, nodeSize, userNumBits, numBits, numBuckets); qDebug(" %p (fakeNode = %p)", this, fakeNext); for (int i = 0; i < numBuckets; ++i) { QString line; Node *n = buckets[i]; if (n != reinterpret_cast(this)) { line.sprintf("%d:", i); while (n != reinterpret_cast(this)) { line += QString().sprintf(" -> [%p]", n); if (!n) { line += " (CORRUPT)"; break; } n = n->next; } qDebug(qPrintable(line)); } } } void CQtManagedRestrictedModificationHashData::checkSanity() { if (fakeNext) qFatal("Fake next isn't 0"); for (int i = 0; i < numBuckets; ++i) { Node *n = buckets[i]; Node *p = n; if (!n) qFatal("%d: Bucket entry is 0", i); if (n != reinterpret_cast(this)) { while (n != reinterpret_cast(this)) { if (!n->next) qFatal("%d: Next of %p is 0, should be %p", i, n, this); n = n->next; } } } } #endif void CQtManagedRestrictedModificationHashData::mightGrow(CMemoryAllocationManager* memMan) // ### Qt 5: eliminate { if (size >= numBuckets) rehash(numBits + 1,memMan); } //inline bool CQtManagedRestrictedModificationHashData::willGrow() //{ // if (size >= numBuckets) { // rehash(numBits + 1); // return true; // } else { // return false; // } //} void CQtManagedRestrictedModificationHashData::hasShrunk(CMemoryAllocationManager* memMan) { if (size <= (numBuckets >> 3) && numBits > userNumBits) { QT_TRY { rehash(qMax(int(numBits) - 2, int(userNumBits)),memMan); } QT_CATCH(const std::bad_alloc &) { // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe. } } } CQtManagedRestrictedModificationHashData::Node *CQtManagedRestrictedModificationHashData::firstNode() { Node *e = reinterpret_cast(this); Node **bucket = buckets; int n = numBuckets; while (n--) { if (*bucket != e) return *bucket; ++bucket; } return e; } #endif // KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_HASH_CONTAINER }; // end namespace Container }; // end namespace Utilities }; // end namespace Konclude