connectivity/source/drivers/dbase/dindexnode.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*************************************************************************
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * Copyright 2000, 2010 Oracle and/or its affiliates.
   7  *
   8  * OpenOffice.org - a multi-platform office productivity suite
   9  *
  10  * This file is part of OpenOffice.org.
  11  *
  12  * OpenOffice.org is free software: you can redistribute it and/or modify
  13  * it under the terms of the GNU Lesser General Public License version 3
  14  * only, as published by the Free Software Foundation.
  15  *
  16  * OpenOffice.org is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU Lesser General Public License version 3 for more details
  20  * (a copy is included in the LICENSE file that accompanied this code).
  21  *
  22  * You should have received a copy of the GNU Lesser General Public License
  23  * version 3 along with OpenOffice.org.  If not, see
  24  * <http://www.openoffice.org/license.html>
  25  * for a copy of the LGPLv3 License.
  26  *
  27  ************************************************************************/
  28
  29 #include "dbase/dindexnode.hxx"
  30 #include "connectivity/CommonTools.hxx"
  31 #include <osl/thread.h>
  32 #include "dbase/DIndex.hxx"
  33 #include <tools/debug.hxx>
  34 #include "diagnose_ex.h"
  35
  36 #include <algorithm>
  37 #include <boost/scoped_array.hpp>
  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.isEmpty())
  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 page
  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 }
  97 //------------------------------------------------------------------
  98 void ONDXPage::QueryDelete()
  99 {
 100     // Store in GarbageCollector
 101     if (IsModified() && rIndex.m_pFileStream)
 102         (*rIndex.m_pFileStream) << *this;
 103
 104     bModified = sal_False;
 105     if (rIndex.UseCollector())
 106     {
 107         if (aChild.Is())
 108             aChild->Release(sal_False);
 109
 110         for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
 111         {
 112             if (ppNodes[i].GetChild().Is())
 113                 ppNodes[i].GetChild()->Release(sal_False);
 114
 115             ppNodes[i] = ONDXNode();
 116         }
 117         RestoreNoDelete();
 118
 119         nCount = 0;
 120         aParent.Clear();
 121         rIndex.Collect(this);
 122     }
 123     else
 124         SvRefBase::QueryDelete();
 125 }
 126 //------------------------------------------------------------------
 127 ONDXPagePtr& ONDXPage::GetChild(ODbaseIndex* pIndex)
 128 {
 129     if (!aChild.Is() && pIndex)
 130     {
 131         aChild = rIndex.CreatePage(aChild.GetPagePos(),this,aChild.HasPage());
 132     }
 133     return aChild;
 134 }
 135
 136 //------------------------------------------------------------------
 137 sal_uInt16 ONDXPage::FindPos(const ONDXKey& rKey) const
 138 {
 139     // searches the position for the given key in a page
 140     sal_uInt16 i = 0;
 141     while (i < nCount && rKey > ((*this)[i]).GetKey())
 142            i++;
 143
 144     return i;
 145 }
 146
 147 //------------------------------------------------------------------
 148 sal_Bool ONDXPage::Find(const ONDXKey& rKey)
 149 {
 150     // searches the given key
 151     // Speciality: At the end of the method
 152     // the actual page and the position of the node, fulfilling the '<=' condition, are saved
 153     // This is considered at insert.
 154     sal_uInt16 i = 0;
 155     while (i < nCount && rKey > ((*this)[i]).GetKey())
 156            i++;
 157
 158     sal_Bool bResult = sal_False;
 159
 160     if (!IsLeaf())
 161     {
 162         // descend further
 163         ONDXPagePtr aPage = (i==0) ? GetChild(&rIndex) : ((*this)[i-1]).GetChild(&rIndex, this);
 164         bResult = aPage.Is() && aPage->Find(rKey);
 165     }
 166     else if (i == nCount)
 167     {
 168         rIndex.m_aCurLeaf = this;
 169         rIndex.m_nCurNode = i - 1;
 170         bResult = sal_False;
 171     }
 172     else
 173     {
 174         bResult = rKey == ((*this)[i]).GetKey();
 175         rIndex.m_aCurLeaf = this;
 176         rIndex.m_nCurNode = bResult ? i : i - 1;
 177     }
 178     return bResult;
 179 }
 180
 181 //------------------------------------------------------------------
 182 sal_Bool ONDXPage::Insert(ONDXNode& rNode, sal_uInt32 nRowsLeft)
 183 {
 184     // When creating an index there can be multiple nodes added,
 185     // these are sorted ascending
 186     sal_Bool bAppend = nRowsLeft > 0;
 187     if (IsFull())
 188     {
 189         sal_Bool bResult = sal_True;
 190         ONDXNode aSplitNode;
 191         if (bAppend)
 192             aSplitNode = rNode;
 193         else
 194         {
 195             // Save the last node
 196             aSplitNode = (*this)[nCount-1];
 197             if(rNode.GetKey() <= aSplitNode.GetKey())
 198             {
 199
 200                 // this practically reduces the number of nodes by 1
 201                 if (IsLeaf() && this == &rIndex.m_aCurLeaf)
 202                 {
 203                     // assumes, that the node, for which the condition (<=) holds, is stored in m_nCurNode
 204                     --nCount;   // (otherwise we might get Assertions and GPFs - 60593)
 205                     bResult = Insert(rIndex.m_nCurNode + 1, rNode);
 206                 }
 207                 else  // position unknown
 208                 {
 209                     sal_uInt16 nPos = NODE_NOTFOUND;
 210                     while (++nPos < nCount && rNode.GetKey() > ((*this)[nPos]).GetKey()) ;
 211
 212                     --nCount;   // (otherwise we might get Assertions and GPFs - 60593)
 213                     bResult = Insert(nPos, rNode);
 214                 }
 215
 216                 // can the new node be inserted
 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         // insert extracted node into parent node
 231         if (!HasParent())
 232         {
 233             // No parent, then new root
 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         // create new leaf and divide page
 243         ONDXPagePtr aNewPage = rIndex.CreatePage(nNewPagePos,aParent);
 244         rIndex.SetPageCount(nNewPageCount);
 245
 246         // How many nodes are being inserted?
 247         // Enough, then we can fill the page to the brim
 248         ONDXNode aInnerNode;
 249         if (!IsLeaf() || nRowsLeft < (sal_uInt32)(rIndex.GetMaxNodes() / 2))
 250             aInnerNode = Split(*aNewPage);
 251         else
 252         {
 253             aInnerNode = (*this)[nCount - 1];
 254
 255             // Node points to the new page
 256             aInnerNode.SetChild(aNewPage);
 257
 258             // Inner nodes have no record number
 259             if (rIndex.isUnique())
 260                 aInnerNode.GetKey().ResetRecord();
 261
 262             // new page points to the page of the extracted node
 263             if (!IsLeaf())
 264                 aNewPage->SetChild(aInnerNode.GetChild());
 265         }
 266
 267         aNewPage->Append(aSplitNode);
 268         ONDXPagePtr aTempParent = aParent;
 269         if (IsLeaf())
 270         {
 271             rIndex.m_aCurLeaf = aNewPage;
 272             rIndex.m_nCurNode = rIndex.m_aCurLeaf->Count() - 1;
 273
 274             // free not needed pages, there are no references to those on the page
 275             // afterwards 'this' can't be valid anymore!!!
 276             ReleaseFull();
 277         }
 278
 279         // Insert extracted node
 280         return aTempParent->Insert(aInnerNode);
 281     }
 282     else // Fill the page up
 283     {
 284         if (bAppend)
 285         {
 286             if (IsLeaf())
 287                 rIndex.m_nCurNode = nCount - 1;
 288             return Append(rNode);
 289         }
 290         else
 291         {
 292             sal_uInt16 nNodePos = FindPos(rNode.GetKey());
 293             if (IsLeaf())
 294                 rIndex.m_nCurNode = nNodePos;
 295
 296             return Insert(nNodePos, rNode);
 297         }
 298     }
 299 }
 300
 301 //------------------------------------------------------------------
 302 sal_Bool ONDXPage::Insert(sal_uInt16 nPos, ONDXNode& rNode)
 303 {
 304     sal_uInt16 nMaxCount = rIndex.getHeader().db_maxkeys;
 305     if (nPos >= nMaxCount)
 306         return sal_False;
 307
 308     if (nCount)
 309     {
 310         ++nCount;
 311         // shift right
 312         for (sal_uInt16 i = std::min((sal_uInt16)(nMaxCount-1), (sal_uInt16)(nCount-1)); nPos < i; --i)
 313             (*this)[i] = (*this)[i-1];
 314     }
 315     else
 316         if (nCount < nMaxCount)
 317             nCount++;
 318
 319     // insert at the position
 320     ONDXNode& rInsertNode = (*this)[nPos];
 321     rInsertNode = rNode;
 322     if (rInsertNode.GetChild().Is())
 323     {
 324         rInsertNode.GetChild()->SetParent(this);
 325         rNode.GetChild()->SetParent(this);
 326     }
 327
 328     bModified = sal_True;
 329
 330     return sal_True;
 331 }
 332
 333 //------------------------------------------------------------------
 334 sal_Bool ONDXPage::Append(ONDXNode& rNode)
 335 {
 336     DBG_ASSERT(!IsFull(), "kein Append moeglich");
 337     return Insert(nCount, rNode);
 338 }
 339 //------------------------------------------------------------------
 340 void ONDXPage::Release(sal_Bool bSave)
 341 {
 342     // free pages
 343     if (aChild.Is())
 344         aChild->Release(bSave);
 345
 346     // free pointer
 347     aChild.Clear();
 348
 349     for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
 350     {
 351         if (ppNodes[i].GetChild())
 352             ppNodes[i].GetChild()->Release(bSave);
 353
 354         ppNodes[i].GetChild().Clear();
 355     }
 356     aParent = NULL;
 357 }
 358 //------------------------------------------------------------------
 359 void ONDXPage::ReleaseFull(sal_Bool bSave)
 360 {
 361     ONDXPagePtr aTempParent = aParent;
 362     Release(bSave);
 363
 364     if (aTempParent.Is())
 365     {
 366         // Free pages not needed, there will be no reference anymore to the pages
 367         // afterwards 'this' can't be valid anymore!!!
 368         sal_uInt16 nParentPos = aTempParent->Search(this);
 369         if (nParentPos != NODE_NOTFOUND)
 370             (*aTempParent)[nParentPos].GetChild().Clear();
 371         else
 372             aTempParent->GetChild().Clear();
 373     }
 374 }
 375 //------------------------------------------------------------------
 376 sal_Bool ONDXPage::Delete(sal_uInt16 nNodePos)
 377 {
 378     if (IsLeaf())
 379     {
 380         // The last element will not be deleted
 381         if (nNodePos == (nCount - 1))
 382         {
 383             ONDXNode aNode = (*this)[nNodePos];
 384
 385             // parent's KeyValue has to be replaced
 386             if (HasParent())
 387                 aParent->SearchAndReplace(aNode.GetKey(),
 388                                           (*this)[nNodePos-1].GetKey());
 389         }
 390     }
 391
 392     // Delete the node
 393     Remove(nNodePos);
 394
 395     // Underflow
 396     if (HasParent() && nCount < (rIndex.GetMaxNodes() / 2))
 397     {
 398         // determine, which node points to the page
 399         sal_uInt16 nParentNodePos = aParent->Search(this);
 400         // last element on parent-page -> merge with secondlast page
 401         if (nParentNodePos == (aParent->Count() - 1))
 402         {
 403             if (!nParentNodePos)
 404             // merge with left neighbour
 405                 Merge(nParentNodePos,aParent->GetChild(&rIndex));
 406             else
 407                 Merge(nParentNodePos,(*aParent)[nParentNodePos-1].GetChild(&rIndex,aParent));
 408         }
 409         // otherwise merge page with next page
 410         else
 411         {
 412             // merge with right neighbour
 413             Merge(nParentNodePos + 1,((*aParent)[nParentNodePos + 1].GetChild(&rIndex,aParent)));
 414             nParentNodePos++;
 415         }
 416         if (HasParent() && !(*aParent)[nParentNodePos].HasChild())
 417             aParent->Delete(nParentNodePos);
 418     }
 419     else if (IsRoot())
 420         // make sure that the position of the root is kept
 421         rIndex.SetRootPos(nPagePos);
 422     return sal_True;
 423 }
 424
 425
 426 //------------------------------------------------------------------
 427 ONDXNode ONDXPage::Split(ONDXPage& rPage)
 428 {
 429     DBG_ASSERT(IsFull(), "Falsches Splitting");
 430     /*  devide one page into two
 431         leaf:
 432             Page 1 is (n - (n/2))
 433             Page 2 is (n/2)
 434             Node n/2 will be duplicated
 435         inner node:
 436             Page 1 is (n+1)/2
 437             Page 2 is (n/2-1)
 438             Node ((n+1)/2 + 1) : will be taken out
 439     */
 440     ONDXNode aResultNode;
 441     if (IsLeaf())
 442     {
 443         for (sal_uInt16 i = (nCount - (nCount / 2)), j = 0 ; i < nCount; i++)
 444             rPage.Insert(j++,(*this)[i]);
 445
 446         // this node contains a key that already exists in the tree and must be replaced
 447         ONDXNode aLastNode = (*this)[nCount - 1];
 448         nCount = nCount - (nCount / 2);
 449         aResultNode = (*this)[nCount - 1];
 450
 451         if (HasParent())
 452             aParent->SearchAndReplace(aLastNode.GetKey(),
 453                                       aResultNode.GetKey());
 454     }
 455     else
 456     {
 457         for (sal_uInt16 i = (nCount + 1) / 2 + 1, j = 0 ; i < nCount; i++)
 458             rPage.Insert(j++,(*this)[i]);
 459
 460         aResultNode = (*this)[(nCount + 1) / 2];
 461         nCount = (nCount + 1) / 2;
 462
 463         // new page points to page with extraced node
 464         rPage.SetChild(aResultNode.GetChild());
 465     }
 466     // node points to new page
 467     aResultNode.SetChild(&rPage);
 468
 469     // inner nodes have no record number
 470     if (rIndex.isUnique())
 471         aResultNode.GetKey().ResetRecord();
 472     bModified = sal_True;
 473     return aResultNode;
 474 }
 475
 476 //------------------------------------------------------------------
 477 void ONDXPage::Merge(sal_uInt16 nParentNodePos, ONDXPagePtr xPage)
 478 {
 479     DBG_ASSERT(HasParent(), "kein Vater vorhanden");
 480     DBG_ASSERT(nParentNodePos != NODE_NOTFOUND, "Falscher Indexaufbau");
 481
 482     /*  Merge 2 pages   */
 483     ONDXNode aResultNode;
 484     sal_uInt16 nMaxNodes = rIndex.GetMaxNodes(),
 485            nMaxNodes_2 = nMaxNodes / 2;
 486
 487     // Determine if page is right or left neighbour
 488     sal_Bool    bRight    = ((*xPage)[0].GetKey() > (*this)[0].GetKey()); // sal_True, whenn xPage the right side is
 489     sal_uInt16  nNewCount = (*xPage).Count() + Count();
 490
 491     if (IsLeaf())
 492     {
 493         // Condition for merge
 494         if (nNewCount < (nMaxNodes_2 * 2))
 495         {
 496             sal_uInt16 nLastNode = bRight ? Count() - 1 : xPage->Count() - 1;
 497             if (bRight)
 498             {
 499                 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
 500                 // shift all nodes from xPage to the left node (append)
 501                 while (xPage->Count())
 502                 {
 503                     Append((*xPage)[0]);
 504                     xPage->Remove(0);
 505                 }
 506             }
 507             else
 508             {
 509                 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
 510                 // xPage is the left page and THIS the right one
 511                 while (xPage->Count())
 512                 {
 513                     Insert(0,(*xPage)[xPage->Count()-1]);
 514                     xPage->Remove(xPage->Count()-1);
 515                 }
 516                 // replace old position of xPage in parent with this
 517                 if (nParentNodePos)
 518                     (*aParent)[nParentNodePos-1].SetChild(this,aParent);
 519                 else // or set as right node
 520                     aParent->SetChild(this);
 521                 aParent->SetModified(sal_True);
 522
 523             }
 524
 525             // cancel Child-relationship at parent node
 526             (*aParent)[nParentNodePos].SetChild();
 527             // replace the Node-value, only if changed page is the left one, otherwise become
 528             if(aParent->IsRoot() && aParent->Count() == 1)
 529             {
 530                 (*aParent)[0].SetChild();
 531                 aParent->ReleaseFull();
 532                 aParent = NULL;
 533                 rIndex.SetRootPos(nPagePos);
 534                 rIndex.m_aRoot = this;
 535                 SetModified(sal_True);
 536             }
 537             else
 538                 aParent->SearchAndReplace((*this)[nLastNode].GetKey(),(*this)[nCount-1].GetKey());
 539
 540             xPage->SetModified(sal_False);
 541             xPage->ReleaseFull(); // is not needed anymore
 542         }
 543         // balance the elements   nNewCount >= (nMaxNodes_2 * 2)
 544         else
 545         {
 546             if (bRight)
 547             {
 548                 // shift all nodes from xPage to the left node (append)
 549                 ONDXNode aReplaceNode = (*this)[nCount - 1];
 550                 while (nCount < nMaxNodes_2)
 551                 {
 552                     Append((*xPage)[0]);
 553                     xPage->Remove(0);
 554                 }
 555                 // Replace the node values: replace old last value by the last of xPage
 556                 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[nCount-1].GetKey());
 557             }
 558             else
 559             {
 560                 // insert all nodes from this in front of the xPage nodes
 561                 ONDXNode aReplaceNode = (*this)[nCount - 1];
 562                 while (xPage->Count() < nMaxNodes_2)
 563                 {
 564                     xPage->Insert(0,(*this)[nCount-1]);
 565                     Remove(nCount-1);
 566                 }
 567                 // Replace the node value
 568                 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[Count()-1].GetKey());
 569             }
 570         }
 571     }
 572     else // !IsLeaf()
 573     {
 574         // Condition for merge
 575         if (nNewCount < nMaxNodes_2 * 2)
 576         {
 577             if (bRight)
 578             {
 579                 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
 580                 // Parent node will be integrated; is initialized with Child from xPage
 581                 (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
 582                 Append((*aParent)[nParentNodePos]);
 583                 for (sal_uInt16 i = 0 ; i < xPage->Count(); i++)
 584                     Append((*xPage)[i]);
 585             }
 586             else
 587             {
 588                 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
 589                 // Parent-node will be integrated; is initialized with child
 590                 (*aParent)[nParentNodePos].SetChild(GetChild(),aParent); // Parent memorizes my child
 591                 Insert(0,(*aParent)[nParentNodePos]); // insert parent node into myself
 592                 while (xPage->Count())
 593                 {
 594                     Insert(0,(*xPage)[xPage->Count()-1]);
 595                     xPage->Remove(xPage->Count()-1);
 596                 }
 597                 SetChild(xPage->GetChild());
 598
 599                 if (nParentNodePos)
 600                     (*aParent)[nParentNodePos-1].SetChild(this,aParent);
 601                 else
 602                     aParent->SetChild(this);
 603             }
 604
 605             // afterwards parent node will be reset
 606             (*aParent)[nParentNodePos].SetChild();
 607             aParent->SetModified(sal_True);
 608
 609             if(aParent->IsRoot() && aParent->Count() == 1)
 610             {
 611                 (*aParent).SetChild();
 612                 aParent->ReleaseFull();
 613                 aParent = NULL;
 614                 rIndex.SetRootPos(nPagePos);
 615                 rIndex.m_aRoot = this;
 616                 SetModified(sal_True);
 617             }
 618             else if(nParentNodePos)
 619                 // replace the node value
 620                 // for Append the range will be enlarged, for Insert the old node from xPage will reference to this
 621                 // thats why the node must be updated here
 622                 aParent->SearchAndReplace((*aParent)[nParentNodePos-1].GetKey(),(*aParent)[nParentNodePos].GetKey());
 623
 624             xPage->SetModified(sal_False);
 625             xPage->ReleaseFull();
 626         }
 627         // balance the elements
 628         else
 629         {
 630             if (bRight)
 631             {
 632                 while (nCount < nMaxNodes_2)
 633                 {
 634                     (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
 635                     Append((*aParent)[nParentNodePos]);
 636                     (*aParent)[nParentNodePos] = (*xPage)[0];
 637                     xPage->Remove(0);
 638                 }
 639                 xPage->SetChild((*aParent)[nParentNodePos].GetChild());
 640                 (*aParent)[nParentNodePos].SetChild(xPage,aParent);
 641             }
 642             else
 643             {
 644                 while (nCount < nMaxNodes_2)
 645                 {
 646                     (*aParent)[nParentNodePos].SetChild(GetChild(),aParent);
 647                     Insert(0,(*aParent)[nParentNodePos]);
 648                     (*aParent)[nParentNodePos] = (*xPage)[xPage->Count()-1];
 649                     xPage->Remove(xPage->Count()-1);
 650                 }
 651                 SetChild((*aParent)[nParentNodePos].GetChild());
 652                 (*aParent)[nParentNodePos].SetChild(this,aParent);
 653
 654             }
 655             aParent->SetModified(sal_True);
 656         }
 657     }
 658 }
 659 //==================================================================
 660 // ONDXNode
 661 //==================================================================
 662
 663 //------------------------------------------------------------------
 664 void ONDXNode::Read(SvStream &rStream, ODbaseIndex& rIndex)
 665 {
 666     rStream >> aKey.nRecord; // key
 667
 668     if (rIndex.getHeader().db_keytype)
 669     {
 670         double aDbl;
 671         rStream >> aDbl;
 672         aKey = ONDXKey(aDbl,aKey.nRecord);
 673     }
 674     else
 675     {
 676         sal_uInt16 nLen = rIndex.getHeader().db_keylen;
 677         rtl::OString aBuf = read_uInt8s_ToOString(rStream, nLen);
 678         //get length minus trailing whitespace
 679         sal_Int32 nContentLen = aBuf.getLength();
 680         while (nContentLen && aBuf[nContentLen-1] == ' ')
 681             --nContentLen;
 682         aKey = ONDXKey(::rtl::OUString(aBuf.getStr(), nContentLen, rIndex.m_pTable->getConnection()->getTextEncoding()) ,aKey.nRecord);
 683     }
 684     rStream >> aChild;
 685 }
 686
 687 //------------------------------------------------------------------
 688 void ONDXNode::Write(SvStream &rStream, const ONDXPage& rPage) const
 689 {
 690     const ODbaseIndex& rIndex = rPage.GetIndex();
 691     if (!rIndex.isUnique() || rPage.IsLeaf())
 692         rStream << (sal_uInt32)aKey.nRecord; // key
 693     else
 694         rStream << (sal_uInt32)0;   // key
 695
 696     if (rIndex.getHeader().db_keytype) // double
 697     {
 698         if (sizeof(double) != rIndex.getHeader().db_keylen)
 699         {
 700             OSL_TRACE("this key length cannot possibly be right?");
 701         }
 702         if (aKey.getValue().isNull())
 703         {
 704             sal_uInt8 buf[sizeof(double)];
 705             memset(&buf[0], 0, sizeof(double));
 706             rStream.Write(&buf[0], sizeof(double));
 707         }
 708         else
 709             rStream << (double) aKey.getValue();
 710     }
 711     else
 712     {
 713         sal_uInt16 const nLen(rIndex.getHeader().db_keylen);
 714         ::boost::scoped_array<sal_uInt8> pBuf(new sal_uInt8[nLen]);
 715         memset(&pBuf[0], 0x20, nLen);
 716         if (!aKey.getValue().isNull())
 717         {
 718             ::rtl::OUString sValue = aKey.getValue();
 719             rtl::OString aText(rtl::OUStringToOString(sValue, rIndex.m_pTable->getConnection()->getTextEncoding()));
 720             strncpy(reinterpret_cast<char *>(&pBuf[0]), aText.getStr(),
 721                 std::min<size_t>(nLen, aText.getLength()));
 722         }
 723         rStream.Write(&pBuf[0], nLen);
 724     }
 725     rStream << aChild;
 726 }
 727
 728
 729 //------------------------------------------------------------------
 730 ONDXPagePtr& ONDXNode::GetChild(ODbaseIndex* pIndex, ONDXPage* pParent)
 731 {
 732     if (!aChild.Is() && pIndex)
 733     {
 734         aChild = pIndex->CreatePage(aChild.GetPagePos(),pParent,aChild.HasPage());
 735     }
 736     return aChild;
 737 }
 738
 739 //==================================================================
 740 // ONDXKey
 741 //==================================================================
 742 //------------------------------------------------------------------
 743 sal_Bool ONDXKey::IsText(sal_Int32 eType)
 744 {
 745     return eType == DataType::VARCHAR || eType == DataType::CHAR;
 746 }
 747
 748 //------------------------------------------------------------------
 749 StringCompare ONDXKey::Compare(const ONDXKey& rKey) const
 750 {
 751     StringCompare eResult;
 752
 753     if (getValue().isNull())
 754     {
 755         if (rKey.getValue().isNull() || (rKey.IsText(getDBType()) && rKey.getValue().getString().isEmpty()))
 756             eResult = COMPARE_EQUAL;
 757         else
 758             eResult = COMPARE_LESS;
 759     }
 760     else if (rKey.getValue().isNull())
 761     {
 762         if (getValue().isNull() || (IsText(getDBType()) && getValue().getString().isEmpty()))
 763             eResult = COMPARE_EQUAL;
 764         else
 765             eResult = COMPARE_GREATER;
 766     }
 767     else if (IsText(getDBType()))
 768     {
 769         sal_Int32 nRes = getValue().getString().compareTo(rKey.getValue());
 770         eResult = (nRes > 0) ? COMPARE_GREATER : (nRes == 0) ? COMPARE_EQUAL : COMPARE_LESS;
 771     }
 772     else
 773     {
 774         double m = getValue(),n = rKey.getValue();
 775         eResult = (m > n) ? COMPARE_GREATER : (n == m) ? COMPARE_EQUAL : COMPARE_LESS;
 776     }
 777
 778     // compare record, if index !Unique
 779     if (eResult == COMPARE_EQUAL && nRecord && rKey.nRecord)
 780         eResult = (nRecord > rKey.nRecord) ? COMPARE_GREATER :
 781                   (nRecord == rKey.nRecord) ? COMPARE_EQUAL : COMPARE_LESS;
 782
 783     return eResult;
 784 }
 785 // -----------------------------------------------------------------------------
 786 void ONDXKey::setValue(const ORowSetValue& _rVal)
 787 {
 788     xValue = _rVal;
 789 }
 790 // -----------------------------------------------------------------------------
 791 const ORowSetValue& ONDXKey::getValue() const
 792 {
 793     return xValue;
 794 }
 795 // -----------------------------------------------------------------------------
 796 SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPagePtr& rPage)
 797 {
 798     rStream >> rPage.nPagePos;
 799     return rStream;
 800 }
 801 // -----------------------------------------------------------------------------
 802 SvStream& connectivity::dbase::operator << (SvStream &rStream, const ONDXPagePtr& rPage)
 803 {
 804     rStream << rPage.nPagePos;
 805     return rStream;
 806 }
 807 // -----------------------------------------------------------------------------
 808 //==================================================================
 809 // ONDXPagePtr
 810 //==================================================================
 811 //------------------------------------------------------------------
 812 ONDXPagePtr::ONDXPagePtr(const ONDXPagePtr& rRef)
 813               :ONDXPageRef(rRef)
 814               ,nPagePos(rRef.nPagePos)
 815 {
 816 }
 817
 818 //------------------------------------------------------------------
 819 ONDXPagePtr::ONDXPagePtr(ONDXPage* pRefPage)
 820               :ONDXPageRef(pRefPage)
 821               ,nPagePos(0)
 822 {
 823     if (pRefPage)
 824         nPagePos = pRefPage->GetPagePos();
 825 }
 826 //------------------------------------------------------------------
 827 ONDXPagePtr& ONDXPagePtr::operator=(const ONDXPagePtr& rRef)
 828 {
 829     ONDXPageRef::operator=(rRef);
 830     nPagePos = rRef.nPagePos;
 831     return *this;
 832 }
 833
 834 //------------------------------------------------------------------
 835 ONDXPagePtr& ONDXPagePtr::operator= (ONDXPage* pRef)
 836 {
 837     ONDXPageRef::operator=(pRef);
 838     nPagePos = (pRef) ? pRef->GetPagePos() : 0;
 839     return *this;
 840 }
 841 // -----------------------------------------------------------------------------
 842 static sal_uInt32 nValue;
 843 //------------------------------------------------------------------
 844 SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPage& rPage)
 845 {
 846     rStream.Seek(rPage.GetPagePos() * PAGE_SIZE);
 847     rStream >> nValue >> rPage.aChild;
 848     rPage.nCount = sal_uInt16(nValue);
 849
 850     for (sal_uInt16 i = 0; i < rPage.nCount; i++)
 851         rPage[i].Read(rStream, rPage.GetIndex());
 852     return rStream;
 853 }
 854
 855 //------------------------------------------------------------------
 856 SvStream& connectivity::dbase::operator << (SvStream &rStream, const ONDXPage& rPage)
 857 {
 858     // Page doesn't exist yet
 859     sal_uIntPtr nSize = (rPage.GetPagePos() + 1) * PAGE_SIZE;
 860     if (nSize > rStream.Seek(STREAM_SEEK_TO_END))
 861     {
 862         rStream.SetStreamSize(nSize);
 863         rStream.Seek(rPage.GetPagePos() * PAGE_SIZE);
 864
 865         char aEmptyData[PAGE_SIZE];
 866         memset(aEmptyData,0x00,PAGE_SIZE);
 867         rStream.Write((sal_uInt8*)aEmptyData,PAGE_SIZE);
 868     }
 869     sal_uIntPtr nCurrentPos = rStream.Seek(rPage.GetPagePos() * PAGE_SIZE);
 870     OSL_UNUSED( nCurrentPos );
 871
 872     nValue = rPage.nCount;
 873     rStream << nValue << rPage.aChild;
 874
 875     sal_uInt16 i = 0;
 876     for (; i < rPage.nCount; i++)
 877         rPage[i].Write(rStream, rPage);
 878
 879     // check if we have to fill the stream with '\0'
 880     if(i < rPage.rIndex.getHeader().db_maxkeys)
 881     {
 882         sal_uIntPtr nTell = rStream.Tell() % PAGE_SIZE;
 883         sal_uInt16 nBufferSize = rStream.GetBufferSize();
 884         sal_uIntPtr nRemainSize = nBufferSize - nTell;
 885         if ( nRemainSize <= nBufferSize )
 886         {
 887             char* pEmptyData = new char[nRemainSize];
 888             memset(pEmptyData,0x00,nRemainSize);
 889             rStream.Write((sal_uInt8*)pEmptyData,nRemainSize);
 890             rStream.Seek(nTell);
 891             delete [] pEmptyData;
 892         }
 893     }
 894     return rStream;
 895 }
 896 // -----------------------------------------------------------------------------
 897 #if OSL_DEBUG_LEVEL > 1
 898 //------------------------------------------------------------------
 899 void ONDXPage::PrintPage()
 900 {
 901     OSL_TRACE("\nSDB: -----------Page: %d  Parent: %d  Count: %d  Child: %d-----",
 902         nPagePos, HasParent() ? aParent->GetPagePos() : 0 ,nCount, aChild.GetPagePos());
 903
 904     for (sal_uInt16 i = 0; i < nCount; i++)
 905     {
 906         ONDXNode rNode = (*this)[i];
 907         ONDXKey&  rKey = rNode.GetKey();
 908         if (!IsLeaf())
 909             rNode.GetChild(&rIndex, this);
 910
 911         if (rKey.getValue().isNull())
 912         {
 913             OSL_TRACE("SDB: [%d,NULL,%d]",rKey.GetRecord(), rNode.GetChild().GetPagePos());
 914         }
 915         else if (rIndex.getHeader().db_keytype)
 916         {
 917             OSL_TRACE("SDB: [%d,%f,%d]",rKey.GetRecord(), rKey.getValue().getDouble(),rNode.GetChild().GetPagePos());
 918         }
 919         else
 920         {
 921             OSL_TRACE("SDB: [%d,%s,%d]",rKey.GetRecord(), rtl::OUStringToOString(rKey.getValue().getString(), rIndex.m_pTable->getConnection()->getTextEncoding()).getStr(),rNode.GetChild().GetPagePos());
 922         }
 923     }
 924     OSL_TRACE("SDB: -----------------------------------------------");
 925     if (!IsLeaf())
 926     {
 927 #if OSL_DEBUG_LEVEL > 1
 928         GetChild(&rIndex)->PrintPage();
 929         for (sal_uInt16 i = 0; i < nCount; i++)
 930         {
 931             ONDXNode rNode = (*this)[i];
 932             rNode.GetChild(&rIndex,this)->PrintPage();
 933         }
 934 #endif
 935     }
 936     OSL_TRACE("SDB: ===============================================");
 937 }
 938 #endif
 939 // -----------------------------------------------------------------------------
 940 sal_Bool ONDXPage::IsFull() const
 941 {
 942     return Count() == rIndex.getHeader().db_maxkeys;
 943 }
 944 // -----------------------------------------------------------------------------
 945 //------------------------------------------------------------------
 946 sal_uInt16 ONDXPage::Search(const ONDXKey& rSearch)
 947 {
 948     // binary search later
 949     sal_uInt16 i = NODE_NOTFOUND;
 950     while (++i < Count())
 951         if ((*this)[i].GetKey() == rSearch)
 952             break;
 953
 954     return (i < Count()) ? i : NODE_NOTFOUND;
 955 }
 956
 957 //------------------------------------------------------------------
 958 sal_uInt16 ONDXPage::Search(const ONDXPage* pPage)
 959 {
 960     sal_uInt16 i = NODE_NOTFOUND;
 961     while (++i < Count())
 962         if (((*this)[i]).GetChild() == pPage)
 963             break;
 964
 965     // if not found, then we assume, that the page itself points to the page
 966     return (i < Count()) ? i : NODE_NOTFOUND;
 967 }
 968 // -----------------------------------------------------------------------------
 969 // runs recursively
 970 void ONDXPage::SearchAndReplace(const ONDXKey& rSearch,
 971                                   ONDXKey& rReplace)
 972 {
 973     OSL_ENSURE(rSearch != rReplace,"Invalid here:rSearch == rReplace");
 974     if (rSearch != rReplace)
 975     {
 976         sal_uInt16 nPos = NODE_NOTFOUND;
 977         ONDXPage* pPage = this;
 978
 979         while (pPage && (nPos = pPage->Search(rSearch)) == NODE_NOTFOUND)
 980             pPage = pPage->aParent;
 981
 982         if (pPage)
 983         {
 984             (*pPage)[nPos].GetKey() = rReplace;
 985             pPage->SetModified(sal_True);
 986         }
 987     }
 988 }
 989 // -----------------------------------------------------------------------------
 990 ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos)
 991 {
 992     DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
 993     return ppNodes[nPos];
 994 }
 995
 996 //------------------------------------------------------------------
 997 const ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos) const
 998 {
 999     DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
1000     return ppNodes[nPos];
1001 }
1002 // -----------------------------------------------------------------------------
1003 void ONDXPage::Remove(sal_uInt16 nPos)
1004 {
1005     DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
1006
1007     for (sal_uInt16 i = nPos; i < (nCount-1); i++)
1008         (*this)[i] = (*this)[i+1];
1009
1010     nCount--;
1011     bModified = sal_True;
1012 }
1013 // -----------------------------------------------------------------------------
1014
1015 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */