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