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 #ifndef _STORE_STORTREE_HXX 29 #define _STORE_STORTREE_HXX "$Revision: 1.6.8.2 $" 30 31 #include "sal/types.h" 32 33 #include "store/types.h" 34 35 #include "storbase.hxx" 36 37 namespace store 38 { 39 40 class OStorePageBIOS; 41 42 /*======================================================================== 43 * 44 * OStoreBTreeEntry. 45 * 46 *======================================================================*/ 47 struct OStoreBTreeEntry 48 { 49 typedef OStorePageKey K; 50 typedef OStorePageLink L; 51 52 /** Representation. 53 */ 54 K m_aKey; 55 L m_aLink; 56 sal_uInt32 m_nAttrib; 57 58 /** Construction. 59 */ 60 explicit OStoreBTreeEntry ( 61 K const & rKey = K(), 62 L const & rLink = L(), 63 sal_uInt32 nAttrib = 0) 64 : m_aKey (rKey), 65 m_aLink (rLink), 66 m_nAttrib (store::htonl(nAttrib)) 67 {} 68 69 OStoreBTreeEntry (const OStoreBTreeEntry & rhs) 70 : m_aKey (rhs.m_aKey), 71 m_aLink (rhs.m_aLink), 72 m_nAttrib (rhs.m_nAttrib) 73 {} 74 75 OStoreBTreeEntry& operator= (const OStoreBTreeEntry & rhs) 76 { 77 m_aKey = rhs.m_aKey; 78 m_aLink = rhs.m_aLink; 79 m_nAttrib = rhs.m_nAttrib; 80 return *this; 81 } 82 83 /** Comparison. 84 */ 85 enum CompareResult 86 { 87 COMPARE_LESS = -1, 88 COMPARE_EQUAL = 0, 89 COMPARE_GREATER = 1 90 }; 91 92 CompareResult compare (const OStoreBTreeEntry& rOther) const 93 { 94 if (m_aKey < rOther.m_aKey) 95 return COMPARE_LESS; 96 else if (m_aKey == rOther.m_aKey) 97 return COMPARE_EQUAL; 98 else 99 return COMPARE_GREATER; 100 } 101 }; 102 103 /*======================================================================== 104 * 105 * OStoreBTreeNodeData. 106 * 107 *======================================================================*/ 108 #define STORE_MAGIC_BTREENODE sal_uInt32(0x58190322) 109 110 struct OStoreBTreeNodeData : public store::OStorePageData 111 { 112 typedef OStorePageData base; 113 typedef OStoreBTreeNodeData self; 114 115 typedef OStorePageGuard G; 116 typedef OStoreBTreeEntry T; 117 118 /** Representation. 119 */ 120 G m_aGuard; 121 T m_pData[1]; 122 123 /** type. 124 */ 125 static const sal_uInt32 theTypeId = STORE_MAGIC_BTREENODE; 126 127 /** theSize. 128 */ 129 static const size_t theSize = sizeof(G); 130 static const sal_uInt16 thePageSize = base::theSize + self::theSize; 131 STORE_STATIC_ASSERT(STORE_MINIMUM_PAGESIZE >= self::thePageSize); 132 133 /** capacity. 134 */ 135 sal_uInt16 capacity (void) const 136 { 137 return (store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize); 138 } 139 140 /** capacityCount (must be even). 141 */ 142 sal_uInt16 capacityCount (void) const 143 { 144 return sal_uInt16(capacity() / sizeof(T)); 145 } 146 147 /** usage. 148 */ 149 sal_uInt16 usage (void) const 150 { 151 return (store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize); 152 } 153 154 /** usageCount. 155 */ 156 sal_uInt16 usageCount (void) const 157 { 158 return sal_uInt16(usage() / sizeof(T)); 159 } 160 void usageCount (sal_uInt16 nCount) 161 { 162 size_t const nBytes = self::thePageSize + nCount * sizeof(T); 163 base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes)); 164 } 165 166 /** Construction. 167 */ 168 explicit OStoreBTreeNodeData (sal_uInt16 nPageSize = self::thePageSize); 169 170 /** guard (external representation). 171 */ 172 void guard() 173 { 174 sal_uInt32 nCRC32 = 0; 175 nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32)); 176 nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity()); 177 m_aGuard.m_nCRC32 = store::htonl(nCRC32); 178 } 179 180 /** verify (external representation). 181 */ 182 storeError verify() const 183 { 184 sal_uInt32 nCRC32 = 0; 185 nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32)); 186 nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity()); 187 if (m_aGuard.m_nCRC32 != store::htonl(nCRC32)) 188 return store_E_InvalidChecksum; 189 else 190 return store_E_None; 191 } 192 193 /** depth. 194 */ 195 sal_uInt32 depth (void) const 196 { 197 return store::ntohl(self::m_aGuard.m_nMagic); 198 } 199 void depth (sal_uInt32 nDepth) 200 { 201 self::m_aGuard.m_nMagic = store::htonl(nDepth); 202 } 203 204 /** queryMerge. 205 */ 206 sal_Bool queryMerge (const self &rPageR) const 207 { 208 return ((usageCount() + rPageR.usageCount()) <= capacityCount()); 209 } 210 211 /** querySplit. 212 */ 213 sal_Bool querySplit (void) const 214 { 215 return (!(usageCount() < capacityCount())); 216 } 217 218 /** Operation. 219 */ 220 sal_uInt16 find (const T& t) const; 221 void insert (sal_uInt16 i, const T& t); 222 void remove (sal_uInt16 i); 223 224 #if 0 /* NYI */ 225 /** merge (with right page). 226 */ 227 void merge (const self& rPageR); 228 #endif 229 230 /** split (left half copied from right half of left page). 231 */ 232 void split (const self& rPageL); 233 234 /** truncate (to n elements). 235 */ 236 void truncate (sal_uInt16 n); 237 }; 238 239 /*======================================================================== 240 * 241 * OStoreBTreeNodeObject. 242 * 243 *======================================================================*/ 244 class OStoreBTreeNodeObject : public store::OStorePageObject 245 { 246 typedef OStorePageObject base; 247 typedef OStoreBTreeNodeObject self; 248 typedef OStoreBTreeNodeData page; 249 250 typedef OStoreBTreeEntry T; 251 252 public: 253 /** Construction. 254 */ 255 explicit OStoreBTreeNodeObject (PageHolder const & rxPage = PageHolder()) 256 : OStorePageObject (rxPage) 257 {} 258 259 /** External representation. 260 */ 261 virtual storeError guard (sal_uInt32 nAddr); 262 virtual storeError verify (sal_uInt32 nAddr) const; 263 264 /** split. 265 * 266 * @param rxPageL [inout] left child to be split 267 */ 268 storeError split ( 269 sal_uInt16 nIndexL, 270 PageHolderObject< page > & rxPageL, 271 OStorePageBIOS & rBIOS); 272 273 /** remove (down to leaf node, recursive). 274 */ 275 storeError remove ( 276 sal_uInt16 nIndexL, 277 OStoreBTreeEntry & rEntryL, 278 OStorePageBIOS & rBIOS); 279 }; 280 281 /*======================================================================== 282 * 283 * OStoreBTreeRootObject. 284 * 285 *======================================================================*/ 286 class OStoreBTreeRootObject : public store::OStoreBTreeNodeObject 287 { 288 typedef OStoreBTreeNodeObject base; 289 typedef OStoreBTreeNodeData page; 290 291 typedef OStoreBTreeEntry T; 292 293 public: 294 /** Construction. 295 */ 296 explicit OStoreBTreeRootObject (PageHolder const & rxPage = PageHolder()) 297 : OStoreBTreeNodeObject (rxPage) 298 {} 299 300 storeError loadOrCreate ( 301 sal_uInt32 nAddr, 302 OStorePageBIOS & rBIOS); 303 304 /** find_lookup (w/o split()). 305 * Precond: root node page loaded. 306 */ 307 storeError find_lookup ( 308 OStoreBTreeNodeObject & rNode, // [out] 309 sal_uInt16 & rIndex, // [out] 310 OStorePageKey const & rKey, 311 OStorePageBIOS & rBIOS); 312 313 /** find_insert (possibly with split()). 314 * Precond: root node page loaded. 315 */ 316 storeError find_insert ( 317 OStoreBTreeNodeObject & rNode, 318 sal_uInt16 & rIndex, 319 OStorePageKey const & rKey, 320 OStorePageBIOS & rBIOS); 321 322 private: 323 /** testInvariant. 324 * Precond: root node page loaded. 325 */ 326 bool testInvariant (char const * message); 327 328 /** change (Root). 329 * 330 * @param rxPageL [out] prev. root (needs split) 331 */ 332 storeError change ( 333 PageHolderObject< page > & rxPageL, 334 OStorePageBIOS & rBIOS); 335 }; 336 337 /*======================================================================== 338 * 339 * The End. 340 * 341 *======================================================================*/ 342 343 } // namespace store 344 345 #endif /* !_STORE_STORTREE_HXX */ 346