1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
|
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
* This file is part of the LibreOffice project.
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*
* This file incorporates work covered by the following license notice:
*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed
* with this work for additional information regarding copyright
* ownership. The ASF licenses this file to you under the Apache
* License, Version 2.0 (the "License"); you may not use this file
* except in compliance with the License. You may obtain a copy of
* the License at http://www.apache.org/licenses/LICENSE-2.0 .
*/
#pragma once
#include <sal/config.h>
#include <memory>
#include <sal/types.h>
#include <store/types.h>
#include "storbase.hxx"
namespace store
{
class OStorePageBIOS;
struct OStoreBTreeEntry
{
typedef OStorePageKey K;
typedef OStorePageLink L;
K m_aKey;
L m_aLink;
sal_uInt32 m_nAttrib;
explicit OStoreBTreeEntry (
K const & rKey = K(),
L const & rLink = L())
: m_aKey (rKey),
m_aLink (rLink),
m_nAttrib (store::htonl(0))
{}
enum CompareResult
{
COMPARE_LESS = -1,
COMPARE_EQUAL = 0,
COMPARE_GREATER = 1
};
CompareResult compare (const OStoreBTreeEntry& rOther) const
{
if (m_aKey < rOther.m_aKey)
return COMPARE_LESS;
else if (m_aKey == rOther.m_aKey)
return COMPARE_EQUAL;
else
return COMPARE_GREATER;
}
};
#define STORE_MAGIC_BTREENODE sal_uInt32(0x58190322)
struct OStoreBTreeNodeData : public store::PageData
{
typedef PageData base;
typedef OStoreBTreeNodeData self;
typedef OStorePageGuard G;
typedef OStoreBTreeEntry T;
G m_aGuard;
T m_pData[1];
static const sal_uInt32 theTypeId = STORE_MAGIC_BTREENODE;
static const size_t theSize = sizeof(G);
static const sal_uInt16 thePageSize = base::theSize + self::theSize;
static_assert(STORE_MINIMUM_PAGESIZE >= self::thePageSize, "got to be at least equal in size");
sal_uInt16 capacity() const
{
return static_cast<sal_uInt16>(store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize);
}
/** capacityCount (must be even).
*/
sal_uInt16 capacityCount() const
{
return sal_uInt16(capacity() / sizeof(T));
}
sal_uInt16 usage() const
{
return static_cast<sal_uInt16>(store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize);
}
sal_uInt16 usageCount() const
{
return sal_uInt16(usage() / sizeof(T));
}
void usageCount (sal_uInt16 nCount)
{
size_t const nBytes = self::thePageSize + nCount * sizeof(T);
base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes));
}
explicit OStoreBTreeNodeData (sal_uInt16 nPageSize);
void guard()
{
sal_uInt32 nCRC32 = rtl_crc32 (0, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
m_aGuard.m_nCRC32 = store::htonl(nCRC32);
}
storeError verify() const
{
sal_uInt32 nCRC32 = rtl_crc32 (0, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
if (m_aGuard.m_nCRC32 != store::htonl(nCRC32))
return store_E_InvalidChecksum;
else
return store_E_None;
}
sal_uInt32 depth() const
{
return store::ntohl(self::m_aGuard.m_nMagic);
}
void depth (sal_uInt32 nDepth)
{
self::m_aGuard.m_nMagic = store::htonl(nDepth);
}
bool querySplit() const
{
return usageCount() >= capacityCount();
}
sal_uInt16 find (const T& t) const;
void insert (sal_uInt16 i, const T& t);
void remove (sal_uInt16 i);
/** split (left half copied from right half of left page).
*/
void split (const self& rPageL);
/** truncate (to n elements).
*/
void truncate (sal_uInt16 n);
};
class OStoreBTreeNodeObject : public store::OStorePageObject
{
typedef OStorePageObject base;
typedef OStoreBTreeNodeObject self;
typedef OStoreBTreeNodeData page;
typedef OStoreBTreeEntry T;
public:
explicit OStoreBTreeNodeObject (std::shared_ptr<PageData> const & rxPage = std::shared_ptr<PageData>())
: OStorePageObject (rxPage)
{}
virtual storeError guard (sal_uInt32 nAddr) override;
virtual storeError verify (sal_uInt32 nAddr) const override;
/** split.
*
* @param rxPageL [inout] left child to be split
*/
storeError split (
sal_uInt16 nIndexL,
PageHolderObject< page > & rxPageL,
OStorePageBIOS & rBIOS);
/** remove (down to leaf node, recursive).
*/
storeError remove (
sal_uInt16 nIndexL,
OStoreBTreeEntry & rEntryL,
OStorePageBIOS & rBIOS);
};
class OStoreBTreeRootObject : public store::OStoreBTreeNodeObject
{
typedef OStoreBTreeNodeObject base;
typedef OStoreBTreeNodeData page;
typedef OStoreBTreeEntry T;
public:
explicit OStoreBTreeRootObject (std::shared_ptr<PageData> const & rxPage = std::shared_ptr<PageData>())
: OStoreBTreeNodeObject (rxPage)
{}
storeError loadOrCreate (
sal_uInt32 nAddr,
OStorePageBIOS & rBIOS);
/** find_lookup (w/o split()).
* Precond: root node page loaded.
*/
storeError find_lookup (
OStoreBTreeNodeObject & rNode, // [out]
sal_uInt16 & rIndex, // [out]
OStorePageKey const & rKey,
OStorePageBIOS & rBIOS) const;
/** find_insert (possibly with split()).
* Precond: root node page loaded.
*/
storeError find_insert (
OStoreBTreeNodeObject & rNode,
sal_uInt16 & rIndex,
OStorePageKey const & rKey,
OStorePageBIOS & rBIOS);
private:
/** testInvariant.
* Precond: root node page loaded.
*/
void testInvariant (char const * message) const;
/** change (Root).
*
* @param rxPageL [out] prev. root (needs split)
*/
storeError change (
PageHolderObject< page > & rxPageL,
OStorePageBIOS & rBIOS);
};
} // namespace store
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
