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