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