Bug Summary

File:store/source/stortree.cxx
Location:line 195, column 24
Description:Called C++ object pointer is null

Annotated 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
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
31using namespace store;
32
33/*========================================================================
34 *
35 * OStoreBTreeNodeData implementation.
36 *
37 *======================================================================*/
38/*
39 * OStoreBTreeNodeData.
40 */
41OStoreBTreeNodeData::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 */
58sal_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 */
85void 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 */
103void 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 */
120void 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 */
130void 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 */
148storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
149{
150 return PageHolderObject< page >::guard (m_xPage, nAddr);
151}
152
153/*
154 * verify.
155 */
156storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
157{
158 return PageHolderObject< page >::verify (m_xPage, nAddr);
159}
160
161/*
162 * split.
163 */
164storeError OStoreBTreeNodeObject::split (
165 sal_uInt16 nIndexL,
166 PageHolderObject< page > & rxPageL,
167 OStorePageBIOS & rBIOS)
168{
169 PageHolderObject< page > xPage (m_xPage);
170 if (!xPage.is())
8
←
Taking false branch
→
171 return store_E_InvalidAccess;
172
173 // Check left page usage.
174 if (!rxPageL.is())
9
←
Taking false branch
→
175 return store_E_InvalidAccess;
176 if (!rxPageL->querySplit())
10
←
Taking false branch
→
177 return store_E_None;
178
179 // Construct right page.
180 PageHolderObject< page > xPageR;
181 if (!xPageR.construct (rBIOS.allocator()))
11
←
Taking false branch
→
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)
12
←
Taking false branch
→
192 return eErrCode;
193
194 // Truncate left page.
195 rxPageL->truncate (rxPageL->capacityCount() / 2);
13
←
Called C++ object pointer is null
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 */
214storeError 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 */
297bool 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 */
308storeError 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 */
332storeError 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 */
374storeError 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 */
439storeError 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())
1
Taking false branch
→
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 >())
2
←
Loop condition is true. Entering loop body
→
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))
3
←
Taking false branch
→
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)))
4
←
Taking false branch
→
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)
5
←
Taking false branch
→
499 return eErrCode;
500
501 // Check for next node split.
502 PageHolderObject< page > xNext (aNext.get());
503 if (xNext->querySplit())
6
←
Taking true branch
→
504 {
505 // Split next node.
506 eErrCode = rNode.split (i, xNext, rBIOS);
7
←
Calling 'split'
→
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: */