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