1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 // CegoAVLIndexManager.cc
4 // -------------------
5 // Cego index manager 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: CegoAVLIndexManager
14 //
15 // Description:
16 //
17 // Status: CLEAN
18 //
19 ///////////////////////////////////////////////////////////////////////////////
20
21 // base includes
22 #include <lfcbase/Exception.h>
23
24 // cego includes
25 #include "CegoAVLIndexManager.h"
26 #include "CegoLockHandler.h"
27 #include "CegoAVLIndexEntry.h"
28 #include "CegoTupleState.h"
29
30 #include <string.h>
31 #include <stdlib.h>
32
CegoAVLIndexManager(CegoTableManager * pTM)33 CegoAVLIndexManager::CegoAVLIndexManager(CegoTableManager *pTM)
34 {
35 _pLogger = pTM->getDBMng();
36 _modId = pTM->getDBMng()->getModId("CegoAVLIndexManager");
37 _pTM = pTM;
38 _lockId = 0;
39 }
40
~CegoAVLIndexManager()41 CegoAVLIndexManager::~CegoAVLIndexManager()
42 {
43 if (_lockId)
44 _pTM->getLockHandler()->unlockData(CegoObject::BTREE, _lockId);
45 }
46
insertNativeIndexTable(CegoTableObject & ioe,const CegoDataPointer & sysEntry,const CegoDataPointer & dp,char * idxPtr,int idxLen,unsigned long long tid,bool insertAtLastPage,CegoDataPointer & ritp)47 void CegoAVLIndexManager::insertNativeIndexTable(CegoTableObject& ioe,
48 const CegoDataPointer& sysEntry,
49 const CegoDataPointer& dp,
50 char* idxPtr,
51 int idxLen,
52 unsigned long long tid,
53 bool insertAtLastPage,
54 CegoDataPointer& ritp)
55 {
56 int tabSetId = ioe.getTabSetId();
57 Chain indexName = ioe.getName();
58 Chain tabName = ioe.getTabName();
59
60 CegoObject::ObjectType idxType = ioe.getType();
61 ListT<CegoField> schema = ioe.getSchema();
62
63 CegoObjectCursor* pC = _pTM->getObjectCursor(tabSetId, tabName, indexName, idxType);
64
65 if ( ! pC )
66 {
67 Chain msg = "Cannot get cursor for <" + indexName + ">";
68 throw Exception(EXLOC, msg);
69 }
70
71 CegoDataPointer rdp;
72 char* p;
73 int len;
74
75 p = (char*)pC->getFirst(len, rdp);
76
77 // root datapointer must not be zero
78 if ( p == 0 )
79 {
80 pC->abort();
81 delete pC;
82 throw Exception(EXLOC, "Missing Index Anchor");
83 }
84
85 // cout << "Write Locking " << rdp.getFileId() << " " << rdp.getPageId() << endl;
86 _lockId = _pTM->getLockHandler()->lockData(CegoObject::BTREE, rdp.getPageId(), CegoLockHandler::WRITE);
87
88 CegoAVLIndexEntry base;
89 base.setPtr(p, len);
90
91 CegoDataPointer nil;
92
93 // is this the first entry ?
94 if ( base.getRightBranch() == nil )
95 {
96 CegoAVLIndexEntry nie;
97
98 nie.initEntry(dp, idxPtr, idxLen);
99 nie.setParent(rdp);
100 nie.setHeight(1);
101
102 CegoDataPointer dp;
103
104 try {
105
106 CegoDataPointer nil;
107 if ( sysEntry == nil )
108 {
109 dp = _pTM->insertData(ioe, (char*)nie.getPtr(), nie.getLen(), insertAtLastPage);
110 }
111 else
112 {
113 dp = _pTM->insertData(sysEntry, ioe, (char*)nie.getPtr(), nie.getLen(), insertAtLastPage);
114 }
115
116 }
117 catch ( Exception e )
118 {
119 pC->abort();
120 delete pC;
121 throw Exception(EXLOC, "Cannot insert index", e);
122 }
123
124 base.setRightBranch(dp);
125
126 ritp = rdp; // *pTP;
127
128 pC->abort();
129 delete pC;
130
131 }
132 else
133 {
134 ritp = rdp; // base.getRightBranch();
135
136 pC->abort();
137 delete pC;
138
139 bool isUnique = false;
140
141 if ( idxType == CegoObject::UAVLTREE || idxType == CegoObject::PAVLTREE )
142 isUnique = true;
143
144 insertIndexTable(ioe, sysEntry, ritp, isUnique, dp, idxPtr, idxLen, tid, insertAtLastPage);
145
146 }
147
148 if ( _lockId )
149 {
150 _pTM->getLockHandler()->unlockData(CegoObject::BTREE, _lockId);
151 _lockId = 0;
152 }
153 }
154
insertIndexTable(CegoTableObject & ioe,const CegoDataPointer & sysEntry,const CegoDataPointer & ritp,bool isUnique,const CegoDataPointer & dp,char * idxPtr,int idxLen,unsigned long long tid,bool insertAtLastPage,bool allowWrite)155 void CegoAVLIndexManager::insertIndexTable(CegoTableObject& ioe,
156 const CegoDataPointer& sysEntry,
157 const CegoDataPointer& ritp,
158 bool isUnique,
159 const CegoDataPointer& dp,
160 char* idxPtr,
161 int idxLen,
162 unsigned long long tid,
163 bool insertAtLastPage,
164 bool allowWrite)
165 {
166 if ( _lockId == 0 )
167 _lockId = _pTM->getLockHandler()->lockData(CegoObject::BTREE, ritp.getPageId(), CegoLockHandler::WRITE);
168
169 int tabSetId = ioe.getTabSetId();
170 ListT<CegoField> schema = ioe.getSchema();
171
172 char* p;
173 int len;
174
175 CegoBufferPool::FixMode fixMode;
176
177 if ( allowWrite )
178 fixMode = CegoBufferPool::NOSYNC;
179 else
180 fixMode = CegoBufferPool::SYNC;
181
182 CegoBufferPage rootPage;
183 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ritp, p, len, rootPage);
184
185 CegoAVLIndexEntry base;
186 base.setPtr(p, len);
187
188 CegoDataPointer itp = base.getRightBranch();
189
190 CegoBufferPage pageIE;
191 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
192
193 CegoDataPointer ptp;
194
195 bool inserted = false;
196 bool treatBalance = true;
197
198 CegoAVLIndexEntry ie;
199
200 int level = 0;
201
202 while ( ! inserted )
203 {
204
205 ie.setPtr(p, len);
206 bool leftBranch = false;
207
208 TupleOrder v = compIndexValue(schema, idxPtr, ie.getIdxPtr());
209
210 if ( v == EQU_NULL )
211 {
212 if ( ALLOW_UNIQUE_NULL == true )
213 v = LT;
214 else
215 v = EQU;
216 }
217
218 if ( v == LT || ( v == EQU && ! isUnique ) )
219 {
220 leftBranch = true;
221 ptp = itp;
222 itp = ie.getLeftBranch();
223 }
224 else if ( v == GT )
225 {
226 leftBranch = false;
227 ptp = itp;
228 itp = ie.getRightBranch();
229 }
230 else
231 {
232 // key maybe already exists
233
234 if ( tid != 0 )
235 {
236
237 // the key may be duplictate if an update operation occurs ( forced transaction )
238 // in this case we allow double entries ( cleanup by commit )
239
240 CegoBufferPage dataPage;
241 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ie.getData(), p, len, dataPage);
242
243 // skipping tid
244 unsigned long long dataTid; // = *(unsigned long long*)p;
245 unsigned long long tastep;
246 CegoTupleState ts;
247
248 CegoQueryHelper::decodeTupleHeader(dataTid, tastep, ts, p);
249
250 _pTM->releaseDataPtrUnlocked(dataPage, false);
251
252 if ( tid == dataTid && ( ts == DELETED || ts == OBSOLETE ))
253 {
254 leftBranch = true;
255 ptp = itp;
256 itp = ie.getLeftBranch();
257 }
258 else
259 {
260 _pTM->releaseDataPtrUnlocked(rootPage, false);
261 _pTM->releaseDataPtrUnlocked(pageIE, false);
262
263 throw Exception(EXLOC, Chain("Duplicate index key on unique index ") + ioe.getName() );
264
265 }
266 }
267 else
268 {
269
270 _pTM->releaseDataPtrUnlocked(rootPage, false);
271 _pTM->releaseDataPtrUnlocked(pageIE, false);
272
273 throw Exception(EXLOC, Chain("Duplicate index key on unique index ") + ioe.getName() );
274 }
275 }
276
277 level++;
278
279 if (itp.getOffset() == 0)
280 {
281
282 CegoAVLIndexEntry nie;
283 nie.initEntry(dp, idxPtr, idxLen);
284 nie.setParent(ptp);
285 nie.setHeight(1);
286
287 CegoDataPointer dp;
288 try {
289
290 CegoDataPointer nil;
291 if ( sysEntry == nil )
292 {
293 dp = _pTM->insertData(ioe, (char*)nie.getPtr(), nie.getLen(), insertAtLastPage, allowWrite);
294 }
295 else
296 {
297 dp = _pTM->insertData(sysEntry, ioe, (char*)nie.getPtr(), nie.getLen(), insertAtLastPage, allowWrite);
298 }
299
300 }
301 catch ( Exception e )
302 {
303 _pTM->releaseDataPtrUnlocked(pageIE, false);
304 _pTM->releaseDataPtrUnlocked(rootPage, false);
305 throw e;
306 }
307
308 inserted = true;
309
310 if (leftBranch)
311 {
312
313 ie.setLeftBranch(dp);
314 if (ie.getHeight() == 1 )
315 {
316 ie.setHeight(2);
317 treatBalance=true;
318 }
319 else
320 {
321 treatBalance=false;
322 }
323 }
324 else
325 {
326
327 ie.setRightBranch(dp);
328
329 if (ie.getHeight() == 1)
330 {
331 ie.setHeight(2);
332 treatBalance=true;
333 }
334 else
335 {
336 treatBalance=false;
337 }
338 }
339 }
340 else
341 {
342 if ( pageIE.isFixed() )
343 _pTM->releaseDataPtrUnlocked(pageIE, true);
344 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
345
346 }
347 }
348
349 if ( level == 1 )
350 {
351 // no balance on tree level 1
352 _pTM->releaseDataPtrUnlocked(rootPage, true);
353
354 if (pageIE.isFixed())
355 _pTM->releaseDataPtrUnlocked(pageIE, true);
356
357
358 if ( _lockId )
359 {
360 _pTM->getLockHandler()->unlockData(CegoObject::BTREE, _lockId);
361 _lockId = 0;
362 }
363
364 return;
365 }
366
367 // skip back
368 itp = ptp;
369 ptp = ie.getParent();
370
371 CegoBufferPage pagePE;
372 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
373
374 CegoAVLIndexEntry pe;
375 pe.setPtr(p, len);
376
377 while ( treatBalance && level > 1 )
378 {
379 char leftHeight, rightHeight;
380 getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);
381
382 if ( pe.getRightBranch() == itp )
383 {
384 if ( rightHeight - leftHeight == 1 )
385 {
386 pe.setHeight(rightHeight + 1);
387
388 if ( pageIE.isFixed() )
389 {
390 _pTM->releaseDataPtrUnlocked(pageIE, true);
391 }
392
393 ie = pe;
394 pageIE = pagePE;
395 itp = ptp;
396
397 ptp = ie.getParent();
398
399 if ( ptp.getOffset() )
400 {
401 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
402 pe.setPtr(p, len);
403 }
404 }
405 else if ( leftHeight == rightHeight )
406 {
407 if ( leftHeight != pe.getHeight() )
408 {
409 pe.setHeight(leftHeight + 1);
410 }
411 else
412 {
413 treatBalance = false;
414 }
415 }
416 else // if (leftHeight < rightHeight)
417 {
418 char subLeftHeight, subRightHeight;
419 getSubTreeHeight(tabSetId, fixMode, ie, subLeftHeight, subRightHeight);
420
421 if ( subLeftHeight < subRightHeight )
422 {
423 rotateRR(tabSetId, ptp, fixMode);
424 }
425 else
426 {
427 rotateRL(tabSetId, ptp, fixMode);
428 }
429 treatBalance = false;
430 }
431 }
432 else
433 {
434 if ( leftHeight - rightHeight == 1 )
435 {
436 pe.setHeight(leftHeight + 1);
437
438 if ( pageIE.isFixed() )
439 {
440 _pTM->releaseDataPtrUnlocked(pageIE, true);
441 }
442
443 pageIE = pagePE;
444 ie = pe;
445 itp = ptp;
446
447 ptp = ie.getParent();
448
449 if ( ptp.getOffset() )
450 {
451 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
452 pe.setPtr(p, len);
453 }
454 }
455 else if ( leftHeight == rightHeight )
456 {
457 if ( leftHeight != pe.getHeight() )
458 {
459 pe.setHeight(leftHeight + 1);
460 }
461 else
462 {
463 treatBalance = false;
464 }
465 }
466 else // if ( leftHeight > rightHeight )
467 {
468 char subLeftHeight, subRightHeight;
469 getSubTreeHeight(tabSetId, fixMode, ie, subLeftHeight, subRightHeight);
470
471 if ( subLeftHeight > subRightHeight )
472 {
473 rotateLL(tabSetId, ptp, fixMode);
474 }
475 else
476 {
477 rotateLR(tabSetId, ptp, fixMode);
478 }
479 treatBalance = false;
480 }
481 }
482 level--;
483 }
484
485 if ( pagePE.isFixed() )
486 _pTM->releaseDataPtrUnlocked(pagePE, true);
487 if ( pageIE.isFixed() )
488 _pTM->releaseDataPtrUnlocked(pageIE, true);
489 if ( rootPage.isFixed() )
490 _pTM->releaseDataPtrUnlocked(rootPage, true);
491
492 if ( _lockId )
493 {
494 _pTM->getLockHandler()->unlockData(CegoObject::BTREE, _lockId);
495 _lockId = 0;
496 }
497 }
498
getSubTreeHeight(int tabSetId,CegoBufferPool::FixMode fixMode,const CegoAVLIndexEntry & pe,char & leftHeight,char & rightHeight)499 void CegoAVLIndexManager::getSubTreeHeight(int tabSetId, CegoBufferPool::FixMode fixMode, const CegoAVLIndexEntry& pe, char& leftHeight, char& rightHeight)
500 {
501 char* p;
502 int len;
503 CegoDataPointer nil;
504
505 CegoDataPointer ldp = pe.getLeftBranch();
506 if ( ldp == nil )
507 {
508 leftHeight=0;
509 }
510 else
511 {
512 CegoBufferPage pageLE;
513 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ldp, p, len, pageLE);
514 CegoAVLIndexEntry li;
515 li.setPtr(p, len);
516 leftHeight = li.getHeight();
517 if ( pageLE.isFixed() )
518 _pTM->releaseDataPtrUnlocked(pageLE, false);
519 }
520
521 CegoDataPointer rdp = pe.getRightBranch();
522 if ( rdp == nil )
523 {
524 rightHeight=0;
525 }
526 else
527 {
528
529 CegoBufferPage pageRE;
530 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, rdp, p, len, pageRE);
531 CegoAVLIndexEntry ri;
532 ri.setPtr(p, len);
533 rightHeight = ri.getHeight();
534 if ( pageRE.isFixed() )
535 _pTM->releaseDataPtrUnlocked(pageRE, false);
536 }
537 return;
538 }
539
deleteIndexTable(int tabSetId,const Chain & tableName,CegoObject::ObjectType tabType,const Chain & indexName,CegoObject::ObjectType idxType,const ListT<CegoField> & schema,const CegoDataPointer & ddp,char * idxPtr,int idxLen,bool allowWrite)540 void CegoAVLIndexManager::deleteIndexTable(int tabSetId, const Chain& tableName, CegoObject::ObjectType tabType, const Chain& indexName, CegoObject::ObjectType idxType, const ListT<CegoField>& schema, const CegoDataPointer& ddp, char* idxPtr, int idxLen, bool allowWrite)
541 {
542
543 CegoBufferPool::FixMode fixMode;
544
545 if ( allowWrite )
546 fixMode = CegoBufferPool::NOSYNC;
547 else
548 fixMode = CegoBufferPool::SYNC;
549
550
551 ///////// get entry pointer //////////////
552
553 CegoObjectCursor* pC = _pTM->getObjectCursor(tabSetId, tableName, indexName, idxType);
554
555 if ( ! pC )
556 {
557 Chain msg = "Cannot get cursor for index <" + indexName + ">";
558 throw Exception(EXLOC, msg);
559 }
560
561 CegoDataPointer rdp;
562 char* p;
563 int len;
564 p = (char*)pC->getFirst(len, rdp);
565
566 if ( p == 0 )
567 {
568 throw Exception(EXLOC, "Missing index anchor for index <" + indexName + ">");
569 }
570
571 pC->abort();
572 delete pC;
573
574 /////////////////////////////////////////
575
576 CegoDataPointer ptp = rdp;
577 CegoBufferPage rootPage;
578 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, rootPage);
579
580 CegoAVLIndexEntry ie;
581 ie.setPtr(p, len);
582
583 CegoDataPointer itp;
584 itp = ie.getRightBranch();
585
586 CegoBufferPage pageIE;
587 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
588
589 bool entryFound = false;
590
591 bool moreIndex = true;
592
593 CegoDataPointer nil;
594
595 //////////////////////////////////
596 // step one : found index entry //
597 //////////////////////////////////
598
599 while ( ! entryFound && moreIndex )
600 {
601 ie.setPtr(p, len);
602 bool leftBranch = false;
603
604 TupleOrder v = compIndexValue(schema, idxPtr, ie.getIdxPtr());
605
606 if ( v == LT )
607 {
608 leftBranch = true;
609 ptp = itp;
610 itp = ie.getLeftBranch();
611 }
612 else if ( v == GT )
613 {
614 leftBranch = false;
615 ptp = itp;
616 itp = ie.getRightBranch();
617 }
618 else
619 {
620 if ( ie.getData() == ddp )
621 {
622 entryFound = true;
623 }
624 else
625 {
626 itp = searchDataPointer(tabSetId, ddp, itp, fixMode );
627 // we still must set up ptp explicit
628 if ( itp != nil )
629 {
630 CegoBufferPage bp;
631 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, bp);
632 ie.setPtr(p, len);
633 ptp = ie.getParent();
634 if ( bp.isFixed() )
635 _pTM->releaseDataPtrUnlocked(bp, false);
636 }
637 }
638 }
639 if ( itp == nil )
640 {
641 moreIndex = false;
642 }
643
644 if ( ! entryFound && moreIndex )
645 {
646
647 if (pageIE.isFixed() )
648 _pTM->releaseDataPtrUnlocked(pageIE, false);
649 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
650 // cout << "claimed ptr " << itp << endl;
651 }
652 }
653
654 //////////////////////////////////////////////////////////////////////////////
655 // step two : delete index entry and perform balancing on node delete level //
656 //////////////////////////////////////////////////////////////////////////////
657
658 try
659 {
660 if ( entryFound )
661 {
662 if ( ie.getLeftBranch() == nil && ie.getRightBranch() == nil )
663 {
664
665 // cout << "Index Delete : case I " << endl;
666
667 CegoAVLIndexEntry pie;
668
669 CegoBufferPage pagePE;
670 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
671 pie.setPtr(p, len);
672
673 if ( pie.getLeftBranch() == itp )
674 {
675 // cout << "Index Delete : case Ia " << endl;
676
677 pie.setLeftBranch(nil);
678
679 // balance just if not root node
680 if ( pie.getData() != nil )
681 {
682 char leftHeight, rightHeight;
683 getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);
684
685 if ( rightHeight - leftHeight == 1 )
686 {
687 // nothing to do
688 }
689 else if ( rightHeight == leftHeight )
690 {
691 pie.setHeight(rightHeight + 1);
692 propagateDecrease(tabSetId, ptp, fixMode);
693 }
694 else // rightHeight >> leftHeight
695 {
696 char h = pie.getHeight();
697
698 CegoDataPointer nptp;
699
700 nptp = rebalanceNode(tabSetId, ptp, fixMode);
701
702 CegoBufferPage pageNE;
703 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len, pageNE);
704
705 CegoAVLIndexEntry nie;
706 nie.setPtr(p, len);
707
708 if ( h != nie.getHeight() )
709 propagateDecrease(tabSetId, nptp, fixMode);
710
711 _pTM->releaseDataPtrUnlocked(pageNE, true);
712
713 }
714 }
715 }
716 else if ( pie.getRightBranch() == itp )
717 {
718
719 // cout << "Index Delete : case Ib " << endl;
720
721 pie.setRightBranch(nil);
722
723 if ( pie.getData() != nil )
724 {
725 char leftHeight, rightHeight;
726 getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);
727
728 if ( leftHeight - rightHeight == 1 )
729 {
730 // nothing to do
731 }
732 else if ( leftHeight == rightHeight )
733 {
734 pie.setHeight(leftHeight + 1);
735 propagateDecrease(tabSetId, ptp, fixMode);
736 }
737 else // leftHeight >> rightHeight
738 {
739
740 char h = pie.getHeight();
741
742 CegoDataPointer nptp;
743
744 nptp = rebalanceNode(tabSetId, ptp, fixMode);
745
746 CegoBufferPage pageNE;
747 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len, pageNE);
748
749 CegoAVLIndexEntry nie;
750 nie.setPtr(p, len);
751
752 if ( h != nie.getHeight() )
753 propagateDecrease(tabSetId, nptp, fixMode);
754
755 _pTM->releaseDataPtrUnlocked(pageNE, true);
756
757 }
758 }
759 }
760
761 _pTM->releaseDataPtrUnlocked(pagePE, true);
762 _pTM->deleteData(idxType, tabSetId, itp);
763
764 }
765 else if ( ie.getRightBranch() == nil )
766 {
767
768 // cout << "Index Delete : case II " << endl;
769
770 CegoDataPointer ldp = ie.getLeftBranch();
771
772 CegoAVLIndexEntry pie, lie;
773
774 CegoBufferPage pagePE;
775 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
776 pie.setPtr(p, len);
777
778 CegoBufferPage pageLE;
779 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ldp, p, len, pageLE);
780 lie.setPtr(p,len);
781
782 lie.setParent(ptp);
783 _pTM->releaseDataPtrUnlocked(pageLE, true);
784
785 if ( pie.getLeftBranch() == itp )
786 {
787 pie.setLeftBranch(ldp);
788
789 if ( pie.getData() != nil )
790 {
791 char leftHeight, rightHeight;
792 getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);
793
794 if ( rightHeight - leftHeight == 1 )
795 {
796 pie.setHeight(rightHeight + 1);
797 // nothing to do
798 }
799 else if ( leftHeight == rightHeight )
800 {
801 pie.setHeight(leftHeight + 1);
802 propagateDecrease(tabSetId, ptp, fixMode);
803 }
804 else // rightHeight >> leftHeight
805 {
806
807 char h = pie.getHeight();
808
809 CegoDataPointer nptp;
810
811 nptp = rebalanceNode(tabSetId, ptp, fixMode);
812
813 CegoBufferPage pageNE;
814 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len, pageNE);
815
816 CegoAVLIndexEntry nie;
817 nie.setPtr(p, len);
818
819 if ( h != nie.getHeight() )
820 propagateDecrease(tabSetId, nptp, fixMode);
821
822 _pTM->releaseDataPtrUnlocked(pageNE, true);
823
824 }
825 }
826 }
827 else if ( pie.getRightBranch() == itp )
828 {
829 pie.setRightBranch(ldp);
830
831 if ( pie.getData() != nil )
832 {
833
834 char leftHeight, rightHeight;
835 getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);
836
837 if ( leftHeight - rightHeight == 1 )
838 {
839 // nothing to do
840 }
841 else if ( leftHeight == rightHeight )
842 {
843 pie.setHeight(leftHeight + 1);
844 propagateDecrease(tabSetId, ptp, fixMode);
845 }
846 else
847 {
848
849 char h = pie.getHeight();
850
851 CegoDataPointer nptp;
852
853 nptp = rebalanceNode(tabSetId, ptp, fixMode);
854
855 CegoBufferPage pageNE;
856 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len, pageNE);
857
858 CegoAVLIndexEntry nie;
859 nie.setPtr(p, len);
860
861 if ( h != nie.getHeight() )
862 propagateDecrease(tabSetId, nptp, fixMode);
863
864 _pTM->releaseDataPtrUnlocked(pageNE, true);
865 }
866 }
867 }
868
869 _pTM->releaseDataPtrUnlocked(pagePE, true);
870 _pTM->deleteData(idxType, tabSetId, itp);
871
872 }
873 else if ( ie.getLeftBranch() == nil )
874 {
875
876 // cout << "Index Delete : case III " << endl;
877
878 CegoDataPointer rdp = ie.getRightBranch();
879
880 CegoAVLIndexEntry pie, rie;
881
882 CegoBufferPage pagePE;
883 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
884 pie.setPtr(p, len);
885
886 if ( pie.getLeftBranch() == itp )
887 {
888 pie.setLeftBranch(rdp);
889
890 if ( pie.getData() != nil )
891 {
892 char leftHeight, rightHeight;
893 getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);
894
895 if ( rightHeight - leftHeight == 1 )
896 {
897 // nothing to do
898 }
899 else if ( rightHeight - leftHeight == 0 )
900 {
901 pie.setHeight(rightHeight + 1);
902 propagateDecrease(tabSetId, ptp, fixMode);
903 }
904 else
905 {
906 char h = pie.getHeight();
907
908 CegoDataPointer nptp;
909
910 nptp = rebalanceNode(tabSetId, ptp, fixMode);
911
912 CegoBufferPage pageNE;
913 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len, pageNE);
914
915 CegoAVLIndexEntry nie;
916 nie.setPtr(p, len);
917
918 if ( h != nie.getHeight() )
919 propagateDecrease(tabSetId, nptp, fixMode);
920
921 _pTM->releaseDataPtrUnlocked(pageNE, true);
922
923 }
924 }
925 }
926 else if ( pie.getRightBranch() == itp )
927 {
928 pie.setRightBranch(rdp);
929
930 if ( pie.getData() != nil )
931 {
932
933 char leftHeight, rightHeight;
934 getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);
935
936 if ( leftHeight - rightHeight == 1 )
937 {
938 // nothing to do
939 }
940 else if ( leftHeight == rightHeight )
941 {
942 pie.setHeight(leftHeight + 1);
943 propagateDecrease(tabSetId, ptp, fixMode);
944 }
945 else
946 {
947
948
949 char h = pie.getHeight();
950
951 CegoDataPointer nptp;
952
953 nptp = rebalanceNode(tabSetId, ptp, fixMode);
954
955 CegoBufferPage pageNE;
956 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len, pageNE);
957
958 CegoAVLIndexEntry nie;
959 nie.setPtr(p, len);
960
961 if ( h != nie.getHeight() )
962 propagateDecrease(tabSetId, nptp, fixMode);
963
964 _pTM->releaseDataPtrUnlocked(pageNE, true);
965 }
966 }
967 }
968 _pTM->releaseDataPtrUnlocked(pagePE, true);
969
970 CegoBufferPage pageR;
971 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, rdp, p, len, pageR);
972 rie.setPtr(p,len);
973 rie.setParent(ptp);
974
975 _pTM->releaseDataPtrUnlocked(pageR, true);
976 _pTM->deleteData(idxType, tabSetId, itp);
977
978 }
979 else
980 {
981
982 // cout << "Index Delete : case IV " << endl;
983
984 CegoDataPointer ndp = ie.getRightBranch();
985
986 CegoAVLIndexEntry nie;
987
988 CegoBufferPage pageNE;
989 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ndp, p, len, pageNE);
990 nie.setPtr(p, len);
991
992 if ( nie.getLeftBranch() == nil )
993 {
994
995 // cout << "Index Delete : case IVa " << endl;
996
997 CegoAVLIndexEntry pie, lie;
998
999 CegoBufferPage pagePE;
1000 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
1001 pie.setPtr(p, len);
1002
1003 if ( pie.getRightBranch() == itp )
1004 {
1005 pie.setRightBranch(ndp);
1006 }
1007 else if ( pie.getLeftBranch() == itp )
1008 {
1009 pie.setLeftBranch(ndp);
1010 }
1011
1012 nie.setParent(ptp);
1013
1014 CegoDataPointer ldp = ie.getLeftBranch();
1015 // cout << "LDP = " << ldp << endl;
1016 CegoBufferPage pageLE;
1017 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ldp, p, len, pageLE);
1018
1019 lie.setPtr(p, len);
1020
1021 lie.setParent(ndp);
1022
1023 nie.setLeftBranch(ldp);
1024
1025 char leftHeight, rightHeight;
1026 getSubTreeHeight(tabSetId, fixMode, nie, leftHeight, rightHeight);
1027
1028 char diff;
1029 diff = leftHeight - rightHeight;
1030
1031 if ( diff == 1 || diff == 0 )
1032 {
1033 nie.setHeight(leftHeight + 1);
1034 propagateDecrease(tabSetId, ndp, fixMode);
1035 }
1036 else // leftHeight >> rightHeight
1037 {
1038 char h = nie.getHeight();
1039 CegoDataPointer nndp = rebalanceNode(tabSetId, ndp, fixMode);
1040
1041 CegoBufferPage pageNN;
1042 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nndp, p, len, pageNN);
1043 CegoAVLIndexEntry nnie;
1044 nnie.setPtr(p, len);
1045
1046 if ( h != nnie.getHeight() )
1047 propagateDecrease(tabSetId, nndp, fixMode);
1048
1049 _pTM->releaseDataPtrUnlocked(pageNN);
1050 }
1051
1052 _pTM->releaseDataPtrUnlocked(pagePE);
1053 _pTM->releaseDataPtrUnlocked(pageLE);
1054
1055 _pTM->deleteData(idxType, tabSetId, itp);
1056
1057 }
1058 else
1059 {
1060
1061 // cout << "Index Delete : case IVb " << endl;
1062
1063 CegoBufferPage pageZE;
1064 CegoBufferPage pageFE;
1065 CegoBufferPage pageAE;
1066 CegoBufferPage pageBE;
1067 CegoBufferPage pageCE;
1068
1069 while ( nie.getLeftBranch() != nil )
1070 {
1071 ndp = nie.getLeftBranch();
1072
1073 if (pageNE.isFixed())
1074 {
1075 _pTM->releaseDataPtrUnlocked(pageNE, false);
1076 }
1077
1078 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ndp, p, len, pageNE);
1079 nie.setPtr(p,len);
1080 }
1081
1082 CegoAVLIndexEntry fie;
1083 CegoDataPointer fdp = nie.getParent();
1084 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, fdp, p, len, pageFE);
1085 fie.setPtr(p,len);
1086
1087 if ( nie.getRightBranch() != nil )
1088 {
1089 CegoDataPointer zdp = nie.getRightBranch();
1090
1091 CegoAVLIndexEntry zie;
1092
1093 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, zdp, p, len, pageZE);
1094 zie.setPtr(p,len);
1095
1096 zie.setParent(nie.getParent());
1097
1098 fie.setLeftBranch(zdp);
1099 }
1100 else
1101 {
1102 fie.setLeftBranch(nil);
1103 }
1104
1105 CegoDataPointer adp, bdp, cdp;
1106 CegoAVLIndexEntry aie, bie, cie;
1107
1108 adp=ie.getParent();
1109 bdp=ie.getLeftBranch();
1110 cdp=ie.getRightBranch();
1111
1112 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, adp, p, len, pageAE);
1113 aie.setPtr(p,len);
1114 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, bdp, p, len, pageBE);
1115 bie.setPtr(p,len);
1116 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, cdp, p, len, pageCE);
1117 cie.setPtr(p,len);
1118
1119 nie.setParent(adp);
1120 nie.setLeftBranch(bdp);
1121 nie.setRightBranch(cdp);
1122
1123 char leftHeight, rightHeight;
1124 getSubTreeHeight(tabSetId, fixMode, nie, leftHeight, rightHeight);
1125 nie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1126
1127 if ( aie.getLeftBranch() == itp )
1128 {
1129 aie.setLeftBranch(ndp);
1130 }
1131 else
1132 {
1133 aie.setRightBranch(ndp);
1134 }
1135 bie.setParent(ndp);
1136 cie.setParent(ndp);
1137
1138 getSubTreeHeight(tabSetId, fixMode, fie, leftHeight, rightHeight);
1139
1140 char diff;
1141 char maxHeight;
1142
1143 if ( leftHeight > rightHeight )
1144 {
1145 diff = leftHeight - rightHeight;
1146 maxHeight = leftHeight;
1147 }
1148 else
1149 {
1150 diff = rightHeight - leftHeight;
1151 maxHeight = rightHeight;
1152 }
1153
1154 if ( diff == 1 || diff == 0)
1155 {
1156 fie.setHeight( maxHeight + 1);
1157 propagateDecrease(tabSetId, fdp, fixMode);
1158 }
1159 else // rightHeight >> leftHeight )
1160 {
1161
1162 char h = fie.getHeight();
1163 CegoDataPointer nfdp;
1164
1165 nfdp = rebalanceNode(tabSetId, fdp, fixMode);
1166
1167 CegoBufferPage pageRE;
1168 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nfdp, p, len, pageRE);
1169
1170 CegoAVLIndexEntry nfie;
1171 nfie.setPtr(p, len);
1172
1173 if ( h != nfie.getHeight() )
1174 propagateDecrease(tabSetId, nfdp, fixMode);
1175
1176 _pTM->releaseDataPtrUnlocked(pageRE, true);
1177 }
1178
1179 if ( pageAE.isFixed() )
1180 _pTM->releaseDataPtrUnlocked(pageAE, true);
1181 if ( pageBE.isFixed() )
1182 _pTM->releaseDataPtrUnlocked(pageBE, true);
1183 if ( pageCE.isFixed() )
1184 _pTM->releaseDataPtrUnlocked(pageCE, true);
1185 if ( pageFE.isFixed() )
1186 _pTM->releaseDataPtrUnlocked(pageFE, true);
1187 if ( pageZE.isFixed() )
1188 _pTM->releaseDataPtrUnlocked(pageZE, true);
1189
1190 _pTM->deleteData(idxType, tabSetId, itp);
1191 }
1192
1193 if ( pageNE.isFixed() )
1194 _pTM->releaseDataPtrUnlocked(pageNE, true);
1195 }
1196 }
1197 else
1198 {
1199
1200
1201 CegoField* pF = schema.First();
1202 char *p = idxPtr;
1203
1204 Chain v;
1205
1206 while ( pF )
1207 {
1208
1209 int flen;
1210 memcpy(&flen, p, sizeof(int));
1211 p += sizeof(int);
1212
1213 CegoFieldValue fv;
1214 fv.setLength(flen);
1215 fv.setValue(p);
1216
1217 if ( flen > 0 )
1218 fv.setType(pF->getType());
1219
1220 p += flen;
1221
1222 v += fv.valAsChain() + Chain(" ");
1223 pF = schema.Next();
1224 }
1225
1226 Chain msg = Chain("Value for index ") + indexName + Chain(" ( value = ") + v + Chain(") not found");
1227 throw Exception(EXLOC, msg);
1228 }
1229 }
1230 catch ( Exception e )
1231 {
1232 _pTM->releaseDataPtrUnlocked(rootPage, false);
1233 throw e;
1234 }
1235
1236 if ( pageIE.isFixed() )
1237 _pTM->releaseDataPtrUnlocked(pageIE, false);
1238
1239 _pTM->releaseDataPtrUnlocked(rootPage, false);
1240 }
1241
propagateDecrease(int tabSetId,CegoDataPointer itp,CegoBufferPool::FixMode fixMode)1242 void CegoAVLIndexManager::propagateDecrease(int tabSetId, CegoDataPointer itp, CegoBufferPool::FixMode fixMode)
1243 {
1244 char* p;
1245 int len;
1246
1247 CegoBufferPage pageIE;
1248 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
1249 CegoAVLIndexEntry ie;
1250 ie.setPtr(p, len);
1251
1252 CegoDataPointer nil;
1253
1254 if ( ie.getData() == nil )
1255 {
1256 if ( pageIE.isFixed() )
1257 _pTM->releaseDataPtrUnlocked(pageIE, true);
1258 return;
1259 }
1260 CegoDataPointer ptp = ie.getParent();
1261
1262 CegoBufferPage pagePE;
1263 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
1264 CegoAVLIndexEntry pie;
1265 pie.setPtr(p, len);
1266
1267 if ( pie.getData() == nil )
1268 {
1269 if ( pageIE.isFixed() )
1270 _pTM->releaseDataPtrUnlocked(pageIE, true);
1271 if ( pagePE.isFixed() )
1272 _pTM->releaseDataPtrUnlocked(pagePE, true);
1273 return;
1274 }
1275 bool treeBalanced = false;
1276 bool rootReached = false;
1277
1278 while ( ! treeBalanced && ! rootReached)
1279 {
1280
1281 char leftHeight, rightHeight;
1282 getSubTreeHeight(tabSetId, fixMode, pie, leftHeight, rightHeight);
1283
1284 char diff;
1285 if ( leftHeight > rightHeight )
1286 diff = leftHeight - rightHeight;
1287 else
1288 diff = rightHeight - leftHeight;
1289
1290
1291 if ( diff == 1 )
1292 {
1293 // nothing to do
1294 }
1295 else if ( diff == 0 )
1296 {
1297 pie.setHeight(leftHeight + 1);
1298 }
1299 else
1300 {
1301
1302 ptp = rebalanceNode(tabSetId, ptp, fixMode);
1303
1304 if ( pagePE.isFixed() )
1305 {
1306 _pTM->releaseDataPtrUnlocked(pagePE, true);
1307 }
1308 if ( ptp.getOffset() )
1309 {
1310 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
1311 pie.setPtr(p, len);
1312 }
1313 }
1314
1315 if ( pageIE.isFixed() )
1316 {
1317 _pTM->releaseDataPtrUnlocked(pageIE, true);
1318 }
1319
1320 itp = ptp;
1321 pageIE = pagePE;
1322 ie = pie;
1323
1324 ptp = ie.getParent();
1325
1326 if ( ptp.getOffset() )
1327 {
1328 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
1329 pie.setPtr(p, len);
1330 }
1331
1332 if ( pie.getData() == nil )
1333 {
1334 pie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1335 rootReached = true;
1336 }
1337 }
1338
1339 if ( pageIE.isFixed() )
1340 _pTM->releaseDataPtrUnlocked(pageIE, true);
1341 if ( pagePE.isFixed() )
1342 _pTM->releaseDataPtrUnlocked(pagePE, true);
1343 }
1344
rebalanceNode(int tabSetId,CegoDataPointer itp,CegoBufferPool::FixMode fixMode)1345 CegoDataPointer CegoAVLIndexManager::rebalanceNode(int tabSetId, CegoDataPointer itp, CegoBufferPool::FixMode fixMode)
1346 {
1347 char* p;
1348 int len;
1349
1350 CegoDataPointer nil;
1351
1352 CegoBufferPage pageIE;
1353 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
1354 CegoAVLIndexEntry ie;
1355 ie.setPtr(p, len);
1356
1357 char leftHeight, rightHeight;
1358 getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);
1359
1360 // cout << "lh=" << (int)leftHeight << " rh=" << (int)rightHeight << endl;
1361
1362 char diff;
1363 if ( leftHeight > rightHeight )
1364 diff = leftHeight - rightHeight;
1365 else
1366 diff = rightHeight - leftHeight;
1367
1368 CegoDataPointer nptp;
1369
1370 if ( leftHeight > rightHeight && diff > 1 )
1371 {
1372
1373 // decide if LL or LR Rotation
1374 CegoDataPointer ldp = ie.getLeftBranch();
1375 CegoBufferPage pageLE;
1376 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ldp, p, len, pageLE);
1377 CegoAVLIndexEntry lie;
1378 lie.setPtr(p, len);
1379
1380 char leftHeight, rightHeight;
1381 getSubTreeHeight(tabSetId, fixMode, lie, leftHeight, rightHeight);
1382
1383 if ( leftHeight >= rightHeight )
1384 {
1385 nptp = rotateLL(tabSetId, itp, fixMode);
1386 }
1387 else
1388 {
1389 nptp = rotateLR(tabSetId, itp, fixMode);
1390 }
1391 _pTM->releaseDataPtrUnlocked(pageLE, true);
1392
1393 }
1394 else if ( leftHeight < rightHeight && diff > 1 )
1395 {
1396
1397 // decide if RR or RL Rotation
1398
1399 CegoDataPointer rdp = ie.getRightBranch();
1400 CegoBufferPage pageRE;
1401 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, rdp, p, len, pageRE);
1402
1403 CegoAVLIndexEntry rie;
1404 rie.setPtr(p, len);
1405
1406 char leftHeight, rightHeight;
1407 getSubTreeHeight(tabSetId, fixMode, rie, leftHeight, rightHeight);
1408
1409 if ( leftHeight <= rightHeight )
1410 {
1411 nptp = rotateRR(tabSetId, itp, fixMode);
1412 }
1413 else
1414 {
1415 nptp = rotateRL(tabSetId, itp, fixMode);
1416 CegoBufferPage pageSE;
1417 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, nptp, p, len, pageSE);
1418
1419 CegoAVLIndexEntry rie;
1420 rie.setPtr(p, len);
1421 CegoDataPointer rdp = rie.getRightBranch();
1422 if ( rdp != nil )
1423 {
1424 CegoDataPointer sub;
1425 sub = rebalanceNode(tabSetId, rdp, fixMode);
1426 }
1427 _pTM->releaseDataPtrUnlocked(pageSE, true);
1428 }
1429 _pTM->releaseDataPtrUnlocked(pageRE, true);
1430 }
1431
1432 _pTM->releaseDataPtrUnlocked(pageIE, true);
1433
1434 return nptp;
1435 }
1436
compIndexValue(const ListT<CegoField> & schema,char * p1,char * p2)1437 CegoAVLIndexManager::TupleOrder CegoAVLIndexManager::compIndexValue(const ListT<CegoField>& schema, char* p1, char* p2)
1438 {
1439 CegoField* pF = schema.First();
1440
1441 while ( pF )
1442 {
1443
1444 int flen1, flen2;
1445 memcpy(&flen1, p1, sizeof(int));
1446 memcpy(&flen2, p2, sizeof(int));
1447
1448 p1 += sizeof(int);
1449 p2 += sizeof(int);
1450
1451 CegoFieldValue fv1, fv2;
1452 fv1.setLength(flen1);
1453 fv2.setLength(flen2);
1454
1455 fv1.setValue(p1);
1456 fv2.setValue(p2);
1457
1458
1459 if ( flen1 > 0 )
1460 fv1.setType(pF->getType());
1461 if ( flen2 > 0 )
1462 fv2.setType(pF->getType());
1463
1464 // both null values
1465 if ( flen1 == 0 && flen2 == 0 )
1466 {
1467 // if ( ALLOW_UNIQUE_NULL == true)
1468 // return LT;
1469 return EQU_NULL;
1470 }
1471 if ( fv1 < fv2 )
1472 {
1473 return LT;
1474 }
1475 if ( fv1 > fv2 )
1476 {
1477 return GT;
1478 }
1479
1480 pF = schema.Next();
1481 if ( pF )
1482 {
1483 p1 += flen1;
1484 p2 += flen2;
1485 }
1486 }
1487
1488 return EQU;
1489 }
1490
rotateRR(int tabSetId,const CegoDataPointer & ptp,CegoBufferPool::FixMode fixMode)1491 CegoDataPointer CegoAVLIndexManager::rotateRR(int tabSetId, const CegoDataPointer& ptp, CegoBufferPool::FixMode fixMode)
1492 {
1493 char *p;
1494 int len;
1495
1496 CegoDataPointer itp, atp, ctp;
1497 CegoAVLIndexEntry pe, ie, ae, ce;
1498
1499 CegoBufferPage pagePE;
1500 CegoBufferPage pageIE;
1501
1502 CegoBufferPage pageAE;
1503 CegoBufferPage pageCE;
1504
1505
1506 // a is parent of pe
1507 // c is left child of ie
1508
1509 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
1510 pe.setPtr(p, len);
1511
1512 atp = pe.getParent();
1513
1514 if ( atp.getOffset() )
1515 {
1516 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, atp, p, len, pageAE);
1517 ae.setPtr(p, len);
1518 }
1519
1520 itp = pe.getRightBranch();
1521
1522 if ( itp.getOffset() )
1523 {
1524 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
1525 ie.setPtr(p, len);
1526 }
1527 else
1528 {
1529 throw Exception(EXLOC, "Invalid index reference at RR rotation");
1530 }
1531
1532 ctp = ie.getLeftBranch();
1533 if ( ctp.getOffset() )
1534 {
1535 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ctp, p, len, pageCE);
1536 ce.setPtr(p, len);
1537 }
1538
1539 /////////////////////
1540
1541 pe.setRightBranch(ctp);
1542 if ( ctp.getOffset() )
1543 {
1544 ce.setParent(ptp);
1545 }
1546
1547 if ( atp.getOffset() )
1548 {
1549 if ( ae.getRightBranch() == ptp )
1550 {
1551 ae.setRightBranch(itp);
1552 }
1553 else
1554 {
1555 ae.setLeftBranch(itp);
1556 }
1557 }
1558
1559 ie.setParent(atp);
1560 pe.setParent(itp);
1561 ie.setLeftBranch(ptp);
1562
1563 // set up balance
1564
1565 char leftHeight, rightHeight;
1566 getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);
1567 pe.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1568
1569 getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);
1570 ie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1571
1572 if ( atp.getOffset() )
1573 {
1574 getSubTreeHeight(tabSetId, fixMode, ae, leftHeight, rightHeight);
1575 ae.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1576 }
1577
1578 if ( pagePE.isFixed() )
1579 _pTM->releaseDataPtrUnlocked(pagePE, true);
1580 if ( pageIE.isFixed() )
1581 _pTM->releaseDataPtrUnlocked(pageIE, true);
1582 if ( pageCE.isFixed() )
1583 _pTM->releaseDataPtrUnlocked(pageCE, true);
1584 if ( pageAE.isFixed() )
1585 _pTM->releaseDataPtrUnlocked(pageAE, true);
1586
1587 return itp;
1588 }
1589
1590
rotateRL(int tabSetId,const CegoDataPointer & ptp,CegoBufferPool::FixMode fixMode)1591 CegoDataPointer CegoAVLIndexManager::rotateRL(int tabSetId, const CegoDataPointer& ptp, CegoBufferPool::FixMode fixMode)
1592 {
1593 char *p;
1594 int len;
1595
1596 CegoDataPointer itp, atp, ctp, etp, ftp;
1597 CegoAVLIndexEntry pe, ie, ae, ce, ee, fe;
1598
1599 CegoBufferPage pagePE;
1600 CegoBufferPage pageIE;
1601
1602 CegoBufferPage pageAE;
1603 CegoBufferPage pageCE;
1604 CegoBufferPage pageEE;
1605 CegoBufferPage pageFE;
1606
1607
1608 // a is parent of pe
1609 // c is left child of ie
1610 // e is left child of c
1611 // f is right child of c
1612
1613 if ( ptp.getOffset() )
1614 {
1615 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
1616 pe.setPtr(p, len);
1617 }
1618 else
1619 {
1620 throw Exception(EXLOC, "Invalid index reference at RL rotation");
1621 }
1622
1623 atp = pe.getParent();
1624
1625 if ( atp.getOffset() )
1626 {
1627 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, atp, p, len, pageAE);
1628 ae.setPtr(p, len);
1629 }
1630
1631 itp = pe.getRightBranch();
1632
1633 if ( itp.getOffset() )
1634 {
1635 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
1636 ie.setPtr(p, len);
1637 }
1638 else
1639 {
1640 throw Exception(EXLOC, "Invalid index reference at RL rotation");
1641 }
1642
1643 ctp = ie.getLeftBranch();
1644 if ( ctp.getOffset() )
1645 {
1646 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ctp, p, len, pageCE);
1647 ce.setPtr(p, len);
1648 }
1649
1650 ftp = ce.getRightBranch();
1651 if ( ftp.getOffset() )
1652 {
1653 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ftp, p, len, pageFE);
1654 fe.setPtr(p, len);
1655 }
1656
1657 etp = ce.getLeftBranch();
1658 if ( etp.getOffset() )
1659 {
1660 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, etp, p, len, pageEE);
1661 ee.setPtr(p, len);
1662 }
1663
1664 ie.setLeftBranch(ftp);
1665 if ( ftp.getOffset() )
1666 {
1667 fe.setParent(itp);
1668 }
1669
1670 if ( atp.getOffset() )
1671 {
1672 if (ae.getRightBranch() == ptp )
1673 {
1674 ae.setRightBranch(ctp);
1675 }
1676 else
1677 {
1678 ae.setLeftBranch(ctp);
1679 }
1680 }
1681 ce.setParent(atp);
1682
1683 ce.setRightBranch(itp);
1684 ie.setParent(ctp);
1685
1686 ie.setLeftBranch(ftp);
1687 if ( ftp.getOffset() )
1688 {
1689 fe.setParent(itp);
1690 }
1691 ce.setLeftBranch(ptp);
1692
1693 pe.setParent(ctp);
1694
1695 if ( etp.getOffset() )
1696 {
1697 ee.setParent(ptp);
1698 }
1699 pe.setRightBranch(etp);
1700
1701 // set up balance
1702
1703 char leftHeight, rightHeight;
1704 getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);
1705 pe.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1706
1707 getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);
1708 ie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1709
1710 getSubTreeHeight(tabSetId, fixMode, ce, leftHeight, rightHeight);
1711 ce.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1712
1713 if ( atp.getOffset() )
1714 {
1715 getSubTreeHeight(tabSetId, fixMode, ae, leftHeight, rightHeight);
1716 ae.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1717 }
1718
1719 if ( pagePE.isFixed() )
1720 _pTM->releaseDataPtrUnlocked(pagePE, true);
1721 if ( pageIE.isFixed() )
1722 _pTM->releaseDataPtrUnlocked(pageIE, true);
1723 if ( pageCE.isFixed() )
1724 _pTM->releaseDataPtrUnlocked(pageCE, true);
1725 if ( pageAE.isFixed() )
1726 _pTM->releaseDataPtrUnlocked(pageAE, true);
1727 if ( pageEE.isFixed() )
1728 _pTM->releaseDataPtrUnlocked(pageEE, true);
1729 if ( pageFE.isFixed() )
1730 _pTM->releaseDataPtrUnlocked(pageFE, true);
1731
1732 return ctp;
1733 }
1734
1735
rotateLL(int tabSetId,const CegoDataPointer & ptp,CegoBufferPool::FixMode fixMode)1736 CegoDataPointer CegoAVLIndexManager::rotateLL(int tabSetId, const CegoDataPointer& ptp, CegoBufferPool::FixMode fixMode)
1737 {
1738 char *p;
1739 int len;
1740
1741 CegoDataPointer itp, atp, dtp;
1742 CegoAVLIndexEntry pe, ie, ae, de;
1743
1744 CegoBufferPage pagePE;
1745 CegoBufferPage pageIE;
1746
1747 CegoBufferPage pageAE;
1748 CegoBufferPage pageDE;
1749
1750 // a is parent of pe
1751 // d is right child of ie
1752
1753 if ( ptp.getOffset() )
1754 {
1755 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
1756 pe.setPtr(p, len);
1757 }
1758 else
1759 {
1760 throw Exception(EXLOC, "Invalid index reference at LL rotation");
1761 }
1762
1763 atp = pe.getParent();
1764
1765 if ( atp.getOffset() )
1766 {
1767 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, atp, p, len, pageAE);
1768 ae.setPtr(p, len);
1769 }
1770
1771 itp = pe.getLeftBranch();
1772
1773 if ( itp.getOffset() )
1774 {
1775 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
1776 ie.setPtr(p, len);
1777 }
1778 else
1779 {
1780 throw Exception(EXLOC, "Invalid index reference at LL rotation");
1781 }
1782
1783 dtp = ie.getRightBranch();
1784
1785 if ( dtp.getOffset() )
1786 {
1787 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, dtp, p, len, pageDE);
1788 de.setPtr(p, len);
1789 }
1790
1791 if ( dtp.getOffset() )
1792 {
1793 de.setParent(ptp);
1794 }
1795 pe.setLeftBranch(dtp);
1796
1797 pe.setParent(itp);
1798 ie.setRightBranch(ptp);
1799
1800 if ( atp.getOffset() )
1801 {
1802
1803 if ( ae.getRightBranch() == ptp )
1804 {
1805 ae.setRightBranch(itp);
1806 }
1807 else
1808 {
1809 ae.setLeftBranch(itp);
1810 }
1811 }
1812 ie.setParent(atp);
1813
1814 char leftHeight, rightHeight;
1815 getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);
1816 pe.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1817
1818 getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);
1819 ie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1820
1821 if ( atp.getOffset() )
1822 {
1823 getSubTreeHeight(tabSetId, fixMode, ae, leftHeight, rightHeight);
1824 ae.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1825 }
1826
1827 if ( pagePE.isFixed() )
1828 _pTM->releaseDataPtrUnlocked(pagePE, true);
1829 if ( pageIE.isFixed() )
1830 _pTM->releaseDataPtrUnlocked(pageIE, true);
1831 if ( pageAE.isFixed() )
1832 _pTM->releaseDataPtrUnlocked(pageAE, true);
1833 if ( pageDE.isFixed() )
1834 _pTM->releaseDataPtrUnlocked(pageDE, true);
1835
1836 return itp;
1837 }
1838
rotateLR(int tabSetId,const CegoDataPointer & ptp,CegoBufferPool::FixMode fixMode)1839 CegoDataPointer CegoAVLIndexManager::rotateLR(int tabSetId, const CegoDataPointer& ptp, CegoBufferPool::FixMode fixMode)
1840 {
1841 char *p;
1842 int len;
1843
1844 CegoDataPointer itp, atp, ctp, dtp, etp;
1845 CegoAVLIndexEntry pe, ie, ae, ce, de, ee;
1846
1847 CegoBufferPage pagePE;
1848 CegoBufferPage pageIE;
1849
1850 CegoBufferPage pageAE;
1851 CegoBufferPage pageCE;
1852 CegoBufferPage pageDE;
1853 CegoBufferPage pageEE;
1854
1855
1856 // a is parent of pie
1857 // d is right child of ie
1858 // c is left child of d
1859 // e is right child of d
1860
1861 if ( ptp.getOffset() )
1862 {
1863 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ptp, p, len, pagePE);
1864 pe.setPtr(p, len);
1865 }
1866 else
1867 {
1868 throw Exception(EXLOC, "Invalid index reference at LR rotation");
1869 }
1870
1871 atp = pe.getParent();
1872
1873 if ( atp.getOffset() )
1874 {
1875 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, atp, p, len, pageAE);
1876 ae.setPtr(p, len);
1877 }
1878
1879 itp = pe.getLeftBranch();
1880
1881 if ( itp.getOffset() )
1882 {
1883 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, itp, p, len, pageIE);
1884 ie.setPtr(p, len);
1885 }
1886 else
1887 {
1888 throw Exception(EXLOC, "Invalid index reference at LR rotation");
1889 }
1890
1891 dtp = ie.getRightBranch();
1892 if ( dtp.getOffset() )
1893 {
1894 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, dtp, p, len, pageDE);
1895 de.setPtr(p, len);
1896 }
1897 else
1898 {
1899 throw Exception(EXLOC, "Invalid index reference at LR rotation");
1900 }
1901
1902 ctp = de.getLeftBranch();
1903 if ( ctp.getOffset() )
1904 {
1905 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, ctp, p, len, pageCE);
1906 ce.setPtr(p, len);
1907 }
1908
1909 etp = de.getRightBranch();
1910 if ( etp.getOffset() )
1911 {
1912 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, etp, p, len, pageEE);
1913 ee.setPtr(p, len);
1914 }
1915
1916 ie.setRightBranch(ctp);
1917
1918 if ( ctp.getOffset() )
1919 {
1920 ce.setParent(itp);
1921 }
1922
1923 ie.setParent(dtp);
1924 de.setLeftBranch(itp);
1925
1926 if ( atp.getOffset() )
1927 {
1928 if ( ae.getRightBranch() == ptp )
1929 {
1930 ae.setRightBranch(dtp);
1931 }
1932 else
1933 {
1934 ae.setLeftBranch(dtp);
1935 }
1936 }
1937
1938 de.setParent(atp);
1939 de.setRightBranch(ptp);
1940 pe.setParent(dtp);
1941
1942 if ( etp.getOffset() )
1943 {
1944 ee.setParent(ptp);
1945 }
1946 pe.setLeftBranch(etp);
1947
1948 // set up balance
1949
1950 char leftHeight, rightHeight;
1951 getSubTreeHeight(tabSetId, fixMode, pe, leftHeight, rightHeight);
1952 pe.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1953
1954 getSubTreeHeight(tabSetId, fixMode, ie, leftHeight, rightHeight);
1955 ie.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1956
1957 getSubTreeHeight(tabSetId, fixMode, de, leftHeight, rightHeight);
1958 de.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1959
1960 if ( atp.getOffset() )
1961 {
1962 getSubTreeHeight(tabSetId, fixMode, ae, leftHeight, rightHeight);
1963 ae.setHeight(leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
1964 }
1965
1966 if ( pagePE.isFixed() )
1967 _pTM->releaseDataPtrUnlocked(pagePE, true);
1968 if ( pageIE.isFixed() )
1969 _pTM->releaseDataPtrUnlocked(pageIE, true);
1970
1971 if ( pageAE.isFixed() )
1972 _pTM->releaseDataPtrUnlocked(pageAE, true);
1973 if ( pageCE.isFixed() )
1974 _pTM->releaseDataPtrUnlocked(pageCE, true);
1975 if ( pageDE.isFixed() )
1976 _pTM->releaseDataPtrUnlocked(pageDE, true);
1977 if ( pageEE.isFixed() )
1978 _pTM->releaseDataPtrUnlocked(pageEE, true);
1979
1980 return dtp;
1981 }
1982
checkIndex(int tabSetId,const Chain & indexName,CegoObject::ObjectType idxType)1983 char CegoAVLIndexManager::checkIndex(int tabSetId, const Chain& indexName, CegoObject::ObjectType idxType)
1984 {
1985 CegoTableObject oe;
1986 _pTM->getObject(tabSetId, indexName, idxType, oe);
1987
1988 CegoObjectCursor* pC = _pTM->getObjectCursor(tabSetId, oe.getTabName(), indexName, idxType);
1989
1990 if ( ! pC )
1991 {
1992 Chain msg = "Cannot get cursor for <" + indexName + ">";
1993 throw Exception(EXLOC, msg);
1994 }
1995
1996 CegoDataPointer rdp;
1997 char* p;
1998 int len;
1999 p = (char*)pC->getFirst(len, rdp);
2000
2001 if ( p == 0 )
2002 {
2003 throw Exception(EXLOC, "Missing Index Anchor");
2004 }
2005
2006 pC->abort();
2007 delete pC;
2008
2009 /////////////////////////////////////////
2010
2011 CegoDataPointer ptp = rdp;
2012 CegoBufferPage rootPage;
2013 _pTM->claimDataPtrUnlocked(tabSetId, CegoBufferPool::SYNC, ptp, p, len, rootPage);
2014
2015 CegoAVLIndexEntry ie;
2016 ie.setPtr(p, len);
2017
2018 CegoDataPointer itp;
2019 itp = ie.getRightBranch();
2020
2021 char h = recursiveIndexNodeCheck(tabSetId, itp);
2022
2023 _pTM->releaseDataPtrUnlocked(rootPage, false);
2024
2025 return h;
2026 }
2027
recursiveIndexNodeCheck(int tabSetId,const CegoDataPointer & dp)2028 char CegoAVLIndexManager::recursiveIndexNodeCheck(int tabSetId, const CegoDataPointer& dp)
2029 {
2030 CegoDataPointer nil;
2031
2032 if ( dp == nil )
2033 return 0;
2034
2035 char* p;
2036 int len;
2037
2038 #ifdef CGDEBUG
2039 _pLogger->log(_modId, Logger::DEBUG, Chain("Claiming datapointer ") + dp.toChain());
2040 #endif
2041
2042 CegoBufferPage bp;
2043 _pTM->claimDataPtrUnlocked(tabSetId, CegoBufferPool::SYNC, dp, p, len, bp);
2044
2045 CegoAVLIndexEntry ie;
2046 ie.setPtr(p, len);
2047
2048 CegoDataPointer rightBranch = ie.getRightBranch();
2049 CegoDataPointer leftBranch = ie.getLeftBranch();
2050 char nodeHeight = ie.getHeight();
2051 #ifdef CGDEBUG
2052 _pLogger->log(_modId, Logger::DEBUG, Chain("Accessing datapointer ") + dp.toChain());
2053 #endif
2054
2055 if ( bp.isFixed() )
2056 {
2057 #ifdef CGDEBUG
2058 _pLogger->log(_modId, Logger::DEBUG, Chain("Releasing datapointer ") + dp.toChain());
2059 #endif
2060
2061 _pTM->releaseDataPtrUnlocked(bp, false);
2062 }
2063
2064 char rightHeight = recursiveIndexNodeCheck(tabSetId, rightBranch);
2065 if ( rightHeight == -1 )
2066 return -1;
2067
2068 char leftHeight = recursiveIndexNodeCheck(tabSetId, leftBranch);
2069 if ( leftHeight == -1 )
2070 return -1;
2071
2072 char subHeight = leftHeight > rightHeight ? leftHeight : rightHeight;
2073
2074 char diff = leftHeight > rightHeight ? leftHeight - rightHeight : rightHeight - leftHeight;
2075
2076 if ( diff > 1 )
2077 {
2078 return -1 ;
2079 }
2080
2081 if ( nodeHeight != subHeight + 1 )
2082 {
2083 // cout << dp << " Node Height = " << (int)nodeHeight << " SubNode Height= " << (int)subHeight<< endl;
2084 return -1;
2085 }
2086
2087 return nodeHeight;
2088 }
2089
searchDataPointer(int tabSetId,const CegoDataPointer & ddp,const CegoDataPointer & rdp,CegoBufferPool::FixMode fixMode)2090 CegoDataPointer CegoAVLIndexManager::searchDataPointer(int tabSetId, const CegoDataPointer& ddp, const CegoDataPointer& rdp, CegoBufferPool::FixMode fixMode)
2091 {
2092 CegoDataPointer itp;
2093
2094 CegoDataPointer nil;
2095
2096 if ( rdp == nil )
2097 return nil;
2098
2099 char* p;
2100 int len;
2101
2102 CegoBufferPage pageRE;
2103 _pTM->claimDataPtrUnlocked(tabSetId, fixMode, rdp, p, len, pageRE);
2104
2105 CegoAVLIndexEntry re;
2106 re.setPtr(p, len);
2107
2108 if ( re.getData() == ddp )
2109 {
2110 itp = rdp;
2111 }
2112 else
2113 {
2114 itp = searchDataPointer ( tabSetId, ddp, re.getLeftBranch(), fixMode);
2115
2116 if ( itp == nil )
2117 {
2118 itp = searchDataPointer ( tabSetId, ddp, re.getRightBranch(), fixMode);
2119 }
2120 }
2121
2122 if ( pageRE.isFixed() )
2123 _pTM->releaseDataPtrUnlocked(pageRE, false);
2124
2125 return itp;
2126 }
2127