File: | store/source/stortree.cxx |
Location: | line 340, column 34 |
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(); |
Called C++ object pointer is null | |
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: */ |