/*
* 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