X-Git-Url: https://git.saurik.com/apple/security.git/blobdiff_plain/80e2389990082500d76eb566d4946be3e786c3ef..d8f41ccd20de16f8ebe2ccc84d47bf1cb2b26bbb:/libsecurity_filedb/lib/DbIndex.cpp diff --git a/libsecurity_filedb/lib/DbIndex.cpp b/libsecurity_filedb/lib/DbIndex.cpp deleted file mode 100644 index d31a8775..00000000 --- a/libsecurity_filedb/lib/DbIndex.cpp +++ /dev/null @@ -1,476 +0,0 @@ -/* - * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved. - * - * The contents of this file constitute Original Code as defined in and are - * subject to the Apple Public Source License Version 1.2 (the 'License'). - * You may not use this file except in compliance with the License. Please obtain - * a copy of the License at http://www.apple.com/publicsource and read it before - * using this file. - * - * This Original Code and all software distributed under the License are - * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS - * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT - * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR - * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the - * specific language governing rights and limitations under the License. - */ - - -// -// DbIndex.cpp -// - -#include "DbIndex.h" -#include "AppleDatabase.h" -#include - -DbQueryKey::DbQueryKey(const DbConstIndex &index) -: mIndex(index), - mTableSection(index.table().getTableSection()) -{ -} - -// Perform a less-than comparison between two keys. An offset of -// kUseQueryKeyOffset means to use the key provided as part of the -// query; otherwise, the key comes from the database. - -const uint32 DbKeyComparator::kUseQueryKeyOffset; - -bool -DbKeyComparator::operator () (uint32 offset1, uint32 offset2) const -{ - ReadSection rs1, rs2; - const ReadSection *key1, *key2; - - // get the read sections to compare - - if (offset1 == kUseQueryKeyOffset) - key1 = &mKey.mKeyData; - else { - rs1 = mKey.mTableSection.subsection(offset1); - key1 = &rs1; - } - - if (offset2 == kUseQueryKeyOffset) - key2 = &mKey.mKeyData; - else { - rs2 = mKey.mTableSection.subsection(offset2); - key2 = &rs2; - } - - // compare the values of the attributes in the keys - - uint32 valueOffset1 = sizeof(uint32), valueOffset2 = sizeof(uint32); - - for (uint32 i = 0; i < mKey.mNumKeyValues; i++) { - const MetaAttribute &metaAttribute = *mKey.mIndex.mAttributes[i]; - auto_ptr value1(metaAttribute.createValue(*key1, valueOffset1)); - auto_ptr value2(metaAttribute.createValue(*key2, valueOffset2)); - - if (metaAttribute.evaluate(value1.get(), value2.get(), CSSM_DB_LESS_THAN)) - return true; - - else if (metaAttribute.evaluate(value2.get(), value1.get(), CSSM_DB_LESS_THAN)) - return false; - } - - // if we are here, the keys are equal - - return false; -} - -// Comparison used when inserting an item into an index, but otherwise -// similar to the version above. - -bool -DbIndexKey::operator < (const DbIndexKey &other) const -{ - // compare the values of the attributes in the keys - - uint32 numAttributes = (uint32) mIndex.mAttributes.size(); - uint32 valueOffset1 = 0, valueOffset2 = 0; - - for (uint32 i = 0; i < numAttributes; i++) { - const MetaAttribute &metaAttribute = *mIndex.mAttributes[i]; - auto_ptr value1(metaAttribute.createValue(mKeySection.subsection(mKeyRange), - valueOffset1)); - auto_ptr value2(metaAttribute.createValue(other.mKeySection.subsection(other.mKeyRange), - valueOffset2)); - - if (metaAttribute.evaluate(value1.get(), value2.get(), CSSM_DB_LESS_THAN)) - return true; - - else if (metaAttribute.evaluate(value2.get(), value1.get(), CSSM_DB_LESS_THAN)) - return false; - } - - // if we are here, the keys are equal - - return false; -} - -DbIndex::DbIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex) -: mMetaRecord(metaRecord), - mIndexId(indexId), - mIsUniqueIndex(isUniqueIndex) -{ -} - -// Append an attribute to the vector used to form index keys. - -void -DbIndex::appendAttribute(uint32 attributeId) -{ - CSSM_DB_ATTRIBUTE_INFO info; - info.AttributeNameFormat = CSSM_DB_ATTRIBUTE_NAME_AS_INTEGER; - info.Label.AttributeID = attributeId; - - mAttributes.push_back(&(mMetaRecord.metaAttribute(info))); -} - -// Construct a new read-only index. - -DbConstIndex::DbConstIndex(const Table &table, uint32 indexId, bool isUniqueIndex) -: DbIndex(table.getMetaRecord(), indexId, isUniqueIndex), - mTable(table) -{ -} - -DbConstIndex::DbConstIndex(const Table &table, const ReadSection &indexSection) -: DbIndex(table.getMetaRecord(), indexSection.at(AtomSize), indexSection.at(2 * AtomSize)), - mTable(table) -{ - uint32 numAttributes = indexSection.at(3 * AtomSize); - - for (uint32 i = 0; i < numAttributes; i++) { - uint32 attributeId = indexSection.at((4 + i) * AtomSize); - appendAttribute(attributeId); - } - - uint32 offset = (4 + numAttributes) * AtomSize; - uint32 numRecords = indexSection.at(offset); - offset += AtomSize; - mKeyOffsetVector.overlay(numRecords, - reinterpret_cast(indexSection.range(Range(offset, numRecords * AtomSize)))); - - offset += numRecords * AtomSize; - mRecordNumberVector.overlay(numRecords, - reinterpret_cast(indexSection.range(Range(offset, numRecords * AtomSize)))); -} - -// Check to see if this index can be used to perform a given query, based on -// the attributes used in the query and their order. They must be a prefix -// of the index key attributes. If there is more than one attribute, all of the -// operators must be EQUAL and the conjunctive must be AND; this is needed to -// ensure that the results are a contiguous segment of the index. On success, -// the appropriate index key is generated from the query. - -bool -DbConstIndex::matchesQuery(const CSSM_QUERY &query, DbQueryKey *&queryKey) const -{ - uint32 numPredicates = query.NumSelectionPredicates; - - if (numPredicates == 0 || numPredicates > mAttributes.size()) - return false; - - // determine which index attributes are used in the query - - auto_array attributeUsed(mAttributes.size()); - for (uint32 i = 0; i < mAttributes.size(); attributeUsed[i++] = ~(uint32)0); - - for (uint32 i = 0, j; i < numPredicates; i++) { - const MetaAttribute &tableAttribute = - mMetaRecord.metaAttribute(query.SelectionPredicate[i].Attribute.Info); - - for (j = 0; j < mAttributes.size(); j++) { - if (tableAttribute.attributeId() == mAttributes[j]->attributeId()) { - if (attributeUsed[j] != ~(uint32)0) - // invalid query: attribute appears twice - CssmError::throwMe(CSSMERR_DL_INVALID_QUERY); - else { - // the jth index component is the ith predicate in the query - attributeUsed[j] = i; - break; - } - } - } - - if (j == mAttributes.size()) { - // the predicate attribute is not in the index, so return failure - return false; - } - } - - // check that the query predicates form a prefix of the index key, which means that - // the first N index components are the N query predicates in some order - - long lastIndex; - for (lastIndex = mAttributes.size() - 1; (lastIndex >= 0) && (attributeUsed[lastIndex] == ~(uint32)0); - lastIndex--); - - if (lastIndex != numPredicates - 1) - return false; - - // if there is more than one predicate, the conjunctive must be AND and all the - // operators must be EQUAL for the compound index to be useful - - CSSM_DB_OPERATOR op; - - if (numPredicates > 1) { - if (query.Conjunctive != CSSM_DB_AND) - return false; - - for (uint32 i = 0; i < numPredicates; i++) - if (query.SelectionPredicate[i].DbOperator != CSSM_DB_EQUAL) - return false; - - op = CSSM_DB_EQUAL; - } - - // for a single predicate, check the operator - - else { - op = query.SelectionPredicate[0].DbOperator; - if (op != CSSM_DB_EQUAL && op != CSSM_DB_LESS_THAN && op != CSSM_DB_GREATER_THAN) - return false; - } - - // ok, after all that, we can use this index, so generate an object used as a key - // for this query on this index - - queryKey = new DbQueryKey(*this); - queryKey->mNumKeyValues = numPredicates; - queryKey->mOp = op; - - uint32 keyLength = sizeof(uint32); - for (uint32 i = 0; i < numPredicates; i++) - mAttributes[i]->packValue(queryKey->mKeyData, keyLength, - *(query.SelectionPredicate[attributeUsed[i]].Attribute.Value)); - queryKey->mKeyData.put(0, keyLength - sizeof(uint32)); - queryKey->mKeyData.size(keyLength); - - return true; -} - -// Perform a query on an index, returning the iterators that bound the -// returned results. - -void -DbConstIndex::performQuery(const DbQueryKey &queryKey, - DbIndexIterator &begin, DbIndexIterator &end) const -{ - DbKeyComparator cmp(queryKey); - - switch (queryKey.mOp) { - - case CSSM_DB_EQUAL: - { - pair result; - result = equal_range(mKeyOffsetVector.begin(), mKeyOffsetVector.end(), - DbKeyComparator::kUseQueryKeyOffset, cmp); - begin = result.first; - end = result.second; - } - break; - - case CSSM_DB_LESS_THAN: - begin = mKeyOffsetVector.begin(); - end = lower_bound(begin, mKeyOffsetVector.end(), - DbKeyComparator::kUseQueryKeyOffset, cmp); - break; - - case CSSM_DB_GREATER_THAN: - end = mKeyOffsetVector.end(); - begin = lower_bound(mKeyOffsetVector.begin(), end, - DbKeyComparator::kUseQueryKeyOffset, cmp); - break; - - default: - CssmError::throwMe(CSSMERR_DL_INTERNAL_ERROR); - break; - } -} - -// Given an iterator as returned by performQuery(), return the read section for the record. - -ReadSection -DbConstIndex::getRecordSection(DbIndexIterator iter) const -{ - uint32 recordNumber = mRecordNumberVector[iter - mKeyOffsetVector.begin()]; - return mTable.getRecordSection(recordNumber); -} - -// Construct a mutable index from a read-only index. - -DbMutableIndex::DbMutableIndex(const DbConstIndex &index) -: DbIndex(index), - mIndexDataSize(0) -{ - // go through the const index and copy all the entries into the - // mutable index - - const ReadSection &tableSection = index.mTable.getTableSection(); - - size_t numRecords = index.mKeyOffsetVector.size(); - for (size_t i = 0; i < numRecords; i++) { - uint32 recordNumber = index.mRecordNumberVector.at(i); - uint32 keyOffset = index.mKeyOffsetVector.at(i); - uint32 keySize = tableSection.at(keyOffset); - DbIndexKey key(tableSection, Range(keyOffset + AtomSize, keySize), *this); - mMap.insert(IndexMap::value_type(key, recordNumber)); - } -} - -DbMutableIndex::DbMutableIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex) -: DbIndex(metaRecord, indexId, isUniqueIndex), - mIndexDataSize(0) -{ -} - -DbMutableIndex::~DbMutableIndex() -{ -} - -// Remove all entries for a record from an index. This is not an ideal implementation, -// since it walks the entire index. In a perfect world, we'd generate all the record's -// keys and lookup matching entries, deleting only those with the correct record number. -// But this is not a perfect world. - -void -DbMutableIndex::removeRecord(uint32 recordNumber) -{ - IndexMap::iterator it, temp; - for (it = mMap.begin(); it != mMap.end(); ) { - temp = it; it++; - if (temp->second == recordNumber) - mMap.erase(temp); - } -} - -// Insert a record into an index. - -void -DbMutableIndex::insertRecord(uint32 recordNumber, const ReadSection &packedRecord) -{ - // The common case is that each indexed attribute has a single value in - // the record; detect and handle this separately since we can avoid an - // expensive recursive technique. - - size_t numAttributes = mAttributes.size(); - bool allSingleValued = true; - - for (size_t i = 0; i < numAttributes; i++) { - uint32 numValues = mAttributes[i]->getNumberOfValues(packedRecord); - if (numValues == 0) { - // record does not have value required by index; for a unique index, - // this is an error, otherwise just don't index the record - if (mIsUniqueIndex) - CssmError::throwMe(CSSMERR_DL_MISSING_VALUE); - else - return; - } - else if (numValues > 1) { - allSingleValued = false; - break; - } - } - - if (allSingleValued) - insertRecordSingle(recordNumber, packedRecord); - - else { - // recursively build all appropriate index keys, and add them to the map - WriteSection keyData; - insertRecordMulti(recordNumber, packedRecord, 0, keyData, 0); - } -} - -void -DbMutableIndex::insertRecordSingle(uint32 recordNumber, const ReadSection &packedRecord) -{ - // append the key values to the index data - uint32 offset = mIndexDataSize; - for (uint32 i = 0; i < mAttributes.size(); i++) - mAttributes[i]->copyValueBytes(0, packedRecord, mIndexData, mIndexDataSize); - mIndexData.size(mIndexDataSize); - - // make an index key - DbIndexKey key(mIndexData, Range(offset, mIndexDataSize - offset), *this); - - // if this is a unique index, check for a record with the same key - if (mIsUniqueIndex && (mMap.find(key) != mMap.end())) - // the key already exists, which is an error - CssmError::throwMe(CSSMERR_DL_INVALID_UNIQUE_INDEX_DATA); - - // insert the item into the map - mMap.insert(IndexMap::value_type(key, recordNumber)); -} - -void -DbMutableIndex::insertRecordMulti(uint32 recordNumber, const ReadSection &packedRecord, - uint32 attributeIndex, WriteSection &keyData, uint32 keySize) -{ - const MetaAttribute &metaAttribute = *(mAttributes[attributeIndex]); - uint32 numValues = metaAttribute.getNumberOfValues(packedRecord); - - for (uint32 i = 0; i < numValues; i++) { - - uint32 newKeySize = keySize; - metaAttribute.copyValueBytes(i, packedRecord, keyData, newKeySize); - - if (attributeIndex + 1 == mAttributes.size()) { - uint32 offset = mIndexDataSize; - mIndexDataSize = mIndexData.put(mIndexDataSize, newKeySize, keyData.address()); - mIndexData.size(mIndexDataSize); - - DbIndexKey key(mIndexData, Range(offset, mIndexDataSize - offset), *this); - if (mIsUniqueIndex && (mMap.find(key) != mMap.end())) - CssmError::throwMe(CSSMERR_DL_INVALID_UNIQUE_INDEX_DATA); - - mMap.insert(IndexMap::value_type(key, recordNumber)); - } - else - // otherwise, recurse with the rest of the attributes - insertRecordMulti(recordNumber, packedRecord, attributeIndex + 1, keyData, newKeySize); - } -} - -uint32 -DbMutableIndex::writeIndex(WriteSection &ws, uint32 offset) -{ - IndexMap::iterator it; - - // reserve space for the index size - uint32 sizeOffset = offset; - offset += AtomSize; - - offset = ws.put(offset, mIndexId); - offset = ws.put(offset, mIsUniqueIndex ? 1 : 0); - - offset = ws.put(offset, (uint32)mAttributes.size()); - for (uint32 i = 0; i < mAttributes.size(); i++) - offset = ws.put(offset, mAttributes[i]->attributeId()); - - offset = ws.put(offset, (uint32)mMap.size()); - - // reserve space for the array of offsets to key data - uint32 keyPtrOffset = offset; - offset += AtomSize * mMap.size(); - - // write the array of record numbers - for (it = mMap.begin(); it != mMap.end(); it++) { - offset = ws.put(offset, it->second); - } - - // write the key data - for (it = mMap.begin(); it != mMap.end(); it++) { - keyPtrOffset = ws.put(keyPtrOffset, offset); - offset = ws.put(offset, it->first.keySize()); - offset = ws.put(offset, it->first.keySize(), it->first.keyData()); - } - - // write the index size - ws.put(sizeOffset, offset - sizeOffset); - - return offset; -}