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