/*
* 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 .
*
*/
#include "COccurrenceUnsatisfiableCacheReader.h"
namespace Konclude {
namespace Reasoner {
namespace Kernel {
namespace Cache {
COccurrenceUnsatisfiableCacheReader::COccurrenceUnsatisfiableCacheReader(COccurrenceUnsatisfiableCache *unsatisfiableCache) {
cache = unsatisfiableCache;
cacheSlotItem = 0;
incCacheEntriesLinker = 0;
incrementUnsatisfiableTestReset();
}
COccurrenceUnsatisfiableCacheReader::~COccurrenceUnsatisfiableCacheReader() {
}
COccurrenceUnsatisfiableCacheUpdateSlotItem *COccurrenceUnsatisfiableCacheReader::changeUpdateSlot(COccurrenceUnsatisfiableCacheUpdateSlotItem *nextUpdateSlot) {
COccurrenceUnsatisfiableCacheUpdateSlotItem *tmpSlotItem = 0;
nextUpdateSlot->incReader();
tmpSlotItem = mNextCacheSlotItemPointer.fetchAndStoreOrdered(nextUpdateSlot);
if (tmpSlotItem) {
tmpSlotItem->decReader();
}
return tmpSlotItem;
}
bool COccurrenceUnsatisfiableCacheReader::moveToNextSlot() {
if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
COccurrenceUnsatisfiableCacheUpdateSlotItem* nextSlotItem = mNextCacheSlotItemPointer.fetchAndStoreOrdered(nullptr);
if (nextSlotItem) {
if (cacheSlotItem) {
cacheSlotItem->decReader();
}
cacheSlotItem = nextSlotItem;
return true;
}
}
return false;
}
void COccurrenceUnsatisfiableCacheReader::incrementUnsatisfiableTestReset() {
while (incCacheEntriesLinker) {
CDblLinker *tmpCacheEntry = incCacheEntriesLinker;
incCacheEntriesLinker = incCacheEntriesLinker->getNext();
memManCacheEntryList.release(tmpCacheEntry);
}
lastUnsatItems.clear();
}
bool COccurrenceUnsatisfiableCacheReader::incrementUnsatisfiableTest(CCacheValue *cacheValue, bool *continueTestingUseful) {
bool unsat = false;
incCacheEntriesLinker = incrementalUnsatisfiableTest(cacheValue,incCacheEntriesLinker,&unsat,continueTestingUseful);
return unsat;
}
CDblLinker *COccurrenceUnsatisfiableCacheReader::incrementalUnsatisfiableTest(CCacheValue *cacheValue, CDblLinker *cacheEntries, bool *unsatisfiable, bool *continueTesting) {
if (!cacheEntries) {
cacheEntries = memManCacheEntryList.allocate()->init(cache->getPrimarCacheEntry());
}
qint64 updateSlot = 0;
if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
moveToNextSlot();
}
bool unsatisfiableFound = false;
bool continueTestingUseful = false;
if (cacheSlotItem) {
updateSlot = cacheSlotItem->getSlotIndex();
CDblLinker *nextCacheEntries = 0;
qint64 itemTag = cacheValue->getTag();
CDblLinker *linkIt = cacheEntries;
while (linkIt) {
if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
moveToNextSlot();
if (cacheSlotItem) {
updateSlot = cacheSlotItem->getSlotIndex();
}
}
CDblLinker *linkNextIt = linkIt->getNext();
if (linkNextIt) {
linkNextIt->removePrev();
}
COccurrenceUnsatisfiableCacheEntry *cacheEntry = linkIt->getData();
qint64 cacheMax = cacheEntry->getMaxTag();
qint64 cacheMin = cacheEntry->getMinTag();
COccurrenceUnsatisfiableCacheEntriesHash *cacheHash = cacheEntry->getSlotCacheEntriesHash(updateSlot);
// test min and max
if (!cacheHash || itemTag > cacheMax) {
// cache entry is no longer needed
memManCacheEntryList.release(linkIt);
} else {
if (!cacheEntry->isSerialized()) {
// cache entry is needed, next round
nextCacheEntries = linkIt->insertNext(nextCacheEntries);
} else {
memManCacheEntryList.release(linkIt);
}
// test to add additional cache entries
if (cacheHash->contains(*cacheValue)) {
COccurrenceUnsatisfiableCacheEntry *nextAddingCacheEntry = cacheHash->value(*cacheValue);
if (nextAddingCacheEntry->isUnsatisfiableTermination()) {
unsatisfiableFound = true;
linkIt = linkNextIt;
if (nextAddingCacheEntry->getCacheTerminationValuesList()) {
lastUnsatItems = *nextAddingCacheEntry->getCacheTerminationValuesList();
}
break;
}
nextCacheEntries = memManCacheEntryList.allocate()->init(nextAddingCacheEntry,nextCacheEntries);
}
}
linkIt = linkNextIt;
}
while (linkIt) {
CDblLinker *tmpCacheEntry = linkIt;
linkIt = linkIt->getNext();
memManCacheEntryList.release(tmpCacheEntry);
}
cacheEntries = nextCacheEntries;
nextCacheEntries = 0;
} else {
while (cacheEntries) {
CDblLinker *tmpCacheEntry = cacheEntries;
cacheEntries = cacheEntries->getNext();
memManCacheEntryList.release(tmpCacheEntry);
}
cacheEntries = 0;
}
if (unsatisfiableFound) {
while (cacheEntries) {
CDblLinker *tmpCacheEntry = cacheEntries;
cacheEntries = cacheEntries->getNext();
memManCacheEntryList.release(tmpCacheEntry);
}
cacheEntries = 0;
}
if (!unsatisfiableFound && cacheEntries) {
continueTestingUseful = true;
}
if (continueTesting) {
*continueTesting = continueTestingUseful;
}
if (unsatisfiable) {
*unsatisfiable = unsatisfiableFound;
}
return cacheEntries;
}
bool COccurrenceUnsatisfiableCacheReader::isUnsatisfiable(QVector &itemVec, qint64 count) {
return isUnsatisfiable(itemVec,count,0);
}
bool COccurrenceUnsatisfiableCacheReader::isUnsatisfiable(QVector &itemVec, qint64 count, QList *unsatisfiableItemList) {
bool unsatisfiable = false;
// list for cache entries
// TODO: use min and max from cache entries to make list smaller
CDblLinker *cacheEntries = memManCacheEntryList.allocate()->init(cache->getPrimarCacheEntry());
qint64 firstIndex = 0;
qint64 lastIndex = count-1;
// make assumption that list is sorted
qint64 minItem = itemVec[0].getTag();
qint64 maxItem = itemVec[lastIndex].getTag();
qint64 updateSlot = 0;
if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
moveToNextSlot();
}
if (cacheSlotItem) {
updateSlot = cacheSlotItem->getSlotIndex();
CDblLinker *nextCacheEntries = 0;
// TODO: Skip items which are not in cache
qint64 index = 0;
while (index < count && !unsatisfiable && cacheEntries) {
CCacheValue &item = itemVec[index++];
qint64 itemTag = item.getTag();
nextCacheEntries = 0;
CDblLinker *linkIt = cacheEntries;
while (linkIt) {
if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
moveToNextSlot();
if (cacheSlotItem) {
updateSlot = cacheSlotItem->getSlotIndex();
}
}
CDblLinker *linkNextIt = linkIt->getNext();
if (linkNextIt) {
linkNextIt->removePrev();
}
COccurrenceUnsatisfiableCacheEntry *cacheEntry = linkIt->getData();
qint64 cacheMax = cacheEntry->getMaxTag();
qint64 cacheMin = cacheEntry->getMinTag();
COccurrenceUnsatisfiableCacheEntriesHash *cacheHash = cacheEntry->getSlotCacheEntriesHash(updateSlot);
// test min and max
if (!cacheHash || cacheMin > maxItem || itemTag > cacheMax) {
// cache entry is no longer needed
memManCacheEntryList.release(linkIt);
} else {
// cache entry is needed, next round
nextCacheEntries = linkIt->insertNext(nextCacheEntries);
// test to add additional cache entries
if (cacheHash->contains(item)) {
COccurrenceUnsatisfiableCacheEntry *nextAddingCacheEntry = cacheHash->value(item);
if (nextAddingCacheEntry->isUnsatisfiableTermination()) {
unsatisfiable = true;
if (nextAddingCacheEntry->getCacheTerminationValuesList()) {
lastUnsatItems = *nextAddingCacheEntry->getCacheTerminationValuesList();
if (unsatisfiableItemList) {
*unsatisfiableItemList = *nextAddingCacheEntry->getCacheTerminationValuesList();
}
}
linkIt = linkNextIt;
break;
}
nextCacheEntries = memManCacheEntryList.allocate()->init(nextAddingCacheEntry,nextCacheEntries);
}
}
linkIt = linkNextIt;
}
while (linkIt) {
CDblLinker *tmpCacheEntry = linkIt;
linkIt = linkIt->getNext();
memManCacheEntryList.release(tmpCacheEntry);
}
cacheEntries = nextCacheEntries;
nextCacheEntries = 0;
}
while (cacheEntries) {
CDblLinker *tmpCacheEntry = cacheEntries;
cacheEntries = cacheEntries->getNext();
memManCacheEntryList.release(tmpCacheEntry);
}
}
if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
moveToNextSlot();
if (cacheSlotItem) {
updateSlot = cacheSlotItem->getSlotIndex();
}
}
return unsatisfiable;
}
QList COccurrenceUnsatisfiableCacheReader::getLastTestedUnsatisfiableItems() {
return lastUnsatItems;
}
QList COccurrenceUnsatisfiableCacheReader::getUnsatisfiableItems(QVector &itemVec, qint64 count) {
QList unsatList;
isUnsatisfiable(itemVec,count,&unsatList);
return unsatList;
}
CXLinker* COccurrenceUnsatisfiableCacheReader::getUnsatisfiableItems(CXLinker* cacheValueTestLinker, CMemoryAllocationManager* memMan) {
CXLinker* unsatLinker = nullptr;
bool unsatisfiable = false;
// list for cache entries
// TODO: use min and max from cache entries to make list smaller
CXLinker* cacheEntries = CObjectAllocator< CXLinker >::allocateAndConstruct(memMan)->initLinker(cache->getPrimarCacheEntry());
//memManCacheEntryList.allocate()->init(cache->getPrimarCacheEntry());
CCacheValue* firstItem = cacheValueTestLinker->getData();
CCacheValue* lastItem = cacheValueTestLinker->getLastListLink()->getData();
CXLinker* testCacheItemIt = cacheValueTestLinker;
// make assumption that list is sorted
qint64 minItem = firstItem->getTag();
qint64 maxItem = lastItem->getTag();
qint64 updateSlot = 0;
if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
moveToNextSlot();
}
if (cacheSlotItem) {
updateSlot = cacheSlotItem->getSlotIndex();
CXLinker *nextCacheEntries = nullptr;
while (testCacheItemIt && cacheEntries) {
CCacheValue* item = testCacheItemIt->getData();
qint64 itemTag = item->getTag();
nextCacheEntries = nullptr;
CXLinker *cacheEntryIt = cacheEntries;
while (cacheEntryIt) {
CXLinker *cacheEntryLinker = cacheEntryIt;
cacheEntryIt = cacheEntryIt->getNext();
cacheEntryLinker->clearNext();
COccurrenceUnsatisfiableCacheEntry *cacheEntry = cacheEntryLinker->getData();
qint64 cacheMax = cacheEntry->getMaxTag();
qint64 cacheMin = cacheEntry->getMinTag();
COccurrenceUnsatisfiableCacheEntriesHash *cacheHash = cacheEntry->getSlotCacheEntriesHash(updateSlot);
// test min and max
if (!cacheHash || cacheMin > maxItem || itemTag > cacheMax) {
// cache entry is no longer needed
} else {
// cache entry is needed, next round
nextCacheEntries = cacheEntryLinker->append(nextCacheEntries);
COccurrenceUnsatisfiableCacheEntry *nextAddingCacheEntry = cacheHash->value(*item,nullptr);
// test to add additional cache entries
if (nextAddingCacheEntry) {
if (nextAddingCacheEntry->isUnsatisfiableTermination()) {
unsatisfiable = true;
QList* unsatValList = nextAddingCacheEntry->getCacheTerminationValuesList();
if (unsatValList) {
CXLinker* unsatCacheItemLinker = cacheValueTestLinker;
CXLinker* lastUnsatCacheItemLinker = nullptr;
CXLinker* firstUnsatCacheItemLinker = nullptr;
for (QList::const_iterator unsatItemIt = unsatValList->constBegin(), unsatItemItEnd = unsatValList->constEnd(); unsatItemIt != unsatItemItEnd; ++unsatItemIt) {
while (*unsatCacheItemLinker->getData() != *unsatItemIt) {
unsatCacheItemLinker = unsatCacheItemLinker->getNext();
}
if (!firstUnsatCacheItemLinker) {
firstUnsatCacheItemLinker = unsatCacheItemLinker;
} else {
lastUnsatCacheItemLinker->setNext(unsatCacheItemLinker);
}
lastUnsatCacheItemLinker = unsatCacheItemLinker;
}
lastUnsatCacheItemLinker->clearNext();
return firstUnsatCacheItemLinker;
} else {
return cacheValueTestLinker;
}
}
nextCacheEntries = CObjectAllocator< CXLinker >::allocateAndConstruct(memMan)->initLinker(nextAddingCacheEntry,nextCacheEntries);
}
}
}
cacheEntries = nextCacheEntries;
nextCacheEntries = nullptr;
testCacheItemIt = testCacheItemIt->getNext();
}
}
return nullptr;
}
cint64 COccurrenceUnsatisfiableCacheReader::getCurrentCachingTag() {
return cache->getCurrentCachingTag();
}
}; // end namespace Cache
}; // end namespace Kernel
}; // end namespace Reasoner
}; // end namespace Konclude