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