1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 // CegoAVLIndexCursor.cc
4 // ------------------
5 // Cego index cursor class implementation
6 //
7 // Design and Implementation by Bjoern Lemke
8 //
9 // (C)opyright 2000-2019 Bjoern Lemke
10 //
11 // IMPLEMENTATION MODULE
12 //
13 // Class: CegoAVLIndexCursor
14 //
15 // Description: Index cursors are used for reading tables based on an available index
16 // for the given attribute condition
17 //
18 // Status: CLEAN
19 //
20 ///////////////////////////////////////////////////////////////////////////////
21
22 // cego includes
23 #include "CegoAVLIndexCursor.h"
24 #include "CegoTupleState.h"
25
26 #include <string.h>
27 #include <stdlib.h>
28
CegoAVLIndexCursor(CegoTableManager * pTM,int tabSetId,const Chain & indexName,CegoObject::ObjectType type,CegoAttrCond * pAttrCond,bool ignoreTouched,bool readUncommitted)29 CegoAVLIndexCursor::CegoAVLIndexCursor(CegoTableManager *pTM, int tabSetId, const Chain& indexName, CegoObject::ObjectType type, CegoAttrCond* pAttrCond, bool ignoreTouched, bool readUncommitted)
30 {
31 _pTM = pTM;
32 _indexName = indexName;
33 _type = type;
34 _pAttrCond = pAttrCond;
35
36 _tabSetId = tabSetId;
37 _ignoreTouched = ignoreTouched;
38 _readUncommitted = readUncommitted;
39 _cursorCached = false;
40 _lockId = 0;
41 }
42
~CegoAVLIndexCursor()43 CegoAVLIndexCursor::~CegoAVLIndexCursor()
44 {
45 abort();
46 _pTM->releaseDataPtrUnlocked(_rootPage, false);
47 _rootPage = CegoBufferPage();
48 }
49
getFirst(ListT<CegoField> & fl,CegoDataPointer & dp)50 bool CegoAVLIndexCursor::getFirst(ListT<CegoField>& fl, CegoDataPointer& dp)
51 {
52 if ( fl.isEmpty() )
53 {
54 throw Exception(EXLOC, "Empty field list");
55 }
56
57 if ( _cursorCached == false )
58 {
59 CegoTableObject ioe;
60
61 _pTM->getObject(_tabSetId, _indexName, _type, ioe);
62
63 _idxSchema = ioe.getSchema();
64
65 Chain tabName = ioe.getTabName();
66
67 CegoObjectCursor* pC = _pTM->getObjectCursor(_tabSetId, tabName, _indexName, _type);
68
69 _cachedPointer = (char*)pC->getFirst(_cachedLen, _rdp);
70 pC->abort();
71 delete pC;
72
73 _pTM->claimDataPtrUnlocked(_tabSetId, CegoBufferPool::SYNC, _rdp, _cachedPointer, _cachedLen, _rootPage);
74
75 _cursorCached = true;
76
77 }
78
79 // cout << "Read Locking " << _rdp.getFileId() << " " << _rdp.getPageId() << endl;
80 if ( _lockId == 0 )
81 _lockId = _pTM->getLockHandler()->lockData(CegoObject::BTREE, _rdp.getPageId(), CegoLockHandler::READ);
82
83
84 // get root entry
85 int len = _cachedLen;
86 char* p = _cachedPointer;
87
88 if ( p == 0 )
89 {
90 _eoc = true;
91 return false;
92 }
93
94 _ie.setPtr(p, len);
95
96 _idp = _ie.getRightBranch();
97
98 CegoDataPointer nil;
99 if (_idp == nil)
100 {
101 _eoc = true;
102 return false;
103 }
104
105 _eoc = false;
106
107 _rootPassed = false;
108
109 bool found = false;
110
111 if (_pAttrCond)
112 {
113
114 if ( _pAttrCond->getPrimaryCompMode() == CegoAttrComp::BTWN )
115 _pAttrCond->setPrimaryComparison( MORE_EQUAL_THAN );
116
117 switch ( _pAttrCond->getPrimaryComparison() )
118 {
119 case NOT_EQUAL:
120 case LESS_THAN:
121 case LESS_EQUAL_THAN:
122
123 {
124 // go to the beginning
125
126 _pTM->claimDataPtrUnlocked(_tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
127
128 _ie.setPtr(p, len);
129
130 while ( _ie.getLeftBranch() != nil)
131 {
132
133 // Traversing to left
134 _idp = _ie.getLeftBranch();
135
136 _pTM->releaseDataPtrUnlocked(_currentPage, false);
137 _pTM->claimDataPtrUnlocked(_tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
138
139 _ie.setPtr(p, len);
140 }
141
142 CegoComparison comp = compValue(_ie.getIdxPtr());
143
144 if ( comp == LESS_THAN
145 || ( comp == EQUAL && _pAttrCond->getPrimaryComparison() == LESS_EQUAL_THAN )
146 || ( comp != EQUAL && _pAttrCond->getPrimaryComparison() == NOT_EQUAL ) )
147 {
148 found = true;
149 }
150 else if ( _pAttrCond->getPrimaryComparison() == NOT_EQUAL )
151 {
152 return getNext(fl, dp);
153 }
154
155 break;
156 }
157 case MORE_THAN:
158 {
159
160 // go to the smallest leaf
161
162 _pTM->claimDataPtrUnlocked(_tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
163
164 _ie.setPtr(p, len);
165
166 while ( ! found )
167 {
168
169 CegoDataPointer idp;
170
171 CegoComparison comp = compValue( _ie.getIdxPtr());
172
173 if ( comp == LESS_THAN || comp == EQUAL )
174 {
175 idp = _ie.getRightBranch();
176
177 if (_ie.getParent() == _rdp )
178 {
179 _rootPassed = true;
180 }
181
182 }
183 else if ( comp == MORE_THAN )
184 {
185 idp = _ie.getLeftBranch();
186
187 if ( idp == nil )
188 found = true;
189 }
190 else
191 {
192 return getNext(fl, dp);
193 }
194
195
196 if ( idp == nil && ! found )
197 {
198 return getNext(fl, dp);
199 }
200 else if ( ! found )
201 {
202 _idp = idp;
203 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, idp, p, len, _currentPage);
204 _ie.setPtr(p, len);
205 }
206 }
207 break;
208 }
209 case EQUAL:
210 case MORE_EQUAL_THAN:
211 {
212
213 // go to the smallest leaf
214
215 _pTM->claimDataPtrUnlocked(_tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
216
217 _ie.setPtr(p, len);
218
219 while ( ! found )
220 {
221
222 CegoDataPointer idp = _idp;
223
224 CegoComparison comp = compValue(_ie.getIdxPtr());
225
226 if ( comp == LESS_THAN )
227 {
228 idp = _ie.getRightBranch();
229
230 if (_ie.getParent() == _rdp )
231 {
232 _rootPassed = true;
233 }
234 }
235 else if ( comp == EQUAL )
236 {
237 idp = _ie.getLeftBranch();
238
239 if ( idp == nil )
240 found = true;
241 }
242 else if ( comp == MORE_THAN )
243 {
244 idp = _ie.getLeftBranch();
245 }
246
247 if ( idp == nil && ! found )
248 {
249 return getNext(fl, dp);
250 }
251 else if ( ! found )
252 {
253 _idp = idp;
254 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, idp, p, len, _currentPage);
255 _ie.setPtr(p, len);
256
257 }
258 }
259 break;
260 }
261
262 }
263 }
264 else
265 {
266 // go to the beginning
267
268 _pTM->claimDataPtrUnlocked(_tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
269
270 _ie.setPtr(p, len);
271
272 while ( _ie.getLeftBranch() != nil)
273 {
274 _idp = _ie.getLeftBranch();
275 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
276 _ie.setPtr(p, len);
277 }
278
279 found = true;
280 }
281
282
283 if (found )
284 {
285
286 char* p;
287 int len;
288
289 dp = _ie.getData();
290
291
292 _pTM->releaseDataPtrUnlocked(_dataPage, false);
293 _pTM->claimDataPtrUnlocked(_tabSetId, CegoBufferPool::SYNC, dp, p, len, _dataPage);
294
295 // skipping tid
296
297 unsigned long long tid;
298 unsigned long long tastep;
299 CegoTupleState ts;
300
301 int toff = _qh.decodeTupleHeader(tid, tastep, ts, p);
302
303 char* tp = p + toff;
304 int tlen = len - toff;
305
306 if (tid != 0)
307 {
308 if ( _ignoreTouched )
309 {
310 if ( ts == INSERTED
311 && tid == _pTM->getTID(_tabSetId)
312 && tastep < _pTM->getTAStep(_tabSetId) )
313 {
314 _qh.decodeFVL(fl, tp, tlen);
315 return true;
316 }
317 else
318 {
319 return getNext(fl,dp);
320 }
321 }
322 else
323 {
324
325 if ( ( _readUncommitted == true
326 && ts == INSERTED )
327 || ( _readUncommitted == false
328 && (( ts == INSERTED && tid == _pTM->getTID(_tabSetId))
329 || ( ts == DELETED && tid != _pTM->getTID(_tabSetId)))))
330 {
331 _qh.decodeFVL(fl, tp, tlen);
332 return true;
333 }
334 else
335 {
336 return getNext(fl,dp);
337 }
338 }
339 }
340 else
341 {
342 _qh.decodeFVL(fl, tp, tlen);
343 return true;
344 }
345 }
346 return false;
347 }
348
getNext(ListT<CegoField> & fl,CegoDataPointer & dp)349 bool CegoAVLIndexCursor::getNext(ListT<CegoField>& fl, CegoDataPointer& dp)
350 {
351 if ( _eoc )
352 return false;
353
354 if ( fl.isEmpty() )
355 {
356 throw Exception(EXLOC, "Empty field list");
357 }
358
359 do {
360
361 CegoDataPointer nil;
362
363 char* p;
364 int len;
365
366 bool attrMatch = false;
367
368 if (_ie.getParent() == _rdp )
369 {
370 _rootPassed = true;
371 }
372
373 if (_ie.getRightBranch() != nil)
374 {
375
376 _idp = _ie.getRightBranch();
377 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
378
379 _ie.setPtr(p, len);
380
381 while ( _ie.getLeftBranch() != nil)
382 {
383 _idp = _ie.getLeftBranch();
384 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
385 _ie.setPtr(p, len);
386 }
387 }
388 else
389 {
390 // searching appropriate parent
391
392 if ( _ie.getParent() == _rdp && _rootPassed )
393 {
394
395 _pTM->releaseDataPtrUnlocked(_currentPage, false);
396 _currentPage = CegoBufferPage();
397 _eoc = true;
398 return false;
399 }
400
401 CegoDataPointer pdp = _ie.getParent();
402
403 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, pdp, p, len, _currentPage);
404
405 _ie.setPtr(p, len);
406
407 bool entryFound = false;
408 while ( ! entryFound )
409 {
410
411 if (_ie.getLeftBranch() == _idp)
412 {
413 _idp = pdp;
414 entryFound = true;
415 }
416 else
417 {
418
419 if ( _ie.getParent() == _rdp )
420 {
421 if ( _rootPassed )
422 {
423 abort();
424 _eoc = true;
425 return false;
426 }
427 else
428 {
429
430 _idp = _ie.getRightBranch();
431 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
432 _ie.setPtr(p, len);
433
434 while ( _ie.getLeftBranch() != nil)
435 {
436 _idp = _ie.getLeftBranch();
437 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, _idp, p, len, _currentPage);
438 _ie.setPtr(p, len);
439 }
440 entryFound = true;
441 }
442 }
443 else
444 {
445 _idp = pdp;
446
447 pdp = _ie.getParent();
448 _pTM->releaseAndClaimDataPtrUnlocked(_currentPage, false, _tabSetId, CegoBufferPool::SYNC, pdp, p, len, _currentPage);
449 _ie.setPtr(p, len);
450 }
451 }
452 }
453 }
454
455 if (_pAttrCond)
456 {
457
458 char *p = _ie.getIdxPtr();
459 CegoComparison comp;
460 comp = compValue(p);
461
462 if ( _pAttrCond->getPrimaryCompMode() == CegoAttrComp::BTWN )
463 {
464 _pAttrCond->setPrimaryComparison(LESS_EQUAL_THAN);
465 }
466
467 switch (_pAttrCond->getPrimaryComparison())
468 {
469
470 case EQUAL:
471 {
472 switch (comp)
473 {
474 case EQUAL:
475 attrMatch=true;
476 break;
477 case LESS_THAN:
478 case MORE_THAN:
479 case LESS_EQUAL_THAN:
480 case MORE_EQUAL_THAN:
481 case NOT_EQUAL:
482 break;
483 }
484 break;
485 }
486 case NOT_EQUAL:
487 {
488 switch (comp)
489 {
490 case LESS_THAN:
491 attrMatch=true;
492 break;
493 case MORE_THAN:
494 attrMatch=true;
495 break;
496 case EQUAL:
497 return getNext(fl, dp);
498 case LESS_EQUAL_THAN:
499 case MORE_EQUAL_THAN:
500 case NOT_EQUAL:
501 break;
502 }
503 break;
504 }
505 case LESS_THAN:
506 {
507 switch (comp)
508 {
509 case LESS_THAN:
510 attrMatch=true;
511 break;
512 case EQUAL:
513 case MORE_THAN:
514 case LESS_EQUAL_THAN:
515 case MORE_EQUAL_THAN:
516 case NOT_EQUAL:
517 break;
518 }
519 break;
520 }
521 case MORE_THAN:
522 {
523 switch (comp)
524 {
525 case MORE_THAN:
526 attrMatch=true;
527 break;
528 case EQUAL:
529 case LESS_THAN:
530 case LESS_EQUAL_THAN:
531 case MORE_EQUAL_THAN:
532 case NOT_EQUAL:
533 break;
534 }
535 break;
536 }
537 case LESS_EQUAL_THAN:
538 {
539 switch (comp)
540 {
541 case EQUAL:
542 attrMatch=true;
543 break;
544 case LESS_THAN:
545 attrMatch=true;
546 break;
547 case MORE_THAN:
548 case LESS_EQUAL_THAN:
549 case MORE_EQUAL_THAN:
550 case NOT_EQUAL:
551 break;
552 }
553 break;
554 }
555
556 case MORE_EQUAL_THAN:
557 {
558 switch (comp)
559 {
560 case EQUAL:
561 attrMatch=true;
562 break;
563 case MORE_THAN:
564 attrMatch=true;
565 break;
566 case LESS_THAN:
567 case LESS_EQUAL_THAN:
568 case MORE_EQUAL_THAN:
569 case NOT_EQUAL:
570 break;
571 }
572 break;
573 }
574 }
575 }
576 else
577 {
578 attrMatch = true;
579 }
580
581 if ( attrMatch )
582 {
583
584 char* p;
585 int len;
586
587 dp = _ie.getData();
588
589 _pTM->releaseDataPtrUnlocked(_dataPage, false);
590 _pTM->claimDataPtrUnlocked(_tabSetId, CegoBufferPool::SYNC, dp, p, len, _dataPage);
591
592 // skipping tid
593
594 unsigned long long tid;
595 unsigned long long tastep;
596 CegoTupleState ts;
597
598 int toff = _qh.decodeTupleHeader(tid, tastep, ts, p);
599
600 char* tp = p + toff;
601 int tlen = len - toff;
602
603 if (tid != 0)
604 {
605 if ( _ignoreTouched == true )
606 {
607 if ( ts == INSERTED
608 && tid == _pTM->getTID(_tabSetId)
609 && tastep < _pTM->getTAStep(_tabSetId) )
610 {
611 _qh.decodeFVL(fl, tp, tlen);
612 return true;
613 }
614 else
615 {
616 // ignore entry
617 }
618 }
619 else
620 {
621
622 if ( ( _readUncommitted == true
623 && ts == INSERTED )
624 || ( _readUncommitted == false
625 && (( ts == INSERTED && tid == _pTM->getTID(_tabSetId))
626 || ( ts == DELETED && tid != _pTM->getTID(_tabSetId)))))
627 {
628 _qh.decodeFVL(fl, tp, tlen);
629 return true;
630 }
631 else
632 {
633 // ignore entry
634 }
635 }
636 }
637 else
638 {
639 _qh.decodeFVL(fl, tp, tlen);
640 return true;
641 }
642 }
643 else
644 {
645 abort();
646 _eoc = true;
647 return false;
648 }
649 } while (1);
650 }
651
abort()652 void CegoAVLIndexCursor::abort()
653 {
654 _pTM->releaseDataPtrUnlocked(_currentPage, false);
655 _currentPage = CegoBufferPage();
656
657 _pTM->releaseDataPtrUnlocked(_dataPage, false);
658 _dataPage = CegoBufferPage();
659
660 if ( _lockId )
661 {
662 _pTM->getLockHandler()->unlockData(CegoObject::BTREE, _lockId);
663 _lockId = 0;
664 }
665 }
666
reset()667 void CegoAVLIndexCursor::reset()
668 {
669 abort();
670 }
671
compValue(char * idxVal)672 CegoComparison CegoAVLIndexCursor::compValue(char* idxVal)
673 {
674 CegoField* pF = _idxSchema.First();
675
676 while ( pF )
677 {
678
679 int flen;
680 memcpy(&flen, idxVal, sizeof(int));
681
682 idxVal += sizeof(int);
683
684 CegoFieldValue fv;
685 fv.setLength(flen);
686 fv.setValue(idxVal);
687 if ( flen > 0 )
688 fv.setType(pF->getType());
689
690 CegoAttrComp* pAC = _pAttrCond->getAttrCompSet().First();
691
692 while ( pAC )
693 {
694 if ( (Chain)pAC->getAttrName() == (Chain)pF->getAttrName() )
695 {
696 if ( fv < pAC->getFieldValue() )
697 {
698 return LESS_THAN;
699 }
700
701 if ( pAC->getCompMode() == CegoAttrComp::VAL
702 || pAC->getCompMode() == CegoAttrComp::ATTR )
703 {
704 if ( fv > pAC->getFieldValue() )
705 {
706 return MORE_THAN;
707 }
708 }
709 else if ( pAC->getCompMode() == CegoAttrComp::BTWN )
710 {
711 if ( fv > pAC->getFieldValue2() )
712 {
713 return MORE_THAN;
714 }
715 }
716 }
717 pAC = _pAttrCond->getAttrCompSet().Next();
718 }
719
720 idxVal += flen;
721
722 pF = _idxSchema.Next();
723 }
724
725 return EQUAL;
726 }
727