Branch data 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 : 4496028 : 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 : 4496028 : m_nAttrib (store::htonl(nAttrib))
59 : 4496028 : {}
60 : :
61 : 3498558 : OStoreBTreeEntry (const OStoreBTreeEntry & rhs)
62 : : : m_aKey (rhs.m_aKey),
63 : : m_aLink (rhs.m_aLink),
64 : 3498558 : m_nAttrib (rhs.m_nAttrib)
65 : 3498558 : {}
66 : :
67 : 356039 : OStoreBTreeEntry& operator= (const OStoreBTreeEntry & rhs)
68 : : {
69 : 356039 : m_aKey = rhs.m_aKey;
70 : 356039 : m_aLink = rhs.m_aLink;
71 : 356039 : m_nAttrib = rhs.m_nAttrib;
72 : 356039 : 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 : 4384237 : CompareResult compare (const OStoreBTreeEntry& rOther) const
85 : : {
86 [ + + ]: 4384237 : if (m_aKey < rOther.m_aKey)
87 : 792805 : return COMPARE_LESS;
88 [ + + ]: 3591432 : else if (m_aKey == rOther.m_aKey)
89 : 2231083 : return COMPARE_EQUAL;
90 : : else
91 : 4384237 : 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 : 6109692 : sal_uInt16 capacity (void) const
128 : : {
129 : 6109692 : return (store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize);
130 : : }
131 : :
132 : : /** capacityCount (must be even).
133 : : */
134 : 5905701 : sal_uInt16 capacityCount (void) const
135 : : {
136 : 5905701 : return sal_uInt16(capacity() / sizeof(T));
137 : : }
138 : :
139 : : /** usage.
140 : : */
141 : 12861872 : sal_uInt16 usage (void) const
142 : : {
143 : 12861872 : return (store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize);
144 : : }
145 : :
146 : : /** usageCount.
147 : : */
148 : 12861872 : sal_uInt16 usageCount (void) const
149 : : {
150 : 12861872 : return sal_uInt16(usage() / sizeof(T));
151 : : }
152 : 96732 : void usageCount (sal_uInt16 nCount)
153 : : {
154 : 96732 : size_t const nBytes = self::thePageSize + nCount * sizeof(T);
155 : 96732 : base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes));
156 : 96732 : }
157 : :
158 : : /** Construction.
159 : : */
160 : : explicit OStoreBTreeNodeData (sal_uInt16 nPageSize = self::thePageSize);
161 : :
162 : : /** guard (external representation).
163 : : */
164 : 109261 : void guard()
165 : : {
166 : 109261 : sal_uInt32 nCRC32 = 0;
167 : 109261 : nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
168 : 109261 : nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
169 : 109261 : m_aGuard.m_nCRC32 = store::htonl(nCRC32);
170 : 109261 : }
171 : :
172 : : /** verify (external representation).
173 : : */
174 : 94730 : storeError verify() const
175 : : {
176 : 94730 : sal_uInt32 nCRC32 = 0;
177 : 94730 : nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
178 : 94730 : nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
179 [ - + ]: 94730 : if (m_aGuard.m_nCRC32 != store::htonl(nCRC32))
180 : 0 : return store_E_InvalidChecksum;
181 : : else
182 : 94730 : return store_E_None;
183 : : }
184 : :
185 : : /** depth.
186 : : */
187 : 6316648 : sal_uInt32 depth (void) const
188 : : {
189 : 6316648 : return store::ntohl(self::m_aGuard.m_nMagic);
190 : : }
191 : 1310 : void depth (sal_uInt32 nDepth)
192 : : {
193 : 1310 : self::m_aGuard.m_nMagic = store::htonl(nDepth);
194 : 1310 : }
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 : 137057 : sal_Bool querySplit (void) const
206 : : {
207 : 137057 : 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 [ - + ]: 2541561 : 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 : 2542312 : explicit OStoreBTreeNodeObject (PageHolder const & rxPage = PageHolder())
242 : 2542312 : : OStorePageObject (rxPage)
243 : 2542312 : {}
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 [ - + ]: 17043 : 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 : 17794 : explicit OStoreBTreeRootObject (PageHolder const & rxPage = PageHolder())
283 : 17794 : : OStoreBTreeNodeObject (rxPage)
284 : 17794 : {}
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: */
|
