cdsa/cdsa_utilities/DbIndex.cpp

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