Branch data 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 : 7561 : OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
42 [ + + ]: 15122 : : OStorePageData (nPageSize)
43 : : {
44 : 7561 : base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
45 : 7561 : base::m_aDescr.m_nUsed = store::htons(self::thePageSize); // usageCount(0)
46 : 7561 : self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)
47 : :
48 : 7561 : sal_uInt16 const n = capacityCount();
49 : 7561 : T const t;
50 : :
51 [ + + ]: 230926 : for (sal_uInt16 i = 1; i < n; i++)
52 : 223365 : m_pData[i] = t;
53 : 7561 : }
54 : :
55 : : /*
56 : : * find.
57 : : */
58 : 6315338 : sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
59 : : {
60 : 6315338 : register sal_Int32 l = 0;
61 : 6315338 : register sal_Int32 r = usageCount() - 1;
62 : :
63 [ + + ]: 26436781 : while (l < r)
64 : : {
65 : 20774951 : register sal_Int32 const m = ((l + r) >> 1);
66 : :
67 [ + + ]: 20774951 : if (t.m_aKey == m_pData[m].m_aKey)
68 : 653508 : return ((sal_uInt16)(m));
69 [ + + ]: 20121443 : if (t.m_aKey < m_pData[m].m_aKey)
70 : 8515308 : r = m - 1;
71 : : else
72 : 11606135 : l = m + 1;
73 : : }
74 : :
75 : 5661830 : sal_uInt16 const k = ((sal_uInt16)(r));
76 [ + - ][ + + ]: 5661830 : if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
[ + + ]
77 : 2420288 : return(k - 1);
78 : : else
79 : 6315338 : return(k);
80 : : }
81 : :
82 : : /*
83 : : * insert.
84 : : */
85 : 94121 : void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
86 : : {
87 : 94121 : sal_uInt16 const n = usageCount();
88 : 94121 : sal_uInt16 const m = capacityCount();
89 [ + - ][ + - ]: 94121 : if ((n < m) && (i < m))
90 : : {
91 : : // shift right.
92 : 94121 : memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));
93 : :
94 : : // insert.
95 : 94121 : m_pData[i] = t;
96 : 94121 : usageCount (n + 1);
97 : : }
98 : 94121 : }
99 : :
100 : : /*
101 : : * remove.
102 : : */
103 : 18 : void OStoreBTreeNodeData::remove (sal_uInt16 i)
104 : : {
105 : 18 : sal_uInt16 const n = usageCount();
106 [ + - ]: 18 : if (i < n)
107 : : {
108 : : // shift left.
109 : 18 : memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T));
110 : :
111 : : // truncate.
112 : 18 : m_pData[n - 1] = T();
113 : 18 : usageCount (n - 1);
114 : : }
115 : 18 : }
116 : :
117 : : /*
118 : : * split (left half copied from right half of left page).
119 : : */
120 : 1283 : void OStoreBTreeNodeData::split (const self& rPageL)
121 : : {
122 : 1283 : sal_uInt16 const h = capacityCount() / 2;
123 : 1283 : memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
124 : 1283 : truncate (h);
125 : 1283 : }
126 : :
127 : : /*
128 : : * truncate.
129 : : */
130 : 2566 : void OStoreBTreeNodeData::truncate (sal_uInt16 n)
131 : : {
132 : 2566 : sal_uInt16 const m = capacityCount();
133 : 2566 : T const t;
134 : :
135 [ + + ]: 41056 : for (sal_uInt16 i = n; i < m; i++)
136 : 38490 : m_pData[i] = t;
137 [ + - ]: 2566 : usageCount (n);
138 : 2566 : }
139 : :
140 : : /*========================================================================
141 : : *
142 : : * OStoreBTreeNodeObject implementation.
143 : : *
144 : : *======================================================================*/
145 : : /*
146 : : * guard.
147 : : */
148 : 109261 : storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
149 : : {
150 : 109261 : return PageHolderObject< page >::guard (m_xPage, nAddr);
151 : : }
152 : :
153 : : /*
154 : : * verify.
155 : : */
156 : 94730 : storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
157 : : {
158 : 94730 : return PageHolderObject< page >::verify (m_xPage, nAddr);
159 : : }
160 : :
161 : : /*
162 : : * split.
163 : : */
164 : 1283 : storeError OStoreBTreeNodeObject::split (
165 : : sal_uInt16 nIndexL,
166 : : PageHolderObject< page > & rxPageL,
167 : : OStorePageBIOS & rBIOS)
168 : : {
169 [ + - ]: 1283 : PageHolderObject< page > xPage (m_xPage);
170 [ - + ]: 1283 : if (!xPage.is())
171 : 0 : return store_E_InvalidAccess;
172 : :
173 : : // Check left page usage.
174 [ - + ]: 1283 : if (!rxPageL.is())
175 : 0 : return store_E_InvalidAccess;
176 [ + - ][ - + ]: 1283 : if (!rxPageL->querySplit())
177 : 0 : return store_E_None;
178 : :
179 : : // Construct right page.
180 [ + - ][ + - ]: 1283 : PageHolderObject< page > xPageR;
[ + - ][ + - ]
181 [ + - ][ - + ]: 1283 : if (!xPageR.construct (rBIOS.allocator()))
182 : 0 : return store_E_OutOfMemory;
183 : :
184 : : // Split right page off left page.
185 [ + - ][ + - ]: 1283 : xPageR->split (*rxPageL);
[ + - ]
186 [ + - ][ + - ]: 1283 : xPageR->depth (rxPageL->depth());
187 : :
188 : : // Allocate right page.
189 [ + - ]: 1283 : self aNodeR (xPageR.get());
190 [ + - ]: 1283 : storeError eErrCode = rBIOS.allocate (aNodeR);
191 [ - + ]: 1283 : if (eErrCode != store_E_None)
192 : 0 : return eErrCode;
193 : :
194 : : // Truncate left page.
195 [ + - ][ + - ]: 1283 : rxPageL->truncate (rxPageL->capacityCount() / 2);
[ + - ]
196 : :
197 : : // Save left page.
198 [ + - ]: 1283 : self aNodeL (rxPageL.get());
199 [ + - ]: 1283 : eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
200 [ - + ]: 1283 : if (eErrCode != store_E_None)
201 : 0 : return eErrCode;
202 : :
203 : : // Insert right page.
204 [ + - ]: 1283 : OStorePageLink aLink (xPageR->location());
205 [ + - ][ + - ]: 1283 : xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));
[ + - ]
206 : :
207 : : // Save this page and leave.
208 [ + - ][ + - ]: 1283 : return rBIOS.saveObjectAt (*this, location());
[ + - ][ + - ]
[ + - ]
209 : : }
210 : :
211 : : /*
212 : : * remove (down to leaf node, recursive).
213 : : */
214 : 18 : storeError OStoreBTreeNodeObject::remove (
215 : : sal_uInt16 nIndexL,
216 : : OStoreBTreeEntry & rEntryL,
217 : : OStorePageBIOS & rBIOS)
218 : : {
219 [ + - ]: 18 : PageHolderObject< page > xImpl (m_xPage);
220 [ + - ]: 18 : page & rPage = (*xImpl);
221 : :
222 : : // Check depth.
223 : 18 : storeError eErrCode = store_E_None;
224 [ - + ]: 18 : 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 [ - + ]: 18 : if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL))
267 : 0 : return store_E_NotExists;
268 : :
269 : : // Save leaf entry.
270 : 18 : rEntryL = rPage.m_pData[nIndexL];
271 : :
272 : : // Remove leaf index.
273 [ + - ]: 18 : rPage.remove (nIndexL);
274 : 18 : touch();
275 : : }
276 : :
277 : : // Check for modified node.
278 [ + - ]: 18 : if (dirty())
279 : : {
280 : : // Save this page.
281 [ + - ]: 18 : eErrCode = rBIOS.saveObjectAt (*this, location());
282 : : }
283 : :
284 : : // Done.
285 [ + - ]: 18 : return eErrCode;
286 : : }
287 : :
288 : : /*========================================================================
289 : : *
290 : : * OStoreBTreeRootObject implementation.
291 : : *
292 : : *======================================================================*/
293 : : /*
294 : : * testInvariant.
295 : : * Precond: root node page loaded.
296 : : */
297 : 4958050 : bool OStoreBTreeRootObject::testInvariant (char const * message)
298 : : {
299 : : OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer");
300 : 4958050 : bool result = ((m_xPage->location() - m_xPage->size()) == 0);
301 : : OSL_POSTCOND(result, message); (void) message;
302 : 4958050 : return result;
303 : : }
304 : :
305 : : /*
306 : : * loadOrCreate.
307 : : */
308 : 6380 : storeError OStoreBTreeRootObject::loadOrCreate (
309 : : sal_uInt32 nAddr,
310 : : OStorePageBIOS & rBIOS)
311 : : {
312 : 6380 : storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
313 [ + + ]: 6380 : if (eErrCode != store_E_NotExists)
314 : 129 : return eErrCode;
315 : :
316 : 6251 : eErrCode = construct<page>(rBIOS.allocator());
317 [ - + ]: 6251 : if (eErrCode != store_E_None)
318 : 0 : return eErrCode;
319 : :
320 : 6251 : eErrCode = rBIOS.allocate (*this);
321 [ - + ]: 6251 : if (eErrCode != store_E_None)
322 : 0 : return eErrCode;
323 : :
324 : : // Notify caller of the creation.
325 : 6251 : (void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
326 : 6380 : return store_E_Pending;
327 : : }
328 : :
329 : : /*
330 : : * change.
331 : : */
332 : 27 : storeError OStoreBTreeRootObject::change (
333 : : PageHolderObject< page > & rxPageL,
334 : : OStorePageBIOS & rBIOS)
335 : : {
336 [ + - ]: 27 : PageHolderObject< page > xPage (m_xPage);
337 : 27 : (void) testInvariant("OStoreBTreeRootObject::change(): enter");
338 : :
339 : : // Save root location.
340 [ + - ]: 27 : sal_uInt32 const nRootAddr = xPage->location();
341 : :
342 : : // Construct new root.
343 [ - + ][ + - ]: 27 : if (!rxPageL.construct (rBIOS.allocator()))
344 : 0 : return store_E_OutOfMemory;
345 : :
346 : : // Save this as prev root.
347 [ + - ]: 27 : storeError eErrCode = rBIOS.allocate (*this);
348 [ - + ]: 27 : if (eErrCode != store_E_None)
349 : 0 : return store_E_OutOfMemory;
350 : :
351 : : // Setup new root.
352 [ + - ][ + - ]: 27 : rxPageL->depth (xPage->depth() + 1);
353 [ + - ][ + - ]: 27 : rxPageL->m_pData[0] = xPage->m_pData[0];
354 [ + - ][ + - ]: 27 : rxPageL->m_pData[0].m_aLink = xPage->location();
355 [ + - ][ + - ]: 27 : rxPageL->usageCount(1);
356 : :
357 : : // Change root.
358 [ + - ]: 27 : rxPageL.swap (xPage);
359 : : {
360 [ + - ]: 27 : PageHolder tmp (xPage.get());
361 [ + - ][ + - ]: 27 : tmp.swap (m_xPage);
362 : : }
363 : :
364 : : // Save this as new root and finish.
365 [ + - ]: 27 : eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
366 : 27 : (void) testInvariant("OStoreBTreeRootObject::change(): leave");
367 [ + - ]: 27 : return eErrCode;
368 : : }
369 : :
370 : : /*
371 : : * find_lookup (w/o split()).
372 : : * Precond: root node page loaded.
373 : : */
374 : 2386160 : 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 : 2386160 : (void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
382 : : {
383 [ + - ]: 2386160 : PageHolder tmp (m_xPage);
384 [ + - ][ + - ]: 2386160 : tmp.swap (rNode.get());
385 : : }
386 : :
387 : : // Setup BTree entry.
388 : 2386160 : T const entry (rKey);
389 : :
390 : : // Check current page.
391 [ + - ]: 2386160 : PageHolderObject< page > xPage (rNode.get());
392 [ + - ][ + - ]: 6179546 : for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
[ + - ][ + - ]
[ + + ]
393 : : {
394 : : // Find next page.
395 [ + - ]: 3793386 : page const & rPage = (*xPage);
396 : 3793386 : sal_uInt16 const i = rPage.find(entry);
397 : 3793386 : sal_uInt16 const n = rPage.usageCount();
398 [ - + ]: 3793386 : 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 : 3793386 : sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
406 [ - + ]: 3793386 : 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 [ + - ]: 3793386 : storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
414 [ - + ]: 3793386 : if (eErrCode != store_E_None)
415 : 0 : return eErrCode;
416 : : }
417 : :
418 : : // Find index.
419 [ + - ]: 2386160 : page const & rPage = (*xPage);
420 : 2386160 : rIndex = rPage.find(entry);
421 [ - + ]: 2386160 : if (!(rIndex < rPage.usageCount()))
422 : 0 : return store_E_NotExists;
423 : :
424 : : // Compare entry.
425 : 2386160 : T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
426 : : OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error");
427 [ - + ]: 2386160 : if (eResult == T::COMPARE_LESS)
428 : 0 : return store_E_Unknown;
429 : :
430 : : // Greater or Equal.
431 : 2386160 : (void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
432 [ + - ]: 2386160 : return store_E_None;
433 : : }
434 : :
435 : : /*
436 : : * find_insert (possibly with split()).
437 : : * Precond: root node page loaded.
438 : : */
439 : 92838 : storeError OStoreBTreeRootObject::find_insert (
440 : : OStoreBTreeNodeObject & rNode, // [out]
441 : : sal_uInt16 & rIndex, // [out]
442 : : OStorePageKey const & rKey,
443 : : OStorePageBIOS & rBIOS)
444 : : {
445 : 92838 : (void) testInvariant("OStoreBTreeRootObject::find_insert(): enter");
446 : :
447 : : // Check for RootNode split.
448 [ + - ]: 92838 : PageHolderObject< page > xRoot (m_xPage);
449 [ + - ][ + + ]: 92838 : if (xRoot->querySplit())
450 : : {
451 [ + - ][ + - ]: 27 : PageHolderObject< page > xPageL;
[ + - ][ + - ]
452 : :
453 : : // Change root.
454 [ + - ]: 27 : storeError eErrCode = change (xPageL, rBIOS);
455 [ - + ]: 27 : if (eErrCode != store_E_None)
456 : 0 : return eErrCode;
457 : :
458 : : // Split left page (prev root).
459 [ + - ]: 27 : eErrCode = split (0, xPageL, rBIOS);
460 [ - + ]: 27 : if (eErrCode != store_E_None)
461 [ + - ][ + - ]: 27 : return eErrCode;
462 : : }
463 : :
464 : : // Init node w/ root page.
465 : : {
466 [ + - ]: 92838 : PageHolder tmp (m_xPage);
467 [ + - ][ + - ]: 92838 : tmp.swap (rNode.get());
468 : : }
469 : :
470 : : // Setup BTree entry.
471 : 92838 : T const entry (rKey);
472 : :
473 : : // Check current Page.
474 [ + - ]: 92838 : PageHolderObject< page > xPage (rNode.get());
475 [ + - ][ + - ]: 135774 : for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
[ + - ][ + - ]
[ + + ]
476 : : {
477 : : // Find next page.
478 [ + - ]: 42936 : page const & rPage = (*xPage);
479 : 42936 : sal_uInt16 const i = rPage.find (entry);
480 : 42936 : sal_uInt16 const n = rPage.usageCount();
481 [ - + ]: 42936 : 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 : 42936 : sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
489 [ - + ]: 42936 : 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 [ + - ][ + - ]: 42936 : OStoreBTreeNodeObject aNext;
[ + - ][ + - ]
497 [ + - ]: 42936 : storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
498 [ - + ]: 42936 : if (eErrCode != store_E_None)
499 : 0 : return eErrCode;
500 : :
501 : : // Check for next node split.
502 [ + - ]: 42936 : PageHolderObject< page > xNext (aNext.get());
503 [ + - ][ + + ]: 42936 : if (xNext->querySplit())
504 : : {
505 : : // Split next node.
506 [ + - ]: 1256 : eErrCode = rNode.split (i, xNext, rBIOS);
507 [ - + ]: 1256 : if (eErrCode != store_E_None)
508 : 0 : return eErrCode;
509 : :
510 : : // Restart.
511 : 1256 : continue;
512 : : }
513 : :
514 : : // Let next page be current.
515 [ + - ]: 41680 : PageHolder tmp (aNext.get());
516 [ + - ]: 41680 : tmp.swap (rNode.get());
517 [ + - ][ + - ]: 42936 : }
[ - + + ]
[ + - ]
[ + - + ]
518 : :
519 : : // Find index.
520 [ + - ]: 92838 : page const & rPage = (*xPage);
521 : 92838 : rIndex = rPage.find(entry);
522 [ + - ]: 92838 : if (rIndex < rPage.usageCount())
523 : : {
524 : : // Compare entry.
525 : 92838 : T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
526 : : OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error");
527 [ - + ]: 92838 : if (result == T::COMPARE_LESS)
528 : 0 : return store_E_Unknown;
529 : :
530 [ + + ]: 92838 : if (result == T::COMPARE_EQUAL)
531 : 6251 : return store_E_AlreadyExists;
532 : : }
533 : :
534 : : // Greater or not (yet) existing.
535 : 86587 : (void) testInvariant("OStoreBTreeRootObject::find_insert(): leave");
536 [ + - ][ + - ]: 92838 : return store_E_None;
537 : : }
538 : :
539 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
