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