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