1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 // MARKER(update_precomp.py): autogen include statement, do not remove 29 #include "precompiled_store.hxx" 30 31 #include "stortree.hxx" 32 33 #include "sal/types.h" 34 #include "osl/diagnose.h" 35 36 #include "store/types.h" 37 38 #include "storbase.hxx" 39 #include "storbios.hxx" 40 41 using namespace store; 42 43 /*======================================================================== 44 * 45 * OStoreBTreeNodeData implementation. 46 * 47 *======================================================================*/ 48 /* 49 * OStoreBTreeNodeData. 50 */ 51 OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize) 52 : OStorePageData (nPageSize) 53 { 54 base::m_aGuard.m_nMagic = store::htonl(self::theTypeId); 55 base::m_aDescr.m_nUsed = store::htons(self::thePageSize); // usageCount(0) 56 self::m_aGuard.m_nMagic = store::htonl(0); // depth(0) 57 58 sal_uInt16 const n = capacityCount(); 59 T const t; 60 61 for (sal_uInt16 i = 1; i < n; i++) 62 m_pData[i] = t; 63 } 64 65 /* 66 * find. 67 */ 68 sal_uInt16 OStoreBTreeNodeData::find (const T& t) const 69 { 70 register sal_Int32 l = 0; 71 register sal_Int32 r = usageCount() - 1; 72 73 while (l < r) 74 { 75 register sal_Int32 const m = ((l + r) >> 1); 76 77 if (t.m_aKey == m_pData[m].m_aKey) 78 return ((sal_uInt16)(m)); 79 if (t.m_aKey < m_pData[m].m_aKey) 80 r = m - 1; 81 else 82 l = m + 1; 83 } 84 85 sal_uInt16 const k = ((sal_uInt16)(r)); 86 if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey)) 87 return(k - 1); 88 else 89 return(k); 90 } 91 92 /* 93 * insert. 94 */ 95 void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t) 96 { 97 sal_uInt16 const n = usageCount(); 98 sal_uInt16 const m = capacityCount(); 99 if ((n < m) && (i < m)) 100 { 101 // shift right. 102 memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T)); 103 104 // insert. 105 m_pData[i] = t; 106 usageCount (n + 1); 107 } 108 } 109 110 /* 111 * remove. 112 */ 113 void OStoreBTreeNodeData::remove (sal_uInt16 i) 114 { 115 sal_uInt16 const n = usageCount(); 116 if (i < n) 117 { 118 // shift left. 119 memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T)); 120 121 // truncate. 122 m_pData[n - 1] = T(); 123 usageCount (n - 1); 124 } 125 } 126 127 #if 0 /* NYI */ 128 /* 129 * merge (with right page). 130 */ 131 void OStoreBTreeNodeData::merge (const self& rPageR) 132 { 133 sal_uInt16 const n = usageCount(); 134 sal_uInt16 const m = rPageR.usageCount(); 135 if ((n + m) <= capacityCount()) 136 { 137 memcpy (&(m_pData[n]), &(rPageR.m_pData[0]), m * sizeof(T)); 138 usageCount (n + m); 139 } 140 } 141 #endif 142 143 /* 144 * split (left half copied from right half of left page). 145 */ 146 void OStoreBTreeNodeData::split (const self& rPageL) 147 { 148 sal_uInt16 const h = capacityCount() / 2; 149 memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T)); 150 truncate (h); 151 } 152 153 /* 154 * truncate. 155 */ 156 void OStoreBTreeNodeData::truncate (sal_uInt16 n) 157 { 158 sal_uInt16 const m = capacityCount(); 159 T const t; 160 161 for (sal_uInt16 i = n; i < m; i++) 162 m_pData[i] = t; 163 usageCount (n); 164 } 165 166 /*======================================================================== 167 * 168 * OStoreBTreeNodeObject implementation. 169 * 170 *======================================================================*/ 171 /* 172 * guard. 173 */ 174 storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr) 175 { 176 return PageHolderObject< page >::guard (m_xPage, nAddr); 177 } 178 179 /* 180 * verify. 181 */ 182 storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const 183 { 184 return PageHolderObject< page >::verify (m_xPage, nAddr); 185 } 186 187 /* 188 * split. 189 */ 190 storeError OStoreBTreeNodeObject::split ( 191 sal_uInt16 nIndexL, 192 PageHolderObject< page > & rxPageL, 193 OStorePageBIOS & rBIOS) 194 { 195 PageHolderObject< page > xPage (m_xPage); 196 if (!xPage.is()) 197 return store_E_InvalidAccess; 198 199 // Check left page usage. 200 if (!rxPageL.is()) 201 return store_E_InvalidAccess; 202 if (!rxPageL->querySplit()) 203 return store_E_None; 204 205 // Construct right page. 206 PageHolderObject< page > xPageR; 207 if (!xPageR.construct (rBIOS.allocator())) 208 return store_E_OutOfMemory; 209 210 // Split right page off left page. 211 xPageR->split (*rxPageL); 212 xPageR->depth (rxPageL->depth()); 213 214 // Allocate right page. 215 self aNodeR (xPageR.get()); 216 storeError eErrCode = rBIOS.allocate (aNodeR); 217 if (eErrCode != store_E_None) 218 return eErrCode; 219 220 // Truncate left page. 221 rxPageL->truncate (rxPageL->capacityCount() / 2); 222 223 // Save left page. 224 self aNodeL (rxPageL.get()); 225 eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location()); 226 if (eErrCode != store_E_None) 227 return eErrCode; 228 229 // Insert right page. 230 OStorePageLink aLink (xPageR->location()); 231 xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink)); 232 233 // Save this page and leave. 234 return rBIOS.saveObjectAt (*this, location()); 235 } 236 237 /* 238 * remove (down to leaf node, recursive). 239 */ 240 storeError OStoreBTreeNodeObject::remove ( 241 sal_uInt16 nIndexL, 242 OStoreBTreeEntry & rEntryL, 243 OStorePageBIOS & rBIOS) 244 { 245 PageHolderObject< page > xImpl (m_xPage); 246 page & rPage = (*xImpl); 247 248 // Check depth. 249 storeError eErrCode = store_E_None; 250 if (rPage.depth()) 251 { 252 // Check link entry. 253 T const aEntryL (rPage.m_pData[nIndexL]); 254 if (!(rEntryL.compare (aEntryL) == T::COMPARE_EQUAL)) 255 return store_E_InvalidAccess; 256 257 // Load link node. 258 self aNodeL; 259 eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location()); 260 if (eErrCode != store_E_None) 261 return eErrCode; 262 263 // Recurse: remove from link node. 264 eErrCode = aNodeL.remove (0, rEntryL, rBIOS); 265 if (eErrCode != store_E_None) 266 return eErrCode; 267 268 // Check resulting link node usage. 269 PageHolderObject< page > xPageL (aNodeL.get()); 270 if (xPageL->usageCount() == 0) 271 { 272 // Free empty link node. 273 eErrCode = rBIOS.free (xPageL->location()); 274 if (eErrCode != store_E_None) 275 return eErrCode; 276 277 // Remove index. 278 rPage.remove (nIndexL); 279 touch(); 280 } 281 else 282 { 283 #if 0 /* NYI */ 284 // Check for right sibling. 285 sal_uInt16 const nIndexR = nIndexL + 1; 286 if (nIndexR < rPage.usageCount()) 287 { 288 // Load right link node. 289 self aNodeR; 290 eErrCode = rBIOS.loadObjectAt (aNodeR, rPage.m_pData[nIndexR].m_aLink.location()); 291 if (eErrCode == store_E_None) 292 { 293 if (rPageL.queryMerge (rPageR)) 294 { 295 rPageL.merge (rPageR); 296 297 eErrCode = rBIOS.free (rPageR.location()); 298 } 299 } 300 } 301 #endif /* NYI */ 302 303 // Relink. 304 rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey; 305 touch(); 306 } 307 } 308 else 309 { 310 // Check leaf entry. 311 if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL)) 312 return store_E_NotExists; 313 314 // Save leaf entry. 315 rEntryL = rPage.m_pData[nIndexL]; 316 317 // Remove leaf index. 318 rPage.remove (nIndexL); 319 touch(); 320 } 321 322 // Check for modified node. 323 if (dirty()) 324 { 325 // Save this page. 326 eErrCode = rBIOS.saveObjectAt (*this, location()); 327 } 328 329 // Done. 330 return eErrCode; 331 } 332 333 /*======================================================================== 334 * 335 * OStoreBTreeRootObject implementation. 336 * 337 *======================================================================*/ 338 /* 339 * testInvariant. 340 * Precond: root node page loaded. 341 */ 342 bool OStoreBTreeRootObject::testInvariant (char const * message) 343 { 344 OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer"); 345 bool result = ((m_xPage->location() - m_xPage->size()) == 0); 346 OSL_POSTCOND(result, message); (void) message; 347 return result; 348 } 349 350 /* 351 * loadOrCreate. 352 */ 353 storeError OStoreBTreeRootObject::loadOrCreate ( 354 sal_uInt32 nAddr, 355 OStorePageBIOS & rBIOS) 356 { 357 storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr); 358 if (eErrCode != store_E_NotExists) 359 return eErrCode; 360 361 eErrCode = construct<page>(rBIOS.allocator()); 362 if (eErrCode != store_E_None) 363 return eErrCode; 364 365 eErrCode = rBIOS.allocate (*this); 366 if (eErrCode != store_E_None) 367 return eErrCode; 368 369 // Notify caller of the creation. 370 (void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave"); 371 return store_E_Pending; 372 } 373 374 /* 375 * change. 376 */ 377 storeError OStoreBTreeRootObject::change ( 378 PageHolderObject< page > & rxPageL, 379 OStorePageBIOS & rBIOS) 380 { 381 PageHolderObject< page > xPage (m_xPage); 382 (void) testInvariant("OStoreBTreeRootObject::change(): enter"); 383 384 // Save root location. 385 sal_uInt32 const nRootAddr = xPage->location(); 386 387 // Construct new root. 388 if (!rxPageL.construct (rBIOS.allocator())) 389 return store_E_OutOfMemory; 390 391 // Save this as prev root. 392 storeError eErrCode = rBIOS.allocate (*this); 393 if (eErrCode != store_E_None) 394 return store_E_OutOfMemory; 395 396 // Setup new root. 397 rxPageL->depth (xPage->depth() + 1); 398 rxPageL->m_pData[0] = xPage->m_pData[0]; 399 rxPageL->m_pData[0].m_aLink = xPage->location(); 400 rxPageL->usageCount(1); 401 402 // Change root. 403 rxPageL.swap (xPage); 404 { 405 PageHolder tmp (xPage.get()); 406 tmp.swap (m_xPage); 407 } 408 409 // Save this as new root and finish. 410 eErrCode = rBIOS.saveObjectAt (*this, nRootAddr); 411 (void) testInvariant("OStoreBTreeRootObject::change(): leave"); 412 return eErrCode; 413 } 414 415 /* 416 * find_lookup (w/o split()). 417 * Precond: root node page loaded. 418 */ 419 storeError OStoreBTreeRootObject::find_lookup ( 420 OStoreBTreeNodeObject & rNode, // [out] 421 sal_uInt16 & rIndex, // [out] 422 OStorePageKey const & rKey, 423 OStorePageBIOS & rBIOS) 424 { 425 // Init node w/ root page. 426 (void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter"); 427 { 428 PageHolder tmp (m_xPage); 429 tmp.swap (rNode.get()); 430 } 431 432 // Setup BTree entry. 433 T const entry (rKey); 434 435 // Check current page. 436 PageHolderObject< page > xPage (rNode.get()); 437 for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >()) 438 { 439 // Find next page. 440 page const & rPage = (*xPage); 441 sal_uInt16 const i = rPage.find(entry); 442 sal_uInt16 const n = rPage.usageCount(); 443 if (!(i < n)) 444 { 445 // Path to entry not exists (Must not happen(?)). 446 return store_E_NotExists; 447 } 448 449 // Check address. 450 sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location(); 451 if (nAddr == STORE_PAGE_NULL) 452 { 453 // Path to entry not exists (Must not happen(?)). 454 return store_E_NotExists; 455 } 456 457 // Load next page. 458 storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr); 459 if (eErrCode != store_E_None) 460 return eErrCode; 461 } 462 463 // Find index. 464 page const & rPage = (*xPage); 465 rIndex = rPage.find(entry); 466 if (!(rIndex < rPage.usageCount())) 467 return store_E_NotExists; 468 469 // Compare entry. 470 T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]); 471 OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error"); 472 if (eResult == T::COMPARE_LESS) 473 return store_E_Unknown; 474 475 // Greater or Equal. 476 (void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave"); 477 return store_E_None; 478 } 479 480 /* 481 * find_insert (possibly with split()). 482 * Precond: root node page loaded. 483 */ 484 storeError OStoreBTreeRootObject::find_insert ( 485 OStoreBTreeNodeObject & rNode, // [out] 486 sal_uInt16 & rIndex, // [out] 487 OStorePageKey const & rKey, 488 OStorePageBIOS & rBIOS) 489 { 490 (void) testInvariant("OStoreBTreeRootObject::find_insert(): enter"); 491 492 // Check for RootNode split. 493 PageHolderObject< page > xRoot (m_xPage); 494 if (xRoot->querySplit()) 495 { 496 PageHolderObject< page > xPageL; 497 498 // Change root. 499 storeError eErrCode = change (xPageL, rBIOS); 500 if (eErrCode != store_E_None) 501 return eErrCode; 502 503 // Split left page (prev root). 504 eErrCode = split (0, xPageL, rBIOS); 505 if (eErrCode != store_E_None) 506 return eErrCode; 507 } 508 509 // Init node w/ root page. 510 { 511 PageHolder tmp (m_xPage); 512 tmp.swap (rNode.get()); 513 } 514 515 // Setup BTree entry. 516 T const entry (rKey); 517 518 // Check current Page. 519 PageHolderObject< page > xPage (rNode.get()); 520 for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >()) 521 { 522 // Find next page. 523 page const & rPage = (*xPage); 524 sal_uInt16 const i = rPage.find (entry); 525 sal_uInt16 const n = rPage.usageCount(); 526 if (!(i < n)) 527 { 528 // Path to entry not exists (Must not happen(?)). 529 return store_E_NotExists; 530 } 531 532 // Check address. 533 sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location(); 534 if (nAddr == STORE_PAGE_NULL) 535 { 536 // Path to entry not exists (Must not happen(?)). 537 return store_E_NotExists; 538 } 539 540 // Load next page. 541 OStoreBTreeNodeObject aNext; 542 storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr); 543 if (eErrCode != store_E_None) 544 return eErrCode; 545 546 // Check for next node split. 547 PageHolderObject< page > xNext (aNext.get()); 548 if (xNext->querySplit()) 549 { 550 // Split next node. 551 eErrCode = rNode.split (i, xNext, rBIOS); 552 if (eErrCode != store_E_None) 553 return eErrCode; 554 555 // Restart. 556 continue; 557 } 558 559 // Let next page be current. 560 PageHolder tmp (aNext.get()); 561 tmp.swap (rNode.get()); 562 } 563 564 // Find index. 565 page const & rPage = (*xPage); 566 rIndex = rPage.find(entry); 567 if (rIndex < rPage.usageCount()) 568 { 569 // Compare entry. 570 T::CompareResult result = entry.compare (rPage.m_pData[rIndex]); 571 OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error"); 572 if (result == T::COMPARE_LESS) 573 return store_E_Unknown; 574 575 if (result == T::COMPARE_EQUAL) 576 return store_E_AlreadyExists; 577 } 578 579 // Greater or not (yet) existing. 580 (void) testInvariant("OStoreBTreeRootObject::find_insert(): leave"); 581 return store_E_None; 582 } 583