AOO410/main/store/source/stortree.cxx - openoffice - Git at Google

 /**************************************************************
  *
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  *
  *************************************************************/


 // MARKER(update_precomp.py): autogen include statement, do not remove
 #include "precompiled_store.hxx"

 #include "stortree.hxx"

 #include "sal/types.h"
 #include "osl/diagnose.h"

 #include "store/types.h"

 #include "storbase.hxx"
 #include "storbios.hxx"

 using namespace store;

 /*========================================================================
  *
  * OStoreBTreeNodeData implementation.
  *
  *======================================================================*/
 /*
  * OStoreBTreeNodeData.
  */
 OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
 	: OStorePageData (nPageSize)
 {
 	base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
 	base::m_aDescr.m_nUsed  = store::htons(self::thePageSize); // usageCount(0)
 	self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)

 	sal_uInt16 const n = capacityCount();
 	T const          t;

 	for (sal_uInt16 i = 1; i < n; i++)
 		m_pData[i] = t;
 }

 /*
  * find.
  */
 sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
 {
 	register sal_Int32 l = 0;
 	register sal_Int32 r = usageCount() - 1;

 	while (l < r)
 	{
 		register sal_Int32 const m = ((l + r) >> 1);

 		if (t.m_aKey == m_pData[m].m_aKey)
 			return ((sal_uInt16)(m));
 		if (t.m_aKey < m_pData[m].m_aKey)
 			r = m - 1;
 		else
 			l = m + 1;
 	}

 	sal_uInt16 const k = ((sal_uInt16)(r));
 	if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
 		return(k - 1);
 	else
 		return(k);
 }

 /*
  * insert.
  */
 void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
 {
 	sal_uInt16 const n = usageCount();
 	sal_uInt16 const m = capacityCount();
 	if ((n < m) && (i < m))
 	{
 		// shift right.
 		memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));

 		// insert.
 		m_pData[i] = t;
         usageCount (n + 1);
 	}
 }

 /*
  * remove.
  */
 void OStoreBTreeNodeData::remove (sal_uInt16 i)
 {
 	sal_uInt16 const n = usageCount();
 	if (i < n)
 	{
 		// shift left.
 		memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T));

 		// truncate.
 		m_pData[n - 1] = T();
         usageCount (n - 1);
 	}
 }

 #if 0  /* NYI */
 /*
  * merge (with right page).
  */
 void OStoreBTreeNodeData::merge (const self& rPageR)
 {
     sal_uInt16 const n = usageCount();
     sal_uInt16 const m = rPageR.usageCount();
     if ((n + m) <= capacityCount())
 	{
 		memcpy (&(m_pData[n]), &(rPageR.m_pData[0]), m * sizeof(T));
 		usageCount (n + m);
 	}
 }
 #endif

 /*
  * split (left half copied from right half of left page).
  */
 void OStoreBTreeNodeData::split (const self& rPageL)
 {
 	sal_uInt16 const h = capacityCount() / 2;
 	memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
 	truncate (h);
 }

 /*
  * truncate.
  */
 void OStoreBTreeNodeData::truncate (sal_uInt16 n)
 {
 	sal_uInt16 const m = capacityCount();
 	T const          t;

 	for (sal_uInt16 i = n; i < m; i++)
 		m_pData[i] = t;
 	usageCount (n);
 }

 /*========================================================================
  *
  * OStoreBTreeNodeObject implementation.
  *
  *======================================================================*/
 /*
  * guard.
  */
 storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
 {
 	return PageHolderObject< page >::guard (m_xPage, nAddr);
 }

 /*
  * verify.
  */
 storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
 {
 	return PageHolderObject< page >::verify (m_xPage, nAddr);
 }

 /*
  * split.
  */
 storeError OStoreBTreeNodeObject::split (
 	sal_uInt16                 nIndexL,
 	PageHolderObject< page > & rxPageL,
 	OStorePageBIOS           & rBIOS)
 {
     PageHolderObject< page > xPage (m_xPage);
     if (!xPage.is())
         return store_E_InvalidAccess;

 	// Check left page usage.
     if (!rxPageL.is())
         return store_E_InvalidAccess;
 	if (!rxPageL->querySplit())
 		return store_E_None;

     // Construct right page.
     PageHolderObject< page > xPageR;
     if (!xPageR.construct (rBIOS.allocator()))
 		return store_E_OutOfMemory;

 	// Split right page off left page.
 	xPageR->split (*rxPageL);
 	xPageR->depth (rxPageL->depth());

 	// Allocate right page.
     self aNodeR (xPageR.get());
 	storeError eErrCode = rBIOS.allocate (aNodeR);
 	if (eErrCode != store_E_None)
 		return eErrCode;

 	// Truncate left page.
 	rxPageL->truncate (rxPageL->capacityCount() / 2);

 	// Save left page.
 	self aNodeL (rxPageL.get());
 	eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
 	if (eErrCode != store_E_None)
 		return eErrCode;

 	// Insert right page.
 	OStorePageLink aLink (xPageR->location());
 	xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));

 	// Save this page and leave.
 	return rBIOS.saveObjectAt (*this, location());
 }

 /*
  * remove (down to leaf node, recursive).
  */
 storeError OStoreBTreeNodeObject::remove (
 	sal_uInt16         nIndexL,
 	OStoreBTreeEntry & rEntryL,
 	OStorePageBIOS &   rBIOS)
 {
     PageHolderObject< page > xImpl (m_xPage);
     page & rPage = (*xImpl);

 	// Check depth.
     storeError eErrCode = store_E_None;
 	if (rPage.depth())
 	{
 		// Check link entry.
         T const aEntryL (rPage.m_pData[nIndexL]);
 		if (!(rEntryL.compare (aEntryL) == T::COMPARE_EQUAL))
 			return store_E_InvalidAccess;

 		// Load link node.
 		self aNodeL;
 		eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location());
 		if (eErrCode != store_E_None)
 			return eErrCode;

 		// Recurse: remove from link node.
 		eErrCode = aNodeL.remove (0, rEntryL, rBIOS);
 		if (eErrCode != store_E_None)
 			return eErrCode;

 		// Check resulting link node usage.
         PageHolderObject< page > xPageL (aNodeL.get());
 		if (xPageL->usageCount() == 0)
 		{
 			// Free empty link node.
 			eErrCode = rBIOS.free (xPageL->location());
 			if (eErrCode != store_E_None)
 				return eErrCode;

 			// Remove index.
 			rPage.remove (nIndexL);
 			touch();
 		}
 		else
 		{
 #if 0   /* NYI */
 			// Check for right sibling.
 			sal_uInt16 const nIndexR = nIndexL + 1;
 			if (nIndexR < rPage.usageCount())
 			{
 				// Load right link node.
 				self aNodeR;
 				eErrCode = rBIOS.loadObjectAt (aNodeR, rPage.m_pData[nIndexR].m_aLink.location());
 				if (eErrCode == store_E_None)
 				{
 					if (rPageL.queryMerge (rPageR))
 					{
 						rPageL.merge (rPageR);

 						eErrCode = rBIOS.free (rPageR.location());
 					}
 				}
 			}
 #endif  /* NYI */

 			// Relink.
 			rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey;
 			touch();
 		}
 	}
 	else
 	{
 		// Check leaf entry.
 		if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL))
 			return store_E_NotExists;

 		// Save leaf entry.
 		rEntryL = rPage.m_pData[nIndexL];

 		// Remove leaf index.
 		rPage.remove (nIndexL);
 		touch();
 	}

 	// Check for modified node.
 	if (dirty())
 	{
 		// Save this page.
 		eErrCode = rBIOS.saveObjectAt (*this, location());
 	}

 	// Done.
     return eErrCode;
 }

 /*========================================================================
  *
  * OStoreBTreeRootObject implementation.
  *
  *======================================================================*/
 /*
  * testInvariant.
  * Precond: root node page loaded.
  */
 bool OStoreBTreeRootObject::testInvariant (char const * message)
 {
     OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer");
     bool result = ((m_xPage->location() - m_xPage->size()) == 0);
     OSL_POSTCOND(result, message); (void) message;
     return result;
 }

 /*
  * loadOrCreate.
  */
 storeError OStoreBTreeRootObject::loadOrCreate (
     sal_uInt32       nAddr,
     OStorePageBIOS & rBIOS)
 {
     storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
     if (eErrCode != store_E_NotExists)
         return eErrCode;

     eErrCode = construct<page>(rBIOS.allocator());
     if (eErrCode != store_E_None)
         return eErrCode;

     eErrCode = rBIOS.allocate (*this);
     if (eErrCode != store_E_None)
         return eErrCode;

     // Notify caller of the creation.
     (void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
     return store_E_Pending;
 }

 /*
  * change.
  */
 storeError OStoreBTreeRootObject::change (
 	PageHolderObject< page > & rxPageL,
 	OStorePageBIOS &           rBIOS)
 {
     PageHolderObject< page > xPage (m_xPage);
     (void) testInvariant("OStoreBTreeRootObject::change(): enter");

     // Save root location.
     sal_uInt32 const nRootAddr = xPage->location();

     // Construct new root.
     if (!rxPageL.construct (rBIOS.allocator()))
 		return store_E_OutOfMemory;

     // Save this as prev root.
     storeError eErrCode = rBIOS.allocate (*this);
     if (eErrCode != store_E_None)
 		return store_E_OutOfMemory;

     // Setup new root.
     rxPageL->depth (xPage->depth() + 1);
     rxPageL->m_pData[0] = xPage->m_pData[0];
     rxPageL->m_pData[0].m_aLink = xPage->location();
     rxPageL->usageCount(1);

 	// Change root.
     rxPageL.swap (xPage);
     {
         PageHolder tmp (xPage.get());
         tmp.swap (m_xPage);
     }

 	// Save this as new root and finish.
 	eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
     (void) testInvariant("OStoreBTreeRootObject::change(): leave");
     return eErrCode;
 }

 /*
  * find_lookup (w/o split()).
  * Precond: root node page loaded.
  */
 storeError OStoreBTreeRootObject::find_lookup (
     OStoreBTreeNodeObject & rNode,  // [out]
     sal_uInt16 &            rIndex, // [out]
     OStorePageKey const &   rKey,
     OStorePageBIOS &        rBIOS)
 {
     // Init node w/ root page.
     (void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
     {
         PageHolder tmp (m_xPage);
         tmp.swap (rNode.get());
     }

     // Setup BTree entry.
     T const entry (rKey);

     // Check current page.
     PageHolderObject< page > xPage (rNode.get());
     for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
     {
         // Find next page.
         page const & rPage = (*xPage);
         sal_uInt16 const i = rPage.find(entry);
         sal_uInt16 const n = rPage.usageCount();
         if (!(i < n))
         {
             // Path to entry not exists (Must not happen(?)).
             return store_E_NotExists;
         }

         // Check address.
         sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
         if (nAddr == STORE_PAGE_NULL)
         {
             // Path to entry not exists (Must not happen(?)).
             return store_E_NotExists;
         }

         // Load next page.
         storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
         if (eErrCode != store_E_None)
             return eErrCode;
     }

     // Find index.
     page const & rPage = (*xPage);
     rIndex = rPage.find(entry);
     if (!(rIndex < rPage.usageCount()))
         return store_E_NotExists;

     // Compare entry.
     T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
     OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error");
     if (eResult == T::COMPARE_LESS)
         return store_E_Unknown;

     // Greater or Equal.
     (void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
     return store_E_None;
 }

 /*
  * find_insert (possibly with split()).
  * Precond: root node page loaded.
  */
 storeError OStoreBTreeRootObject::find_insert (
     OStoreBTreeNodeObject & rNode,  // [out]
     sal_uInt16 &            rIndex, // [out]
     OStorePageKey const &   rKey,
     OStorePageBIOS &        rBIOS)
 {
     (void) testInvariant("OStoreBTreeRootObject::find_insert(): enter");

     // Check for RootNode split.
     PageHolderObject< page > xRoot (m_xPage);
     if (xRoot->querySplit())
     {
         PageHolderObject< page > xPageL;

         // Change root.
         storeError eErrCode = change (xPageL, rBIOS);
         if (eErrCode != store_E_None)
             return eErrCode;

         // Split left page (prev root).
         eErrCode = split (0, xPageL, rBIOS);
         if (eErrCode != store_E_None)
             return eErrCode;
 	}

     // Init node w/ root page.
     {
         PageHolder tmp (m_xPage);
         tmp.swap (rNode.get());
     }

     // Setup BTree entry.
     T const entry (rKey);

 	// Check current Page.
     PageHolderObject< page > xPage (rNode.get());
     for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
 	{
 		// Find next page.
         page const & rPage = (*xPage);
 		sal_uInt16 const i = rPage.find (entry);
         sal_uInt16 const n = rPage.usageCount();
 		if (!(i < n))
 		{
 			// Path to entry not exists (Must not happen(?)).
 			return store_E_NotExists;
 		}

 		// Check address.
 		sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
 		if (nAddr == STORE_PAGE_NULL)
 		{
 			// Path to entry not exists (Must not happen(?)).
 			return store_E_NotExists;
 		}

 		// Load next page.
         OStoreBTreeNodeObject aNext;
 		storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
 		if (eErrCode != store_E_None)
 			return eErrCode;

 		// Check for next node split.
         PageHolderObject< page > xNext (aNext.get());
 		if (xNext->querySplit())
 		{
 			// Split next node.
 			eErrCode = rNode.split (i, xNext, rBIOS);
 			if (eErrCode != store_E_None)
 				return eErrCode;

 			// Restart.
 			continue;
 		}

         // Let next page be current.
         PageHolder tmp (aNext.get());
         tmp.swap (rNode.get());
     }

 	// Find index.
     page const & rPage = (*xPage);
 	rIndex = rPage.find(entry);
 	if (rIndex < rPage.usageCount())
 	{
 		// Compare entry.
 		T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
 		OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error");
 		if (result == T::COMPARE_LESS)
 			return store_E_Unknown;

 		if (result == T::COMPARE_EQUAL)
 			return store_E_AlreadyExists;
 	}

     // Greater or not (yet) existing.
     (void) testInvariant("OStoreBTreeRootObject::find_insert(): leave");
     return store_E_None;
 }
	/**************************************************************
	*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*
	*************************************************************/



	// MARKER(update_precomp.py): autogen include statement, do not remove
	#include "precompiled_store.hxx"

	#include "stortree.hxx"

	#include "sal/types.h"
	#include "osl/diagnose.h"

	#include "store/types.h"

	#include "storbase.hxx"
	#include "storbios.hxx"

	using namespace store;

	/*========================================================================
	*
	* OStoreBTreeNodeData implementation.
	*
	======================================================================/
	/*
	* OStoreBTreeNodeData.
	*/
	OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
	: OStorePageData (nPageSize)
	{
	base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
	base::m_aDescr.m_nUsed = store::htons(self::thePageSize); // usageCount(0)
	self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)

	sal_uInt16 const n = capacityCount();
	T const t;

	for (sal_uInt16 i = 1; i < n; i++)
	m_pData[i] = t;
	}

	/*
	* find.
	*/
	sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
	{
	register sal_Int32 l = 0;
	register sal_Int32 r = usageCount() - 1;

	while (l < r)
	{
	register sal_Int32 const m = ((l + r) >> 1);

	if (t.m_aKey == m_pData[m].m_aKey)
	return ((sal_uInt16)(m));
	if (t.m_aKey < m_pData[m].m_aKey)
	r = m - 1;
	else
	l = m + 1;
	}

	sal_uInt16 const k = ((sal_uInt16)(r));
	if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
	return(k - 1);
	else
	return(k);
	}

	/*
	* insert.
	*/
	void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
	{
	sal_uInt16 const n = usageCount();
	sal_uInt16 const m = capacityCount();
	if ((n < m) && (i < m))
	{
	// shift right.
	memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));

	// insert.
	m_pData[i] = t;
	usageCount (n + 1);
	}
	}

	/*
	* remove.
	*/
	void OStoreBTreeNodeData::remove (sal_uInt16 i)
	{
	sal_uInt16 const n = usageCount();
	if (i < n)
	{
	// shift left.
	memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T));

	// truncate.
	m_pData[n - 1] = T();
	usageCount (n - 1);
	}
	}

	#if 0 /* NYI */
	/*
	* merge (with right page).
	*/
	void OStoreBTreeNodeData::merge (const self& rPageR)
	{
	sal_uInt16 const n = usageCount();
	sal_uInt16 const m = rPageR.usageCount();
	if ((n + m) <= capacityCount())
	{
	memcpy (&(m_pData[n]), &(rPageR.m_pData[0]), m * sizeof(T));
	usageCount (n + m);
	}
	}
	#endif

	/*
	* split (left half copied from right half of left page).
	*/
	void OStoreBTreeNodeData::split (const self& rPageL)
	{
	sal_uInt16 const h = capacityCount() / 2;
	memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
	truncate (h);
	}

	/*
	* truncate.
	*/
	void OStoreBTreeNodeData::truncate (sal_uInt16 n)
	{
	sal_uInt16 const m = capacityCount();
	T const t;

	for (sal_uInt16 i = n; i < m; i++)
	m_pData[i] = t;
	usageCount (n);
	}

	/*========================================================================
	*
	* OStoreBTreeNodeObject implementation.
	*
	======================================================================/
	/*
	* guard.
	*/
	storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
	{
	return PageHolderObject< page >::guard (m_xPage, nAddr);
	}

	/*
	* verify.
	*/
	storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
	{
	return PageHolderObject< page >::verify (m_xPage, nAddr);
	}

	/*
	* split.
	*/
	storeError OStoreBTreeNodeObject::split (
	sal_uInt16 nIndexL,
	PageHolderObject< page > & rxPageL,
	OStorePageBIOS & rBIOS)
	{
	PageHolderObject< page > xPage (m_xPage);
	if (!xPage.is())
	return store_E_InvalidAccess;

	// Check left page usage.
	if (!rxPageL.is())
	return store_E_InvalidAccess;
	if (!rxPageL->querySplit())
	return store_E_None;

	// Construct right page.
	PageHolderObject< page > xPageR;
	if (!xPageR.construct (rBIOS.allocator()))
	return store_E_OutOfMemory;

	// Split right page off left page.
	xPageR->split (*rxPageL);
	xPageR->depth (rxPageL->depth());

	// Allocate right page.
	self aNodeR (xPageR.get());
	storeError eErrCode = rBIOS.allocate (aNodeR);
	if (eErrCode != store_E_None)
	return eErrCode;

	// Truncate left page.
	rxPageL->truncate (rxPageL->capacityCount() / 2);

	// Save left page.
	self aNodeL (rxPageL.get());
	eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
	if (eErrCode != store_E_None)
	return eErrCode;

	// Insert right page.
	OStorePageLink aLink (xPageR->location());
	xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));

	// Save this page and leave.
	return rBIOS.saveObjectAt (*this, location());
	}

	/*
	* remove (down to leaf node, recursive).
	*/
	storeError OStoreBTreeNodeObject::remove (
	sal_uInt16 nIndexL,
	OStoreBTreeEntry & rEntryL,
	OStorePageBIOS & rBIOS)
	{
	PageHolderObject< page > xImpl (m_xPage);
	page & rPage = (*xImpl);

	// Check depth.
	storeError eErrCode = store_E_None;
	if (rPage.depth())
	{
	// Check link entry.
	T const aEntryL (rPage.m_pData[nIndexL]);
	if (!(rEntryL.compare (aEntryL) == T::COMPARE_EQUAL))
	return store_E_InvalidAccess;

	// Load link node.
	self aNodeL;
	eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location());
	if (eErrCode != store_E_None)
	return eErrCode;

	// Recurse: remove from link node.
	eErrCode = aNodeL.remove (0, rEntryL, rBIOS);
	if (eErrCode != store_E_None)
	return eErrCode;

	// Check resulting link node usage.
	PageHolderObject< page > xPageL (aNodeL.get());
	if (xPageL->usageCount() == 0)
	{
	// Free empty link node.
	eErrCode = rBIOS.free (xPageL->location());
	if (eErrCode != store_E_None)
	return eErrCode;

	// Remove index.
	rPage.remove (nIndexL);
	touch();
	}
	else
	{
	#if 0 /* NYI */
	// Check for right sibling.
	sal_uInt16 const nIndexR = nIndexL + 1;
	if (nIndexR < rPage.usageCount())
	{
	// Load right link node.
	self aNodeR;
	eErrCode = rBIOS.loadObjectAt (aNodeR, rPage.m_pData[nIndexR].m_aLink.location());
	if (eErrCode == store_E_None)
	{
	if (rPageL.queryMerge (rPageR))
	{
	rPageL.merge (rPageR);

	eErrCode = rBIOS.free (rPageR.location());
	}
	}
	}
	#endif /* NYI */

	// Relink.
	rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey;
	touch();
	}
	}
	else
	{
	// Check leaf entry.
	if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL))
	return store_E_NotExists;

	// Save leaf entry.
	rEntryL = rPage.m_pData[nIndexL];

	// Remove leaf index.
	rPage.remove (nIndexL);
	touch();
	}

	// Check for modified node.
	if (dirty())
	{
	// Save this page.
	eErrCode = rBIOS.saveObjectAt (*this, location());
	}

	// Done.
	return eErrCode;
	}

	/*========================================================================
	*
	* OStoreBTreeRootObject implementation.
	*
	======================================================================/
	/*
	* testInvariant.
	* Precond: root node page loaded.
	*/
	bool OStoreBTreeRootObject::testInvariant (char const * message)
	{
	OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer");
	bool result = ((m_xPage->location() - m_xPage->size()) == 0);
	OSL_POSTCOND(result, message); (void) message;
	return result;
	}

	/*
	* loadOrCreate.
	*/
	storeError OStoreBTreeRootObject::loadOrCreate (
	sal_uInt32 nAddr,
	OStorePageBIOS & rBIOS)
	{
	storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
	if (eErrCode != store_E_NotExists)
	return eErrCode;

	eErrCode = construct<page>(rBIOS.allocator());
	if (eErrCode != store_E_None)
	return eErrCode;

	eErrCode = rBIOS.allocate (*this);
	if (eErrCode != store_E_None)
	return eErrCode;

	// Notify caller of the creation.
	(void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
	return store_E_Pending;
	}

	/*
	* change.
	*/
	storeError OStoreBTreeRootObject::change (
	PageHolderObject< page > & rxPageL,
	OStorePageBIOS & rBIOS)
	{
	PageHolderObject< page > xPage (m_xPage);
	(void) testInvariant("OStoreBTreeRootObject::change(): enter");

	// Save root location.
	sal_uInt32 const nRootAddr = xPage->location();

	// Construct new root.
	if (!rxPageL.construct (rBIOS.allocator()))
	return store_E_OutOfMemory;

	// Save this as prev root.
	storeError eErrCode = rBIOS.allocate (*this);
	if (eErrCode != store_E_None)
	return store_E_OutOfMemory;

	// Setup new root.
	rxPageL->depth (xPage->depth() + 1);
	rxPageL->m_pData[0] = xPage->m_pData[0];
	rxPageL->m_pData[0].m_aLink = xPage->location();
	rxPageL->usageCount(1);

	// Change root.
	rxPageL.swap (xPage);
	{
	PageHolder tmp (xPage.get());
	tmp.swap (m_xPage);
	}

	// Save this as new root and finish.
	eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
	(void) testInvariant("OStoreBTreeRootObject::change(): leave");
	return eErrCode;
	}

	/*
	* find_lookup (w/o split()).
	* Precond: root node page loaded.
	*/
	storeError OStoreBTreeRootObject::find_lookup (
	OStoreBTreeNodeObject & rNode, // [out]
	sal_uInt16 & rIndex, // [out]
	OStorePageKey const & rKey,
	OStorePageBIOS & rBIOS)
	{
	// Init node w/ root page.
	(void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
	{
	PageHolder tmp (m_xPage);
	tmp.swap (rNode.get());
	}

	// Setup BTree entry.
	T const entry (rKey);

	// Check current page.
	PageHolderObject< page > xPage (rNode.get());
	for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
	{
	// Find next page.
	page const & rPage = (*xPage);
	sal_uInt16 const i = rPage.find(entry);
	sal_uInt16 const n = rPage.usageCount();
	if (!(i < n))
	{
	// Path to entry not exists (Must not happen(?)).
	return store_E_NotExists;
	}

	// Check address.
	sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
	if (nAddr == STORE_PAGE_NULL)
	{
	// Path to entry not exists (Must not happen(?)).
	return store_E_NotExists;
	}

	// Load next page.
	storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
	if (eErrCode != store_E_None)
	return eErrCode;
	}

	// Find index.
	page const & rPage = (*xPage);
	rIndex = rPage.find(entry);
	if (!(rIndex < rPage.usageCount()))
	return store_E_NotExists;

	// Compare entry.
	T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
	OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error");
	if (eResult == T::COMPARE_LESS)
	return store_E_Unknown;

	// Greater or Equal.
	(void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
	return store_E_None;
	}

	/*
	* find_insert (possibly with split()).
	* Precond: root node page loaded.
	*/
	storeError OStoreBTreeRootObject::find_insert (
	OStoreBTreeNodeObject & rNode, // [out]
	sal_uInt16 & rIndex, // [out]
	OStorePageKey const & rKey,
	OStorePageBIOS & rBIOS)
	{
	(void) testInvariant("OStoreBTreeRootObject::find_insert(): enter");

	// Check for RootNode split.
	PageHolderObject< page > xRoot (m_xPage);
	if (xRoot->querySplit())
	{
	PageHolderObject< page > xPageL;

	// Change root.
	storeError eErrCode = change (xPageL, rBIOS);
	if (eErrCode != store_E_None)
	return eErrCode;

	// Split left page (prev root).
	eErrCode = split (0, xPageL, rBIOS);
	if (eErrCode != store_E_None)
	return eErrCode;
	}

	// Init node w/ root page.
	{
	PageHolder tmp (m_xPage);
	tmp.swap (rNode.get());
	}

	// Setup BTree entry.
	T const entry (rKey);

	// Check current Page.
	PageHolderObject< page > xPage (rNode.get());
	for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
	{
	// Find next page.
	page const & rPage = (*xPage);
	sal_uInt16 const i = rPage.find (entry);
	sal_uInt16 const n = rPage.usageCount();
	if (!(i < n))
	{
	// Path to entry not exists (Must not happen(?)).
	return store_E_NotExists;
	}

	// Check address.
	sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
	if (nAddr == STORE_PAGE_NULL)
	{
	// Path to entry not exists (Must not happen(?)).
	return store_E_NotExists;
	}

	// Load next page.
	OStoreBTreeNodeObject aNext;
	storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
	if (eErrCode != store_E_None)
	return eErrCode;

	// Check for next node split.
	PageHolderObject< page > xNext (aNext.get());
	if (xNext->querySplit())
	{
	// Split next node.
	eErrCode = rNode.split (i, xNext, rBIOS);
	if (eErrCode != store_E_None)
	return eErrCode;

	// Restart.
	continue;
	}

	// Let next page be current.
	PageHolder tmp (aNext.get());
	tmp.swap (rNode.get());
	}

	// Find index.
	page const & rPage = (*xPage);
	rIndex = rPage.find(entry);
	if (rIndex < rPage.usageCount())
	{
	// Compare entry.
	T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
	OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error");
	if (result == T::COMPARE_LESS)
	return store_E_Unknown;

	if (result == T::COMPARE_EQUAL)
	return store_E_AlreadyExists;
	}

	// Greater or not (yet) existing.
	(void) testInvariant("OStoreBTreeRootObject::find_insert(): leave");
	return store_E_None;
	}