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