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