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