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 :
21 : #include "stortree.hxx"
22 :
23 : #include "sal/types.h"
24 : #include "osl/diagnose.h"
25 :
26 : #include "store/types.h"
27 :
28 : #include "storbase.hxx"
29 : #include "storbios.hxx"
30 :
31 : using namespace store;
32 :
33 : /*========================================================================
34 : *
35 : * OStoreBTreeNodeData implementation.
36 : *
37 : *======================================================================*/
38 : /*
39 : * OStoreBTreeNodeData.
40 : */
41 6089 : OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
42 6089 : : OStorePageData (nPageSize)
43 : {
44 6089 : base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
45 6089 : base::m_aDescr.m_nUsed = store::htons(self::thePageSize); // usageCount(0)
46 6089 : self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)
47 :
48 6089 : sal_uInt16 const n = capacityCount();
49 6089 : T const t;
50 :
51 182734 : for (sal_uInt16 i = 1; i < n; i++)
52 176645 : m_pData[i] = t;
53 6089 : }
54 :
55 : /*
56 : * find.
57 : */
58 1010580 : sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
59 : {
60 1010580 : sal_Int32 l = 0;
61 1010580 : sal_Int32 r = usageCount() - 1;
62 :
63 4836839 : while (l < r)
64 : {
65 2979557 : sal_Int32 const m = ((l + r) >> 1);
66 :
67 2979557 : if (t.m_aKey == m_pData[m].m_aKey)
68 163878 : return ((sal_uInt16)(m));
69 2815679 : if (t.m_aKey < m_pData[m].m_aKey)
70 1164093 : r = m - 1;
71 : else
72 1651586 : l = m + 1;
73 : }
74 :
75 846702 : sal_uInt16 const k = ((sal_uInt16)(r));
76 846702 : if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
77 263385 : return(k - 1);
78 : else
79 583317 : return(k);
80 : }
81 :
82 : /*
83 : * insert.
84 : */
85 72021 : void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
86 : {
87 72021 : sal_uInt16 const n = usageCount();
88 72021 : sal_uInt16 const m = capacityCount();
89 72021 : if ((n < m) && (i < m))
90 : {
91 : // shift right.
92 72021 : memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));
93 :
94 : // insert.
95 72021 : m_pData[i] = t;
96 72021 : usageCount (n + 1);
97 : }
98 72021 : }
99 :
100 : /*
101 : * remove.
102 : */
103 9 : void OStoreBTreeNodeData::remove (sal_uInt16 i)
104 : {
105 9 : sal_uInt16 const n = usageCount();
106 9 : if (i < n)
107 : {
108 : // shift left.
109 9 : memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T));
110 :
111 : // truncate.
112 9 : m_pData[n - 1] = T();
113 9 : usageCount (n - 1);
114 : }
115 9 : }
116 :
117 : /*
118 : * split (left half copied from right half of left page).
119 : */
120 634 : void OStoreBTreeNodeData::split (const self& rPageL)
121 : {
122 634 : sal_uInt16 const h = capacityCount() / 2;
123 634 : memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
124 634 : truncate (h);
125 634 : }
126 :
127 : /*
128 : * truncate.
129 : */
130 1268 : void OStoreBTreeNodeData::truncate (sal_uInt16 n)
131 : {
132 1268 : sal_uInt16 const m = capacityCount();
133 1268 : T const t;
134 :
135 20288 : for (sal_uInt16 i = n; i < m; i++)
136 19020 : m_pData[i] = t;
137 1268 : usageCount (n);
138 1268 : }
139 :
140 : /*========================================================================
141 : *
142 : * OStoreBTreeNodeObject implementation.
143 : *
144 : *======================================================================*/
145 : /*
146 : * guard.
147 : */
148 84208 : storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
149 : {
150 84208 : return PageHolderObject< page >::guard (m_xPage, nAddr);
151 : }
152 :
153 : /*
154 : * verify.
155 : */
156 6890 : storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
157 : {
158 6890 : return PageHolderObject< page >::verify (m_xPage, nAddr);
159 : }
160 :
161 : /*
162 : * split.
163 : */
164 634 : storeError OStoreBTreeNodeObject::split (
165 : sal_uInt16 nIndexL,
166 : PageHolderObject< page > & rxPageL,
167 : OStorePageBIOS & rBIOS)
168 : {
169 634 : PageHolderObject< page > xPage (m_xPage);
170 634 : if (!xPage.is())
171 0 : return store_E_InvalidAccess;
172 :
173 : // Check left page usage.
174 634 : if (!rxPageL.is())
175 0 : return store_E_InvalidAccess;
176 634 : if (!rxPageL->querySplit())
177 0 : return store_E_None;
178 :
179 : // Construct right page.
180 1268 : PageHolderObject< page > xPageR;
181 634 : if (!xPageR.construct (rBIOS.allocator()))
182 0 : return store_E_OutOfMemory;
183 :
184 : // Split right page off left page.
185 634 : xPageR->split (*rxPageL);
186 634 : xPageR->depth (rxPageL->depth());
187 :
188 : // Allocate right page.
189 1268 : self aNodeR (xPageR.get());
190 634 : storeError eErrCode = rBIOS.allocate (aNodeR);
191 634 : if (eErrCode != store_E_None)
192 0 : return eErrCode;
193 :
194 : // Truncate left page.
195 634 : rxPageL->truncate (rxPageL->capacityCount() / 2);
196 :
197 : // Save left page.
198 1268 : self aNodeL (rxPageL.get());
199 634 : eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
200 634 : if (eErrCode != store_E_None)
201 0 : return eErrCode;
202 :
203 : // Insert right page.
204 634 : OStorePageLink aLink (xPageR->location());
205 634 : xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));
206 :
207 : // Save this page and leave.
208 1268 : return rBIOS.saveObjectAt (*this, location());
209 : }
210 :
211 : /*
212 : * remove (down to leaf node, recursive).
213 : */
214 9 : storeError OStoreBTreeNodeObject::remove (
215 : sal_uInt16 nIndexL,
216 : OStoreBTreeEntry & rEntryL,
217 : OStorePageBIOS & rBIOS)
218 : {
219 9 : PageHolderObject< page > xImpl (m_xPage);
220 9 : page & rPage = (*xImpl);
221 :
222 : // Check depth.
223 9 : storeError eErrCode = store_E_None;
224 9 : if (rPage.depth())
225 : {
226 : // Check link entry.
227 0 : T const aEntryL (rPage.m_pData[nIndexL]);
228 0 : if (!(rEntryL.compare (aEntryL) == T::COMPARE_EQUAL))
229 0 : return store_E_InvalidAccess;
230 :
231 : // Load link node.
232 0 : self aNodeL;
233 0 : eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location());
234 0 : if (eErrCode != store_E_None)
235 0 : return eErrCode;
236 :
237 : // Recurse: remove from link node.
238 0 : eErrCode = aNodeL.remove (0, rEntryL, rBIOS);
239 0 : if (eErrCode != store_E_None)
240 0 : return eErrCode;
241 :
242 : // Check resulting link node usage.
243 0 : PageHolderObject< page > xPageL (aNodeL.get());
244 0 : if (xPageL->usageCount() == 0)
245 : {
246 : // Free empty link node.
247 0 : eErrCode = rBIOS.free (xPageL->location());
248 0 : if (eErrCode != store_E_None)
249 0 : return eErrCode;
250 :
251 : // Remove index.
252 0 : rPage.remove (nIndexL);
253 0 : touch();
254 : }
255 : else
256 : {
257 :
258 : // Relink.
259 0 : rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey;
260 0 : touch();
261 0 : }
262 : }
263 : else
264 : {
265 : // Check leaf entry.
266 9 : if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL))
267 0 : return store_E_NotExists;
268 :
269 : // Save leaf entry.
270 9 : rEntryL = rPage.m_pData[nIndexL];
271 :
272 : // Remove leaf index.
273 9 : rPage.remove (nIndexL);
274 9 : touch();
275 : }
276 :
277 : // Check for modified node.
278 9 : if (dirty())
279 : {
280 : // Save this page.
281 9 : eErrCode = rBIOS.saveObjectAt (*this, location());
282 : }
283 :
284 : // Done.
285 9 : return eErrCode;
286 : }
287 :
288 : /*========================================================================
289 : *
290 : * OStoreBTreeRootObject implementation.
291 : *
292 : *======================================================================*/
293 : /*
294 : * testInvariant.
295 : * Precond: root node page loaded.
296 : */
297 1146290 : bool OStoreBTreeRootObject::testInvariant (char const * message)
298 : {
299 : OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer");
300 1146290 : bool result = ((m_xPage->location() - m_xPage->size()) == 0);
301 : OSL_POSTCOND(result, message); (void) message;
302 1146290 : return result;
303 : }
304 :
305 : /*
306 : * loadOrCreate.
307 : */
308 5440 : storeError OStoreBTreeRootObject::loadOrCreate (
309 : sal_uInt32 nAddr,
310 : OStorePageBIOS & rBIOS)
311 : {
312 5440 : storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
313 5440 : if (eErrCode != store_E_NotExists)
314 0 : return eErrCode;
315 :
316 5440 : eErrCode = construct<page>(rBIOS.allocator());
317 5440 : if (eErrCode != store_E_None)
318 0 : return eErrCode;
319 :
320 5440 : eErrCode = rBIOS.allocate (*this);
321 5440 : if (eErrCode != store_E_None)
322 0 : return eErrCode;
323 :
324 : // Notify caller of the creation.
325 5440 : (void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
326 5440 : return store_E_Pending;
327 : }
328 :
329 : /*
330 : * change.
331 : */
332 15 : storeError OStoreBTreeRootObject::change (
333 : PageHolderObject< page > & rxPageL,
334 : OStorePageBIOS & rBIOS)
335 : {
336 15 : PageHolderObject< page > xPage (m_xPage);
337 15 : (void) testInvariant("OStoreBTreeRootObject::change(): enter");
338 :
339 : // Save root location.
340 15 : sal_uInt32 const nRootAddr = xPage->location();
341 :
342 : // Construct new root.
343 15 : if (!rxPageL.construct (rBIOS.allocator()))
344 0 : return store_E_OutOfMemory;
345 :
346 : // Save this as prev root.
347 15 : storeError eErrCode = rBIOS.allocate (*this);
348 15 : if (eErrCode != store_E_None)
349 0 : return store_E_OutOfMemory;
350 :
351 : // Setup new root.
352 15 : rxPageL->depth (xPage->depth() + 1);
353 15 : rxPageL->m_pData[0] = xPage->m_pData[0];
354 15 : rxPageL->m_pData[0].m_aLink = xPage->location();
355 15 : rxPageL->usageCount(1);
356 :
357 : // Change root.
358 15 : rxPageL.swap (xPage);
359 : {
360 15 : PageHolder tmp (xPage.get());
361 15 : tmp.swap (m_xPage);
362 : }
363 :
364 : // Save this as new root and finish.
365 15 : eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
366 15 : (void) testInvariant("OStoreBTreeRootObject::change(): leave");
367 15 : return eErrCode;
368 : }
369 :
370 : /*
371 : * find_lookup (w/o split()).
372 : * Precond: root node page loaded.
373 : */
374 501743 : storeError OStoreBTreeRootObject::find_lookup (
375 : OStoreBTreeNodeObject & rNode, // [out]
376 : sal_uInt16 & rIndex, // [out]
377 : OStorePageKey const & rKey,
378 : OStorePageBIOS & rBIOS)
379 : {
380 : // Init node w/ root page.
381 501743 : (void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
382 : {
383 501743 : PageHolder tmp (m_xPage);
384 501743 : tmp.swap (rNode.get());
385 : }
386 :
387 : // Setup BTree entry.
388 501743 : T const entry (rKey);
389 :
390 : // Check current page.
391 501743 : PageHolderObject< page > xPage (rNode.get());
392 916828 : for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
393 : {
394 : // Find next page.
395 415085 : page const & rPage = (*xPage);
396 415085 : sal_uInt16 const i = rPage.find(entry);
397 415085 : sal_uInt16 const n = rPage.usageCount();
398 415085 : if (!(i < n))
399 : {
400 : // Path to entry not exists (Must not happen(?)).
401 0 : return store_E_NotExists;
402 : }
403 :
404 : // Check address.
405 415085 : sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
406 415085 : if (nAddr == STORE_PAGE_NULL)
407 : {
408 : // Path to entry not exists (Must not happen(?)).
409 0 : return store_E_NotExists;
410 : }
411 :
412 : // Load next page.
413 415085 : storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
414 415085 : if (eErrCode != store_E_None)
415 0 : return eErrCode;
416 : }
417 :
418 : // Find index.
419 501743 : page const & rPage = (*xPage);
420 501743 : rIndex = rPage.find(entry);
421 501743 : if (!(rIndex < rPage.usageCount()))
422 0 : return store_E_NotExists;
423 :
424 : // Compare entry.
425 501743 : T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
426 : OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error");
427 501743 : if (eResult == T::COMPARE_LESS)
428 0 : return store_E_Unknown;
429 :
430 : // Greater or Equal.
431 501743 : (void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
432 501743 : return store_E_None;
433 : }
434 :
435 : /*
436 : * find_insert (possibly with split()).
437 : * Precond: root node page loaded.
438 : */
439 71387 : storeError OStoreBTreeRootObject::find_insert (
440 : OStoreBTreeNodeObject & rNode, // [out]
441 : sal_uInt16 & rIndex, // [out]
442 : OStorePageKey const & rKey,
443 : OStorePageBIOS & rBIOS)
444 : {
445 71387 : (void) testInvariant("OStoreBTreeRootObject::find_insert(): enter");
446 :
447 : // Check for RootNode split.
448 71387 : PageHolderObject< page > xRoot (m_xPage);
449 71387 : if (xRoot->querySplit())
450 : {
451 15 : PageHolderObject< page > xPageL;
452 :
453 : // Change root.
454 15 : storeError eErrCode = change (xPageL, rBIOS);
455 15 : if (eErrCode != store_E_None)
456 0 : return eErrCode;
457 :
458 : // Split left page (prev root).
459 15 : eErrCode = split (0, xPageL, rBIOS);
460 15 : if (eErrCode != store_E_None)
461 0 : return eErrCode;
462 : }
463 :
464 : // Init node w/ root page.
465 : {
466 71387 : PageHolder tmp (m_xPage);
467 71387 : tmp.swap (rNode.get());
468 : }
469 :
470 : // Setup BTree entry.
471 71387 : T const entry (rKey);
472 :
473 : // Check current Page.
474 142774 : PageHolderObject< page > xPage (rNode.get());
475 93743 : for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
476 : {
477 : // Find next page.
478 22356 : page const & rPage = (*xPage);
479 22356 : sal_uInt16 const i = rPage.find (entry);
480 22356 : sal_uInt16 const n = rPage.usageCount();
481 22356 : if (!(i < n))
482 : {
483 : // Path to entry not exists (Must not happen(?)).
484 0 : return store_E_NotExists;
485 : }
486 :
487 : // Check address.
488 22356 : sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
489 22356 : if (nAddr == STORE_PAGE_NULL)
490 : {
491 : // Path to entry not exists (Must not happen(?)).
492 0 : return store_E_NotExists;
493 : }
494 :
495 : // Load next page.
496 22356 : OStoreBTreeNodeObject aNext;
497 22356 : storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
498 22356 : if (eErrCode != store_E_None)
499 0 : return eErrCode;
500 :
501 : // Check for next node split.
502 44093 : PageHolderObject< page > xNext (aNext.get());
503 22356 : if (xNext->querySplit())
504 : {
505 : // Split next node.
506 619 : eErrCode = rNode.split (i, xNext, rBIOS);
507 619 : if (eErrCode != store_E_None)
508 0 : return eErrCode;
509 :
510 : // Restart.
511 619 : continue;
512 : }
513 :
514 : // Let next page be current.
515 43474 : PageHolder tmp (aNext.get());
516 21737 : tmp.swap (rNode.get());
517 21737 : }
518 :
519 : // Find index.
520 71387 : page const & rPage = (*xPage);
521 71387 : rIndex = rPage.find(entry);
522 71387 : if (rIndex < rPage.usageCount())
523 : {
524 : // Compare entry.
525 71387 : T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
526 : OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error");
527 71387 : if (result == T::COMPARE_LESS)
528 0 : return store_E_Unknown;
529 :
530 71387 : if (result == T::COMPARE_EQUAL)
531 5440 : return store_E_AlreadyExists;
532 : }
533 :
534 : // Greater or not (yet) existing.
535 65947 : (void) testInvariant("OStoreBTreeRootObject::find_insert(): leave");
536 137334 : return store_E_None;
537 : }
538 :
539 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
