File: | store/source/stortree.cxx |
Location: | line 195, column 24 |
Description: | Called C++ object pointer is null |
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 | ||||
21 | #include "stortree.hxx" | |||
22 | ||||
23 | #include "sal/types.h" | |||
24 | #include "osl/diagnose.h" | |||
25 | ||||
26 | #include "store/types.h" | |||
27 | ||||
28 | #include "storbase.hxx" | |||
29 | #include "storbios.hxx" | |||
30 | ||||
31 | using namespace store; | |||
32 | ||||
33 | /*======================================================================== | |||
34 | * | |||
35 | * OStoreBTreeNodeData implementation. | |||
36 | * | |||
37 | *======================================================================*/ | |||
38 | /* | |||
39 | * OStoreBTreeNodeData. | |||
40 | */ | |||
41 | OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize) | |||
42 | : OStorePageData (nPageSize) | |||
43 | { | |||
44 | base::m_aGuard.m_nMagic = store::htonl(self::theTypeId); | |||
45 | base::m_aDescr.m_nUsed = store::htons(self::thePageSize); // usageCount(0) | |||
46 | self::m_aGuard.m_nMagic = store::htonl(0); // depth(0) | |||
47 | ||||
48 | sal_uInt16 const n = capacityCount(); | |||
49 | T const t; | |||
50 | ||||
51 | for (sal_uInt16 i = 1; i < n; i++) | |||
52 | m_pData[i] = t; | |||
53 | } | |||
54 | ||||
55 | /* | |||
56 | * find. | |||
57 | */ | |||
58 | sal_uInt16 OStoreBTreeNodeData::find (const T& t) const | |||
59 | { | |||
60 | register sal_Int32 l = 0; | |||
61 | register sal_Int32 r = usageCount() - 1; | |||
62 | ||||
63 | while (l < r) | |||
64 | { | |||
65 | register sal_Int32 const m = ((l + r) >> 1); | |||
66 | ||||
67 | if (t.m_aKey == m_pData[m].m_aKey) | |||
68 | return ((sal_uInt16)(m)); | |||
69 | if (t.m_aKey < m_pData[m].m_aKey) | |||
70 | r = m - 1; | |||
71 | else | |||
72 | l = m + 1; | |||
73 | } | |||
74 | ||||
75 | sal_uInt16 const k = ((sal_uInt16)(r)); | |||
76 | if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey)) | |||
77 | return(k - 1); | |||
78 | else | |||
79 | return(k); | |||
80 | } | |||
81 | ||||
82 | /* | |||
83 | * insert. | |||
84 | */ | |||
85 | void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t) | |||
86 | { | |||
87 | sal_uInt16 const n = usageCount(); | |||
88 | sal_uInt16 const m = capacityCount(); | |||
89 | if ((n < m) && (i < m)) | |||
90 | { | |||
91 | // shift right. | |||
92 | memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T)); | |||
93 | ||||
94 | // insert. | |||
95 | m_pData[i] = t; | |||
96 | usageCount (n + 1); | |||
97 | } | |||
98 | } | |||
99 | ||||
100 | /* | |||
101 | * remove. | |||
102 | */ | |||
103 | void OStoreBTreeNodeData::remove (sal_uInt16 i) | |||
104 | { | |||
105 | sal_uInt16 const n = usageCount(); | |||
106 | if (i < n) | |||
107 | { | |||
108 | // shift left. | |||
109 | memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T)); | |||
110 | ||||
111 | // truncate. | |||
112 | m_pData[n - 1] = T(); | |||
113 | usageCount (n - 1); | |||
114 | } | |||
115 | } | |||
116 | ||||
117 | /* | |||
118 | * split (left half copied from right half of left page). | |||
119 | */ | |||
120 | void OStoreBTreeNodeData::split (const self& rPageL) | |||
121 | { | |||
122 | sal_uInt16 const h = capacityCount() / 2; | |||
123 | memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T)); | |||
124 | truncate (h); | |||
125 | } | |||
126 | ||||
127 | /* | |||
128 | * truncate. | |||
129 | */ | |||
130 | void OStoreBTreeNodeData::truncate (sal_uInt16 n) | |||
131 | { | |||
132 | sal_uInt16 const m = capacityCount(); | |||
133 | T const t; | |||
134 | ||||
135 | for (sal_uInt16 i = n; i < m; i++) | |||
136 | m_pData[i] = t; | |||
137 | usageCount (n); | |||
138 | } | |||
139 | ||||
140 | /*======================================================================== | |||
141 | * | |||
142 | * OStoreBTreeNodeObject implementation. | |||
143 | * | |||
144 | *======================================================================*/ | |||
145 | /* | |||
146 | * guard. | |||
147 | */ | |||
148 | storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr) | |||
149 | { | |||
150 | return PageHolderObject< page >::guard (m_xPage, nAddr); | |||
151 | } | |||
152 | ||||
153 | /* | |||
154 | * verify. | |||
155 | */ | |||
156 | storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const | |||
157 | { | |||
158 | return PageHolderObject< page >::verify (m_xPage, nAddr); | |||
159 | } | |||
160 | ||||
161 | /* | |||
162 | * split. | |||
163 | */ | |||
164 | storeError OStoreBTreeNodeObject::split ( | |||
165 | sal_uInt16 nIndexL, | |||
166 | PageHolderObject< page > & rxPageL, | |||
167 | OStorePageBIOS & rBIOS) | |||
168 | { | |||
169 | PageHolderObject< page > xPage (m_xPage); | |||
170 | if (!xPage.is()) | |||
171 | return store_E_InvalidAccess; | |||
172 | ||||
173 | // Check left page usage. | |||
174 | if (!rxPageL.is()) | |||
175 | return store_E_InvalidAccess; | |||
176 | if (!rxPageL->querySplit()) | |||
177 | return store_E_None; | |||
178 | ||||
179 | // Construct right page. | |||
180 | PageHolderObject< page > xPageR; | |||
181 | if (!xPageR.construct (rBIOS.allocator())) | |||
182 | return store_E_OutOfMemory; | |||
183 | ||||
184 | // Split right page off left page. | |||
185 | xPageR->split (*rxPageL); | |||
186 | xPageR->depth (rxPageL->depth()); | |||
187 | ||||
188 | // Allocate right page. | |||
189 | self aNodeR (xPageR.get()); | |||
190 | storeError eErrCode = rBIOS.allocate (aNodeR); | |||
191 | if (eErrCode != store_E_None) | |||
192 | return eErrCode; | |||
193 | ||||
194 | // Truncate left page. | |||
195 | rxPageL->truncate (rxPageL->capacityCount() / 2); | |||
| ||||
196 | ||||
197 | // Save left page. | |||
198 | self aNodeL (rxPageL.get()); | |||
199 | eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location()); | |||
200 | if (eErrCode != store_E_None) | |||
201 | return eErrCode; | |||
202 | ||||
203 | // Insert right page. | |||
204 | OStorePageLink aLink (xPageR->location()); | |||
205 | xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink)); | |||
206 | ||||
207 | // Save this page and leave. | |||
208 | return rBIOS.saveObjectAt (*this, location()); | |||
209 | } | |||
210 | ||||
211 | /* | |||
212 | * remove (down to leaf node, recursive). | |||
213 | */ | |||
214 | storeError OStoreBTreeNodeObject::remove ( | |||
215 | sal_uInt16 nIndexL, | |||
216 | OStoreBTreeEntry & rEntryL, | |||
217 | OStorePageBIOS & rBIOS) | |||
218 | { | |||
219 | PageHolderObject< page > xImpl (m_xPage); | |||
220 | page & rPage = (*xImpl); | |||
221 | ||||
222 | // Check depth. | |||
223 | storeError eErrCode = store_E_None; | |||
224 | if (rPage.depth()) | |||
225 | { | |||
226 | // Check link entry. | |||
227 | T const aEntryL (rPage.m_pData[nIndexL]); | |||
228 | if (!(rEntryL.compare (aEntryL) == T::COMPARE_EQUAL)) | |||
229 | return store_E_InvalidAccess; | |||
230 | ||||
231 | // Load link node. | |||
232 | self aNodeL; | |||
233 | eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location()); | |||
234 | if (eErrCode != store_E_None) | |||
235 | return eErrCode; | |||
236 | ||||
237 | // Recurse: remove from link node. | |||
238 | eErrCode = aNodeL.remove (0, rEntryL, rBIOS); | |||
239 | if (eErrCode != store_E_None) | |||
240 | return eErrCode; | |||
241 | ||||
242 | // Check resulting link node usage. | |||
243 | PageHolderObject< page > xPageL (aNodeL.get()); | |||
244 | if (xPageL->usageCount() == 0) | |||
245 | { | |||
246 | // Free empty link node. | |||
247 | eErrCode = rBIOS.free (xPageL->location()); | |||
248 | if (eErrCode != store_E_None) | |||
249 | return eErrCode; | |||
250 | ||||
251 | // Remove index. | |||
252 | rPage.remove (nIndexL); | |||
253 | touch(); | |||
254 | } | |||
255 | else | |||
256 | { | |||
257 | ||||
258 | // Relink. | |||
259 | rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey; | |||
260 | touch(); | |||
261 | } | |||
262 | } | |||
263 | else | |||
264 | { | |||
265 | // Check leaf entry. | |||
266 | if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL)) | |||
267 | return store_E_NotExists; | |||
268 | ||||
269 | // Save leaf entry. | |||
270 | rEntryL = rPage.m_pData[nIndexL]; | |||
271 | ||||
272 | // Remove leaf index. | |||
273 | rPage.remove (nIndexL); | |||
274 | touch(); | |||
275 | } | |||
276 | ||||
277 | // Check for modified node. | |||
278 | if (dirty()) | |||
279 | { | |||
280 | // Save this page. | |||
281 | eErrCode = rBIOS.saveObjectAt (*this, location()); | |||
282 | } | |||
283 | ||||
284 | // Done. | |||
285 | return eErrCode; | |||
286 | } | |||
287 | ||||
288 | /*======================================================================== | |||
289 | * | |||
290 | * OStoreBTreeRootObject implementation. | |||
291 | * | |||
292 | *======================================================================*/ | |||
293 | /* | |||
294 | * testInvariant. | |||
295 | * Precond: root node page loaded. | |||
296 | */ | |||
297 | bool OStoreBTreeRootObject::testInvariant (char const * message) | |||
298 | { | |||
299 | OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer")do { if (true && (!(m_xPage.get() != 0))) { sal_detail_logFormat ((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/usr/local/src/libreoffice/store/source/stortree.cxx" ":" "299" ": "), "%s", "OStoreBTreeRootObject::testInvariant(): Null pointer" ); } } while (false); | |||
300 | bool result = ((m_xPage->location() - m_xPage->size()) == 0); | |||
301 | OSL_POSTCOND(result, message)do { if (true && (!(result))) { sal_detail_logFormat( (SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/usr/local/src/libreoffice/store/source/stortree.cxx" ":" "301" ": "), "%s", message); } } while (false); (void) message; | |||
302 | return result; | |||
303 | } | |||
304 | ||||
305 | /* | |||
306 | * loadOrCreate. | |||
307 | */ | |||
308 | storeError OStoreBTreeRootObject::loadOrCreate ( | |||
309 | sal_uInt32 nAddr, | |||
310 | OStorePageBIOS & rBIOS) | |||
311 | { | |||
312 | storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr); | |||
313 | if (eErrCode != store_E_NotExists) | |||
314 | return eErrCode; | |||
315 | ||||
316 | eErrCode = construct<page>(rBIOS.allocator()); | |||
317 | if (eErrCode != store_E_None) | |||
318 | return eErrCode; | |||
319 | ||||
320 | eErrCode = rBIOS.allocate (*this); | |||
321 | if (eErrCode != store_E_None) | |||
322 | return eErrCode; | |||
323 | ||||
324 | // Notify caller of the creation. | |||
325 | (void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave"); | |||
326 | return store_E_Pending; | |||
327 | } | |||
328 | ||||
329 | /* | |||
330 | * change. | |||
331 | */ | |||
332 | storeError OStoreBTreeRootObject::change ( | |||
333 | PageHolderObject< page > & rxPageL, | |||
334 | OStorePageBIOS & rBIOS) | |||
335 | { | |||
336 | PageHolderObject< page > xPage (m_xPage); | |||
337 | (void) testInvariant("OStoreBTreeRootObject::change(): enter"); | |||
338 | ||||
339 | // Save root location. | |||
340 | sal_uInt32 const nRootAddr = xPage->location(); | |||
341 | ||||
342 | // Construct new root. | |||
343 | if (!rxPageL.construct (rBIOS.allocator())) | |||
344 | return store_E_OutOfMemory; | |||
345 | ||||
346 | // Save this as prev root. | |||
347 | storeError eErrCode = rBIOS.allocate (*this); | |||
348 | if (eErrCode != store_E_None) | |||
349 | return store_E_OutOfMemory; | |||
350 | ||||
351 | // Setup new root. | |||
352 | rxPageL->depth (xPage->depth() + 1); | |||
353 | rxPageL->m_pData[0] = xPage->m_pData[0]; | |||
354 | rxPageL->m_pData[0].m_aLink = xPage->location(); | |||
355 | rxPageL->usageCount(1); | |||
356 | ||||
357 | // Change root. | |||
358 | rxPageL.swap (xPage); | |||
359 | { | |||
360 | PageHolder tmp (xPage.get()); | |||
361 | tmp.swap (m_xPage); | |||
362 | } | |||
363 | ||||
364 | // Save this as new root and finish. | |||
365 | eErrCode = rBIOS.saveObjectAt (*this, nRootAddr); | |||
366 | (void) testInvariant("OStoreBTreeRootObject::change(): leave"); | |||
367 | return eErrCode; | |||
368 | } | |||
369 | ||||
370 | /* | |||
371 | * find_lookup (w/o split()). | |||
372 | * Precond: root node page loaded. | |||
373 | */ | |||
374 | storeError OStoreBTreeRootObject::find_lookup ( | |||
375 | OStoreBTreeNodeObject & rNode, // [out] | |||
376 | sal_uInt16 & rIndex, // [out] | |||
377 | OStorePageKey const & rKey, | |||
378 | OStorePageBIOS & rBIOS) | |||
379 | { | |||
380 | // Init node w/ root page. | |||
381 | (void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter"); | |||
382 | { | |||
383 | PageHolder tmp (m_xPage); | |||
384 | tmp.swap (rNode.get()); | |||
385 | } | |||
386 | ||||
387 | // Setup BTree entry. | |||
388 | T const entry (rKey); | |||
389 | ||||
390 | // Check current page. | |||
391 | PageHolderObject< page > xPage (rNode.get()); | |||
392 | for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >()) | |||
393 | { | |||
394 | // Find next page. | |||
395 | page const & rPage = (*xPage); | |||
396 | sal_uInt16 const i = rPage.find(entry); | |||
397 | sal_uInt16 const n = rPage.usageCount(); | |||
398 | if (!(i < n)) | |||
399 | { | |||
400 | // Path to entry not exists (Must not happen(?)). | |||
401 | return store_E_NotExists; | |||
402 | } | |||
403 | ||||
404 | // Check address. | |||
405 | sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location(); | |||
406 | if (nAddr == STORE_PAGE_NULL((sal_uInt32)(~0))) | |||
407 | { | |||
408 | // Path to entry not exists (Must not happen(?)). | |||
409 | return store_E_NotExists; | |||
410 | } | |||
411 | ||||
412 | // Load next page. | |||
413 | storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr); | |||
414 | if (eErrCode != store_E_None) | |||
415 | return eErrCode; | |||
416 | } | |||
417 | ||||
418 | // Find index. | |||
419 | page const & rPage = (*xPage); | |||
420 | rIndex = rPage.find(entry); | |||
421 | if (!(rIndex < rPage.usageCount())) | |||
422 | return store_E_NotExists; | |||
423 | ||||
424 | // Compare entry. | |||
425 | T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]); | |||
426 | OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error")do { if (true && (!(eResult != T::COMPARE_LESS))) { sal_detail_logFormat ((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/usr/local/src/libreoffice/store/source/stortree.cxx" ":" "426" ": "), "%s", "store::BTreeRoot::find_lookup(): sort error" ); } } while (false); | |||
427 | if (eResult == T::COMPARE_LESS) | |||
428 | return store_E_Unknown; | |||
429 | ||||
430 | // Greater or Equal. | |||
431 | (void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave"); | |||
432 | return store_E_None; | |||
433 | } | |||
434 | ||||
435 | /* | |||
436 | * find_insert (possibly with split()). | |||
437 | * Precond: root node page loaded. | |||
438 | */ | |||
439 | storeError OStoreBTreeRootObject::find_insert ( | |||
440 | OStoreBTreeNodeObject & rNode, // [out] | |||
441 | sal_uInt16 & rIndex, // [out] | |||
442 | OStorePageKey const & rKey, | |||
443 | OStorePageBIOS & rBIOS) | |||
444 | { | |||
445 | (void) testInvariant("OStoreBTreeRootObject::find_insert(): enter"); | |||
446 | ||||
447 | // Check for RootNode split. | |||
448 | PageHolderObject< page > xRoot (m_xPage); | |||
449 | if (xRoot->querySplit()) | |||
| ||||
450 | { | |||
451 | PageHolderObject< page > xPageL; | |||
452 | ||||
453 | // Change root. | |||
454 | storeError eErrCode = change (xPageL, rBIOS); | |||
455 | if (eErrCode != store_E_None) | |||
456 | return eErrCode; | |||
457 | ||||
458 | // Split left page (prev root). | |||
459 | eErrCode = split (0, xPageL, rBIOS); | |||
460 | if (eErrCode != store_E_None) | |||
461 | return eErrCode; | |||
462 | } | |||
463 | ||||
464 | // Init node w/ root page. | |||
465 | { | |||
466 | PageHolder tmp (m_xPage); | |||
467 | tmp.swap (rNode.get()); | |||
468 | } | |||
469 | ||||
470 | // Setup BTree entry. | |||
471 | T const entry (rKey); | |||
472 | ||||
473 | // Check current Page. | |||
474 | PageHolderObject< page > xPage (rNode.get()); | |||
475 | for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >()) | |||
476 | { | |||
477 | // Find next page. | |||
478 | page const & rPage = (*xPage); | |||
479 | sal_uInt16 const i = rPage.find (entry); | |||
480 | sal_uInt16 const n = rPage.usageCount(); | |||
481 | if (!(i < n)) | |||
482 | { | |||
483 | // Path to entry not exists (Must not happen(?)). | |||
484 | return store_E_NotExists; | |||
485 | } | |||
486 | ||||
487 | // Check address. | |||
488 | sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location(); | |||
489 | if (nAddr == STORE_PAGE_NULL((sal_uInt32)(~0))) | |||
490 | { | |||
491 | // Path to entry not exists (Must not happen(?)). | |||
492 | return store_E_NotExists; | |||
493 | } | |||
494 | ||||
495 | // Load next page. | |||
496 | OStoreBTreeNodeObject aNext; | |||
497 | storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr); | |||
498 | if (eErrCode != store_E_None) | |||
499 | return eErrCode; | |||
500 | ||||
501 | // Check for next node split. | |||
502 | PageHolderObject< page > xNext (aNext.get()); | |||
503 | if (xNext->querySplit()) | |||
504 | { | |||
505 | // Split next node. | |||
506 | eErrCode = rNode.split (i, xNext, rBIOS); | |||
507 | if (eErrCode != store_E_None) | |||
508 | return eErrCode; | |||
509 | ||||
510 | // Restart. | |||
511 | continue; | |||
512 | } | |||
513 | ||||
514 | // Let next page be current. | |||
515 | PageHolder tmp (aNext.get()); | |||
516 | tmp.swap (rNode.get()); | |||
517 | } | |||
518 | ||||
519 | // Find index. | |||
520 | page const & rPage = (*xPage); | |||
521 | rIndex = rPage.find(entry); | |||
522 | if (rIndex < rPage.usageCount()) | |||
523 | { | |||
524 | // Compare entry. | |||
525 | T::CompareResult result = entry.compare (rPage.m_pData[rIndex]); | |||
526 | OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error")do { if (true && (!(result != T::COMPARE_LESS))) { sal_detail_logFormat ((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/usr/local/src/libreoffice/store/source/stortree.cxx" ":" "526" ": "), "%s", "store::BTreeRoot::find_insert(): sort error" ); } } while (false); | |||
527 | if (result == T::COMPARE_LESS) | |||
528 | return store_E_Unknown; | |||
529 | ||||
530 | if (result == T::COMPARE_EQUAL) | |||
531 | return store_E_AlreadyExists; | |||
532 | } | |||
533 | ||||
534 | // Greater or not (yet) existing. | |||
535 | (void) testInvariant("OStoreBTreeRootObject::find_insert(): leave"); | |||
536 | return store_E_None; | |||
537 | } | |||
538 | ||||
539 | /* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |