connectivity/source/drivers/dbase/dindexnode.cxx

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