xref: /trunk/main/store/source/stortree.hxx (revision b9fd132d) 
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 #ifndef _STORE_STORTREE_HXX
25 #define _STORE_STORTREE_HXX "$Revision$"
26 
27 #include "sal/types.h"
28 
29 #include "store/types.h"
30 
31 #include "storbase.hxx"
32 
33 namespace store
34 {
35 
36 class OStorePageBIOS;
37 
38 /*========================================================================
39  *
40  * OStoreBTreeEntry.
41  *
42  *======================================================================*/
43 struct OStoreBTreeEntry
44 {
45 	typedef OStorePageKey  K;
46 	typedef OStorePageLink L;
47 
48 	/** Representation.
49 	*/
50 	K          m_aKey;
51 	L          m_aLink;
52 	sal_uInt32 m_nAttrib;
53 
54 	/** Construction.
55 	*/
OStoreBTreeEntrystore::OStoreBTreeEntry56 	explicit OStoreBTreeEntry (
57         K const &  rKey    = K(),
58         L const &  rLink   = L(),
59         sal_uInt32 nAttrib = 0)
60         : m_aKey    (rKey),
61           m_aLink   (rLink),
62           m_nAttrib (store::htonl(nAttrib))
63 	{}
64 
OStoreBTreeEntrystore::OStoreBTreeEntry65 	OStoreBTreeEntry (const OStoreBTreeEntry & rhs)
66 		: m_aKey    (rhs.m_aKey),
67 		  m_aLink   (rhs.m_aLink),
68 		  m_nAttrib (rhs.m_nAttrib)
69 	{}
70 
operator =store::OStoreBTreeEntry71 	OStoreBTreeEntry& operator= (const OStoreBTreeEntry & rhs)
72 	{
73 		m_aKey    = rhs.m_aKey;
74 		m_aLink   = rhs.m_aLink;
75 		m_nAttrib = rhs.m_nAttrib;
76 		return *this;
77 	}
78 
79 	/** Comparison.
80 	*/
81 	enum CompareResult
82 	{
83 		COMPARE_LESS    = -1,
84 		COMPARE_EQUAL   =  0,
85 		COMPARE_GREATER =  1
86 	};
87 
comparestore::OStoreBTreeEntry88 	CompareResult compare (const OStoreBTreeEntry& rOther) const
89 	{
90 		if (m_aKey < rOther.m_aKey)
91 			return COMPARE_LESS;
92 		else if (m_aKey == rOther.m_aKey)
93 			return COMPARE_EQUAL;
94 		else
95 			return COMPARE_GREATER;
96 	}
97 };
98 
99 /*========================================================================
100  *
101  * OStoreBTreeNodeData.
102  *
103  *======================================================================*/
104 #define STORE_MAGIC_BTREENODE sal_uInt32(0x58190322)
105 
106 struct OStoreBTreeNodeData : public store::OStorePageData
107 {
108 	typedef OStorePageData      base;
109 	typedef OStoreBTreeNodeData self;
110 
111 	typedef OStorePageGuard     G;
112 	typedef OStoreBTreeEntry    T;
113 
114 	/** Representation.
115      */
116 	G m_aGuard;
117 	T m_pData[1];
118 
119     /** type.
120      */
121     static const sal_uInt32 theTypeId = STORE_MAGIC_BTREENODE;
122 
123 	/** theSize.
124      */
125     static const size_t     theSize     = sizeof(G);
126     static const sal_uInt16 thePageSize = base::theSize + self::theSize;
127     STORE_STATIC_ASSERT(STORE_MINIMUM_PAGESIZE >= self::thePageSize);
128 
129 	/** capacity.
130 	*/
capacitystore::OStoreBTreeNodeData131 	sal_uInt16 capacity (void) const
132 	{
133 		return (store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize);
134 	}
135 
136 	/** capacityCount (must be even).
137 	*/
capacityCountstore::OStoreBTreeNodeData138 	sal_uInt16 capacityCount (void) const
139 	{
140 		return sal_uInt16(capacity() / sizeof(T));
141 	}
142 
143 	/** usage.
144 	*/
usagestore::OStoreBTreeNodeData145 	sal_uInt16 usage (void) const
146 	{
147 		return (store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize);
148 	}
149 
150 	/** usageCount.
151 	*/
usageCountstore::OStoreBTreeNodeData152 	sal_uInt16 usageCount (void) const
153 	{
154 		return sal_uInt16(usage() / sizeof(T));
155 	}
usageCountstore::OStoreBTreeNodeData156 	void usageCount (sal_uInt16 nCount)
157 	{
158         size_t const nBytes = self::thePageSize + nCount * sizeof(T);
159 		base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes));
160 	}
161 
162 	/** Construction.
163 	*/
164 	explicit OStoreBTreeNodeData (sal_uInt16 nPageSize = self::thePageSize);
165 
166 	/** guard (external representation).
167 	*/
guardstore::OStoreBTreeNodeData168 	void guard()
169 	{
170 		sal_uInt32 nCRC32 = 0;
171 		nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
172 		nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
173 		m_aGuard.m_nCRC32 = store::htonl(nCRC32);
174 	}
175 
176 	/** verify (external representation).
177 	*/
verifystore::OStoreBTreeNodeData178 	storeError verify() const
179 	{
180 		sal_uInt32 nCRC32 = 0;
181 		nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
182 		nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
183 		if (m_aGuard.m_nCRC32 != store::htonl(nCRC32))
184 			return store_E_InvalidChecksum;
185 		else
186 			return store_E_None;
187 	}
188 
189 	/** depth.
190 	*/
depthstore::OStoreBTreeNodeData191 	sal_uInt32 depth (void) const
192 	{
193 		return store::ntohl(self::m_aGuard.m_nMagic);
194 	}
depthstore::OStoreBTreeNodeData195 	void depth (sal_uInt32 nDepth)
196 	{
197 		self::m_aGuard.m_nMagic = store::htonl(nDepth);
198 	}
199 
200 	/** queryMerge.
201 	*/
queryMergestore::OStoreBTreeNodeData202 	sal_Bool queryMerge (const self &rPageR) const
203 	{
204 		return ((usageCount() + rPageR.usageCount()) <= capacityCount());
205 	}
206 
207 	/** querySplit.
208 	*/
querySplitstore::OStoreBTreeNodeData209 	sal_Bool querySplit (void) const
210 	{
211 		return (!(usageCount() < capacityCount()));
212 	}
213 
214 	/** Operation.
215 	*/
216 	sal_uInt16 find   (const T& t) const;
217 	void       insert (sal_uInt16 i, const T& t);
218 	void       remove (sal_uInt16 i);
219 
220 #if 0  /* NYI */
221 	/** merge (with right page).
222 	 */
223 	void merge (const self& rPageR);
224 #endif
225 
226 	/** split (left half copied from right half of left page).
227 	*/
228 	void split (const self& rPageL);
229 
230 	/** truncate (to n elements).
231 	*/
232 	void truncate (sal_uInt16 n);
233 };
234 
235 /*========================================================================
236  *
237  * OStoreBTreeNodeObject.
238  *
239  *======================================================================*/
240 class OStoreBTreeNodeObject : public store::OStorePageObject
241 {
242 	typedef OStorePageObject      base;
243 	typedef OStoreBTreeNodeObject self;
244 	typedef OStoreBTreeNodeData   page;
245 
246 	typedef OStoreBTreeEntry      T;
247 
248 public:
249 	/** Construction.
250 	*/
OStoreBTreeNodeObject(PageHolder const & rxPage=PageHolder ())251     explicit OStoreBTreeNodeObject (PageHolder const & rxPage = PageHolder())
252         : OStorePageObject (rxPage)
253     {}
254 
255 	/** External representation.
256 	*/
257 	virtual storeError guard  (sal_uInt32 nAddr);
258 	virtual storeError verify (sal_uInt32 nAddr) const;
259 
260 	/** split.
261      *
262      *  @param rxPageL [inout] left child to be split
263      */
264 	storeError split (
265 		sal_uInt16                 nIndexL,
266 		PageHolderObject< page > & rxPageL,
267 		OStorePageBIOS &           rBIOS);
268 
269 	/** remove (down to leaf node, recursive).
270 	*/
271 	storeError remove (
272 		sal_uInt16         nIndexL,
273 		OStoreBTreeEntry & rEntryL,
274 		OStorePageBIOS &   rBIOS);
275 };
276 
277 /*========================================================================
278  *
279  * OStoreBTreeRootObject.
280  *
281  *======================================================================*/
282 class OStoreBTreeRootObject : public store::OStoreBTreeNodeObject
283 {
284 	typedef OStoreBTreeNodeObject base;
285 	typedef OStoreBTreeNodeData   page;
286 
287 	typedef OStoreBTreeEntry      T;
288 
289 public:
290 	/** Construction.
291      */
OStoreBTreeRootObject(PageHolder const & rxPage=PageHolder ())292     explicit OStoreBTreeRootObject (PageHolder const & rxPage = PageHolder())
293         : OStoreBTreeNodeObject (rxPage)
294     {}
295 
296     storeError loadOrCreate (
297         sal_uInt32       nAddr,
298         OStorePageBIOS & rBIOS);
299 
300     /** find_lookup (w/o split()).
301      *  Precond: root node page loaded.
302      */
303     storeError find_lookup (
304         OStoreBTreeNodeObject & rNode,  // [out]
305         sal_uInt16 &            rIndex, // [out]
306         OStorePageKey const &   rKey,
307         OStorePageBIOS &        rBIOS);
308 
309     /** find_insert (possibly with split()).
310      *  Precond: root node page loaded.
311      */
312     storeError find_insert (
313         OStoreBTreeNodeObject & rNode,
314         sal_uInt16 &            rIndex,
315         OStorePageKey const &   rKey,
316         OStorePageBIOS &        rBIOS);
317 
318 private:
319     /** testInvariant.
320      *  Precond: root node page loaded.
321      */
322     bool testInvariant (char const * message);
323 
324 	/** change (Root).
325      *
326      *  @param rxPageL [out] prev. root (needs split)
327      */
328 	storeError change (
329 		PageHolderObject< page > & rxPageL,
330 		OStorePageBIOS &           rBIOS);
331 };
332 
333 /*========================================================================
334  *
335  * The End.
336  *
337  *======================================================================*/
338 
339 } // namespace store
340 
341 #endif /* !_STORE_STORTREE_HXX */
342