xref: /trunk/main/store/source/stortree.cxx (revision c1e8cc3a)
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