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 296 : OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
42 296 : : OStorePageData (nPageSize)
43 : {
44 296 : base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
45 296 : base::m_aDescr.m_nUsed = store::htons(self::thePageSize); // usageCount(0)
46 296 : self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)
47 :
48 296 : sal_uInt16 const n = capacityCount();
49 296 : T const t;
50 :
51 9008 : for (sal_uInt16 i = 1; i < n; i++)
52 8712 : m_pData[i] = t;
53 296 : }
54 :
55 : /*
56 : * find.
57 : */
58 4780 : sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
59 : {
60 4780 : sal_Int32 l = 0;
61 4780 : sal_Int32 r = usageCount() - 1;
62 :
63 15916 : while (l < r)
64 : {
65 6734 : sal_Int32 const m = ((l + r) >> 1);
66 :
67 6734 : if (t.m_aKey == m_pData[m].m_aKey)
68 378 : return ((sal_uInt16)(m));
69 6356 : if (t.m_aKey < m_pData[m].m_aKey)
70 1568 : r = m - 1;
71 : else
72 4788 : l = m + 1;
73 : }
74 :
75 4402 : sal_uInt16 const k = ((sal_uInt16)(r));
76 4402 : if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
77 816 : return(k - 1);
78 : else
79 3586 : return(k);
80 : }
81 :
82 : /*
83 : * insert.
84 : */
85 1918 : void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
86 : {
87 1918 : sal_uInt16 const n = usageCount();
88 1918 : sal_uInt16 const m = capacityCount();
89 1918 : if ((n < m) && (i < m))
90 : {
91 : // shift right.
92 1918 : memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));
93 :
94 : // insert.
95 1918 : m_pData[i] = t;
96 1918 : usageCount (n + 1);
97 : }
98 1918 : }
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 0 : void OStoreBTreeNodeData::split (const self& rPageL)
121 : {
122 0 : sal_uInt16 const h = capacityCount() / 2;
123 0 : memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
124 0 : truncate (h);
125 0 : }
126 :
127 : /*
128 : * truncate.
129 : */
130 0 : void OStoreBTreeNodeData::truncate (sal_uInt16 n)
131 : {
132 0 : sal_uInt16 const m = capacityCount();
133 0 : T const t;
134 :
135 0 : for (sal_uInt16 i = n; i < m; i++)
136 0 : m_pData[i] = t;
137 0 : usageCount (n);
138 0 : }
139 :
140 : /*========================================================================
141 : *
142 : * OStoreBTreeNodeObject implementation.
143 : *
144 : *======================================================================*/
145 : /*
146 : * guard.
147 : */
148 2528 : storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
149 : {
150 2528 : return PageHolderObject< page >::guard (m_xPage, nAddr);
151 : }
152 :
153 : /*
154 : * verify.
155 : */
156 0 : storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
157 : {
158 0 : return PageHolderObject< page >::verify (m_xPage, nAddr);
159 : }
160 :
161 : /*
162 : * split.
163 : */
164 0 : storeError OStoreBTreeNodeObject::split (
165 : sal_uInt16 nIndexL,
166 : PageHolderObject< page > & rxPageL,
167 : OStorePageBIOS & rBIOS)
168 : {
169 0 : PageHolderObject< page > xPage (m_xPage);
170 0 : if (!xPage.is())
171 0 : return store_E_InvalidAccess;
172 :
173 : // Check left page usage.
174 0 : if (!rxPageL.is())
175 0 : return store_E_InvalidAccess;
176 0 : if (!rxPageL->querySplit())
177 0 : return store_E_None;
178 :
179 : // Construct right page.
180 0 : PageHolderObject< page > xPageR;
181 0 : if (!xPageR.construct (rBIOS.allocator()))
182 0 : return store_E_OutOfMemory;
183 :
184 : // Split right page off left page.
185 0 : xPageR->split (*rxPageL);
186 0 : xPageR->depth (rxPageL->depth());
187 :
188 : // Allocate right page.
189 0 : self aNodeR (xPageR.get());
190 0 : storeError eErrCode = rBIOS.allocate (aNodeR);
191 0 : if (eErrCode != store_E_None)
192 0 : return eErrCode;
193 :
194 : // Truncate left page.
195 0 : rxPageL->truncate (rxPageL->capacityCount() / 2);
196 :
197 : // Save left page.
198 0 : self aNodeL (rxPageL.get());
199 0 : eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
200 0 : if (eErrCode != store_E_None)
201 0 : return eErrCode;
202 :
203 : // Insert right page.
204 0 : OStorePageLink aLink (xPageR->location());
205 0 : xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));
206 :
207 : // Save this page and leave.
208 0 : 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 9524 : void OStoreBTreeRootObject::testInvariant (char const * message)
298 : {
299 : OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer");
300 : SAL_WARN_IF( (m_xPage->location() - m_xPage->size()) != 0, "store", message);
301 9524 : }
302 :
303 : /*
304 : * loadOrCreate.
305 : */
306 296 : storeError OStoreBTreeRootObject::loadOrCreate (
307 : sal_uInt32 nAddr,
308 : OStorePageBIOS & rBIOS)
309 : {
310 296 : storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
311 296 : if (eErrCode != store_E_NotExists)
312 0 : return eErrCode;
313 :
314 296 : eErrCode = construct<page>(rBIOS.allocator());
315 296 : if (eErrCode != store_E_None)
316 0 : return eErrCode;
317 :
318 296 : eErrCode = rBIOS.allocate (*this);
319 296 : if (eErrCode != store_E_None)
320 0 : return eErrCode;
321 :
322 : // Notify caller of the creation.
323 296 : testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
324 296 : return store_E_Pending;
325 : }
326 :
327 : /*
328 : * change.
329 : */
330 0 : storeError OStoreBTreeRootObject::change (
331 : PageHolderObject< page > & rxPageL,
332 : OStorePageBIOS & rBIOS)
333 : {
334 0 : PageHolderObject< page > xPage (m_xPage);
335 0 : testInvariant("OStoreBTreeRootObject::change(): enter");
336 :
337 : // Save root location.
338 0 : sal_uInt32 const nRootAddr = xPage->location();
339 :
340 : // Construct new root.
341 0 : if (!rxPageL.construct (rBIOS.allocator()))
342 0 : return store_E_OutOfMemory;
343 :
344 : // Save this as prev root.
345 0 : storeError eErrCode = rBIOS.allocate (*this);
346 0 : if (eErrCode != store_E_None)
347 0 : return store_E_OutOfMemory;
348 :
349 : // Setup new root.
350 0 : rxPageL->depth (xPage->depth() + 1);
351 0 : rxPageL->m_pData[0] = xPage->m_pData[0];
352 0 : rxPageL->m_pData[0].m_aLink = xPage->location();
353 0 : rxPageL->usageCount(1);
354 :
355 : // Change root.
356 0 : rxPageL.swap (xPage);
357 : {
358 0 : PageHolder tmp (xPage.get());
359 0 : tmp.swap (m_xPage);
360 : }
361 :
362 : // Save this as new root and finish.
363 0 : eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
364 0 : testInvariant("OStoreBTreeRootObject::change(): leave");
365 0 : return eErrCode;
366 : }
367 :
368 : /*
369 : * find_lookup (w/o split()).
370 : * Precond: root node page loaded.
371 : */
372 2844 : storeError OStoreBTreeRootObject::find_lookup (
373 : OStoreBTreeNodeObject & rNode, // [out]
374 : sal_uInt16 & rIndex, // [out]
375 : OStorePageKey const & rKey,
376 : OStorePageBIOS & rBIOS)
377 : {
378 : // Init node w/ root page.
379 2844 : testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
380 : {
381 2844 : PageHolder tmp (m_xPage);
382 2844 : tmp.swap (rNode.get());
383 : }
384 :
385 : // Setup BTree entry.
386 2844 : T const entry (rKey);
387 :
388 : // Check current page.
389 2844 : PageHolderObject< page > xPage (rNode.get());
390 2844 : for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
391 : {
392 : // Find next page.
393 0 : page const & rPage = (*xPage);
394 0 : sal_uInt16 const i = rPage.find(entry);
395 0 : sal_uInt16 const n = rPage.usageCount();
396 0 : if (!(i < n))
397 : {
398 : // Path to entry not exists (Must not happen(?)).
399 0 : return store_E_NotExists;
400 : }
401 :
402 : // Check address.
403 0 : sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
404 0 : if (nAddr == STORE_PAGE_NULL)
405 : {
406 : // Path to entry not exists (Must not happen(?)).
407 0 : return store_E_NotExists;
408 : }
409 :
410 : // Load next page.
411 0 : storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
412 0 : if (eErrCode != store_E_None)
413 0 : return eErrCode;
414 : }
415 :
416 : // Find index.
417 2844 : page const & rPage = (*xPage);
418 2844 : rIndex = rPage.find(entry);
419 2844 : if (!(rIndex < rPage.usageCount()))
420 0 : return store_E_NotExists;
421 :
422 : // Compare entry.
423 2844 : T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
424 2844 : if (eResult == T::COMPARE_LESS)
425 : {
426 : SAL_WARN("store", "store::BTreeRoot::find_lookup(): sort error");
427 0 : return store_E_Unknown;
428 : }
429 :
430 : // Greater or Equal.
431 2844 : testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
432 2844 : return store_E_None;
433 : }
434 :
435 : /*
436 : * find_insert (possibly with split()).
437 : * Precond: root node page loaded.
438 : */
439 1918 : storeError OStoreBTreeRootObject::find_insert (
440 : OStoreBTreeNodeObject & rNode, // [out]
441 : sal_uInt16 & rIndex, // [out]
442 : OStorePageKey const & rKey,
443 : OStorePageBIOS & rBIOS)
444 : {
445 1918 : testInvariant("OStoreBTreeRootObject::find_insert(): enter");
446 :
447 : // Check for RootNode split.
448 1918 : PageHolderObject< page > xRoot (m_xPage);
449 1918 : if (xRoot->querySplit())
450 : {
451 0 : PageHolderObject< page > xPageL;
452 :
453 : // Change root.
454 0 : storeError eErrCode = change (xPageL, rBIOS);
455 0 : if (eErrCode != store_E_None)
456 0 : return eErrCode;
457 :
458 : // Split left page (prev root).
459 0 : eErrCode = split (0, xPageL, rBIOS);
460 0 : if (eErrCode != store_E_None)
461 0 : return eErrCode;
462 : }
463 :
464 : // Init node w/ root page.
465 : {
466 1918 : PageHolder tmp (m_xPage);
467 1918 : tmp.swap (rNode.get());
468 : }
469 :
470 : // Setup BTree entry.
471 1918 : T const entry (rKey);
472 :
473 : // Check current Page.
474 3836 : PageHolderObject< page > xPage (rNode.get());
475 1918 : for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
476 : {
477 : // Find next page.
478 0 : page const & rPage = (*xPage);
479 0 : sal_uInt16 const i = rPage.find (entry);
480 0 : sal_uInt16 const n = rPage.usageCount();
481 0 : 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 0 : sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
489 0 : 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 0 : OStoreBTreeNodeObject aNext;
497 0 : storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
498 0 : if (eErrCode != store_E_None)
499 0 : return eErrCode;
500 :
501 : // Check for next node split.
502 0 : PageHolderObject< page > xNext (aNext.get());
503 0 : if (xNext->querySplit())
504 : {
505 : // Split next node.
506 0 : eErrCode = rNode.split (i, xNext, rBIOS);
507 0 : if (eErrCode != store_E_None)
508 0 : return eErrCode;
509 :
510 : // Restart.
511 0 : continue;
512 : }
513 :
514 : // Let next page be current.
515 0 : PageHolder tmp (aNext.get());
516 0 : tmp.swap (rNode.get());
517 0 : }
518 :
519 : // Find index.
520 1918 : page const & rPage = (*xPage);
521 1918 : rIndex = rPage.find(entry);
522 1918 : if (rIndex < rPage.usageCount())
523 : {
524 : // Compare entry.
525 1918 : T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
526 1918 : if (result == T::COMPARE_LESS)
527 : {
528 : SAL_WARN("store", "store::BTreeRoot::find_insert(): sort error");
529 0 : return store_E_Unknown;
530 : }
531 :
532 1918 : if (result == T::COMPARE_EQUAL)
533 296 : return store_E_AlreadyExists;
534 : }
535 :
536 : // Greater or not (yet) existing.
537 1622 : testInvariant("OStoreBTreeRootObject::find_insert(): leave");
538 3540 : return store_E_None;
539 : }
540 :
541 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
