--- /dev/null
+/*
+ * Copyright (c) 2000-2001,2011-2012,2014 Apple 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 <stdio.h>
+
+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<DbValue> value1(metaAttribute.createValue(*key1, valueOffset1));
+ auto_ptr<DbValue> 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<DbValue> value1(metaAttribute.createValue(mKeySection.subsection(mKeyRange),
+ valueOffset1));
+ auto_ptr<DbValue> 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<const Atom *>(indexSection.range(Range(offset, numRecords * AtomSize))));
+
+ offset += numRecords * AtomSize;
+ mRecordNumberVector.overlay(numRecords,
+ reinterpret_cast<const Atom *>(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<uint32> 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<DbIndexIterator, DbIndexIterator> 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;
+}
projects / apple / security.git / blobdiff