connectivity/source/drivers/dbase/dindexnode.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <dbase/dindexnode.hxx>
  21 #include <dbase/DIndex.hxx>
  22 #include <o3tl/safeint.hxx>
  23 #include <tools/debug.hxx>
  24 #include <tools/stream.hxx>
  25 #include <sal/log.hxx>
  26
  27 #include <algorithm>
  28 #include <memory>
  29
  30
  31 using namespace connectivity;
  32 using namespace connectivity::dbase;
  33 using namespace connectivity::file;
  34 using namespace com::sun::star::sdbc;
  35
  36 ONDXKey::ONDXKey()
  37     :nRecord(0)
  38 {
  39 }
  40
  41 ONDXKey::ONDXKey(const ORowSetValue& rVal, sal_Int32 eType, sal_uInt32 nRec)
  42     : ONDXKey_BASE(eType)
  43     , nRecord(nRec)
  44     , xValue(rVal)
  45 {
  46 }
  47
  48 ONDXKey::ONDXKey(const OUString& aStr, sal_uInt32 nRec)
  49     : ONDXKey_BASE(css::sdbc::DataType::VARCHAR)
  50      ,nRecord(nRec)
  51 {
  52     if (!aStr.isEmpty())
  53     {
  54         xValue = aStr;
  55         xValue.setBound(true);
  56     }
  57 }
  58
  59 ONDXKey::ONDXKey(double aVal, sal_uInt32 nRec)
  60     : ONDXKey_BASE(css::sdbc::DataType::DOUBLE)
  61      ,nRecord(nRec)
  62      ,xValue(aVal)
  63 {
  64 }
  65
  66 // index page
  67 ONDXPage::ONDXPage(ODbaseIndex& rInd, sal_uInt32 nPos, ONDXPage* pParent)
  68     : nRefCount(0)
  69     , bNoDelete(1)
  70     , nPagePos(nPos)
  71     , bModified(false)
  72     , nCount(0)
  73     , aParent(pParent)
  74     , rIndex(rInd)
  75 {
  76     sal_uInt16 nT = rIndex.getHeader().db_maxkeys;
  77     ppNodes.reset( new ONDXNode[nT] );
  78 }
  79
  80 ONDXPage::~ONDXPage()
  81 {
  82 }
  83
  84 void ONDXPage::ReleaseRef()
  85 {
  86     assert( nRefCount >= 1);
  87     if(--nRefCount == 0 && !bNoDelete)
  88     {
  89         QueryDelete();
  90     }
  91 }
  92
  93 void ONDXPage::QueryDelete()
  94 {
  95     // Store in GarbageCollector
  96     if (IsModified() && rIndex.m_pFileStream)
  97         WriteONDXPage( *rIndex.m_pFileStream, *this );
  98
  99     bModified = false;
 100     if (rIndex.UseCollector())
 101     {
 102         if (aChild.Is())
 103             aChild->Release(false);
 104
 105         for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
 106         {
 107             if (ppNodes[i].GetChild().Is())
 108                 ppNodes[i].GetChild()->Release(false);
 109
 110             ppNodes[i] = ONDXNode();
 111         }
 112         bNoDelete = 1;
 113
 114         nCount = 0;
 115         aParent.Clear();
 116         rIndex.Collect(this);
 117     }
 118     else
 119     {
 120         // I'm not sure about the original purpose of this line, but right now
 121         // it serves the purpose that anything that attempts to do an AddFirstRef()
 122         // after an object is deleted will trip an assert.
 123         nRefCount = 1 << 30;
 124         delete this;
 125     }
 126 }
 127
 128 ONDXPagePtr& ONDXPage::GetChild(ODbaseIndex const * pIndex)
 129 {
 130     if (!aChild.Is() && pIndex)
 131     {
 132         aChild = rIndex.CreatePage(aChild.GetPagePos(),this,aChild.HasPage());
 133     }
 134     return aChild;
 135 }
 136
 137
 138 sal_uInt16 ONDXPage::FindPos(const ONDXKey& rKey) const
 139 {
 140     // searches the position for the given key in a page
 141     sal_uInt16 i = 0;
 142     while (i < nCount && rKey > ((*this)[i]).GetKey())
 143            i++;
 144
 145     return i;
 146 }
 147
 148
 149 bool ONDXPage::Find(const ONDXKey& rKey)
 150 {
 151     // searches the given key
 152     // Speciality: At the end of the method
 153     // the actual page and the position of the node, fulfilling the '<=' condition, are saved
 154     // This is considered at insert.
 155     sal_uInt16 i = 0;
 156     while (i < nCount && rKey > ((*this)[i]).GetKey())
 157            i++;
 158
 159     bool bResult = false;
 160
 161     if (!IsLeaf())
 162     {
 163         // descend further
 164         ONDXPagePtr aPage = (i==0) ? GetChild(&rIndex) : ((*this)[i-1]).GetChild(&rIndex, this);
 165         bResult = aPage.Is() && aPage->Find(rKey);
 166     }
 167     else if (i == nCount)
 168     {
 169         rIndex.m_aCurLeaf = this;
 170         rIndex.m_nCurNode = i - 1;
 171         bResult = false;
 172     }
 173     else
 174     {
 175         bResult = rKey == ((*this)[i]).GetKey();
 176         rIndex.m_aCurLeaf = this;
 177         rIndex.m_nCurNode = bResult ? i : i - 1;
 178     }
 179     return bResult;
 180 }
 181
 182
 183 bool ONDXPage::Insert(ONDXNode& rNode, sal_uInt32 nRowsLeft)
 184 {
 185     // When creating an index there can be multiple nodes added,
 186     // these are sorted ascending
 187     bool bAppend = nRowsLeft > 0;
 188     if (IsFull())
 189     {
 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                 bool bResult = true;
 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 < o3tl::make_unsigned(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 bool ONDXPage::Insert(sal_uInt16 nPos, ONDXNode& rNode)
 303 {
 304     sal_uInt16 nMaxCount = rIndex.getHeader().db_maxkeys;
 305     if (nPos >= nMaxCount)
 306         return false;
 307
 308     if (nCount)
 309     {
 310         ++nCount;
 311         // shift right
 312         for (sal_uInt16 i = std::min(static_cast<sal_uInt16>(nMaxCount-1), static_cast<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 = true;
 329
 330     return true;
 331 }
 332
 333
 334 bool ONDXPage::Append(ONDXNode& rNode)
 335 {
 336     DBG_ASSERT(!IsFull(), "no Append possible");
 337     return Insert(nCount, rNode);
 338 }
 339
 340 void ONDXPage::Release(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.Clear();
 357 }
 358
 359 void ONDXPage::ReleaseFull()
 360 {
 361     ONDXPagePtr aTempParent = aParent;
 362     Release();
 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 void 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 }
 423
 424
 425 ONDXNode ONDXPage::Split(ONDXPage& rPage)
 426 {
 427     DBG_ASSERT(IsFull(), "Incorrect Splitting");
 428     /*  divide one page into two
 429         leaf:
 430             Page 1 is (n - (n/2))
 431             Page 2 is (n/2)
 432             Node n/2 will be duplicated
 433         inner node:
 434             Page 1 is (n+1)/2
 435             Page 2 is (n/2-1)
 436             Node ((n+1)/2 + 1) : will be taken out
 437     */
 438     ONDXNode aResultNode;
 439     if (IsLeaf())
 440     {
 441         for (sal_uInt16 i = nCount - (nCount / 2), j = 0 ; i < nCount; i++)
 442             rPage.Insert(j++,(*this)[i]);
 443
 444         // this node contains a key that already exists in the tree and must be replaced
 445         ONDXNode aLastNode = (*this)[nCount - 1];
 446         nCount = nCount - (nCount / 2);
 447         aResultNode = (*this)[nCount - 1];
 448
 449         if (HasParent())
 450             aParent->SearchAndReplace(aLastNode.GetKey(),
 451                                       aResultNode.GetKey());
 452     }
 453     else
 454     {
 455         for (sal_uInt16 i = (nCount + 1) / 2 + 1, j = 0 ; i < nCount; i++)
 456             rPage.Insert(j++,(*this)[i]);
 457
 458         aResultNode = (*this)[(nCount + 1) / 2];
 459         nCount = (nCount + 1) / 2;
 460
 461         // new page points to page with extracted node
 462         rPage.SetChild(aResultNode.GetChild());
 463     }
 464     // node points to new page
 465     aResultNode.SetChild(&rPage);
 466
 467     // inner nodes have no record number
 468     if (rIndex.isUnique())
 469         aResultNode.GetKey().ResetRecord();
 470     bModified = true;
 471     return aResultNode;
 472 }
 473
 474
 475 void ONDXPage::Merge(sal_uInt16 nParentNodePos, const ONDXPagePtr& xPage)
 476 {
 477     DBG_ASSERT(HasParent(), "no parent existing");
 478     DBG_ASSERT(nParentNodePos != NODE_NOTFOUND, "Wrong index setup");
 479
 480     /*  Merge 2 pages   */
 481     sal_uInt16 nMaxNodes = rIndex.GetMaxNodes(),
 482            nMaxNodes_2 = nMaxNodes / 2;
 483
 484     // Determine if page is right or left neighbour
 485     bool    bRight    = ((*xPage)[0].GetKey() > (*this)[0].GetKey()); // sal_True, whenn xPage the right side is
 486     sal_uInt16  nNewCount = (*xPage).Count() + Count();
 487
 488     if (IsLeaf())
 489     {
 490         // Condition for merge
 491         if (nNewCount < (nMaxNodes_2 * 2))
 492         {
 493             sal_uInt16 nLastNode = bRight ? Count() - 1 : xPage->Count() - 1;
 494             if (bRight)
 495             {
 496                 DBG_ASSERT(xPage != this,"xPage and THIS must not be the same: infinite loop");
 497                 // shift all nodes from xPage to the left node (append)
 498                 while (xPage->Count())
 499                 {
 500                     Append((*xPage)[0]);
 501                     xPage->Remove(0);
 502                 }
 503             }
 504             else
 505             {
 506                 DBG_ASSERT(xPage != this,"xPage and THIS must not be the same: infinite loop");
 507                 // xPage is the left page and THIS the right one
 508                 while (xPage->Count())
 509                 {
 510                     Insert(0,(*xPage)[xPage->Count()-1]);
 511                     xPage->Remove(xPage->Count()-1);
 512                 }
 513                 // replace old position of xPage in parent with this
 514                 if (nParentNodePos)
 515                     (*aParent)[nParentNodePos-1].SetChild(this,aParent);
 516                 else // or set as right node
 517                     aParent->SetChild(this);
 518                 aParent->SetModified(true);
 519
 520             }
 521
 522             // cancel Child-relationship at parent node
 523             (*aParent)[nParentNodePos].SetChild();
 524             // replace the Node-value, only if changed page is the left one, otherwise become
 525             if(aParent->IsRoot() && aParent->Count() == 1)
 526             {
 527                 (*aParent)[0].SetChild();
 528                 aParent->ReleaseFull();
 529                 aParent.Clear();
 530                 rIndex.SetRootPos(nPagePos);
 531                 rIndex.m_aRoot = this;
 532                 SetModified(true);
 533             }
 534             else
 535                 aParent->SearchAndReplace((*this)[nLastNode].GetKey(),(*this)[nCount-1].GetKey());
 536
 537             xPage->SetModified(false);
 538             xPage->ReleaseFull(); // is not needed anymore
 539         }
 540         // balance the elements   nNewCount >= (nMaxNodes_2 * 2)
 541         else
 542         {
 543             if (bRight)
 544             {
 545                 // shift all nodes from xPage to the left node (append)
 546                 ONDXNode aReplaceNode = (*this)[nCount - 1];
 547                 while (nCount < nMaxNodes_2)
 548                 {
 549                     Append((*xPage)[0]);
 550                     xPage->Remove(0);
 551                 }
 552                 // Replace the node values: replace old last value by the last of xPage
 553                 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[nCount-1].GetKey());
 554             }
 555             else
 556             {
 557                 // insert all nodes from this in front of the xPage nodes
 558                 ONDXNode aReplaceNode = (*this)[nCount - 1];
 559                 while (xPage->Count() < nMaxNodes_2)
 560                 {
 561                     xPage->Insert(0,(*this)[nCount-1]);
 562                     Remove(nCount-1);
 563                 }
 564                 // Replace the node value
 565                 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[Count()-1].GetKey());
 566             }
 567         }
 568     }
 569     else // !IsLeaf()
 570     {
 571         // Condition for merge
 572         if (nNewCount < nMaxNodes_2 * 2)
 573         {
 574             if (bRight)
 575             {
 576                 DBG_ASSERT(xPage != this,"xPage and THIS must not be the same: infinite loop");
 577                 // Parent node will be integrated; is initialized with Child from xPage
 578                 (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
 579                 Append((*aParent)[nParentNodePos]);
 580                 for (sal_uInt16 i = 0 ; i < xPage->Count(); i++)
 581                     Append((*xPage)[i]);
 582             }
 583             else
 584             {
 585                 DBG_ASSERT(xPage != this,"xPage and THIS must not be the same: infinite loop");
 586                 // Parent-node will be integrated; is initialized with child
 587                 (*aParent)[nParentNodePos].SetChild(GetChild(),aParent); // Parent memorizes my child
 588                 Insert(0,(*aParent)[nParentNodePos]); // insert parent node into myself
 589                 while (xPage->Count())
 590                 {
 591                     Insert(0,(*xPage)[xPage->Count()-1]);
 592                     xPage->Remove(xPage->Count()-1);
 593                 }
 594                 SetChild(xPage->GetChild());
 595
 596                 if (nParentNodePos)
 597                     (*aParent)[nParentNodePos-1].SetChild(this,aParent);
 598                 else
 599                     aParent->SetChild(this);
 600             }
 601
 602             // afterwards parent node will be reset
 603             (*aParent)[nParentNodePos].SetChild();
 604             aParent->SetModified(true);
 605
 606             if(aParent->IsRoot() && aParent->Count() == 1)
 607             {
 608                 (*aParent).SetChild();
 609                 aParent->ReleaseFull();
 610                 aParent.Clear();
 611                 rIndex.SetRootPos(nPagePos);
 612                 rIndex.m_aRoot = this;
 613                 SetModified(true);
 614             }
 615             else if(nParentNodePos)
 616                 // replace the node value
 617                 // for Append the range will be enlarged, for Insert the old node from xPage will reference to this
 618                 // that's why the node must be updated here
 619                 aParent->SearchAndReplace((*aParent)[nParentNodePos-1].GetKey(),(*aParent)[nParentNodePos].GetKey());
 620
 621             xPage->SetModified(false);
 622             xPage->ReleaseFull();
 623         }
 624         // balance the elements
 625         else
 626         {
 627             if (bRight)
 628             {
 629                 while (nCount < nMaxNodes_2)
 630                 {
 631                     (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
 632                     Append((*aParent)[nParentNodePos]);
 633                     (*aParent)[nParentNodePos] = (*xPage)[0];
 634                     xPage->Remove(0);
 635                 }
 636                 xPage->SetChild((*aParent)[nParentNodePos].GetChild());
 637                 (*aParent)[nParentNodePos].SetChild(xPage,aParent);
 638             }
 639             else
 640             {
 641                 while (nCount < nMaxNodes_2)
 642                 {
 643                     (*aParent)[nParentNodePos].SetChild(GetChild(),aParent);
 644                     Insert(0,(*aParent)[nParentNodePos]);
 645                     (*aParent)[nParentNodePos] = (*xPage)[xPage->Count()-1];
 646                     xPage->Remove(xPage->Count()-1);
 647                 }
 648                 SetChild((*aParent)[nParentNodePos].GetChild());
 649                 (*aParent)[nParentNodePos].SetChild(this,aParent);
 650
 651             }
 652             aParent->SetModified(true);
 653         }
 654     }
 655 }
 656
 657 // ONDXNode
 658
 659
 660 void ONDXNode::Read(SvStream &rStream, ODbaseIndex const & rIndex)
 661 {
 662     rStream.ReadUInt32( aKey.nRecord ); // key
 663
 664     if (rIndex.getHeader().db_keytype)
 665     {
 666         double aDbl;
 667         rStream.ReadDouble( aDbl );
 668         aKey = ONDXKey(aDbl,aKey.nRecord);
 669     }
 670     else
 671     {
 672         sal_uInt16 nLen = rIndex.getHeader().db_keylen;
 673         OString aBuf = read_uInt8s_ToOString(rStream, nLen);
 674         //get length minus trailing whitespace
 675         sal_Int32 nContentLen = aBuf.getLength();
 676         while (nContentLen && aBuf[nContentLen-1] == ' ')
 677             --nContentLen;
 678         aKey = ONDXKey(OUString(aBuf.getStr(), nContentLen, rIndex.m_pTable->getConnection()->getTextEncoding()) ,aKey.nRecord);
 679     }
 680     rStream >> aChild;
 681 }
 682
 683
 684 void ONDXNode::Write(SvStream &rStream, const ONDXPage& rPage) const
 685 {
 686     const ODbaseIndex& rIndex = rPage.GetIndex();
 687     if (!rIndex.isUnique() || rPage.IsLeaf())
 688         rStream.WriteUInt32( aKey.nRecord ); // key
 689     else
 690         rStream.WriteUInt32( 0 );   // key
 691
 692     if (rIndex.getHeader().db_keytype) // double
 693     {
 694         if (sizeof(double) != rIndex.getHeader().db_keylen)
 695         {
 696             SAL_WARN("connectivity.dbase", "this key length cannot possibly be right?");
 697         }
 698         if (aKey.getValue().isNull())
 699         {
 700             sal_uInt8 buf[sizeof(double)] = {};
 701             rStream.WriteBytes(&buf[0], sizeof(double));
 702         }
 703         else
 704             rStream.WriteDouble( static_cast<double>(aKey.getValue()) );
 705     }
 706     else
 707     {
 708         sal_uInt16 const nLen(rIndex.getHeader().db_keylen);
 709         std::unique_ptr<sal_uInt8[]> pBuf(new sal_uInt8[nLen]);
 710         memset(&pBuf[0], 0x20, nLen);
 711         if (!aKey.getValue().isNull())
 712         {
 713             OUString sValue = aKey.getValue();
 714             OString aText(OUStringToOString(sValue, rIndex.m_pTable->getConnection()->getTextEncoding()));
 715             strncpy(reinterpret_cast<char *>(&pBuf[0]), aText.getStr(),
 716                 std::min<size_t>(nLen, aText.getLength()));
 717         }
 718         rStream.WriteBytes(&pBuf[0], nLen);
 719     }
 720     WriteONDXPagePtr( rStream, aChild );
 721 }
 722
 723
 724 ONDXPagePtr& ONDXNode::GetChild(ODbaseIndex* pIndex, ONDXPage* pParent)
 725 {
 726     if (!aChild.Is() && pIndex)
 727     {
 728         aChild = pIndex->CreatePage(aChild.GetPagePos(),pParent,aChild.HasPage());
 729     }
 730     return aChild;
 731 }
 732
 733
 734 // ONDXKey
 735
 736
 737 bool ONDXKey::IsText(sal_Int32 eType)
 738 {
 739     return eType == DataType::VARCHAR || eType == DataType::CHAR;
 740 }
 741
 742
 743 int ONDXKey::Compare(const ONDXKey& rKey) const
 744 {
 745     sal_Int32 nRes;
 746
 747     if (getValue().isNull())
 748     {
 749         if (rKey.getValue().isNull() || (IsText(getDBType()) && rKey.getValue().getString().isEmpty()))
 750             nRes = 0;
 751         else
 752             nRes = -1;
 753     }
 754     else if (rKey.getValue().isNull())
 755     {
 756         if (getValue().isNull() || (IsText(getDBType()) && getValue().getString().isEmpty()))
 757             nRes = 0;
 758         else
 759             nRes = 1;
 760     }
 761     else if (IsText(getDBType()))
 762     {
 763         nRes = getValue().getString().compareTo(rKey.getValue().getString());
 764     }
 765     else
 766     {
 767         double m = getValue();
 768         double n = rKey.getValue();
 769         nRes = (m > n) ? 1 : ( m < n) ? -1 : 0;
 770     }
 771
 772     // compare record, if index !Unique
 773     if (nRes == 0 && nRecord && rKey.nRecord)
 774     {
 775         nRes = (nRecord > rKey.nRecord) ? 1 :
 776             (nRecord == rKey.nRecord) ? 0 : -1;
 777     }
 778     return nRes;
 779 }
 780
 781 void ONDXKey::setValue(const ORowSetValue& _rVal)
 782 {
 783     xValue = _rVal;
 784 }
 785
 786 const ORowSetValue& ONDXKey::getValue() const
 787 {
 788     return xValue;
 789 }
 790
 791 SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPagePtr& rPage)
 792 {
 793     rStream.ReadUInt32( rPage.nPagePos );
 794     return rStream;
 795 }
 796
 797 SvStream& connectivity::dbase::WriteONDXPagePtr(SvStream &rStream, const ONDXPagePtr& rPage)
 798 {
 799     rStream.WriteUInt32( rPage.nPagePos );
 800     return rStream;
 801 }
 802
 803 // ONDXPagePtr
 804 ONDXPagePtr::ONDXPagePtr()
 805     : mpPage(nullptr)
 806     , nPagePos(0)
 807 {
 808 }
 809
 810 ONDXPagePtr::ONDXPagePtr(ONDXPagePtr&& rRef) noexcept
 811 {
 812     mpPage = rRef.mpPage;
 813     rRef.mpPage = nullptr;
 814     nPagePos = rRef.nPagePos;
 815 }
 816
 817 ONDXPagePtr::ONDXPagePtr(ONDXPagePtr const & rRef)
 818     : mpPage(rRef.mpPage)
 819     , nPagePos(rRef.nPagePos)
 820 {
 821     if (mpPage != nullptr)
 822         mpPage->AddNextRef();
 823 }
 824
 825 ONDXPagePtr::ONDXPagePtr(ONDXPage* pRefPage)
 826     : mpPage(pRefPage)
 827     , nPagePos(0)
 828 {
 829     if (mpPage != nullptr)
 830         mpPage->AddFirstRef();
 831     if (pRefPage)
 832         nPagePos = pRefPage->GetPagePos();
 833 }
 834
 835 ONDXPagePtr::~ONDXPagePtr()
 836 {
 837     if (mpPage != nullptr) mpPage->ReleaseRef();
 838 }
 839
 840 void ONDXPagePtr::Clear()
 841 {
 842     if (mpPage != nullptr) {
 843         ONDXPage * pRefObj = mpPage;
 844         mpPage = nullptr;
 845         pRefObj->ReleaseRef();
 846     }
 847 }
 848
 849 ONDXPagePtr& ONDXPagePtr::operator=(ONDXPagePtr const & rOther)
 850 {
 851     ONDXPagePtr aTemp(rOther);
 852     *this = std::move(aTemp);
 853     return *this;
 854 }
 855
 856 ONDXPagePtr& ONDXPagePtr::operator=(ONDXPagePtr && rOther)
 857 {
 858     if (mpPage != nullptr) {
 859         mpPage->ReleaseRef();
 860     }
 861     mpPage = rOther.mpPage;
 862     nPagePos = rOther.nPagePos;
 863     rOther.mpPage = nullptr;
 864     return *this;
 865 }
 866
 867 static sal_uInt32 nValue;
 868
 869 SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPage& rPage)
 870 {
 871     rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
 872     rStream.ReadUInt32( nValue ) >> rPage.aChild;
 873     rPage.nCount = sal_uInt16(nValue);
 874
 875     for (sal_uInt16 i = 0; i < rPage.nCount; i++)
 876         rPage[i].Read(rStream, rPage.GetIndex());
 877     return rStream;
 878 }
 879
 880
 881 SvStream& connectivity::dbase::WriteONDXPage(SvStream &rStream, const ONDXPage& rPage)
 882 {
 883     // Page doesn't exist yet
 884     std::size_t nSize = rPage.GetPagePos() + 1;
 885     nSize *= DINDEX_PAGE_SIZE;
 886     if (nSize > rStream.TellEnd())
 887     {
 888         rStream.SetStreamSize(nSize);
 889         rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
 890
 891         char aEmptyData[DINDEX_PAGE_SIZE] = {};
 892         rStream.WriteBytes(aEmptyData, DINDEX_PAGE_SIZE);
 893     }
 894     rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
 895
 896     nValue = rPage.nCount;
 897     rStream.WriteUInt32( nValue );
 898     WriteONDXPagePtr( rStream, rPage.aChild );
 899
 900     sal_uInt16 i = 0;
 901     for (; i < rPage.nCount; i++)
 902         rPage[i].Write(rStream, rPage);
 903
 904     // check if we have to fill the stream with '\0'
 905     if(i < rPage.rIndex.getHeader().db_maxkeys)
 906     {
 907         std::size_t nTell = rStream.Tell() % DINDEX_PAGE_SIZE;
 908         sal_uInt16 nBufferSize = rStream.GetBufferSize();
 909         std::size_t nRemainSize = nBufferSize - nTell;
 910         if ( nRemainSize <= nBufferSize )
 911         {
 912             std::unique_ptr<char[]> pEmptyData( new char[nRemainSize] );
 913             memset(pEmptyData.get(), 0x00, nRemainSize);
 914             rStream.WriteBytes(pEmptyData.get(), nRemainSize);
 915             rStream.Seek(nTell);
 916         }
 917     }
 918     return rStream;
 919 }
 920
 921 #if OSL_DEBUG_LEVEL > 1
 922
 923 void ONDXPage::PrintPage()
 924 {
 925     SAL_WARN("connectivity.dbase", "SDB: -----------Page: " << nPagePos << "  Parent: " << (HasParent() ? aParent->GetPagePos() : 0)
 926               << "  Count: " << nCount << "  Child: " << aChild.GetPagePos() << "-----");
 927
 928     for (sal_uInt16 i = 0; i < nCount; i++)
 929     {
 930         ONDXNode rNode = (*this)[i];
 931         ONDXKey&  rKey = rNode.GetKey();
 932         if (!IsLeaf())
 933             rNode.GetChild(&rIndex, this);
 934
 935         if (rKey.getValue().isNull())
 936         {
 937             SAL_WARN("connectivity.dbase", "SDB: [" << rKey.GetRecord() << ",NULL," << rNode.GetChild().GetPagePos() << "]");
 938         }
 939         else if (rIndex.getHeader().db_keytype)
 940         {
 941             SAL_WARN("connectivity.dbase", "SDB: [" << rKey.GetRecord() << "," << rKey.getValue().getDouble()
 942                                            << "," << rNode.GetChild().GetPagePos() << "]");
 943         }
 944         else
 945         {
 946             SAL_WARN("connectivity.dbase", "SDB: [" << rKey.GetRecord() << "," << rKey.getValue().getString()
 947                                            << "," << rNode.GetChild().GetPagePos() << "]" );
 948         }
 949     }
 950     SAL_WARN("connectivity.dbase", "SDB: -----------------------------------------------");
 951     if (!IsLeaf())
 952     {
 953 #if OSL_DEBUG_LEVEL > 1
 954         GetChild(&rIndex)->PrintPage();
 955         for (sal_uInt16 i = 0; i < nCount; i++)
 956         {
 957             ONDXNode rNode = (*this)[i];
 958             rNode.GetChild(&rIndex,this)->PrintPage();
 959         }
 960 #endif
 961     }
 962     SAL_WARN("connectivity.dbase", "SDB: ===============================================");
 963 }
 964 #endif
 965
 966 bool ONDXPage::IsFull() const
 967 {
 968     return Count() == rIndex.getHeader().db_maxkeys;
 969 }
 970
 971
 972 sal_uInt16 ONDXPage::Search(const ONDXKey& rSearch)
 973 {
 974     // binary search later
 975     sal_uInt16 i = NODE_NOTFOUND;
 976     while (++i < Count())
 977         if ((*this)[i].GetKey() == rSearch)
 978             break;
 979
 980     return (i < Count()) ? i : NODE_NOTFOUND;
 981 }
 982
 983
 984 sal_uInt16 ONDXPage::Search(const ONDXPage* pPage)
 985 {
 986     sal_uInt16 i = NODE_NOTFOUND;
 987     while (++i < Count())
 988         if (((*this)[i]).GetChild() == pPage)
 989             break;
 990
 991     // if not found, then we assume, that the page itself points to the page
 992     return (i < Count()) ? i : NODE_NOTFOUND;
 993 }
 994
 995 // runs recursively
 996 void ONDXPage::SearchAndReplace(const ONDXKey& rSearch,
 997                                   ONDXKey const & rReplace)
 998 {
 999     OSL_ENSURE(rSearch != rReplace,"Invalid here:rSearch == rReplace");
1000     if (rSearch == rReplace)
1001         return;
1002
1003     sal_uInt16 nPos = NODE_NOTFOUND;
1004     ONDXPage* pPage = this;
1005
1006     while (pPage)
1007     {
1008         nPos = pPage->Search(rSearch);
1009         if (nPos != NODE_NOTFOUND)
1010             break;
1011         pPage = pPage->aParent;
1012     }
1013
1014     if (pPage)
1015     {
1016         (*pPage)[nPos].GetKey() = rReplace;
1017         pPage->SetModified(true);
1018     }
1019 }
1020
1021 ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos)
1022 {
1023     DBG_ASSERT(nCount > nPos, "incorrect index access");
1024     return ppNodes[nPos];
1025 }
1026
1027
1028 const ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos) const
1029 {
1030     DBG_ASSERT(nCount > nPos, "incorrect index access");
1031     return ppNodes[nPos];
1032 }
1033
1034 void ONDXPage::Remove(sal_uInt16 nPos)
1035 {
1036     DBG_ASSERT(nCount > nPos, "incorrect index access");
1037
1038     for (sal_uInt16 i = nPos; i < (nCount-1); i++)
1039         (*this)[i] = (*this)[i+1];
1040
1041     nCount--;
1042     bModified = true;
1043 }
1044
1045
1046 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */