1 /**************************************************************
2 *
3 * Licensed to the Apache Software Foundation (ASF) under one
4 * or more contributor license agreements. See the NOTICE file
5 * distributed with this work for additional information
6 * regarding copyright ownership. The ASF licenses this file
7 * to you under the Apache License, Version 2.0 (the
8 * "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing,
14 * software distributed under the License is distributed on an
15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 * KIND, either express or implied. See the License for the
17 * specific language governing permissions and limitations
18 * under the License.
19 *
20 *************************************************************/
21
22
23
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_connectivity.hxx"
26 #include "dbase/dindexnode.hxx"
27 #include "connectivity/CommonTools.hxx"
28 #include <osl/thread.h>
29 #include "dbase/DIndex.hxx"
30 #include <tools/debug.hxx>
31 #include "diagnose_ex.h"
32
33 #include <algorithm>
34
35
36 using namespace connectivity;
37 using namespace connectivity::dbase;
38 using namespace connectivity::file;
39 using namespace com::sun::star::sdbc;
40 // -----------------------------------------------------------------------------
ONDXKey(sal_uInt32 nRec)41 ONDXKey::ONDXKey(sal_uInt32 nRec)
42 :nRecord(nRec)
43 {
44 }
45 // -----------------------------------------------------------------------------
ONDXKey(const ORowSetValue & rVal,sal_Int32 eType,sal_uInt32 nRec)46 ONDXKey::ONDXKey(const ORowSetValue& rVal, sal_Int32 eType, sal_uInt32 nRec)
47 : ONDXKey_BASE(eType)
48 , nRecord(nRec)
49 , xValue(rVal)
50 {
51 }
52 // -----------------------------------------------------------------------------
ONDXKey(const rtl::OUString & aStr,sal_uInt32 nRec)53 ONDXKey::ONDXKey(const rtl::OUString& aStr, sal_uInt32 nRec)
54 : ONDXKey_BASE(::com::sun::star::sdbc::DataType::VARCHAR)
55 ,nRecord(nRec)
56 {
57 if (aStr.getLength())
58 {
59 xValue = aStr;
60 xValue.setBound(sal_True);
61 }
62 }
63 // -----------------------------------------------------------------------------
64
ONDXKey(double aVal,sal_uInt32 nRec)65 ONDXKey::ONDXKey(double aVal, sal_uInt32 nRec)
66 : ONDXKey_BASE(::com::sun::star::sdbc::DataType::DOUBLE)
67 ,nRecord(nRec)
68 ,xValue(aVal)
69 {
70 }
71 // -----------------------------------------------------------------------------
72
73 //==================================================================
74 // Index Seite
75 //==================================================================
ONDXPage(ODbaseIndex & rInd,sal_uInt32 nPos,ONDXPage * pParent)76 ONDXPage::ONDXPage(ODbaseIndex& rInd, sal_uInt32 nPos, ONDXPage* pParent)
77 :nPagePos(nPos)
78 ,bModified(sal_False)
79 ,nCount(0)
80 ,aParent(pParent)
81 ,rIndex(rInd)
82 ,ppNodes(NULL)
83 {
84 sal_uInt16 nT = rIndex.getHeader().db_maxkeys;
85 ppNodes = new ONDXNode[nT];
86 }
87
88 //------------------------------------------------------------------
~ONDXPage()89 ONDXPage::~ONDXPage()
90 {
91 delete[] ppNodes;
92 // delete aParent;
93 // delete aChild;
94 }
95 //------------------------------------------------------------------
QueryDelete()96 void ONDXPage::QueryDelete()
97 {
98 // Ablegen im GarbageCollector
99 if (IsModified() && rIndex.m_pFileStream)
100 (*rIndex.m_pFileStream) << *this;
101
102 bModified = sal_False;
103 if (rIndex.UseCollector())
104 {
105 if (aChild.Is())
106 aChild->Release(sal_False);
107
108 for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
109 {
110 if (ppNodes[i].GetChild().Is())
111 ppNodes[i].GetChild()->Release(sal_False);
112
113 ppNodes[i] = ONDXNode();
114 }
115 RestoreNoDelete();
116
117 nCount = 0;
118 aParent.Clear();
119 rIndex.Collect(this);
120 }
121 else
122 SvRefBase::QueryDelete();
123 }
124 //------------------------------------------------------------------
GetChild(ODbaseIndex * pIndex)125 ONDXPagePtr& ONDXPage::GetChild(ODbaseIndex* pIndex)
126 {
127 if (!aChild.Is() && pIndex)
128 {
129 aChild = rIndex.CreatePage(aChild.GetPagePos(),this,aChild.HasPage());
130 }
131 return aChild;
132 }
133
134 //------------------------------------------------------------------
FindPos(const ONDXKey & rKey) const135 sal_uInt16 ONDXPage::FindPos(const ONDXKey& rKey) const
136 {
137 // sucht nach Platz fuer den vorgegeben key auf einer Seite
138 sal_uInt16 i = 0;
139 while (i < nCount && rKey > ((*this)[i]).GetKey())
140 i++;
141
142 return i;
143 }
144
145 //------------------------------------------------------------------
Find(const ONDXKey & rKey)146 sal_Bool ONDXPage::Find(const ONDXKey& rKey)
147 {
148 // sucht den vorgegeben key
149 // Besonderheit: gelangt der Algorithmus ans Ende
150 // wird immer die aktuelle Seite und die Knotenposition vermerkt
151 // auf die die Bedingung <= zutrifft
152 // dieses findet beim Insert besondere Beachtung
153 sal_uInt16 i = 0;
154 while (i < nCount && rKey > ((*this)[i]).GetKey())
155 i++;
156
157 sal_Bool bResult = sal_False;
158
159 if (!IsLeaf())
160 {
161 // weiter absteigen
162 ONDXPagePtr aPage = (i==0) ? GetChild(&rIndex) : ((*this)[i-1]).GetChild(&rIndex, this);
163 bResult = aPage.Is() && aPage->Find(rKey);
164 }
165 else if (i == nCount)
166 {
167 rIndex.m_aCurLeaf = this;
168 rIndex.m_nCurNode = i - 1;
169 bResult = sal_False;
170 }
171 else
172 {
173 bResult = rKey == ((*this)[i]).GetKey();
174 rIndex.m_aCurLeaf = this;
175 rIndex.m_nCurNode = bResult ? i : i - 1;
176 }
177 return bResult;
178 }
179
180 //------------------------------------------------------------------
Insert(ONDXNode & rNode,sal_uInt32 nRowsLeft)181 sal_Bool ONDXPage::Insert(ONDXNode& rNode, sal_uInt32 nRowsLeft)
182 {
183 // beim Erzeugen eines Index koennen auch mehrere Knoten eingefuegt werden
184 // diese sin dann aufsteigend sortiert
185 sal_Bool bAppend = nRowsLeft > 0;
186 if (IsFull())
187 {
188 sal_Bool bResult = sal_True;
189 ONDXNode aSplitNode;
190 if (bAppend)
191 aSplitNode = rNode;
192 else
193 {
194 // merken des letzten Knotens
195 aSplitNode = (*this)[nCount-1];
196 if(rNode.GetKey() <= aSplitNode.GetKey())
197 {
198
199 // und damit habe ich im folgenden praktisch eine Node weniger
200 if (IsLeaf() && this == &rIndex.m_aCurLeaf)
201 {
202 // geht davon aus, dass der Knoten, auf dem die Bedingung (<=)
203 // zutrifft, als m_nCurNode gesetzt ist
204 --nCount; // (sonst bekomme ich u.U. Assertions und GPFs - 60593)
205 bResult = Insert(rIndex.m_nCurNode + 1, rNode);
206 }
207 else // Position unbekannt
208 {
209 sal_uInt16 nPos = NODE_NOTFOUND;
210 while (++nPos < nCount && rNode.GetKey() > ((*this)[nPos]).GetKey()) ;
211
212 --nCount; // (sonst bekomme ich u.U. Assertions und GPFs - 60593)
213 bResult = Insert(nPos, rNode);
214 }
215
216 // konnte der neue Knoten eingefuegt werden
217 if (!bResult)
218 {
219 nCount++;
220 aSplitNode = rNode;
221 }
222 }
223 else
224 aSplitNode = rNode;
225 }
226
227 sal_uInt32 nNewPagePos = rIndex.GetPageCount();
228 sal_uInt32 nNewPageCount = nNewPagePos + 1;
229
230 // Herausgeloesten Knoten beim Vater einfuegen
231 if (!HasParent())
232 {
233 // Kein Vater, dann neue Wurzel
234 ONDXPagePtr aNewRoot = rIndex.CreatePage(nNewPagePos + 1);
235 aNewRoot->SetChild(this);
236
237 rIndex.m_aRoot = aNewRoot;
238 rIndex.SetRootPos(nNewPagePos + 1);
239 rIndex.SetPageCount(++nNewPageCount);
240 }
241
242 // neues blatt erzeugen und Seite aufteilen
243 ONDXPagePtr aNewPage = rIndex.CreatePage(nNewPagePos,aParent);
244 rIndex.SetPageCount(nNewPageCount);
245
246 // wieviele Knoten weren noch eingefuegt
247 // kommen noch ausreichend, dann koennen die Seiten bis zum Rand vollgestopft werden
248
249 ONDXNode aInnerNode;
250 if (!IsLeaf() || nRowsLeft < (sal_uInt32)(rIndex.GetMaxNodes() / 2))
251 aInnerNode = Split(*aNewPage);
252 else
253 {
254 aInnerNode = (*this)[nCount - 1];
255 //aInnerNode = aSplitNode;
256
257 // Knoten zeigt auf neue Seite
258 aInnerNode.SetChild(aNewPage);
259
260 // innere Knoten haben keine Recordnummer
261 if (rIndex.isUnique())
262 aInnerNode.GetKey().ResetRecord();
263
264 // neue Seite zeigt nun auf Seite des herausgeloesten Knoten
265 if (!IsLeaf())
266 aNewPage->SetChild(aInnerNode.GetChild());
267 }
268
269 aNewPage->Append(aSplitNode);
270 ONDXPagePtr aTempParent = aParent;
271 if (IsLeaf())
272 {
273 rIndex.m_aCurLeaf = aNewPage;
274 rIndex.m_nCurNode = rIndex.m_aCurLeaf->Count() - 1;
275
276 // Freigeben nicht benoetigter Seiten, danach besteht keine Referenz
277 // mehr auf die Seite, danach kann 'this' nicht mehr gueltig sein!!!
278 ReleaseFull();
279 }
280
281 // Einfuegen des herausgeloesten Knotens
282 return aTempParent->Insert(aInnerNode);
283 }
284 else // Seite einfach weiter auffuellen
285 {
286 if (bAppend)
287 {
288 if (IsLeaf())
289 rIndex.m_nCurNode = nCount - 1;
290 return Append(rNode);
291 }
292 else
293 {
294 sal_uInt16 nNodePos = FindPos(rNode.GetKey());
295 if (IsLeaf())
296 rIndex.m_nCurNode = nNodePos;
297
298 return Insert(nNodePos, rNode);
299 }
300 }
301 }
302
303 //------------------------------------------------------------------
Insert(sal_uInt16 nPos,ONDXNode & rNode)304 sal_Bool ONDXPage::Insert(sal_uInt16 nPos, ONDXNode& rNode)
305 {
306 sal_uInt16 nMaxCount = rIndex.getHeader().db_maxkeys;
307 if (nPos >= nMaxCount)
308 return sal_False;
309
310 if (nCount)
311 {
312 ++nCount;
313 // nach rechts verschieben
314 for (sal_uInt16 i = std::min((sal_uInt16)(nMaxCount-1), (sal_uInt16)(nCount-1)); nPos < i; --i)
315 (*this)[i] = (*this)[i-1];
316 }
317 else
318 if (nCount < nMaxCount)
319 nCount++;
320
321 // einfuegen an der Position
322 ONDXNode& rInsertNode = (*this)[nPos];
323 rInsertNode = rNode;
324 if (rInsertNode.GetChild().Is())
325 {
326 rInsertNode.GetChild()->SetParent(this);
327 rNode.GetChild()->SetParent(this);
328 }
329
330 bModified = sal_True;
331
332 return sal_True;
333 }
334
335 //------------------------------------------------------------------
Append(ONDXNode & rNode)336 sal_Bool ONDXPage::Append(ONDXNode& rNode)
337 {
338 DBG_ASSERT(!IsFull(), "kein Append moeglich");
339 return Insert(nCount, rNode);
340 }
341 //------------------------------------------------------------------
Release(sal_Bool bSave)342 void ONDXPage::Release(sal_Bool bSave)
343 {
344 // freigeben der Pages
345 if (aChild.Is())
346 aChild->Release(bSave);
347
348 // Pointer freigeben
349 aChild.Clear();
350
351 for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
352 {
353 if (ppNodes[i].GetChild())
354 ppNodes[i].GetChild()->Release(bSave);
355
356 ppNodes[i].GetChild().Clear();
357 }
358 aParent = NULL;
359 }
360 //------------------------------------------------------------------
ReleaseFull(sal_Bool bSave)361 void ONDXPage::ReleaseFull(sal_Bool bSave)
362 {
363 ONDXPagePtr aTempParent = aParent;
364 Release(bSave);
365
366 if (aTempParent.Is())
367 {
368 // Freigeben nicht benoetigter Seiten, danach besteht keine Referenz
369 // mehr auf die Seite, danach kann 'this' nicht mehr gueltig sein!!!
370 sal_uInt16 nParentPos = aTempParent->Search(this);
371 if (nParentPos != NODE_NOTFOUND)
372 (*aTempParent)[nParentPos].GetChild().Clear();
373 else
374 aTempParent->GetChild().Clear();
375 }
376 }
377 //------------------------------------------------------------------
Delete(sal_uInt16 nNodePos)378 sal_Bool ONDXPage::Delete(sal_uInt16 nNodePos)
379 {
380 if (IsLeaf())
381 {
382 // Letztes Element wird geloescht
383 if (nNodePos == (nCount - 1))
384 {
385 ONDXNode aNode = (*this)[nNodePos];
386
387 // beim Parent muss nun der KeyValue ausgetauscht werden
388 if (HasParent())
389 aParent->SearchAndReplace(aNode.GetKey(),
390 (*this)[nNodePos-1].GetKey());
391 }
392 }
393
394 // Loeschen des Knoten
395 Remove(nNodePos);
396
397 // Unterlauf
398 if (HasParent() && nCount < (rIndex.GetMaxNodes() / 2))
399 {
400 // Feststellen, welcher Knoten auf die Seite zeigt
401 sal_uInt16 nParentNodePos = aParent->Search(this);
402 // letzte Element auf Vaterseite
403 // -> zusammenlegen mit vorletzter Seite
404 if (nParentNodePos == (aParent->Count() - 1))
405 {
406 if (!nParentNodePos)
407 // zusammenlegen mit linken nachbarn
408 Merge(nParentNodePos,aParent->GetChild(&rIndex));
409 else
410 Merge(nParentNodePos,(*aParent)[nParentNodePos-1].GetChild(&rIndex,aParent));
411 }
412 // sonst Seite mit naechster Seite zusammenlegen
413 else
414 {
415 // zusammenlegen mit rechten nachbarn
416 Merge(nParentNodePos + 1,((*aParent)[nParentNodePos + 1].GetChild(&rIndex,aParent)));
417 nParentNodePos++;
418 }
419 if (HasParent() && !(*aParent)[nParentNodePos].HasChild())
420 aParent->Delete(nParentNodePos);
421 /*
422 // letzte Element auf Vaterseite
423 // -> zusammenlegen mit vorletzter Seite
424 if (nParentNodePos == (aParent->Count() - 1))
425 {
426 if (!nParentNodePos)
427 // zusammenlegen mit linken nachbarn
428 Merge(nParentNodePos,aParent->GetChild(&rIndex));
429 else
430 Merge(nParentNodePos,(*aParent)[nParentNodePos-1].GetChild(&rIndex,aParent));
431 }
432 // sonst Seite mit naechster Seite zusammenlegen
433 else if(nParentNodePos != NODE_NOTFOUND)
434 {
435 // zusammenlegen mit rechten nachbarn
436 Merge(nParentNodePos + 1,((*aParent)[nParentNodePos + 1].GetChild(&rIndex,aParent)));
437 nParentNodePos++;
438 }
439 else // Sonderbehandlung
440 {
441 // Page ist aChild Page vom Parent => erste Page aus ppNodes an aChild anhaengen
442 Merge(0,(*aParent)[0].GetChild(&rIndex,aParent));
443 nParentNodePos = 0;
444 }
445
446 if (HasParent() && !(*aParent)[nParentNodePos].HasChild())
447 aParent->Delete(nParentNodePos);
448 */
449
450 }
451 else if (IsRoot())
452 // Sicherstellen das die Position der Wurzel festgehalten wird
453 rIndex.SetRootPos(nPagePos);
454 return sal_True;
455 }
456
457
458 //------------------------------------------------------------------
Split(ONDXPage & rPage)459 ONDXNode ONDXPage::Split(ONDXPage& rPage)
460 {
461 DBG_ASSERT(IsFull(), "Falsches Splitting");
462 /* Aufteilen einer Seite auf zwei
463 Blatt:
464 Seite 1 behaelt (n - (n/2))
465 Seite 2 erhaelt (n/2)
466 Knoten n/2 wird dupliziert
467 Innerer Knoten:
468 Seite 1 behaelt (n+1)/2
469 Seite 2 erhaelt (n/2-1)
470 Knoten ((n+1)/2 + 1) : wird herausgenommen
471 */
472 ONDXNode aResultNode;
473 if (IsLeaf())
474 {
475 for (sal_uInt16 i = (nCount - (nCount / 2)), j = 0 ; i < nCount; i++)
476 rPage.Insert(j++,(*this)[i]);
477
478 // dieser Knoten enthaelt einen Schluessel der noch einmal im Tree vorkommt
479 // und ersetzt werden muss
480 ONDXNode aLastNode = (*this)[nCount - 1];
481 nCount = nCount - (nCount / 2);
482 aResultNode = (*this)[nCount - 1];
483
484 if (HasParent())
485 aParent->SearchAndReplace(aLastNode.GetKey(),
486 aResultNode.GetKey());
487 }
488 else
489 {
490 for (sal_uInt16 i = (nCount + 1) / 2 + 1, j = 0 ; i < nCount; i++)
491 rPage.Insert(j++,(*this)[i]);
492
493 aResultNode = (*this)[(nCount + 1) / 2];
494 nCount = (nCount + 1) / 2;
495
496 // neue Seite zeigt nun auf Seite des herausgeloesten Knoten
497 rPage.SetChild(aResultNode.GetChild());
498 }
499 // Knoten zeigt auf neue Seite
500 aResultNode.SetChild(&rPage);
501
502 // innere Knoten haben keine Recordnummer
503 if (rIndex.isUnique())
504 aResultNode.GetKey().ResetRecord();
505 bModified = sal_True;
506 return aResultNode;
507 }
508
509 //------------------------------------------------------------------
Merge(sal_uInt16 nParentNodePos,ONDXPagePtr xPage)510 void ONDXPage::Merge(sal_uInt16 nParentNodePos, ONDXPagePtr xPage)
511 {
512 DBG_ASSERT(HasParent(), "kein Vater vorhanden");
513 DBG_ASSERT(nParentNodePos != NODE_NOTFOUND, "Falscher Indexaufbau");
514
515 /* Zusammenlegen zweier Seiten */
516 ONDXNode aResultNode;
517 sal_uInt16 nMaxNodes = rIndex.GetMaxNodes(),
518 nMaxNodes_2 = nMaxNodes / 2;
519
520 // Feststellen ob Seite rechter oder linker Nachbar
521 sal_Bool bRight = ((*xPage)[0].GetKey() > (*this)[0].GetKey()); // sal_True, wenn xPage die rechte Seite ist
522 sal_uInt16 nNewCount = (*xPage).Count() + Count();
523
524 if (IsLeaf())
525 {
526 // Bedingung fuers zusammenlegen
527 if (nNewCount < (nMaxNodes_2 * 2))
528 {
529 sal_uInt16 nLastNode = bRight ? Count() - 1 : xPage->Count() - 1;
530 if (bRight)
531 {
532 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
533 // alle Knoten aus xPage auf den linken Knoten verschieben (anhaengen)
534 while (xPage->Count())
535 {
536 Append((*xPage)[0]);
537 xPage->Remove(0);
538 }
539 }
540 else
541 {
542 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
543 // xPage ist die linke Page und THIS die rechte
544 while (xPage->Count())
545 {
546 Insert(0,(*xPage)[xPage->Count()-1]);
547 xPage->Remove(xPage->Count()-1);
548 }
549 // alte Position von xPage beim Parent mit this ersetzen
550 if (nParentNodePos)
551 (*aParent)[nParentNodePos-1].SetChild(this,aParent);
552 else // oder als rechten Knoten setzen
553 aParent->SetChild(this);
554 aParent->SetModified(sal_True);
555
556 }
557
558 // Child beziehung beim Vaterknoten aufheben
559 (*aParent)[nParentNodePos].SetChild();
560 // Austauschen des KnotenWertes, nur wenn geaenderte Page
561 // die linke ist, ansonsten werde
562
563 if(aParent->IsRoot() && aParent->Count() == 1)
564 {
565 (*aParent)[0].SetChild();
566 aParent->ReleaseFull();
567 aParent = NULL;
568 rIndex.SetRootPos(nPagePos);
569 rIndex.m_aRoot = this;
570 SetModified(sal_True);
571 }
572 else
573 aParent->SearchAndReplace((*this)[nLastNode].GetKey(),(*this)[nCount-1].GetKey());
574
575 xPage->SetModified(sal_False);
576 xPage->ReleaseFull(); // wird nicht mehr benoetigt
577 }
578 // Ausgleichen der Elemente nNewCount >= (nMaxNodes_2 * 2)
579 else
580 {
581 if (bRight)
582 {
583 // alle Knoten aus xPage auf den linken Knoten verschieben (anhaengen)
584 ONDXNode aReplaceNode = (*this)[nCount - 1];
585 while (nCount < nMaxNodes_2)
586 {
587 Append((*xPage)[0]);
588 xPage->Remove(0);
589 }
590 // Austauschen des KnotenWertes: Setzt alten letzten Wert durch den letzten von xPage
591 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[nCount-1].GetKey());
592 }
593 else
594 {
595 // alle Knoten aus this vor die xPage Knoten einfuegen
596 ONDXNode aReplaceNode = (*this)[nCount - 1];
597 while (xPage->Count() < nMaxNodes_2)
598 {
599 xPage->Insert(0,(*this)[nCount-1]);
600 Remove(nCount-1);
601 }
602 // Austauschen des KnotenWertes
603 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[Count()-1].GetKey());
604 }
605 }
606 }
607 else // !IsLeaf()
608 {
609 // Bedingung fuers zusammenlegen
610 if (nNewCount < nMaxNodes_2 * 2)
611 {
612 if (bRight)
613 {
614 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
615 // Vaterknoten wird mit integriert
616 // erhaelt zunaechst Child von xPage
617 (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
618 Append((*aParent)[nParentNodePos]);
619 for (sal_uInt16 i = 0 ; i < xPage->Count(); i++)
620 Append((*xPage)[i]);
621 }
622 else
623 {
624 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
625 // Vaterknoten wird mit integriert
626 // erhaelt zunaechst Child
627 (*aParent)[nParentNodePos].SetChild(GetChild(),aParent); // Parent merkt sich mein Child
628 Insert(0,(*aParent)[nParentNodePos]); // Node vom Parent bei mir einfuegen
629 while (xPage->Count())
630 {
631 Insert(0,(*xPage)[xPage->Count()-1]);
632 xPage->Remove(xPage->Count()-1);
633 }
634 SetChild(xPage->GetChild());
635
636 if (nParentNodePos)
637 (*aParent)[nParentNodePos-1].SetChild(this,aParent);
638 else
639 aParent->SetChild(this);
640 }
641
642 // danach wird der Vaterknoten zurueckgesetzt
643 (*aParent)[nParentNodePos].SetChild();
644 aParent->SetModified(sal_True);
645
646 if(aParent->IsRoot() && aParent->Count() == 1)
647 {
648 (*aParent).SetChild();
649 aParent->ReleaseFull();
650 aParent = NULL;
651 rIndex.SetRootPos(nPagePos);
652 rIndex.m_aRoot = this;
653 SetModified(sal_True);
654 }
655 else if(nParentNodePos)
656 // Austauschen des KnotenWertes
657 // beim Append wird der Bereich erweitert, beim INsert verweist der alte Knoten von xPage auf this
658 // deshalb muss der Knoten auch hier aktualisiert werden
659 aParent->SearchAndReplace((*aParent)[nParentNodePos-1].GetKey(),(*aParent)[nParentNodePos].GetKey());
660
661 xPage->SetModified(sal_False);
662 xPage->ReleaseFull();
663 }
664 // Ausgleichen der Elemente
665 else
666 {
667 if (bRight)
668 {
669 while (nCount < nMaxNodes_2)
670 {
671 (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
672 Append((*aParent)[nParentNodePos]);
673 (*aParent)[nParentNodePos] = (*xPage)[0];
674 xPage->Remove(0);
675 }
676 xPage->SetChild((*aParent)[nParentNodePos].GetChild());
677 (*aParent)[nParentNodePos].SetChild(xPage,aParent);
678 }
679 else
680 {
681 while (nCount < nMaxNodes_2)
682 {
683 (*aParent)[nParentNodePos].SetChild(GetChild(),aParent);
684 Insert(0,(*aParent)[nParentNodePos]);
685 (*aParent)[nParentNodePos] = (*xPage)[xPage->Count()-1];
686 xPage->Remove(xPage->Count()-1);
687 }
688 SetChild((*aParent)[nParentNodePos].GetChild());
689 (*aParent)[nParentNodePos].SetChild(this,aParent);
690
691 }
692 aParent->SetModified(sal_True);
693 }
694 }
695 }
696 //==================================================================
697 // ONDXNode
698 //==================================================================
699
700 //------------------------------------------------------------------
Read(SvStream & rStream,ODbaseIndex & rIndex)701 void ONDXNode::Read(SvStream &rStream, ODbaseIndex& rIndex)
702 {
703 rStream >> aKey.nRecord; // schluessel
704
705 if (rIndex.getHeader().db_keytype)
706 {
707 double aDbl;
708 rStream >> aDbl;
709 aKey = ONDXKey(aDbl,aKey.nRecord);
710 }
711 else
712 {
713 ByteString aBuf;
714 sal_uInt16 nLen = rIndex.getHeader().db_keylen;
715 char* pStr = aBuf.AllocBuffer(nLen+1);
716
717 rStream.Read(pStr,nLen);
718 pStr[nLen] = 0;
719 aBuf.ReleaseBufferAccess();
720 aBuf.EraseTrailingChars();
721
722 // aKey = ONDXKey((aBuf,rIndex.GetDBFConnection()->GetCharacterSet()) ,aKey.nRecord);
723 aKey = ONDXKey(::rtl::OUString(aBuf.GetBuffer(),aBuf.Len(),rIndex.m_pTable->getConnection()->getTextEncoding()) ,aKey.nRecord);
724 }
725 rStream >> aChild;
726 }
727
728 union NodeData
729 {
730 double aDbl;
731 char aData[128];
732 } aNodeData;
733 //------------------------------------------------------------------
Write(SvStream & rStream,const ONDXPage & rPage) const734 void ONDXNode::Write(SvStream &rStream, const ONDXPage& rPage) const
735 {
736 const ODbaseIndex& rIndex = rPage.GetIndex();
737 if (!rIndex.isUnique() || rPage.IsLeaf())
738 rStream << (sal_uInt32)aKey.nRecord; // schluessel
739 else
740 rStream << (sal_uInt32)0; // schluessel
741
742 if (rIndex.getHeader().db_keytype) // double
743 {
744 if (aKey.getValue().isNull())
745 {
746 memset(aNodeData.aData,0,rIndex.getHeader().db_keylen);
747 rStream.Write((sal_uInt8*)aNodeData.aData,rIndex.getHeader().db_keylen);
748 }
749 else
750 rStream << (double) aKey.getValue();
751 }
752 else
753 {
754 memset(aNodeData.aData,0x20,rIndex.getHeader().db_keylen);
755 if (!aKey.getValue().isNull())
756 {
757 ::rtl::OUString sValue = aKey.getValue();
758 ByteString aText(sValue.getStr(), rIndex.m_pTable->getConnection()->getTextEncoding());
759 strncpy(aNodeData.aData,aText.GetBuffer(),std::min(rIndex.getHeader().db_keylen, aText.Len()));
760 }
761 rStream.Write((sal_uInt8*)aNodeData.aData,rIndex.getHeader().db_keylen);
762 }
763 rStream << aChild;
764 }
765
766
767 //------------------------------------------------------------------
GetChild(ODbaseIndex * pIndex,ONDXPage * pParent)768 ONDXPagePtr& ONDXNode::GetChild(ODbaseIndex* pIndex, ONDXPage* pParent)
769 {
770 if (!aChild.Is() && pIndex)
771 {
772 aChild = pIndex->CreatePage(aChild.GetPagePos(),pParent,aChild.HasPage());
773 }
774 return aChild;
775 }
776
777 //==================================================================
778 // ONDXKey
779 //==================================================================
780 //------------------------------------------------------------------
IsText(sal_Int32 eType)781 sal_Bool ONDXKey::IsText(sal_Int32 eType)
782 {
783 return eType == DataType::VARCHAR || eType == DataType::CHAR;
784 }
785
786 //------------------------------------------------------------------
Compare(const ONDXKey & rKey) const787 StringCompare ONDXKey::Compare(const ONDXKey& rKey) const
788 {
789 // DBG_ASSERT(is(), "Falscher Indexzugriff");
790 StringCompare eResult;
791
792 if (getValue().isNull())
793 {
794 if (rKey.getValue().isNull() || (rKey.IsText(getDBType()) && !rKey.getValue().getString().getLength()))
795 eResult = COMPARE_EQUAL;
796 else
797 eResult = COMPARE_LESS;
798 }
799 else if (rKey.getValue().isNull())
800 {
801 if (getValue().isNull() || (IsText(getDBType()) && !getValue().getString().getLength()))
802 eResult = COMPARE_EQUAL;
803 else
804 eResult = COMPARE_GREATER;
805 }
806 else if (IsText(getDBType()))
807 {
808 sal_Int32 nRes = getValue().getString().compareTo(rKey.getValue());
809 eResult = (nRes > 0) ? COMPARE_GREATER : (nRes == 0) ? COMPARE_EQUAL : COMPARE_LESS;
810 }
811 else
812 {
813 double m = getValue(),n = rKey.getValue();
814 eResult = (m > n) ? COMPARE_GREATER : (n == m) ? COMPARE_EQUAL : COMPARE_LESS;
815 }
816
817 // Record vergleich, wenn Index !Unique
818 if (eResult == COMPARE_EQUAL && nRecord && rKey.nRecord)
819 eResult = (nRecord > rKey.nRecord) ? COMPARE_GREATER :
820 (nRecord == rKey.nRecord) ? COMPARE_EQUAL : COMPARE_LESS;
821
822 return eResult;
823 }
824 // -----------------------------------------------------------------------------
setValue(const ORowSetValue & _rVal)825 void ONDXKey::setValue(const ORowSetValue& _rVal)
826 {
827 xValue = _rVal;
828 }
829 // -----------------------------------------------------------------------------
getValue() const830 const ORowSetValue& ONDXKey::getValue() const
831 {
832 return xValue;
833 }
834 // -----------------------------------------------------------------------------
operator >>(SvStream & rStream,ONDXPagePtr & rPage)835 SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPagePtr& rPage)
836 {
837 rStream >> rPage.nPagePos;
838 return rStream;
839 }
840 // -----------------------------------------------------------------------------
operator <<(SvStream & rStream,const ONDXPagePtr & rPage)841 SvStream& connectivity::dbase::operator << (SvStream &rStream, const ONDXPagePtr& rPage)
842 {
843 rStream << rPage.nPagePos;
844 return rStream;
845 }
846 // -----------------------------------------------------------------------------
847 //==================================================================
848 // ONDXPagePtr
849 //==================================================================
850 //------------------------------------------------------------------
ONDXPagePtr(const ONDXPagePtr & rRef)851 ONDXPagePtr::ONDXPagePtr(const ONDXPagePtr& rRef)
852 :ONDXPageRef(rRef)
853 ,nPagePos(rRef.nPagePos)
854 {
855 }
856
857 //------------------------------------------------------------------
ONDXPagePtr(ONDXPage * pRefPage)858 ONDXPagePtr::ONDXPagePtr(ONDXPage* pRefPage)
859 :ONDXPageRef(pRefPage)
860 ,nPagePos(0)
861 {
862 if (pRefPage)
863 nPagePos = pRefPage->GetPagePos();
864 }
865 //------------------------------------------------------------------
operator =(const ONDXPagePtr & rRef)866 ONDXPagePtr& ONDXPagePtr::operator=(const ONDXPagePtr& rRef)
867 {
868 ONDXPageRef::operator=(rRef);
869 nPagePos = rRef.nPagePos;
870 return *this;
871 }
872
873 //------------------------------------------------------------------
operator =(ONDXPage * pRef)874 ONDXPagePtr& ONDXPagePtr::operator= (ONDXPage* pRef)
875 {
876 ONDXPageRef::operator=(pRef);
877 nPagePos = (pRef) ? pRef->GetPagePos() : 0;
878 return *this;
879 }
880 // -----------------------------------------------------------------------------
881 static sal_uInt32 nValue;
882 //------------------------------------------------------------------
operator >>(SvStream & rStream,ONDXPage & rPage)883 SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPage& rPage)
884 {
885 rStream.Seek(rPage.GetPagePos() * PAGE_SIZE);
886 rStream >> nValue >> rPage.aChild;
887 rPage.nCount = sal_uInt16(nValue);
888
889 // DBG_ASSERT(rPage.nCount && rPage.nCount < rPage.GetIndex().GetMaxNodes(), "Falscher Count");
890 for (sal_uInt16 i = 0; i < rPage.nCount; i++)
891 rPage[i].Read(rStream, rPage.GetIndex());
892 return rStream;
893 }
894
895 //------------------------------------------------------------------
operator <<(SvStream & rStream,const ONDXPage & rPage)896 SvStream& connectivity::dbase::operator << (SvStream &rStream, const ONDXPage& rPage)
897 {
898 // Seite existiert noch nicht
899 sal_uIntPtr nSize = (rPage.GetPagePos() + 1) * PAGE_SIZE;
900 if (nSize > rStream.Seek(STREAM_SEEK_TO_END))
901 {
902 rStream.SetStreamSize(nSize);
903 rStream.Seek(rPage.GetPagePos() * PAGE_SIZE);
904
905 char aEmptyData[PAGE_SIZE];
906 memset(aEmptyData,0x00,PAGE_SIZE);
907 rStream.Write((sal_uInt8*)aEmptyData,PAGE_SIZE);
908 }
909 sal_uIntPtr nCurrentPos = rStream.Seek(rPage.GetPagePos() * PAGE_SIZE);
910 OSL_UNUSED( nCurrentPos );
911
912 nValue = rPage.nCount;
913 rStream << nValue << rPage.aChild;
914
915 sal_uInt16 i = 0;
916 for (; i < rPage.nCount; i++)
917 rPage[i].Write(rStream, rPage);
918
919 // check if we have to fill the stream with '\0'
920 if(i < rPage.rIndex.getHeader().db_maxkeys)
921 {
922 sal_uIntPtr nTell = rStream.Tell() % PAGE_SIZE;
923 sal_uInt16 nBufferSize = rStream.GetBufferSize();
924 sal_uIntPtr nRemainSize = nBufferSize - nTell;
925 if ( nRemainSize <= nBufferSize )
926 {
927 char* pEmptyData = new char[nRemainSize];
928 memset(pEmptyData,0x00,nRemainSize);
929 rStream.Write((sal_uInt8*)pEmptyData,nRemainSize);
930 rStream.Seek(nTell);
931 delete [] pEmptyData;
932 }
933 }
934 return rStream;
935 }
936 // -----------------------------------------------------------------------------
937 #if OSL_DEBUG_LEVEL > 1
938 //------------------------------------------------------------------
PrintPage()939 void ONDXPage::PrintPage()
940 {
941 DBG_TRACE4("\nSDB: -----------Page: %d Parent: %d Count: %d Child: %d-----",
942 nPagePos, HasParent() ? aParent->GetPagePos() : 0 ,nCount, aChild.GetPagePos());
943
944 for (sal_uInt16 i = 0; i < nCount; i++)
945 {
946 ONDXNode rNode = (*this)[i];
947 ONDXKey& rKey = rNode.GetKey();
948 if (!IsLeaf())
949 rNode.GetChild(&rIndex, this);
950
951 if (rKey.getValue().isNull())
952 {
953 DBG_TRACE2("SDB: [%d,NULL,%d]",rKey.GetRecord(), rNode.GetChild().GetPagePos());
954 }
955 else if (rIndex.getHeader().db_keytype)
956 {
957 DBG_TRACE3("SDB: [%d,%f,%d]",rKey.GetRecord(), rKey.getValue().getDouble(),rNode.GetChild().GetPagePos());
958 }
959 else
960 {
961 DBG_TRACE3("SDB: [%d,%s,%d]",rKey.GetRecord(), (const char* )ByteString(rKey.getValue().getString().getStr(), rIndex.m_pTable->getConnection()->getTextEncoding()).GetBuffer(),rNode.GetChild().GetPagePos());
962 }
963 }
964 DBG_TRACE("SDB: -----------------------------------------------\n");
965 if (!IsLeaf())
966 {
967 #if OSL_DEBUG_LEVEL > 1
968 GetChild(&rIndex)->PrintPage();
969 for (sal_uInt16 i = 0; i < nCount; i++)
970 {
971 ONDXNode rNode = (*this)[i];
972 rNode.GetChild(&rIndex,this)->PrintPage();
973 }
974 #endif
975 }
976 DBG_TRACE("SDB: ===============================================\n");
977 }
978 #endif
979 // -----------------------------------------------------------------------------
IsFull() const980 sal_Bool ONDXPage::IsFull() const
981 {
982 return Count() == rIndex.getHeader().db_maxkeys;
983 }
984 // -----------------------------------------------------------------------------
985 //------------------------------------------------------------------
Search(const ONDXKey & rSearch)986 sal_uInt16 ONDXPage::Search(const ONDXKey& rSearch)
987 {
988 // binare Suche spaeter
989 sal_uInt16 i = NODE_NOTFOUND;
990 while (++i < Count())
991 if ((*this)[i].GetKey() == rSearch)
992 break;
993
994 return (i < Count()) ? i : NODE_NOTFOUND;
995 }
996
997 //------------------------------------------------------------------
Search(const ONDXPage * pPage)998 sal_uInt16 ONDXPage::Search(const ONDXPage* pPage)
999 {
1000 sal_uInt16 i = NODE_NOTFOUND;
1001 while (++i < Count())
1002 if (((*this)[i]).GetChild() == pPage)
1003 break;
1004
1005 // wenn nicht gefunden, dann wird davon ausgegangen, dass die Seite selbst
1006 // auf die Page zeigt
1007 return (i < Count()) ? i : NODE_NOTFOUND;
1008 }
1009 // -----------------------------------------------------------------------------
1010 // laeuft rekursiv
SearchAndReplace(const ONDXKey & rSearch,ONDXKey & rReplace)1011 void ONDXPage::SearchAndReplace(const ONDXKey& rSearch,
1012 ONDXKey& rReplace)
1013 {
1014 OSL_ENSURE(rSearch != rReplace,"Invalid here:rSearch == rReplace");
1015 if (rSearch != rReplace)
1016 {
1017 sal_uInt16 nPos = NODE_NOTFOUND;
1018 ONDXPage* pPage = this;
1019
1020 while (pPage && (nPos = pPage->Search(rSearch)) == NODE_NOTFOUND)
1021 pPage = pPage->aParent;
1022
1023 if (pPage)
1024 {
1025 (*pPage)[nPos].GetKey() = rReplace;
1026 pPage->SetModified(sal_True);
1027 }
1028 }
1029 }
1030 // -----------------------------------------------------------------------------
operator [](sal_uInt16 nPos)1031 ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos)
1032 {
1033 DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
1034 return ppNodes[nPos];
1035 }
1036
1037 //------------------------------------------------------------------
operator [](sal_uInt16 nPos) const1038 const ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos) const
1039 {
1040 DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
1041 return ppNodes[nPos];
1042 }
1043 // -----------------------------------------------------------------------------
Remove(sal_uInt16 nPos)1044 void ONDXPage::Remove(sal_uInt16 nPos)
1045 {
1046 DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
1047
1048 for (sal_uInt16 i = nPos; i < (nCount-1); i++)
1049 (*this)[i] = (*this)[i+1];
1050
1051 nCount--;
1052 bModified = sal_True;
1053 }
1054 // -----------------------------------------------------------------------------
1055
1056