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