| 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 |
*/ |
| 20 |
|
| 21 |
#include "CReuseCompletionGraphCacheReader.h" |
| 22 |
|
| 23 |
|
| 24 |
namespace Konclude { |
| 25 |
|
| 26 |
namespace Reasoner { |
| 27 |
|
| 28 |
namespace Kernel { |
| 29 |
|
| 30 |
namespace Cache { |
| 31 |
|
| 32 |
|
| 33 |
CReuseCompletionGraphCacheReader::CReuseCompletionGraphCacheReader() : CLinkerBase<CReuseCompletionGraphCacheReader*,CReuseCompletionGraphCacheReader>(this) { |
| 34 |
mCurrentSlot = nullptr; |
| 35 |
mFreeLinker = nullptr; |
| 36 |
} |
| 37 |
|
| 38 |
|
| 39 |
CReuseCompletionGraphCacheReader* CReuseCompletionGraphCacheReader::updateSlot(CReuseCompletionGraphCacheSlotItem* updatedSlot) { |
| 40 |
CReuseCompletionGraphCacheSlotItem* prevSlot = mUpdatedSlot.fetchAndStoreOrdered(updatedSlot); |
| 41 |
if (prevSlot != nullptr) { |
| 42 |
prevSlot->decReader(); |
| 43 |
} |
| 44 |
return this; |
| 45 |
} |
| 46 |
|
| 47 |
|
| 48 |
bool CReuseCompletionGraphCacheReader::hasUpdatedSlotItem() { |
| 49 |
return mUpdatedSlot.fetchAndAddRelaxed(0) != nullptr; |
| 50 |
} |
| 51 |
|
| 52 |
|
| 53 |
bool CReuseCompletionGraphCacheReader::switchToUpdatedSlotItem() { |
| 54 |
CReuseCompletionGraphCacheSlotItem* updatedSlot = mUpdatedSlot.fetchAndStoreOrdered(nullptr); |
| 55 |
if (updatedSlot) { |
| 56 |
CReuseCompletionGraphCacheSlotItem* prevSlot = mCurrentSlot; |
| 57 |
mCurrentSlot = updatedSlot; |
| 58 |
if (prevSlot != nullptr) { |
| 59 |
prevSlot->decReader(); |
| 60 |
} |
| 61 |
return true; |
| 62 |
} |
| 63 |
return false; |
| 64 |
} |
| 65 |
|
| 66 |
|
| 67 |
CXLinker<TConceptNegPair>* CReuseCompletionGraphCacheReader::getConceptTestLinker() { |
| 68 |
CXLinker<TConceptNegPair>* linker = nullptr; |
| 69 |
if (mFreeLinker) { |
| 70 |
linker = mFreeLinker; |
| 71 |
mFreeLinker = mFreeLinker->getNext(); |
| 72 |
} else { |
| 73 |
linker = CObjectAllocator< CXLinker<TConceptNegPair> >::allocateAndConstruct(mContext.getMemoryAllocationManager()); |
| 74 |
} |
| 75 |
linker->clearNext(); |
| 76 |
return linker; |
| 77 |
} |
| 78 |
|
| 79 |
|
| 80 |
CReuseCompletionGraphCacheReader* CReuseCompletionGraphCacheReader::releaseConceptTestLinker(CXLinker<TConceptNegPair>* linker) { |
| 81 |
mFreeLinker = linker->append(mFreeLinker); |
| 82 |
return this; |
| 83 |
} |
| 84 |
|
| 85 |
|
| 86 |
bool CReuseCompletionGraphCacheReader::addTestingConcepts(CSortedNegLinker<CConcept*>* conLinker, bool negate, cint64 addingLevel, CCACHINGSET<CConcept*>* testedConceptSet) { |
| 87 |
bool oneAdded = false; |
| 88 |
for (CSortedNegLinker<CConcept*>* conLinkerIt = conLinker; conLinkerIt; conLinkerIt = conLinkerIt->getNext()) { |
| 89 |
CConcept* concept = conLinkerIt->getData(); |
| 90 |
bool negated = conLinkerIt->isNegated(); |
| 91 |
oneAdded |= addTestingConcept(concept,negated^negate,addingLevel,testedConceptSet); |
| 92 |
} |
| 93 |
return oneAdded; |
| 94 |
} |
| 95 |
|
| 96 |
|
| 97 |
|
| 98 |
bool CReuseCompletionGraphCacheReader::addTestingConcept(CConcept* concept, bool negated, cint64 addingLevel, CCACHINGSET<CConcept*>* testedConceptSet) { |
| 99 |
if (!testedConceptSet->contains(concept)) { |
| 100 |
testedConceptSet->insert(concept); |
| 101 |
CXLinker<TConceptNegPair>* newLinker = getConceptTestLinker(); |
| 102 |
newLinker->initLinker(TConceptNegPair(concept,negated)); |
| 103 |
if (addingLevel < mTestConceptLinkerLevel) { |
| 104 |
addingLevel = mTestConceptLinkerLevel; |
| 105 |
} |
| 106 |
mTestConceptLinkerVec[addingLevel] = newLinker->append(mTestConceptLinkerVec[addingLevel]); |
| 107 |
++mTestConceptLinkerCount; |
| 108 |
return true; |
| 109 |
} |
| 110 |
return false; |
| 111 |
} |
| 112 |
|
| 113 |
|
| 114 |
CReuseCompletionGraphCacheEntry* CReuseCompletionGraphCacheReader::getCacheEntry(CConcept* concept, bool* minimalCompletionGraph, bool* deterministicConnection) { |
| 115 |
CReuseCompletionGraphCacheEntry* entry = nullptr; |
| 116 |
if (hasUpdatedSlotItem()) { |
| 117 |
switchToUpdatedSlotItem(); |
| 118 |
} |
| 119 |
if (mCurrentSlot) { |
| 120 |
CReuseCompletionGraphCompatibilityEntryHash* entryHash = mCurrentSlot->getEntryHash(); |
| 121 |
cint64 entryCount = mCurrentSlot->getEntryCount(); |
| 122 |
|
| 123 |
if (entryCount > 0) { |
| 124 |
|
| 125 |
if (mEntryVotingVec.size() < entryCount) { |
| 126 |
mEntryVotingVec.resize(entryCount); |
| 127 |
} |
| 128 |
|
| 129 |
for (cint64 i = 0; i < entryCount; ++i) { |
| 130 |
CCacheEntryVotingItem& item = mEntryVotingVec[i]; |
| 131 |
item.reset(); |
| 132 |
} |
| 133 |
|
| 134 |
CCACHINGSET<CConcept*> testedConceptSet(&mContext); |
| 135 |
|
| 136 |
for (cint64 i = 0; i < mTestConceptLinkerVecSize; ++i) { |
| 137 |
mTestConceptLinkerVec[i] = nullptr; |
| 138 |
} |
| 139 |
mTestConceptLinkerCount = 1; |
| 140 |
mTestConceptLinkerLevel = 0; |
| 141 |
CXLinker<TConceptNegPair>* testConceptLinker = getConceptTestLinker(); |
| 142 |
testConceptLinker->initLinker(TConceptNegPair(concept,false)); |
| 143 |
mTestConceptLinkerVec[0] = testConceptLinker; |
| 144 |
testedConceptSet.insert(concept); |
| 145 |
|
| 146 |
while (mTestConceptLinkerCount > 0) { |
| 147 |
CXLinker<TConceptNegPair>* tmpTestConLinker = nullptr; |
| 148 |
for (; mTestConceptLinkerLevel < mTestConceptLinkerVecSize; ++mTestConceptLinkerLevel) { |
| 149 |
tmpTestConLinker = mTestConceptLinkerVec[mTestConceptLinkerLevel]; |
| 150 |
if (tmpTestConLinker) { |
| 151 |
mTestConceptLinkerVec[mTestConceptLinkerLevel] = tmpTestConLinker->getNext(); |
| 152 |
tmpTestConLinker->clearNext(); |
| 153 |
break; |
| 154 |
} |
| 155 |
} |
| 156 |
--mTestConceptLinkerCount; |
| 157 |
CConcept* testCon = tmpTestConLinker->getData().first; |
| 158 |
bool testConNeg = tmpTestConLinker->getData().second; |
| 159 |
|
| 160 |
bool searchOperandConcepts = true; |
| 161 |
|
| 162 |
if (!testConNeg && testCon->hasClassName()) { |
| 163 |
// test whether concept is available in cache |
| 164 |
CCacheValue cacheValue(testCon->getConceptTag(),(cint64)testCon,CCacheValue::CACHEVALTAGANDCONCEPT); |
| 165 |
const CReuseCompletionGraphCompatibilityEntryHashData& data = entryHash->value(cacheValue); |
| 166 |
CXLinker<CReuseCompletionGraphCacheEntry*>* entailedEntryLinker = data.getEntailedEntryLinker(); |
| 167 |
CXLinker<CReuseCompletionGraphCacheEntry*>* incompatibleEntryLinker = data.getIncompatibleEntryLinker(); |
| 168 |
if (entailedEntryLinker || incompatibleEntryLinker) { |
| 169 |
|
| 170 |
for (CXLinker<CReuseCompletionGraphCacheEntry*>* entailedEntryLinkerIt = entailedEntryLinker; entailedEntryLinkerIt; entailedEntryLinkerIt = entailedEntryLinkerIt->getNext()) { |
| 171 |
CReuseCompletionGraphCacheEntry* entry = entailedEntryLinkerIt->getData(); |
| 172 |
CCacheEntryVotingItem& item = mEntryVotingVec[entry->getEntryID()]; |
| 173 |
item.mEntry = entry; |
| 174 |
item.mEntailedCount++; |
| 175 |
item.mTmpReferenced = true; |
| 176 |
item.mMinConnectionLevel = qMin(item.mMinConnectionLevel,mTestConceptLinkerLevel); |
| 177 |
item.mMinimalFound |= entry->hasMinimalValue(cacheValue); |
| 178 |
} |
| 179 |
|
| 180 |
for (CXLinker<CReuseCompletionGraphCacheEntry*>* incompatibleEntryLinkerIt = incompatibleEntryLinker; incompatibleEntryLinkerIt; incompatibleEntryLinkerIt = incompatibleEntryLinkerIt->getNext()) { |
| 181 |
CReuseCompletionGraphCacheEntry* entry = incompatibleEntryLinkerIt->getData(); |
| 182 |
CCacheEntryVotingItem& item = mEntryVotingVec[entry->getEntryID()]; |
| 183 |
item.mEntry = entry; |
| 184 |
item.mIncompatibleCount++; |
| 185 |
item.mTmpReferenced = true; |
| 186 |
} |
| 187 |
|
| 188 |
for (cint64 i = 0; i < entryCount; ++i) { |
| 189 |
CCacheEntryVotingItem& item = mEntryVotingVec[i]; |
| 190 |
if (!item.mTmpReferenced) { |
| 191 |
item.mMissingCount++; |
| 192 |
} else { |
| 193 |
item.mTmpReferenced = false; |
| 194 |
} |
| 195 |
} |
| 196 |
|
| 197 |
searchOperandConcepts = false; |
| 198 |
} |
| 199 |
} |
| 200 |
|
| 201 |
if (searchOperandConcepts) { |
| 202 |
|
| 203 |
CRole* role = testCon->getRole(); |
| 204 |
if (role) { |
| 205 |
addTestingConcepts(role->getDomainConceptList(),false,0,&testedConceptSet); |
| 206 |
addTestingConcepts(role->getRangeConceptList(),false,2,&testedConceptSet); |
| 207 |
} |
| 208 |
cint64 opCode = testCon->getOperatorCode(); |
| 209 |
CSortedNegLinker<CConcept*>* opLinker = testCon->getOperandList(); |
| 210 |
|
| 211 |
if (!testConNeg && (opCode == CCIMPLAQAND || opCode == CCBRANCHAQAND || opCode == CCAQAND || opCode == CCEQ || opCode == CCAND || opCode == CCSUB || opCode == CCIMPLTRIG) || testConNeg && (opCode == CCOR)) { |
| 212 |
addTestingConcepts(opLinker,testConNeg,0,&testedConceptSet); |
| 213 |
} else if (!testConNeg && (opCode == CCOR) || testConNeg && (opCode == CCEQ || opCode == CCAND)) { |
| 214 |
addTestingConcepts(opLinker,testConNeg,3,&testedConceptSet); |
| 215 |
} else if (!testConNeg && (opCode == CCSOME || opCode == CCAQSOME) || testConNeg && (opCode == CCALL)) { |
| 216 |
addTestingConcepts(opLinker,testConNeg,1,&testedConceptSet); |
| 217 |
} else if (!testConNeg && (opCode == CCATLEAST) || testConNeg && (opCode == CCATMOST)) { |
| 218 |
cint64 cardinality = testCon->getParameter() + 1*testConNeg; |
| 219 |
if (cardinality >= 1) { |
| 220 |
addTestingConcepts(opLinker,testConNeg,1,&testedConceptSet); |
| 221 |
} |
| 222 |
} else if (opCode == CCAQALL || opCode == CCIMPLALL || opCode == CCBRANCHALL) { |
| 223 |
addTestingConcepts(opLinker,false,2,&testedConceptSet); |
| 224 |
} else if (opCode == CCATMOST || opCode == CCATLEAST) { |
| 225 |
addTestingConcepts(opLinker,false,3,&testedConceptSet); |
| 226 |
} else if (opCode == CCIMPL) { |
| 227 |
addTestingConcept(opLinker->getData(),opLinker->isNegated(),0,&testedConceptSet); |
| 228 |
} else if (opCode == CCAQCHOOCE) { |
| 229 |
for (CSortedNegLinker<CConcept*>* opLinkerIt = opLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) { |
| 230 |
if (opLinkerIt->isNegated() == testConNeg) { |
| 231 |
addTestingConcept(opLinkerIt->getData(),false,0,&testedConceptSet); |
| 232 |
} |
| 233 |
} |
| 234 |
} |
| 235 |
|
| 236 |
} |
| 237 |
|
| 238 |
releaseConceptTestLinker(tmpTestConLinker); |
| 239 |
} |
| 240 |
|
| 241 |
cint64 minMissingCount = 0; |
| 242 |
CCacheEntryVotingItem* bestEntryItem = nullptr; |
| 243 |
|
| 244 |
for (cint64 i = 0; i < entryCount; ++i) { |
| 245 |
CCacheEntryVotingItem& item = mEntryVotingVec[i]; |
| 246 |
if (item.mEntailedCount >= 1 && item.mIncompatibleCount <= 0 && (bestEntryItem == nullptr || minMissingCount < item.mMissingCount)) { |
| 247 |
minMissingCount = item.mMissingCount; |
| 248 |
bestEntryItem = &item; |
| 249 |
} |
| 250 |
} |
| 251 |
|
| 252 |
if (bestEntryItem) { |
| 253 |
entry = bestEntryItem->mEntry; |
| 254 |
if (deterministicConnection) { |
| 255 |
*deterministicConnection = bestEntryItem->mMinConnectionLevel <= 1; |
| 256 |
} |
| 257 |
if (minimalCompletionGraph) { |
| 258 |
*minimalCompletionGraph = bestEntryItem->mMinimalFound; |
| 259 |
} |
| 260 |
} |
| 261 |
} |
| 262 |
|
| 263 |
} |
| 264 |
return entry; |
| 265 |
} |
| 266 |
|
| 267 |
|
| 268 |
}; // end namespace Cache |
| 269 |
|
| 270 |
}; // end namespace Kernel |
| 271 |
|
| 272 |
}; // end namespace Reasoner |
| 273 |
|
| 274 |
}; // end namespace Konclude |