Debian Codegraph @

Source/Reasoner/Kernel/Cache/COccurrenceUnsatisfiableCacheReader.cpp

raw
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 "COccurrenceUnsatisfiableCacheReader.h"
22
23
24 namespace Konclude {
25
26 namespace Reasoner {
27
28 namespace Kernel {
29
30 namespace Cache {
31
32
33 COccurrenceUnsatisfiableCacheReader::COccurrenceUnsatisfiableCacheReader(COccurrenceUnsatisfiableCache *unsatisfiableCache) {
34 cache = unsatisfiableCache;
35 cacheSlotItem = 0;
36 incCacheEntriesLinker = 0;
37 incrementUnsatisfiableTestReset();
38 }
39
40
41 COccurrenceUnsatisfiableCacheReader::~COccurrenceUnsatisfiableCacheReader() {
42 }
43
44
45
46 COccurrenceUnsatisfiableCacheUpdateSlotItem *COccurrenceUnsatisfiableCacheReader::changeUpdateSlot(COccurrenceUnsatisfiableCacheUpdateSlotItem *nextUpdateSlot) {
47 COccurrenceUnsatisfiableCacheUpdateSlotItem *tmpSlotItem = 0;
48 nextUpdateSlot->incReader();
49 tmpSlotItem = mNextCacheSlotItemPointer.fetchAndStoreOrdered(nextUpdateSlot);
50 if (tmpSlotItem) {
51 tmpSlotItem->decReader();
52 }
53 return tmpSlotItem;
54 }
55
56
57
58 bool COccurrenceUnsatisfiableCacheReader::moveToNextSlot() {
59 if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
60
61 COccurrenceUnsatisfiableCacheUpdateSlotItem* nextSlotItem = mNextCacheSlotItemPointer.fetchAndStoreOrdered(nullptr);
62 if (nextSlotItem) {
63 if (cacheSlotItem) {
64 cacheSlotItem->decReader();
65 }
66 cacheSlotItem = nextSlotItem;
67 return true;
68 }
69 }
70 return false;
71 }
72
73
74
75 void COccurrenceUnsatisfiableCacheReader::incrementUnsatisfiableTestReset() {
76 while (incCacheEntriesLinker) {
77 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *tmpCacheEntry = incCacheEntriesLinker;
78 incCacheEntriesLinker = incCacheEntriesLinker->getNext();
79 memManCacheEntryList.release(tmpCacheEntry);
80 }
81 lastUnsatItems.clear();
82 }
83
84
85 bool COccurrenceUnsatisfiableCacheReader::incrementUnsatisfiableTest(CCacheValue *cacheValue, bool *continueTestingUseful) {
86 bool unsat = false;
87 incCacheEntriesLinker = incrementalUnsatisfiableTest(cacheValue,incCacheEntriesLinker,&unsat,continueTestingUseful);
88 return unsat;
89 }
90
91
92
93 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *COccurrenceUnsatisfiableCacheReader::incrementalUnsatisfiableTest(CCacheValue *cacheValue, CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *cacheEntries, bool *unsatisfiable, bool *continueTesting) {
94 if (!cacheEntries) {
95 cacheEntries = memManCacheEntryList.allocate()->init(cache->getPrimarCacheEntry());
96 }
97 qint64 updateSlot = 0;
98 if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
99 moveToNextSlot();
100 }
101 bool unsatisfiableFound = false;
102 bool continueTestingUseful = false;
103 if (cacheSlotItem) {
104 updateSlot = cacheSlotItem->getSlotIndex();
105
106 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *nextCacheEntries = 0;
107 qint64 itemTag = cacheValue->getTag();
108
109 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *linkIt = cacheEntries;
110 while (linkIt) {
111
112 if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
113 moveToNextSlot();
114 if (cacheSlotItem) {
115 updateSlot = cacheSlotItem->getSlotIndex();
116 }
117 }
118
119 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *linkNextIt = linkIt->getNext();
120 if (linkNextIt) {
121 linkNextIt->removePrev();
122 }
123 COccurrenceUnsatisfiableCacheEntry *cacheEntry = linkIt->getData();
124
125 qint64 cacheMax = cacheEntry->getMaxTag();
126 qint64 cacheMin = cacheEntry->getMinTag();
127
128 COccurrenceUnsatisfiableCacheEntriesHash *cacheHash = cacheEntry->getSlotCacheEntriesHash(updateSlot);
129
130 // test min and max
131 if (!cacheHash || itemTag > cacheMax) {
132 // cache entry is no longer needed
133 memManCacheEntryList.release(linkIt);
134 } else {
135 if (!cacheEntry->isSerialized()) {
136 // cache entry is needed, next round
137 nextCacheEntries = linkIt->insertNext(nextCacheEntries);
138 } else {
139 memManCacheEntryList.release(linkIt);
140 }
141
142 // test to add additional cache entries
143 if (cacheHash->contains(*cacheValue)) {
144 COccurrenceUnsatisfiableCacheEntry *nextAddingCacheEntry = cacheHash->value(*cacheValue);
145 if (nextAddingCacheEntry->isUnsatisfiableTermination()) {
146 unsatisfiableFound = true;
147 linkIt = linkNextIt;
148 if (nextAddingCacheEntry->getCacheTerminationValuesList()) {
149 lastUnsatItems = *nextAddingCacheEntry->getCacheTerminationValuesList();
150 }
151 break;
152 }
153 nextCacheEntries = memManCacheEntryList.allocate()->init(nextAddingCacheEntry,nextCacheEntries);
154 }
155 }
156 linkIt = linkNextIt;
157 }
158
159 while (linkIt) {
160 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *tmpCacheEntry = linkIt;
161 linkIt = linkIt->getNext();
162 memManCacheEntryList.release(tmpCacheEntry);
163 }
164
165 cacheEntries = nextCacheEntries;
166 nextCacheEntries = 0;
167 } else {
168 while (cacheEntries) {
169 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *tmpCacheEntry = cacheEntries;
170 cacheEntries = cacheEntries->getNext();
171 memManCacheEntryList.release(tmpCacheEntry);
172 }
173 cacheEntries = 0;
174 }
175 if (unsatisfiableFound) {
176 while (cacheEntries) {
177 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *tmpCacheEntry = cacheEntries;
178 cacheEntries = cacheEntries->getNext();
179 memManCacheEntryList.release(tmpCacheEntry);
180 }
181 cacheEntries = 0;
182 }
183 if (!unsatisfiableFound && cacheEntries) {
184 continueTestingUseful = true;
185 }
186
187 if (continueTesting) {
188 *continueTesting = continueTestingUseful;
189 }
190 if (unsatisfiable) {
191 *unsatisfiable = unsatisfiableFound;
192 }
193 return cacheEntries;
194 }
195
196
197
198 bool COccurrenceUnsatisfiableCacheReader::isUnsatisfiable(QVector<CCacheValue> &itemVec, qint64 count) {
199 return isUnsatisfiable(itemVec,count,0);
200 }
201
202 bool COccurrenceUnsatisfiableCacheReader::isUnsatisfiable(QVector<CCacheValue> &itemVec, qint64 count, QList<CCacheValue> *unsatisfiableItemList) {
203
204 bool unsatisfiable = false;
205
206 // list for cache entries
207 // TODO: use min and max from cache entries to make list smaller
208 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *cacheEntries = memManCacheEntryList.allocate()->init(cache->getPrimarCacheEntry());
209
210
211 qint64 firstIndex = 0;
212 qint64 lastIndex = count-1;
213
214 // make assumption that list is sorted
215 qint64 minItem = itemVec[0].getTag();
216 qint64 maxItem = itemVec[lastIndex].getTag();
217
218
219 qint64 updateSlot = 0;
220 if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
221 moveToNextSlot();
222 }
223 if (cacheSlotItem) {
224 updateSlot = cacheSlotItem->getSlotIndex();
225
226 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *nextCacheEntries = 0;
227
228
229 // TODO: Skip items which are not in cache
230 qint64 index = 0;
231 while (index < count && !unsatisfiable && cacheEntries) {
232 CCacheValue &item = itemVec[index++];
233 qint64 itemTag = item.getTag();
234
235 nextCacheEntries = 0;
236
237 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *linkIt = cacheEntries;
238 while (linkIt) {
239
240 if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
241 moveToNextSlot();
242 if (cacheSlotItem) {
243 updateSlot = cacheSlotItem->getSlotIndex();
244 }
245 }
246
247 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *linkNextIt = linkIt->getNext();
248 if (linkNextIt) {
249 linkNextIt->removePrev();
250 }
251 COccurrenceUnsatisfiableCacheEntry *cacheEntry = linkIt->getData();
252
253 qint64 cacheMax = cacheEntry->getMaxTag();
254 qint64 cacheMin = cacheEntry->getMinTag();
255
256 COccurrenceUnsatisfiableCacheEntriesHash *cacheHash = cacheEntry->getSlotCacheEntriesHash(updateSlot);
257
258 // test min and max
259 if (!cacheHash || cacheMin > maxItem || itemTag > cacheMax) {
260 // cache entry is no longer needed
261
262 memManCacheEntryList.release(linkIt);
263
264 } else {
265 // cache entry is needed, next round
266 nextCacheEntries = linkIt->insertNext(nextCacheEntries);
267
268
269
270 // test to add additional cache entries
271 if (cacheHash->contains(item)) {
272
273 COccurrenceUnsatisfiableCacheEntry *nextAddingCacheEntry = cacheHash->value(item);
274
275 if (nextAddingCacheEntry->isUnsatisfiableTermination()) {
276 unsatisfiable = true;
277 if (nextAddingCacheEntry->getCacheTerminationValuesList()) {
278 lastUnsatItems = *nextAddingCacheEntry->getCacheTerminationValuesList();
279 if (unsatisfiableItemList) {
280 *unsatisfiableItemList = *nextAddingCacheEntry->getCacheTerminationValuesList();
281 }
282 }
283 linkIt = linkNextIt;
284 break;
285 }
286
287 nextCacheEntries = memManCacheEntryList.allocate()->init(nextAddingCacheEntry,nextCacheEntries);
288 }
289
290 }
291
292 linkIt = linkNextIt;
293 }
294
295
296 while (linkIt) {
297 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *tmpCacheEntry = linkIt;
298 linkIt = linkIt->getNext();
299 memManCacheEntryList.release(tmpCacheEntry);
300 }
301
302 cacheEntries = nextCacheEntries;
303 nextCacheEntries = 0;
304 }
305
306
307 while (cacheEntries) {
308 CDblLinker<COccurrenceUnsatisfiableCacheEntry *> *tmpCacheEntry = cacheEntries;
309 cacheEntries = cacheEntries->getNext();
310 memManCacheEntryList.release(tmpCacheEntry);
311 }
312 }
313
314 if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
315 moveToNextSlot();
316 if (cacheSlotItem) {
317 updateSlot = cacheSlotItem->getSlotIndex();
318 }
319 }
320 return unsatisfiable;
321 }
322
323
324 QList<CCacheValue> COccurrenceUnsatisfiableCacheReader::getLastTestedUnsatisfiableItems() {
325 return lastUnsatItems;
326 }
327
328
329
330 QList<CCacheValue> COccurrenceUnsatisfiableCacheReader::getUnsatisfiableItems(QVector<CCacheValue> &itemVec, qint64 count) {
331 QList<CCacheValue> unsatList;
332 isUnsatisfiable(itemVec,count,&unsatList);
333 return unsatList;
334 }
335
336
337 CXLinker<CCacheValue*>* COccurrenceUnsatisfiableCacheReader::getUnsatisfiableItems(CXLinker<CCacheValue*>* cacheValueTestLinker, CMemoryAllocationManager* memMan) {
338 CXLinker<CCacheValue*>* unsatLinker = nullptr;
339
340
341
342 bool unsatisfiable = false;
343
344 // list for cache entries
345 // TODO: use min and max from cache entries to make list smaller
346 CXLinker<COccurrenceUnsatisfiableCacheEntry*>* cacheEntries = CObjectAllocator< CXLinker<COccurrenceUnsatisfiableCacheEntry*> >::allocateAndConstruct(memMan)->initLinker(cache->getPrimarCacheEntry());
347 //memManCacheEntryList.allocate()->init(cache->getPrimarCacheEntry());
348
349
350 CCacheValue* firstItem = cacheValueTestLinker->getData();
351 CCacheValue* lastItem = cacheValueTestLinker->getLastListLink()->getData();
352
353
354 CXLinker<CCacheValue*>* testCacheItemIt = cacheValueTestLinker;
355
356 // make assumption that list is sorted
357 qint64 minItem = firstItem->getTag();
358 qint64 maxItem = lastItem->getTag();
359
360
361 qint64 updateSlot = 0;
362 if (mNextCacheSlotItemPointer.fetchAndAddRelaxed(0) != nullptr) {
363 moveToNextSlot();
364 }
365 if (cacheSlotItem) {
366 updateSlot = cacheSlotItem->getSlotIndex();
367
368 CXLinker<COccurrenceUnsatisfiableCacheEntry *> *nextCacheEntries = nullptr;
369
370
371 while (testCacheItemIt && cacheEntries) {
372 CCacheValue* item = testCacheItemIt->getData();
373 qint64 itemTag = item->getTag();
374
375 nextCacheEntries = nullptr;
376
377 CXLinker<COccurrenceUnsatisfiableCacheEntry *> *cacheEntryIt = cacheEntries;
378 while (cacheEntryIt) {
379
380
381 CXLinker<COccurrenceUnsatisfiableCacheEntry *> *cacheEntryLinker = cacheEntryIt;
382 cacheEntryIt = cacheEntryIt->getNext();
383 cacheEntryLinker->clearNext();
384
385
386 COccurrenceUnsatisfiableCacheEntry *cacheEntry = cacheEntryLinker->getData();
387
388 qint64 cacheMax = cacheEntry->getMaxTag();
389 qint64 cacheMin = cacheEntry->getMinTag();
390
391 COccurrenceUnsatisfiableCacheEntriesHash *cacheHash = cacheEntry->getSlotCacheEntriesHash(updateSlot);
392
393 // test min and max
394 if (!cacheHash || cacheMin > maxItem || itemTag > cacheMax) {
395 // cache entry is no longer needed
396
397 } else {
398 // cache entry is needed, next round
399 nextCacheEntries = cacheEntryLinker->append(nextCacheEntries);
400
401
402 COccurrenceUnsatisfiableCacheEntry *nextAddingCacheEntry = cacheHash->value(*item,nullptr);
403
404 // test to add additional cache entries
405 if (nextAddingCacheEntry) {
406
407 if (nextAddingCacheEntry->isUnsatisfiableTermination()) {
408 unsatisfiable = true;
409 QList<CCacheValue>* unsatValList = nextAddingCacheEntry->getCacheTerminationValuesList();
410 if (unsatValList) {
411
412 CXLinker<CCacheValue*>* unsatCacheItemLinker = cacheValueTestLinker;
413 CXLinker<CCacheValue*>* lastUnsatCacheItemLinker = nullptr;
414 CXLinker<CCacheValue*>* firstUnsatCacheItemLinker = nullptr;
415 for (QList<CCacheValue>::const_iterator unsatItemIt = unsatValList->constBegin(), unsatItemItEnd = unsatValList->constEnd(); unsatItemIt != unsatItemItEnd; ++unsatItemIt) {
416 while (*unsatCacheItemLinker->getData() != *unsatItemIt) {
417 unsatCacheItemLinker = unsatCacheItemLinker->getNext();
418 }
419 if (!firstUnsatCacheItemLinker) {
420 firstUnsatCacheItemLinker = unsatCacheItemLinker;
421 } else {
422 lastUnsatCacheItemLinker->setNext(unsatCacheItemLinker);
423 }
424 lastUnsatCacheItemLinker = unsatCacheItemLinker;
425 }
426 lastUnsatCacheItemLinker->clearNext();
427 return firstUnsatCacheItemLinker;
428 } else {
429 return cacheValueTestLinker;
430 }
431 }
432
433 nextCacheEntries = CObjectAllocator< CXLinker<COccurrenceUnsatisfiableCacheEntry*> >::allocateAndConstruct(memMan)->initLinker(nextAddingCacheEntry,nextCacheEntries);
434 }
435
436 }
437
438 }
439
440 cacheEntries = nextCacheEntries;
441 nextCacheEntries = nullptr;
442
443 testCacheItemIt = testCacheItemIt->getNext();
444 }
445 }
446
447 return nullptr;
448 }
449
450 cint64 COccurrenceUnsatisfiableCacheReader::getCurrentCachingTag() {
451 return cache->getCurrentCachingTag();
452 }
453
454 }; // end namespace Cache
455
456 }; // end namespace Kernel
457
458 }; // end namespace Reasoner
459
460 }; // end namespace Konclude