/*
* 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 "CQtManagedRestrictedModificationListData.h"
namespace Konclude {
namespace Utilities {
namespace Container {
#ifdef KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_LIST_CONTAINER
CQtManagedRestrictedModificationListData::Data CQtManagedRestrictedModificationListData::shared_null = { nullptr, 0, 0, 0, true, { 0 } };
int cAllocMore(int alloc, int extra)
{
if (alloc == 0 && extra == 0)
return 0;
const int page = 1 << 12;
int nalloc;
alloc += extra;
if (alloc < 1<<6) {
nalloc = (1<<3) + ((alloc >>3) << 3);
} else {
// don't do anything if the loop will overflow signed int.
if (alloc >= INT_MAX/2)
return INT_MAX;
nalloc = (alloc < page) ? 1 << 3 : page;
while (nalloc < alloc) {
if (nalloc <= 0)
return INT_MAX;
nalloc *= 2;
}
}
return nalloc - extra;
}
static int grow(int size, CMemoryAllocationManager* memMan)
{
// dear compiler: don't optimize me out.
//if (!memMan) {
volatile int x = cAllocMore(size * sizeof(void *), CQtManagedRestrictedModificationListData::DataHeaderSize) / sizeof(void *);
return x;
/*} else {
return memMan->getOptimizedMoreAllocationSize(size * sizeof(void *)+ CQtManagedRestrictedModificationListData::DataHeaderSize) / sizeof(void *);
}*/
}
/*!
* Detaches the CQtManagedRestrictedModificationListData by allocating new memory for a list which will be bigger
* than the copied one and is expected to grow further.
* *idx is the desired insertion point and is clamped to the actual size of the list.
* num is the number of new elements to insert at the insertion point.
* Returns the old (shared) data, it is up to the caller to deref() and free().
* For the new data node_copy needs to be called.
*
* \internal
*/
CQtManagedRestrictedModificationListData::Data *CQtManagedRestrictedModificationListData::detach_grow(int *idx, int num, CMemoryAllocationManager* memMan, CQtManagedRestrictedModificationListBase* listBase)
{
Data *x = d;
int l = x->end - x->begin;
int nl = l + num;
int alloc = grow(nl,memMan);
Data* t = static_cast(CMemoryAllocator::allocateMemory(memMan,DataHeaderSize + alloc * sizeof(void *)));
Q_CHECK_PTR(t);
//t->ref = 1;
t->refList = listBase;
t->sharable = true;
t->alloc = alloc;
// The space reservation algorithm's optimization is biased towards appending:
// Something which looks like an append will put the data at the beginning,
// while something which looks like a prepend will put it in the middle
// instead of at the end. That's based on the assumption that prepending
// is uncommon and even an initial prepend will eventually be followed by
// at least some appends.
int bg;
if (*idx < 0) {
*idx = 0;
bg = (alloc - nl) >> 1;
} else if (*idx > l) {
*idx = l;
bg = 0;
} else if (*idx < (l >> 1)) {
bg = (alloc - nl) >> 1;
} else {
bg = 0;
}
t->begin = bg;
t->end = bg + nl;
d = t;
return x;
}
/*!
* Detaches the CQtManagedRestrictedModificationListData by allocating new memory for a list which possibly
* has a different size than the copied one.
* Returns the old (shared) data, it is up to the caller to deref() and free()
* For the new data node_copy needs to be called.
*
* \internal
*/
CQtManagedRestrictedModificationListData::Data *CQtManagedRestrictedModificationListData::detach(int alloc, CMemoryAllocationManager* memMan, CQtManagedRestrictedModificationListBase* listBase)
{
Data *x = d;
Data* t = nullptr;
//t = static_cast(qMalloc(DataHeaderSize + alloc * sizeof(void *)));
t = static_cast(CMemoryAllocator::allocateMemory(memMan,DataHeaderSize + alloc * sizeof(void *)));
Q_CHECK_PTR(t);
//t->ref = 1;
t->refList = listBase;
t->sharable = true;
t->alloc = alloc;
if (!alloc) {
t->begin = 0;
t->end = 0;
} else {
t->begin = x->begin;
t->end = x->end;
}
d = t;
return x;
}
// ensures that enough space is available to append n elements
void **CQtManagedRestrictedModificationListData::append(int n, CMemoryAllocationManager* memMan)
{
//Q_ASSERT(d->ref == 1);
int e = d->end;
if (e + n > d->alloc) {
int b = d->begin;
if (b - n >= 2 * d->alloc / 3) {
// we have enough space. Just not at the end -> move it.
e -= b;
::memcpy(d->array, d->array + b, e * sizeof(void *));
d->begin = 0;
} else {
realloc(grow(d->alloc + n,memMan),memMan);
}
}
d->end = e + n;
return d->array + e;
}
// ensures that enough space is available to append one element
void **CQtManagedRestrictedModificationListData::append(CMemoryAllocationManager* memMan)
{
return append(1,memMan);
}
// ensures that enough space is available to append the list
void **CQtManagedRestrictedModificationListData::append2(const CQtManagedRestrictedModificationListData& l, CMemoryAllocationManager* memMan)
{
return append(l.d->end - l.d->begin,memMan);
}
void **CQtManagedRestrictedModificationListData::append(const CQtManagedRestrictedModificationListData& l, CMemoryAllocationManager* memMan)
{
//Q_ASSERT(d->ref == 1);
int e = d->end;
int n = l.d->end - l.d->begin;
if (n) {
if (e + n > d->alloc)
realloc(grow(e + n,memMan),memMan);
::memcpy(d->array + d->end, l.d->array + l.d->begin, n*sizeof(void*));
d->end += n;
}
return d->array + e;
}
void **CQtManagedRestrictedModificationListData::prepend(CMemoryAllocationManager* memMan)
{
//Q_ASSERT(d->ref == 1);
if (d->begin == 0) {
if (d->end >= d->alloc / 3)
realloc(grow(d->alloc + 1,memMan),memMan);
if (d->end < d->alloc / 3)
d->begin = d->alloc - 2 * d->end;
else
d->begin = d->alloc - d->end;
::memmove(d->array + d->begin, d->array, d->end * sizeof(void *));
d->end += d->begin;
}
return d->array + --d->begin;
}
void **CQtManagedRestrictedModificationListData::insert(int i, CMemoryAllocationManager* memMan)
{
//Q_ASSERT(d->ref == 1);
if (i <= 0)
return prepend(memMan);
int size = d->end - d->begin;
if (i >= size)
return append(memMan);
bool leftward = false;
if (d->begin == 0) {
if (d->end == d->alloc) {
// If the array is full, we expand it and move some items rightward
realloc(grow(d->alloc + 1,memMan),memMan);
} else {
// If there is free space at the end of the array, we move some items rightward
}
} else {
if (d->end == d->alloc) {
// If there is free space at the beginning of the array, we move some items leftward
leftward = true;
} else {
// If there is free space at both ends, we move as few items as possible
leftward = (i < size - i);
}
}
if (leftward) {
--d->begin;
::memmove(d->array + d->begin, d->array + d->begin + 1, i * sizeof(void *));
} else {
::memmove(d->array + d->begin + i + 1, d->array + d->begin + i,
(size - i) * sizeof(void *));
++d->end;
}
return d->array + d->begin + i;
}
void CQtManagedRestrictedModificationListData::remove(int i)
{
//Q_ASSERT(d->ref == 1);
i += d->begin;
if (i - d->begin < d->end - i) {
if (int offset = i - d->begin)
::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
d->begin++;
} else {
if (int offset = d->end - i - 1)
::memmove(d->array + i, d->array + i + 1, offset * sizeof(void *));
d->end--;
}
}
void CQtManagedRestrictedModificationListData::remove(int i, int n)
{
//Q_ASSERT(d->ref == 1);
i += d->begin;
int middle = i + n/2;
if (middle - d->begin < d->end - middle) {
::memmove(d->array + d->begin + n, d->array + d->begin,
(i - d->begin) * sizeof(void*));
d->begin += n;
} else {
::memmove(d->array + i, d->array + i + n,
(d->end - i - n) * sizeof(void*));
d->end -= n;
}
}
void CQtManagedRestrictedModificationListData::move(int from, int to)
{
//Q_ASSERT(d->ref == 1);
if (from == to)
return;
from += d->begin;
to += d->begin;
void *t = d->array[from];
if (from < to) {
if (d->end == d->alloc || 3 * (to - from) < 2 * (d->end - d->begin)) {
::memmove(d->array + from, d->array + from + 1, (to - from) * sizeof(void *));
} else {
// optimization
if (int offset = from - d->begin)
::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
if (int offset = d->end - (to + 1))
::memmove(d->array + to + 2, d->array + to + 1, offset * sizeof(void *));
++d->begin;
++d->end;
++to;
}
} else {
if (d->begin == 0 || 3 * (from - to) < 2 * (d->end - d->begin)) {
::memmove(d->array + to + 1, d->array + to, (from - to) * sizeof(void *));
} else {
// optimization
if (int offset = to - d->begin)
::memmove(d->array + d->begin - 1, d->array + d->begin, offset * sizeof(void *));
if (int offset = d->end - (from + 1))
::memmove(d->array + from, d->array + from + 1, offset * sizeof(void *));
--d->begin;
--d->end;
--to;
}
}
d->array[to] = t;
}
void **CQtManagedRestrictedModificationListData::erase(void **xi)
{
//Q_ASSERT(d->ref == 1);
int i = xi - (d->array + d->begin);
remove(i);
return d->array + d->begin + i;
}
void CQtManagedRestrictedModificationListData::realloc(int alloc, CMemoryAllocationManager* memMan)
{
//Q_ASSERT(d->ref == 1);
//Data *x = static_cast(qRealloc(d, DataHeaderSize + alloc * sizeof(void *)));
Data *x = nullptr;
x = static_cast(CMemoryAllocator::reallocateMemory(d,memMan, DataHeaderSize + d->alloc * sizeof(void *), DataHeaderSize + alloc * sizeof(void *)));
Q_CHECK_PTR(x);
d = x;
d->alloc = alloc;
if (!alloc)
d->begin = d->end = 0;
}
#endif // KONCLUDE_EMPLOY_QT_MANAGED_RESTRICTED_MODIFICATION_LIST_CONTAINER
}; // end namespace Container
}; // end namespace Utilities
}; // end namespace Konclude