1/* 2 * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved. 3 * 4 * The contents of this file constitute Original Code as defined in and are 5 * subject to the Apple Public Source License Version 1.2 (the 'License'). 6 * You may not use this file except in compliance with the License. Please obtain 7 * a copy of the License at http://www.apple.com/publicsource and read it before 8 * using this file. 9 * 10 * This Original Code and all software distributed under the License are 11 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS 12 * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT 13 * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR 14 * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the 15 * specific language governing rights and limitations under the License. 16 */ 17 18 19// 20// DbIndex.cpp 21// 22 23#include "DbIndex.h" 24#include "AppleDatabase.h" 25#include <stdio.h> 26 27DbQueryKey::DbQueryKey(const DbConstIndex &index) 28: mIndex(index), 29 mTableSection(index.table().getTableSection()) 30{ 31} 32 33// Perform a less-than comparison between two keys. An offset of 34// kUseQueryKeyOffset means to use the key provided as part of the 35// query; otherwise, the key comes from the database. 36 37const uint32 DbKeyComparator::kUseQueryKeyOffset; 38 39bool 40DbKeyComparator::operator () (uint32 offset1, uint32 offset2) const 41{ 42 ReadSection rs1, rs2; 43 const ReadSection *key1, *key2; 44 45 // get the read sections to compare 46 47 if (offset1 == kUseQueryKeyOffset) 48 key1 = &mKey.mKeyData; 49 else { 50 rs1 = mKey.mTableSection.subsection(offset1); 51 key1 = &rs1; 52 } 53 54 if (offset2 == kUseQueryKeyOffset) 55 key2 = &mKey.mKeyData; 56 else { 57 rs2 = mKey.mTableSection.subsection(offset2); 58 key2 = &rs2; 59 } 60 61 // compare the values of the attributes in the keys 62 63 uint32 valueOffset1 = sizeof(uint32), valueOffset2 = sizeof(uint32); 64 65 for (uint32 i = 0; i < mKey.mNumKeyValues; i++) { 66 const MetaAttribute &metaAttribute = *mKey.mIndex.mAttributes[i]; 67 auto_ptr<DbValue> value1(metaAttribute.createValue(*key1, valueOffset1)); 68 auto_ptr<DbValue> value2(metaAttribute.createValue(*key2, valueOffset2)); 69 70 if (metaAttribute.evaluate(value1.get(), value2.get(), CSSM_DB_LESS_THAN)) 71 return true; 72 73 else if (metaAttribute.evaluate(value2.get(), value1.get(), CSSM_DB_LESS_THAN)) 74 return false; 75 } 76 77 // if we are here, the keys are equal 78 79 return false; 80} 81 82// Comparison used when inserting an item into an index, but otherwise 83// similar to the version above. 84 85bool 86DbIndexKey::operator < (const DbIndexKey &other) const 87{ 88 // compare the values of the attributes in the keys 89 90 uint32 numAttributes = (uint32) mIndex.mAttributes.size(); 91 uint32 valueOffset1 = 0, valueOffset2 = 0; 92 93 for (uint32 i = 0; i < numAttributes; i++) { 94 const MetaAttribute &metaAttribute = *mIndex.mAttributes[i]; 95 auto_ptr<DbValue> value1(metaAttribute.createValue(mKeySection.subsection(mKeyRange), 96 valueOffset1)); 97 auto_ptr<DbValue> value2(metaAttribute.createValue(other.mKeySection.subsection(other.mKeyRange), 98 valueOffset2)); 99 100 if (metaAttribute.evaluate(value1.get(), value2.get(), CSSM_DB_LESS_THAN)) 101 return true; 102 103 else if (metaAttribute.evaluate(value2.get(), value1.get(), CSSM_DB_LESS_THAN)) 104 return false; 105 } 106 107 // if we are here, the keys are equal 108 109 return false; 110} 111 112DbIndex::DbIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex) 113: mMetaRecord(metaRecord), 114 mIndexId(indexId), 115 mIsUniqueIndex(isUniqueIndex) 116{ 117} 118 119// Append an attribute to the vector used to form index keys. 120 121void 122DbIndex::appendAttribute(uint32 attributeId) 123{ 124 CSSM_DB_ATTRIBUTE_INFO info; 125 info.AttributeNameFormat = CSSM_DB_ATTRIBUTE_NAME_AS_INTEGER; 126 info.Label.AttributeID = attributeId; 127 128 mAttributes.push_back(&(mMetaRecord.metaAttribute(info))); 129} 130 131// Construct a new read-only index. 132 133DbConstIndex::DbConstIndex(const Table &table, uint32 indexId, bool isUniqueIndex) 134: DbIndex(table.getMetaRecord(), indexId, isUniqueIndex), 135 mTable(table) 136{ 137} 138 139DbConstIndex::DbConstIndex(const Table &table, const ReadSection &indexSection) 140: DbIndex(table.getMetaRecord(), indexSection.at(AtomSize), indexSection.at(2 * AtomSize)), 141 mTable(table) 142{ 143 uint32 numAttributes = indexSection.at(3 * AtomSize); 144 145 for (uint32 i = 0; i < numAttributes; i++) { 146 uint32 attributeId = indexSection.at((4 + i) * AtomSize); 147 appendAttribute(attributeId); 148 } 149 150 uint32 offset = (4 + numAttributes) * AtomSize; 151 uint32 numRecords = indexSection.at(offset); 152 offset += AtomSize; 153 mKeyOffsetVector.overlay(numRecords, 154 reinterpret_cast<const Atom *>(indexSection.range(Range(offset, numRecords * AtomSize)))); 155 156 offset += numRecords * AtomSize; 157 mRecordNumberVector.overlay(numRecords, 158 reinterpret_cast<const Atom *>(indexSection.range(Range(offset, numRecords * AtomSize)))); 159} 160 161// Check to see if this index can be used to perform a given query, based on 162// the attributes used in the query and their order. They must be a prefix 163// of the index key attributes. If there is more than one attribute, all of the 164// operators must be EQUAL and the conjunctive must be AND; this is needed to 165// ensure that the results are a contiguous segment of the index. On success, 166// the appropriate index key is generated from the query. 167 168bool 169DbConstIndex::matchesQuery(const CSSM_QUERY &query, DbQueryKey *&queryKey) const 170{ 171 uint32 numPredicates = query.NumSelectionPredicates; 172 173 if (numPredicates == 0 || numPredicates > mAttributes.size()) 174 return false; 175 176 // determine which index attributes are used in the query 177 178 auto_array<uint32> attributeUsed(mAttributes.size()); 179 for (uint32 i = 0; i < mAttributes.size(); attributeUsed[i++] = ~(uint32)0); 180 181 for (uint32 i = 0, j; i < numPredicates; i++) { 182 const MetaAttribute &tableAttribute = 183 mMetaRecord.metaAttribute(query.SelectionPredicate[i].Attribute.Info); 184 185 for (j = 0; j < mAttributes.size(); j++) { 186 if (tableAttribute.attributeId() == mAttributes[j]->attributeId()) { 187 if (attributeUsed[j] != ~(uint32)0) 188 // invalid query: attribute appears twice 189 CssmError::throwMe(CSSMERR_DL_INVALID_QUERY); 190 else { 191 // the jth index component is the ith predicate in the query 192 attributeUsed[j] = i; 193 break; 194 } 195 } 196 } 197 198 if (j == mAttributes.size()) { 199 // the predicate attribute is not in the index, so return failure 200 return false; 201 } 202 } 203 204 // check that the query predicates form a prefix of the index key, which means that 205 // the first N index components are the N query predicates in some order 206 207 long lastIndex; 208 for (lastIndex = mAttributes.size() - 1; (lastIndex >= 0) && (attributeUsed[lastIndex] == ~(uint32)0); 209 lastIndex--); 210 211 if (lastIndex != numPredicates - 1) 212 return false; 213 214 // if there is more than one predicate, the conjunctive must be AND and all the 215 // operators must be EQUAL for the compound index to be useful 216 217 CSSM_DB_OPERATOR op; 218 219 if (numPredicates > 1) { 220 if (query.Conjunctive != CSSM_DB_AND) 221 return false; 222 223 for (uint32 i = 0; i < numPredicates; i++) 224 if (query.SelectionPredicate[i].DbOperator != CSSM_DB_EQUAL) 225 return false; 226 227 op = CSSM_DB_EQUAL; 228 } 229 230 // for a single predicate, check the operator 231 232 else { 233 op = query.SelectionPredicate[0].DbOperator; 234 if (op != CSSM_DB_EQUAL && op != CSSM_DB_LESS_THAN && op != CSSM_DB_GREATER_THAN) 235 return false; 236 } 237 238 // ok, after all that, we can use this index, so generate an object used as a key 239 // for this query on this index 240 241 queryKey = new DbQueryKey(*this); 242 queryKey->mNumKeyValues = numPredicates; 243 queryKey->mOp = op; 244 245 uint32 keyLength = sizeof(uint32); 246 for (uint32 i = 0; i < numPredicates; i++) 247 mAttributes[i]->packValue(queryKey->mKeyData, keyLength, 248 *(query.SelectionPredicate[attributeUsed[i]].Attribute.Value)); 249 queryKey->mKeyData.put(0, keyLength - sizeof(uint32)); 250 queryKey->mKeyData.size(keyLength); 251 252 return true; 253} 254 255// Perform a query on an index, returning the iterators that bound the 256// returned results. 257 258void 259DbConstIndex::performQuery(const DbQueryKey &queryKey, 260 DbIndexIterator &begin, DbIndexIterator &end) const 261{ 262 DbKeyComparator cmp(queryKey); 263 264 switch (queryKey.mOp) { 265 266 case CSSM_DB_EQUAL: 267 { 268 pair<DbIndexIterator, DbIndexIterator> result; 269 result = equal_range(mKeyOffsetVector.begin(), mKeyOffsetVector.end(), 270 DbKeyComparator::kUseQueryKeyOffset, cmp); 271 begin = result.first; 272 end = result.second; 273 } 274 break; 275 276 case CSSM_DB_LESS_THAN: 277 begin = mKeyOffsetVector.begin(); 278 end = lower_bound(begin, mKeyOffsetVector.end(), 279 DbKeyComparator::kUseQueryKeyOffset, cmp); 280 break; 281 282 case CSSM_DB_GREATER_THAN: 283 end = mKeyOffsetVector.end(); 284 begin = lower_bound(mKeyOffsetVector.begin(), end, 285 DbKeyComparator::kUseQueryKeyOffset, cmp); 286 break; 287 288 default: 289 CssmError::throwMe(CSSMERR_DL_INTERNAL_ERROR); 290 break; 291 } 292} 293 294// Given an iterator as returned by performQuery(), return the read section for the record. 295 296ReadSection 297DbConstIndex::getRecordSection(DbIndexIterator iter) const 298{ 299 uint32 recordNumber = mRecordNumberVector[iter - mKeyOffsetVector.begin()]; 300 return mTable.getRecordSection(recordNumber); 301} 302 303// Construct a mutable index from a read-only index. 304 305DbMutableIndex::DbMutableIndex(const DbConstIndex &index) 306: DbIndex(index), 307 mIndexDataSize(0) 308{ 309 // go through the const index and copy all the entries into the 310 // mutable index 311 312 const ReadSection &tableSection = index.mTable.getTableSection(); 313 314 size_t numRecords = index.mKeyOffsetVector.size(); 315 for (size_t i = 0; i < numRecords; i++) { 316 uint32 recordNumber = index.mRecordNumberVector.at(i); 317 uint32 keyOffset = index.mKeyOffsetVector.at(i); 318 uint32 keySize = tableSection.at(keyOffset); 319 DbIndexKey key(tableSection, Range(keyOffset + AtomSize, keySize), *this); 320 mMap.insert(IndexMap::value_type(key, recordNumber)); 321 } 322} 323 324DbMutableIndex::DbMutableIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex) 325: DbIndex(metaRecord, indexId, isUniqueIndex), 326 mIndexDataSize(0) 327{ 328} 329 330DbMutableIndex::~DbMutableIndex() 331{ 332} 333 334// Remove all entries for a record from an index. This is not an ideal implementation, 335// since it walks the entire index. In a perfect world, we'd generate all the record's 336// keys and lookup matching entries, deleting only those with the correct record number. 337// But this is not a perfect world. 338 339void 340DbMutableIndex::removeRecord(uint32 recordNumber) 341{ 342 IndexMap::iterator it, temp; 343 for (it = mMap.begin(); it != mMap.end(); ) { 344 temp = it; it++; 345 if (temp->second == recordNumber) 346 mMap.erase(temp); 347 } 348} 349 350// Insert a record into an index. 351 352void 353DbMutableIndex::insertRecord(uint32 recordNumber, const ReadSection &packedRecord) 354{ 355 // The common case is that each indexed attribute has a single value in 356 // the record; detect and handle this separately since we can avoid an 357 // expensive recursive technique. 358 359 size_t numAttributes = mAttributes.size(); 360 bool allSingleValued = true; 361 362 for (size_t i = 0; i < numAttributes; i++) { 363 uint32 numValues = mAttributes[i]->getNumberOfValues(packedRecord); 364 if (numValues == 0) { 365 // record does not have value required by index; for a unique index, 366 // this is an error, otherwise just don't index the record 367 if (mIsUniqueIndex) 368 CssmError::throwMe(CSSMERR_DL_MISSING_VALUE); 369 else 370 return; 371 } 372 else if (numValues > 1) { 373 allSingleValued = false; 374 break; 375 } 376 } 377 378 if (allSingleValued) 379 insertRecordSingle(recordNumber, packedRecord); 380 381 else { 382 // recursively build all appropriate index keys, and add them to the map 383 WriteSection keyData; 384 insertRecordMulti(recordNumber, packedRecord, 0, keyData, 0); 385 } 386} 387 388void 389DbMutableIndex::insertRecordSingle(uint32 recordNumber, const ReadSection &packedRecord) 390{ 391 // append the key values to the index data 392 uint32 offset = mIndexDataSize; 393 for (uint32 i = 0; i < mAttributes.size(); i++) 394 mAttributes[i]->copyValueBytes(0, packedRecord, mIndexData, mIndexDataSize); 395 mIndexData.size(mIndexDataSize); 396 397 // make an index key 398 DbIndexKey key(mIndexData, Range(offset, mIndexDataSize - offset), *this); 399 400 // if this is a unique index, check for a record with the same key 401 if (mIsUniqueIndex && (mMap.find(key) != mMap.end())) 402 // the key already exists, which is an error 403 CssmError::throwMe(CSSMERR_DL_INVALID_UNIQUE_INDEX_DATA); 404 405 // insert the item into the map 406 mMap.insert(IndexMap::value_type(key, recordNumber)); 407} 408 409void 410DbMutableIndex::insertRecordMulti(uint32 recordNumber, const ReadSection &packedRecord, 411 uint32 attributeIndex, WriteSection &keyData, uint32 keySize) 412{ 413 const MetaAttribute &metaAttribute = *(mAttributes[attributeIndex]); 414 uint32 numValues = metaAttribute.getNumberOfValues(packedRecord); 415 416 for (uint32 i = 0; i < numValues; i++) { 417 418 uint32 newKeySize = keySize; 419 metaAttribute.copyValueBytes(i, packedRecord, keyData, newKeySize); 420 421 if (attributeIndex + 1 == mAttributes.size()) { 422 uint32 offset = mIndexDataSize; 423 mIndexDataSize = mIndexData.put(mIndexDataSize, newKeySize, keyData.address()); 424 mIndexData.size(mIndexDataSize); 425 426 DbIndexKey key(mIndexData, Range(offset, mIndexDataSize - offset), *this); 427 if (mIsUniqueIndex && (mMap.find(key) != mMap.end())) 428 CssmError::throwMe(CSSMERR_DL_INVALID_UNIQUE_INDEX_DATA); 429 430 mMap.insert(IndexMap::value_type(key, recordNumber)); 431 } 432 else 433 // otherwise, recurse with the rest of the attributes 434 insertRecordMulti(recordNumber, packedRecord, attributeIndex + 1, keyData, newKeySize); 435 } 436} 437 438uint32 439DbMutableIndex::writeIndex(WriteSection &ws, uint32 offset) 440{ 441 IndexMap::iterator it; 442 443 // reserve space for the index size 444 uint32 sizeOffset = offset; 445 offset += AtomSize; 446 447 offset = ws.put(offset, mIndexId); 448 offset = ws.put(offset, mIsUniqueIndex ? 1 : 0); 449 450 offset = ws.put(offset, (uint32)mAttributes.size()); 451 for (uint32 i = 0; i < mAttributes.size(); i++) 452 offset = ws.put(offset, mAttributes[i]->attributeId()); 453 454 offset = ws.put(offset, (uint32)mMap.size()); 455 456 // reserve space for the array of offsets to key data 457 uint32 keyPtrOffset = offset; 458 offset += AtomSize * mMap.size(); 459 460 // write the array of record numbers 461 for (it = mMap.begin(); it != mMap.end(); it++) { 462 offset = ws.put(offset, it->second); 463 } 464 465 // write the key data 466 for (it = mMap.begin(); it != mMap.end(); it++) { 467 keyPtrOffset = ws.put(keyPtrOffset, offset); 468 offset = ws.put(offset, it->first.keySize()); 469 offset = ws.put(offset, it->first.keySize(), it->first.keyData()); 470 } 471 472 // write the index size 473 ws.put(sizeOffset, offset - sizeOffset); 474 475 return offset; 476} 477