1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 // MARKER(update_precomp.py): autogen include statement, do not remove 29 #include "precompiled_connectivity.hxx" 30 #include "dbase/dindexnode.hxx" 31 #include "connectivity/CommonTools.hxx" 32 #include <osl/thread.h> 33 #include "dbase/DIndex.hxx" 34 #include <tools/debug.hxx> 35 #include "diagnose_ex.h" 36 37 #include <algorithm> 38 39 40 using namespace connectivity; 41 using namespace connectivity::dbase; 42 using namespace connectivity::file; 43 using namespace com::sun::star::sdbc; 44 // ----------------------------------------------------------------------------- 45 ONDXKey::ONDXKey(sal_uInt32 nRec) 46 :nRecord(nRec) 47 { 48 } 49 // ----------------------------------------------------------------------------- 50 ONDXKey::ONDXKey(const ORowSetValue& rVal, sal_Int32 eType, sal_uInt32 nRec) 51 : ONDXKey_BASE(eType) 52 , nRecord(nRec) 53 , xValue(rVal) 54 { 55 } 56 // ----------------------------------------------------------------------------- 57 ONDXKey::ONDXKey(const rtl::OUString& aStr, sal_uInt32 nRec) 58 : ONDXKey_BASE(::com::sun::star::sdbc::DataType::VARCHAR) 59 ,nRecord(nRec) 60 { 61 if (aStr.getLength()) 62 { 63 xValue = aStr; 64 xValue.setBound(sal_True); 65 } 66 } 67 // ----------------------------------------------------------------------------- 68 69 ONDXKey::ONDXKey(double aVal, sal_uInt32 nRec) 70 : ONDXKey_BASE(::com::sun::star::sdbc::DataType::DOUBLE) 71 ,nRecord(nRec) 72 ,xValue(aVal) 73 { 74 } 75 // ----------------------------------------------------------------------------- 76 77 //================================================================== 78 // Index Seite 79 //================================================================== 80 ONDXPage::ONDXPage(ODbaseIndex& rInd, sal_uInt32 nPos, ONDXPage* pParent) 81 :nPagePos(nPos) 82 ,bModified(sal_False) 83 ,nCount(0) 84 ,aParent(pParent) 85 ,rIndex(rInd) 86 ,ppNodes(NULL) 87 { 88 sal_uInt16 nT = rIndex.getHeader().db_maxkeys; 89 ppNodes = new ONDXNode[nT]; 90 } 91 92 //------------------------------------------------------------------ 93 ONDXPage::~ONDXPage() 94 { 95 delete[] ppNodes; 96 // delete aParent; 97 // delete aChild; 98 } 99 //------------------------------------------------------------------ 100 void ONDXPage::QueryDelete() 101 { 102 // Ablegen im GarbageCollector 103 if (IsModified() && rIndex.m_pFileStream) 104 (*rIndex.m_pFileStream) << *this; 105 106 bModified = sal_False; 107 if (rIndex.UseCollector()) 108 { 109 if (aChild.Is()) 110 aChild->Release(sal_False); 111 112 for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++) 113 { 114 if (ppNodes[i].GetChild().Is()) 115 ppNodes[i].GetChild()->Release(sal_False); 116 117 ppNodes[i] = ONDXNode(); 118 } 119 RestoreNoDelete(); 120 121 nCount = 0; 122 aParent.Clear(); 123 rIndex.Collect(this); 124 } 125 else 126 SvRefBase::QueryDelete(); 127 } 128 //------------------------------------------------------------------ 129 ONDXPagePtr& ONDXPage::GetChild(ODbaseIndex* pIndex) 130 { 131 if (!aChild.Is() && pIndex) 132 { 133 aChild = rIndex.CreatePage(aChild.GetPagePos(),this,aChild.HasPage()); 134 } 135 return aChild; 136 } 137 138 //------------------------------------------------------------------ 139 sal_uInt16 ONDXPage::FindPos(const ONDXKey& rKey) const 140 { 141 // sucht nach Platz fuer den vorgegeben key auf einer Seite 142 sal_uInt16 i = 0; 143 while (i < nCount && rKey > ((*this)[i]).GetKey()) 144 i++; 145 146 return i; 147 } 148 149 //------------------------------------------------------------------ 150 sal_Bool ONDXPage::Find(const ONDXKey& rKey) 151 { 152 // sucht den vorgegeben key 153 // Besonderheit: gelangt der Algorithmus ans Ende 154 // wird immer die aktuelle Seite und die Knotenposition vermerkt 155 // auf die die Bedingung <= zutrifft 156 // dieses findet beim Insert besondere Beachtung 157 sal_uInt16 i = 0; 158 while (i < nCount && rKey > ((*this)[i]).GetKey()) 159 i++; 160 161 sal_Bool bResult = sal_False; 162 163 if (!IsLeaf()) 164 { 165 // weiter absteigen 166 ONDXPagePtr aPage = (i==0) ? GetChild(&rIndex) : ((*this)[i-1]).GetChild(&rIndex, this); 167 bResult = aPage.Is() && aPage->Find(rKey); 168 } 169 else if (i == nCount) 170 { 171 rIndex.m_aCurLeaf = this; 172 rIndex.m_nCurNode = i - 1; 173 bResult = sal_False; 174 } 175 else 176 { 177 bResult = rKey == ((*this)[i]).GetKey(); 178 rIndex.m_aCurLeaf = this; 179 rIndex.m_nCurNode = bResult ? i : i - 1; 180 } 181 return bResult; 182 } 183 184 //------------------------------------------------------------------ 185 sal_Bool ONDXPage::Insert(ONDXNode& rNode, sal_uInt32 nRowsLeft) 186 { 187 // beim Erzeugen eines Index koennen auch mehrere Knoten eingefuegt werden 188 // diese sin dann aufsteigend sortiert 189 sal_Bool bAppend = nRowsLeft > 0; 190 if (IsFull()) 191 { 192 sal_Bool bResult = sal_True; 193 ONDXNode aSplitNode; 194 if (bAppend) 195 aSplitNode = rNode; 196 else 197 { 198 // merken des letzten Knotens 199 aSplitNode = (*this)[nCount-1]; 200 if(rNode.GetKey() <= aSplitNode.GetKey()) 201 { 202 203 // und damit habe ich im folgenden praktisch eine Node weniger 204 if (IsLeaf() && this == &rIndex.m_aCurLeaf) 205 { 206 // geht davon aus, dass der Knoten, auf dem die Bedingung (<=) 207 // zutrifft, als m_nCurNode gesetzt ist 208 --nCount; // (sonst bekomme ich u.U. Assertions und GPFs - 60593) 209 bResult = Insert(rIndex.m_nCurNode + 1, rNode); 210 } 211 else // Position unbekannt 212 { 213 sal_uInt16 nPos = NODE_NOTFOUND; 214 while (++nPos < nCount && rNode.GetKey() > ((*this)[nPos]).GetKey()) ; 215 216 --nCount; // (sonst bekomme ich u.U. Assertions und GPFs - 60593) 217 bResult = Insert(nPos, rNode); 218 } 219 220 // konnte der neue Knoten eingefuegt werden 221 if (!bResult) 222 { 223 nCount++; 224 aSplitNode = rNode; 225 } 226 } 227 else 228 aSplitNode = rNode; 229 } 230 231 sal_uInt32 nNewPagePos = rIndex.GetPageCount(); 232 sal_uInt32 nNewPageCount = nNewPagePos + 1; 233 234 // Herausgeloesten Knoten beim Vater einfuegen 235 if (!HasParent()) 236 { 237 // Kein Vater, dann neue Wurzel 238 ONDXPagePtr aNewRoot = rIndex.CreatePage(nNewPagePos + 1); 239 aNewRoot->SetChild(this); 240 241 rIndex.m_aRoot = aNewRoot; 242 rIndex.SetRootPos(nNewPagePos + 1); 243 rIndex.SetPageCount(++nNewPageCount); 244 } 245 246 // neues blatt erzeugen und Seite aufteilen 247 ONDXPagePtr aNewPage = rIndex.CreatePage(nNewPagePos,aParent); 248 rIndex.SetPageCount(nNewPageCount); 249 250 // wieviele Knoten weren noch eingefuegt 251 // kommen noch ausreichend, dann koennen die Seiten bis zum Rand vollgestopft werden 252 253 ONDXNode aInnerNode; 254 if (!IsLeaf() || nRowsLeft < (sal_uInt32)(rIndex.GetMaxNodes() / 2)) 255 aInnerNode = Split(*aNewPage); 256 else 257 { 258 aInnerNode = (*this)[nCount - 1]; 259 //aInnerNode = aSplitNode; 260 261 // Knoten zeigt auf neue Seite 262 aInnerNode.SetChild(aNewPage); 263 264 // innere Knoten haben keine Recordnummer 265 if (rIndex.isUnique()) 266 aInnerNode.GetKey().ResetRecord(); 267 268 // neue Seite zeigt nun auf Seite des herausgeloesten Knoten 269 if (!IsLeaf()) 270 aNewPage->SetChild(aInnerNode.GetChild()); 271 } 272 273 aNewPage->Append(aSplitNode); 274 ONDXPagePtr aTempParent = aParent; 275 if (IsLeaf()) 276 { 277 rIndex.m_aCurLeaf = aNewPage; 278 rIndex.m_nCurNode = rIndex.m_aCurLeaf->Count() - 1; 279 280 // Freigeben nicht benoetigter Seiten, danach besteht keine Referenz 281 // mehr auf die Seite, danach kann 'this' nicht mehr gueltig sein!!! 282 ReleaseFull(); 283 } 284 285 // Einfuegen des herausgeloesten Knotens 286 return aTempParent->Insert(aInnerNode); 287 } 288 else // Seite einfach weiter auffuellen 289 { 290 if (bAppend) 291 { 292 if (IsLeaf()) 293 rIndex.m_nCurNode = nCount - 1; 294 return Append(rNode); 295 } 296 else 297 { 298 sal_uInt16 nNodePos = FindPos(rNode.GetKey()); 299 if (IsLeaf()) 300 rIndex.m_nCurNode = nNodePos; 301 302 return Insert(nNodePos, rNode); 303 } 304 } 305 } 306 307 //------------------------------------------------------------------ 308 sal_Bool ONDXPage::Insert(sal_uInt16 nPos, ONDXNode& rNode) 309 { 310 sal_uInt16 nMaxCount = rIndex.getHeader().db_maxkeys; 311 if (nPos >= nMaxCount) 312 return sal_False; 313 314 if (nCount) 315 { 316 ++nCount; 317 // nach rechts verschieben 318 for (sal_uInt16 i = std::min((sal_uInt16)(nMaxCount-1), (sal_uInt16)(nCount-1)); nPos < i; --i) 319 (*this)[i] = (*this)[i-1]; 320 } 321 else 322 if (nCount < nMaxCount) 323 nCount++; 324 325 // einfuegen an der Position 326 ONDXNode& rInsertNode = (*this)[nPos]; 327 rInsertNode = rNode; 328 if (rInsertNode.GetChild().Is()) 329 { 330 rInsertNode.GetChild()->SetParent(this); 331 rNode.GetChild()->SetParent(this); 332 } 333 334 bModified = sal_True; 335 336 return sal_True; 337 } 338 339 //------------------------------------------------------------------ 340 sal_Bool ONDXPage::Append(ONDXNode& rNode) 341 { 342 DBG_ASSERT(!IsFull(), "kein Append moeglich"); 343 return Insert(nCount, rNode); 344 } 345 //------------------------------------------------------------------ 346 void ONDXPage::Release(sal_Bool bSave) 347 { 348 // freigeben der Pages 349 if (aChild.Is()) 350 aChild->Release(bSave); 351 352 // Pointer freigeben 353 aChild.Clear(); 354 355 for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++) 356 { 357 if (ppNodes[i].GetChild()) 358 ppNodes[i].GetChild()->Release(bSave); 359 360 ppNodes[i].GetChild().Clear(); 361 } 362 aParent = NULL; 363 } 364 //------------------------------------------------------------------ 365 void ONDXPage::ReleaseFull(sal_Bool bSave) 366 { 367 ONDXPagePtr aTempParent = aParent; 368 Release(bSave); 369 370 if (aTempParent.Is()) 371 { 372 // Freigeben nicht benoetigter Seiten, danach besteht keine Referenz 373 // mehr auf die Seite, danach kann 'this' nicht mehr gueltig sein!!! 374 sal_uInt16 nParentPos = aTempParent->Search(this); 375 if (nParentPos != NODE_NOTFOUND) 376 (*aTempParent)[nParentPos].GetChild().Clear(); 377 else 378 aTempParent->GetChild().Clear(); 379 } 380 } 381 //------------------------------------------------------------------ 382 sal_Bool ONDXPage::Delete(sal_uInt16 nNodePos) 383 { 384 if (IsLeaf()) 385 { 386 // Letztes Element wird geloescht 387 if (nNodePos == (nCount - 1)) 388 { 389 ONDXNode aNode = (*this)[nNodePos]; 390 391 // beim Parent muss nun der KeyValue ausgetauscht werden 392 if (HasParent()) 393 aParent->SearchAndReplace(aNode.GetKey(), 394 (*this)[nNodePos-1].GetKey()); 395 } 396 } 397 398 // Loeschen des Knoten 399 Remove(nNodePos); 400 401 // Unterlauf 402 if (HasParent() && nCount < (rIndex.GetMaxNodes() / 2)) 403 { 404 // Feststellen, welcher Knoten auf die Seite zeigt 405 sal_uInt16 nParentNodePos = aParent->Search(this); 406 // letzte Element auf Vaterseite 407 // -> zusammenlegen mit vorletzter Seite 408 if (nParentNodePos == (aParent->Count() - 1)) 409 { 410 if (!nParentNodePos) 411 // zusammenlegen mit linken nachbarn 412 Merge(nParentNodePos,aParent->GetChild(&rIndex)); 413 else 414 Merge(nParentNodePos,(*aParent)[nParentNodePos-1].GetChild(&rIndex,aParent)); 415 } 416 // sonst Seite mit naechster Seite zusammenlegen 417 else 418 { 419 // zusammenlegen mit rechten nachbarn 420 Merge(nParentNodePos + 1,((*aParent)[nParentNodePos + 1].GetChild(&rIndex,aParent))); 421 nParentNodePos++; 422 } 423 if (HasParent() && !(*aParent)[nParentNodePos].HasChild()) 424 aParent->Delete(nParentNodePos); 425 /* 426 // letzte Element auf Vaterseite 427 // -> zusammenlegen mit vorletzter Seite 428 if (nParentNodePos == (aParent->Count() - 1)) 429 { 430 if (!nParentNodePos) 431 // zusammenlegen mit linken nachbarn 432 Merge(nParentNodePos,aParent->GetChild(&rIndex)); 433 else 434 Merge(nParentNodePos,(*aParent)[nParentNodePos-1].GetChild(&rIndex,aParent)); 435 } 436 // sonst Seite mit naechster Seite zusammenlegen 437 else if(nParentNodePos != NODE_NOTFOUND) 438 { 439 // zusammenlegen mit rechten nachbarn 440 Merge(nParentNodePos + 1,((*aParent)[nParentNodePos + 1].GetChild(&rIndex,aParent))); 441 nParentNodePos++; 442 } 443 else // Sonderbehandlung 444 { 445 // Page ist aChild Page vom Parent => erste Page aus ppNodes an aChild anhaengen 446 Merge(0,(*aParent)[0].GetChild(&rIndex,aParent)); 447 nParentNodePos = 0; 448 } 449 450 if (HasParent() && !(*aParent)[nParentNodePos].HasChild()) 451 aParent->Delete(nParentNodePos); 452 */ 453 454 } 455 else if (IsRoot()) 456 // Sicherstellen das die Position der Wurzel festgehalten wird 457 rIndex.SetRootPos(nPagePos); 458 return sal_True; 459 } 460 461 462 //------------------------------------------------------------------ 463 ONDXNode ONDXPage::Split(ONDXPage& rPage) 464 { 465 DBG_ASSERT(IsFull(), "Falsches Splitting"); 466 /* Aufteilen einer Seite auf zwei 467 Blatt: 468 Seite 1 behaelt (n - (n/2)) 469 Seite 2 erhaelt (n/2) 470 Knoten n/2 wird dupliziert 471 Innerer Knoten: 472 Seite 1 behaelt (n+1)/2 473 Seite 2 erhaelt (n/2-1) 474 Knoten ((n+1)/2 + 1) : wird herausgenommen 475 */ 476 ONDXNode aResultNode; 477 if (IsLeaf()) 478 { 479 for (sal_uInt16 i = (nCount - (nCount / 2)), j = 0 ; i < nCount; i++) 480 rPage.Insert(j++,(*this)[i]); 481 482 // dieser Knoten enthaelt einen Schluessel der noch einmal im Tree vorkommt 483 // und ersetzt werden muss 484 ONDXNode aLastNode = (*this)[nCount - 1]; 485 nCount = nCount - (nCount / 2); 486 aResultNode = (*this)[nCount - 1]; 487 488 if (HasParent()) 489 aParent->SearchAndReplace(aLastNode.GetKey(), 490 aResultNode.GetKey()); 491 } 492 else 493 { 494 for (sal_uInt16 i = (nCount + 1) / 2 + 1, j = 0 ; i < nCount; i++) 495 rPage.Insert(j++,(*this)[i]); 496 497 aResultNode = (*this)[(nCount + 1) / 2]; 498 nCount = (nCount + 1) / 2; 499 500 // neue Seite zeigt nun auf Seite des herausgeloesten Knoten 501 rPage.SetChild(aResultNode.GetChild()); 502 } 503 // Knoten zeigt auf neue Seite 504 aResultNode.SetChild(&rPage); 505 506 // innere Knoten haben keine Recordnummer 507 if (rIndex.isUnique()) 508 aResultNode.GetKey().ResetRecord(); 509 bModified = sal_True; 510 return aResultNode; 511 } 512 513 //------------------------------------------------------------------ 514 void ONDXPage::Merge(sal_uInt16 nParentNodePos, ONDXPagePtr xPage) 515 { 516 DBG_ASSERT(HasParent(), "kein Vater vorhanden"); 517 DBG_ASSERT(nParentNodePos != NODE_NOTFOUND, "Falscher Indexaufbau"); 518 519 /* Zusammenlegen zweier Seiten */ 520 ONDXNode aResultNode; 521 sal_uInt16 nMaxNodes = rIndex.GetMaxNodes(), 522 nMaxNodes_2 = nMaxNodes / 2; 523 524 // Feststellen ob Seite rechter oder linker Nachbar 525 sal_Bool bRight = ((*xPage)[0].GetKey() > (*this)[0].GetKey()); // sal_True, wenn xPage die rechte Seite ist 526 sal_uInt16 nNewCount = (*xPage).Count() + Count(); 527 528 if (IsLeaf()) 529 { 530 // Bedingung fuers zusammenlegen 531 if (nNewCount < (nMaxNodes_2 * 2)) 532 { 533 sal_uInt16 nLastNode = bRight ? Count() - 1 : xPage->Count() - 1; 534 if (bRight) 535 { 536 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife"); 537 // alle Knoten aus xPage auf den linken Knoten verschieben (anhaengen) 538 while (xPage->Count()) 539 { 540 Append((*xPage)[0]); 541 xPage->Remove(0); 542 } 543 } 544 else 545 { 546 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife"); 547 // xPage ist die linke Page und THIS die rechte 548 while (xPage->Count()) 549 { 550 Insert(0,(*xPage)[xPage->Count()-1]); 551 xPage->Remove(xPage->Count()-1); 552 } 553 // alte Position von xPage beim Parent mit this ersetzen 554 if (nParentNodePos) 555 (*aParent)[nParentNodePos-1].SetChild(this,aParent); 556 else // oder als rechten Knoten setzen 557 aParent->SetChild(this); 558 aParent->SetModified(sal_True); 559 560 } 561 562 // Child beziehung beim Vaterknoten aufheben 563 (*aParent)[nParentNodePos].SetChild(); 564 // Austauschen des KnotenWertes, nur wenn geaenderte Page 565 // die linke ist, ansonsten werde 566 567 if(aParent->IsRoot() && aParent->Count() == 1) 568 { 569 (*aParent)[0].SetChild(); 570 aParent->ReleaseFull(); 571 aParent = NULL; 572 rIndex.SetRootPos(nPagePos); 573 rIndex.m_aRoot = this; 574 SetModified(sal_True); 575 } 576 else 577 aParent->SearchAndReplace((*this)[nLastNode].GetKey(),(*this)[nCount-1].GetKey()); 578 579 xPage->SetModified(sal_False); 580 xPage->ReleaseFull(); // wird nicht mehr benoetigt 581 } 582 // Ausgleichen der Elemente nNewCount >= (nMaxNodes_2 * 2) 583 else 584 { 585 if (bRight) 586 { 587 // alle Knoten aus xPage auf den linken Knoten verschieben (anhaengen) 588 ONDXNode aReplaceNode = (*this)[nCount - 1]; 589 while (nCount < nMaxNodes_2) 590 { 591 Append((*xPage)[0]); 592 xPage->Remove(0); 593 } 594 // Austauschen des KnotenWertes: Setzt alten letzten Wert durch den letzten von xPage 595 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[nCount-1].GetKey()); 596 } 597 else 598 { 599 // alle Knoten aus this vor die xPage Knoten einfuegen 600 ONDXNode aReplaceNode = (*this)[nCount - 1]; 601 while (xPage->Count() < nMaxNodes_2) 602 { 603 xPage->Insert(0,(*this)[nCount-1]); 604 Remove(nCount-1); 605 } 606 // Austauschen des KnotenWertes 607 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[Count()-1].GetKey()); 608 } 609 } 610 } 611 else // !IsLeaf() 612 { 613 // Bedingung fuers zusammenlegen 614 if (nNewCount < nMaxNodes_2 * 2) 615 { 616 if (bRight) 617 { 618 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife"); 619 // Vaterknoten wird mit integriert 620 // erhaelt zunaechst Child von xPage 621 (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent); 622 Append((*aParent)[nParentNodePos]); 623 for (sal_uInt16 i = 0 ; i < xPage->Count(); i++) 624 Append((*xPage)[i]); 625 } 626 else 627 { 628 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife"); 629 // Vaterknoten wird mit integriert 630 // erhaelt zunaechst Child 631 (*aParent)[nParentNodePos].SetChild(GetChild(),aParent); // Parent merkt sich mein Child 632 Insert(0,(*aParent)[nParentNodePos]); // Node vom Parent bei mir einfuegen 633 while (xPage->Count()) 634 { 635 Insert(0,(*xPage)[xPage->Count()-1]); 636 xPage->Remove(xPage->Count()-1); 637 } 638 SetChild(xPage->GetChild()); 639 640 if (nParentNodePos) 641 (*aParent)[nParentNodePos-1].SetChild(this,aParent); 642 else 643 aParent->SetChild(this); 644 } 645 646 // danach wird der Vaterknoten zurueckgesetzt 647 (*aParent)[nParentNodePos].SetChild(); 648 aParent->SetModified(sal_True); 649 650 if(aParent->IsRoot() && aParent->Count() == 1) 651 { 652 (*aParent).SetChild(); 653 aParent->ReleaseFull(); 654 aParent = NULL; 655 rIndex.SetRootPos(nPagePos); 656 rIndex.m_aRoot = this; 657 SetModified(sal_True); 658 } 659 else if(nParentNodePos) 660 // Austauschen des KnotenWertes 661 // beim Append wird der Bereich erweitert, beim INsert verweist der alte Knoten von xPage auf this 662 // deshalb muss der Knoten auch hier aktualisiert werden 663 aParent->SearchAndReplace((*aParent)[nParentNodePos-1].GetKey(),(*aParent)[nParentNodePos].GetKey()); 664 665 xPage->SetModified(sal_False); 666 xPage->ReleaseFull(); 667 } 668 // Ausgleichen der Elemente 669 else 670 { 671 if (bRight) 672 { 673 while (nCount < nMaxNodes_2) 674 { 675 (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent); 676 Append((*aParent)[nParentNodePos]); 677 (*aParent)[nParentNodePos] = (*xPage)[0]; 678 xPage->Remove(0); 679 } 680 xPage->SetChild((*aParent)[nParentNodePos].GetChild()); 681 (*aParent)[nParentNodePos].SetChild(xPage,aParent); 682 } 683 else 684 { 685 while (nCount < nMaxNodes_2) 686 { 687 (*aParent)[nParentNodePos].SetChild(GetChild(),aParent); 688 Insert(0,(*aParent)[nParentNodePos]); 689 (*aParent)[nParentNodePos] = (*xPage)[xPage->Count()-1]; 690 xPage->Remove(xPage->Count()-1); 691 } 692 SetChild((*aParent)[nParentNodePos].GetChild()); 693 (*aParent)[nParentNodePos].SetChild(this,aParent); 694 695 } 696 aParent->SetModified(sal_True); 697 } 698 } 699 } 700 //================================================================== 701 // ONDXNode 702 //================================================================== 703 704 //------------------------------------------------------------------ 705 void ONDXNode::Read(SvStream &rStream, ODbaseIndex& rIndex) 706 { 707 rStream >> aKey.nRecord; // schluessel 708 709 if (rIndex.getHeader().db_keytype) 710 { 711 double aDbl; 712 rStream >> aDbl; 713 aKey = ONDXKey(aDbl,aKey.nRecord); 714 } 715 else 716 { 717 ByteString aBuf; 718 sal_uInt16 nLen = rIndex.getHeader().db_keylen; 719 char* pStr = aBuf.AllocBuffer(nLen+1); 720 721 rStream.Read(pStr,nLen); 722 pStr[nLen] = 0; 723 aBuf.ReleaseBufferAccess(); 724 aBuf.EraseTrailingChars(); 725 726 // aKey = ONDXKey((aBuf,rIndex.GetDBFConnection()->GetCharacterSet()) ,aKey.nRecord); 727 aKey = ONDXKey(::rtl::OUString(aBuf.GetBuffer(),aBuf.Len(),rIndex.m_pTable->getConnection()->getTextEncoding()) ,aKey.nRecord); 728 } 729 rStream >> aChild; 730 } 731 732 union NodeData 733 { 734 double aDbl; 735 char aData[128]; 736 } aNodeData; 737 //------------------------------------------------------------------ 738 void ONDXNode::Write(SvStream &rStream, const ONDXPage& rPage) const 739 { 740 const ODbaseIndex& rIndex = rPage.GetIndex(); 741 if (!rIndex.isUnique() || rPage.IsLeaf()) 742 rStream << (sal_uInt32)aKey.nRecord; // schluessel 743 else 744 rStream << (sal_uInt32)0; // schluessel 745 746 if (rIndex.getHeader().db_keytype) // double 747 { 748 if (aKey.getValue().isNull()) 749 { 750 memset(aNodeData.aData,0,rIndex.getHeader().db_keylen); 751 rStream.Write((sal_uInt8*)aNodeData.aData,rIndex.getHeader().db_keylen); 752 } 753 else 754 rStream << (double) aKey.getValue(); 755 } 756 else 757 { 758 memset(aNodeData.aData,0x20,rIndex.getHeader().db_keylen); 759 if (!aKey.getValue().isNull()) 760 { 761 ::rtl::OUString sValue = aKey.getValue(); 762 ByteString aText(sValue.getStr(), rIndex.m_pTable->getConnection()->getTextEncoding()); 763 strncpy(aNodeData.aData,aText.GetBuffer(),std::min(rIndex.getHeader().db_keylen, aText.Len())); 764 } 765 rStream.Write((sal_uInt8*)aNodeData.aData,rIndex.getHeader().db_keylen); 766 } 767 rStream << aChild; 768 } 769 770 771 //------------------------------------------------------------------ 772 ONDXPagePtr& ONDXNode::GetChild(ODbaseIndex* pIndex, ONDXPage* pParent) 773 { 774 if (!aChild.Is() && pIndex) 775 { 776 aChild = pIndex->CreatePage(aChild.GetPagePos(),pParent,aChild.HasPage()); 777 } 778 return aChild; 779 } 780 781 //================================================================== 782 // ONDXKey 783 //================================================================== 784 //------------------------------------------------------------------ 785 sal_Bool ONDXKey::IsText(sal_Int32 eType) 786 { 787 return eType == DataType::VARCHAR || eType == DataType::CHAR; 788 } 789 790 //------------------------------------------------------------------ 791 StringCompare ONDXKey::Compare(const ONDXKey& rKey) const 792 { 793 // DBG_ASSERT(is(), "Falscher Indexzugriff"); 794 StringCompare eResult; 795 796 if (getValue().isNull()) 797 { 798 if (rKey.getValue().isNull() || (rKey.IsText(getDBType()) && !rKey.getValue().getString().getLength())) 799 eResult = COMPARE_EQUAL; 800 else 801 eResult = COMPARE_LESS; 802 } 803 else if (rKey.getValue().isNull()) 804 { 805 if (getValue().isNull() || (IsText(getDBType()) && !getValue().getString().getLength())) 806 eResult = COMPARE_EQUAL; 807 else 808 eResult = COMPARE_GREATER; 809 } 810 else if (IsText(getDBType())) 811 { 812 sal_Int32 nRes = getValue().getString().compareTo(rKey.getValue()); 813 eResult = (nRes > 0) ? COMPARE_GREATER : (nRes == 0) ? COMPARE_EQUAL : COMPARE_LESS; 814 } 815 else 816 { 817 double m = getValue(),n = rKey.getValue(); 818 eResult = (m > n) ? COMPARE_GREATER : (n == m) ? COMPARE_EQUAL : COMPARE_LESS; 819 } 820 821 // Record vergleich, wenn Index !Unique 822 if (eResult == COMPARE_EQUAL && nRecord && rKey.nRecord) 823 eResult = (nRecord > rKey.nRecord) ? COMPARE_GREATER : 824 (nRecord == rKey.nRecord) ? COMPARE_EQUAL : COMPARE_LESS; 825 826 return eResult; 827 } 828 // ----------------------------------------------------------------------------- 829 void ONDXKey::setValue(const ORowSetValue& _rVal) 830 { 831 xValue = _rVal; 832 } 833 // ----------------------------------------------------------------------------- 834 const ORowSetValue& ONDXKey::getValue() const 835 { 836 return xValue; 837 } 838 // ----------------------------------------------------------------------------- 839 SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPagePtr& rPage) 840 { 841 rStream >> rPage.nPagePos; 842 return rStream; 843 } 844 // ----------------------------------------------------------------------------- 845 SvStream& connectivity::dbase::operator << (SvStream &rStream, const ONDXPagePtr& rPage) 846 { 847 rStream << rPage.nPagePos; 848 return rStream; 849 } 850 // ----------------------------------------------------------------------------- 851 //================================================================== 852 // ONDXPagePtr 853 //================================================================== 854 //------------------------------------------------------------------ 855 ONDXPagePtr::ONDXPagePtr(const ONDXPagePtr& rRef) 856 :ONDXPageRef(rRef) 857 ,nPagePos(rRef.nPagePos) 858 { 859 } 860 861 //------------------------------------------------------------------ 862 ONDXPagePtr::ONDXPagePtr(ONDXPage* pRefPage) 863 :ONDXPageRef(pRefPage) 864 ,nPagePos(0) 865 { 866 if (pRefPage) 867 nPagePos = pRefPage->GetPagePos(); 868 } 869 //------------------------------------------------------------------ 870 ONDXPagePtr& ONDXPagePtr::operator=(const ONDXPagePtr& rRef) 871 { 872 ONDXPageRef::operator=(rRef); 873 nPagePos = rRef.nPagePos; 874 return *this; 875 } 876 877 //------------------------------------------------------------------ 878 ONDXPagePtr& ONDXPagePtr::operator= (ONDXPage* pRef) 879 { 880 ONDXPageRef::operator=(pRef); 881 nPagePos = (pRef) ? pRef->GetPagePos() : 0; 882 return *this; 883 } 884 // ----------------------------------------------------------------------------- 885 static sal_uInt32 nValue; 886 //------------------------------------------------------------------ 887 SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPage& rPage) 888 { 889 rStream.Seek(rPage.GetPagePos() * PAGE_SIZE); 890 rStream >> nValue >> rPage.aChild; 891 rPage.nCount = sal_uInt16(nValue); 892 893 // DBG_ASSERT(rPage.nCount && rPage.nCount < rPage.GetIndex().GetMaxNodes(), "Falscher Count"); 894 for (sal_uInt16 i = 0; i < rPage.nCount; i++) 895 rPage[i].Read(rStream, rPage.GetIndex()); 896 return rStream; 897 } 898 899 //------------------------------------------------------------------ 900 SvStream& connectivity::dbase::operator << (SvStream &rStream, const ONDXPage& rPage) 901 { 902 // Seite existiert noch nicht 903 sal_uIntPtr nSize = (rPage.GetPagePos() + 1) * PAGE_SIZE; 904 if (nSize > rStream.Seek(STREAM_SEEK_TO_END)) 905 { 906 rStream.SetStreamSize(nSize); 907 rStream.Seek(rPage.GetPagePos() * PAGE_SIZE); 908 909 char aEmptyData[PAGE_SIZE]; 910 memset(aEmptyData,0x00,PAGE_SIZE); 911 rStream.Write((sal_uInt8*)aEmptyData,PAGE_SIZE); 912 } 913 sal_uIntPtr nCurrentPos = rStream.Seek(rPage.GetPagePos() * PAGE_SIZE); 914 OSL_UNUSED( nCurrentPos ); 915 916 nValue = rPage.nCount; 917 rStream << nValue << rPage.aChild; 918 919 sal_uInt16 i = 0; 920 for (; i < rPage.nCount; i++) 921 rPage[i].Write(rStream, rPage); 922 923 // check if we have to fill the stream with '\0' 924 if(i < rPage.rIndex.getHeader().db_maxkeys) 925 { 926 sal_uIntPtr nTell = rStream.Tell() % PAGE_SIZE; 927 sal_uInt16 nBufferSize = rStream.GetBufferSize(); 928 sal_uIntPtr nRemainSize = nBufferSize - nTell; 929 if ( nRemainSize <= nBufferSize ) 930 { 931 char* pEmptyData = new char[nRemainSize]; 932 memset(pEmptyData,0x00,nRemainSize); 933 rStream.Write((sal_uInt8*)pEmptyData,nRemainSize); 934 rStream.Seek(nTell); 935 delete [] pEmptyData; 936 } 937 } 938 return rStream; 939 } 940 // ----------------------------------------------------------------------------- 941 #if OSL_DEBUG_LEVEL > 1 942 //------------------------------------------------------------------ 943 void ONDXPage::PrintPage() 944 { 945 DBG_TRACE4("\nSDB: -----------Page: %d Parent: %d Count: %d Child: %d-----", 946 nPagePos, HasParent() ? aParent->GetPagePos() : 0 ,nCount, aChild.GetPagePos()); 947 948 for (sal_uInt16 i = 0; i < nCount; i++) 949 { 950 ONDXNode rNode = (*this)[i]; 951 ONDXKey& rKey = rNode.GetKey(); 952 if (!IsLeaf()) 953 rNode.GetChild(&rIndex, this); 954 955 if (rKey.getValue().isNull()) 956 { 957 DBG_TRACE2("SDB: [%d,NULL,%d]",rKey.GetRecord(), rNode.GetChild().GetPagePos()); 958 } 959 else if (rIndex.getHeader().db_keytype) 960 { 961 DBG_TRACE3("SDB: [%d,%f,%d]",rKey.GetRecord(), rKey.getValue().getDouble(),rNode.GetChild().GetPagePos()); 962 } 963 else 964 { 965 DBG_TRACE3("SDB: [%d,%s,%d]",rKey.GetRecord(), (const char* )ByteString(rKey.getValue().getString().getStr(), rIndex.m_pTable->getConnection()->getTextEncoding()).GetBuffer(),rNode.GetChild().GetPagePos()); 966 } 967 } 968 DBG_TRACE("SDB: -----------------------------------------------\n"); 969 if (!IsLeaf()) 970 { 971 #if OSL_DEBUG_LEVEL > 1 972 GetChild(&rIndex)->PrintPage(); 973 for (sal_uInt16 i = 0; i < nCount; i++) 974 { 975 ONDXNode rNode = (*this)[i]; 976 rNode.GetChild(&rIndex,this)->PrintPage(); 977 } 978 #endif 979 } 980 DBG_TRACE("SDB: ===============================================\n"); 981 } 982 #endif 983 // ----------------------------------------------------------------------------- 984 sal_Bool ONDXPage::IsFull() const 985 { 986 return Count() == rIndex.getHeader().db_maxkeys; 987 } 988 // ----------------------------------------------------------------------------- 989 //------------------------------------------------------------------ 990 sal_uInt16 ONDXPage::Search(const ONDXKey& rSearch) 991 { 992 // binare Suche spaeter 993 sal_uInt16 i = NODE_NOTFOUND; 994 while (++i < Count()) 995 if ((*this)[i].GetKey() == rSearch) 996 break; 997 998 return (i < Count()) ? i : NODE_NOTFOUND; 999 } 1000 1001 //------------------------------------------------------------------ 1002 sal_uInt16 ONDXPage::Search(const ONDXPage* pPage) 1003 { 1004 sal_uInt16 i = NODE_NOTFOUND; 1005 while (++i < Count()) 1006 if (((*this)[i]).GetChild() == pPage) 1007 break; 1008 1009 // wenn nicht gefunden, dann wird davon ausgegangen, dass die Seite selbst 1010 // auf die Page zeigt 1011 return (i < Count()) ? i : NODE_NOTFOUND; 1012 } 1013 // ----------------------------------------------------------------------------- 1014 // laeuft rekursiv 1015 void ONDXPage::SearchAndReplace(const ONDXKey& rSearch, 1016 ONDXKey& rReplace) 1017 { 1018 OSL_ENSURE(rSearch != rReplace,"Invalid here:rSearch == rReplace"); 1019 if (rSearch != rReplace) 1020 { 1021 sal_uInt16 nPos = NODE_NOTFOUND; 1022 ONDXPage* pPage = this; 1023 1024 while (pPage && (nPos = pPage->Search(rSearch)) == NODE_NOTFOUND) 1025 pPage = pPage->aParent; 1026 1027 if (pPage) 1028 { 1029 (*pPage)[nPos].GetKey() = rReplace; 1030 pPage->SetModified(sal_True); 1031 } 1032 } 1033 } 1034 // ----------------------------------------------------------------------------- 1035 ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos) 1036 { 1037 DBG_ASSERT(nCount > nPos, "falscher Indexzugriff"); 1038 return ppNodes[nPos]; 1039 } 1040 1041 //------------------------------------------------------------------ 1042 const ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos) const 1043 { 1044 DBG_ASSERT(nCount > nPos, "falscher Indexzugriff"); 1045 return ppNodes[nPos]; 1046 } 1047 // ----------------------------------------------------------------------------- 1048 void ONDXPage::Remove(sal_uInt16 nPos) 1049 { 1050 DBG_ASSERT(nCount > nPos, "falscher Indexzugriff"); 1051 1052 for (sal_uInt16 i = nPos; i < (nCount-1); i++) 1053 (*this)[i] = (*this)[i+1]; 1054 1055 nCount--; 1056 bModified = sal_True; 1057 } 1058 // ----------------------------------------------------------------------------- 1059 1060