libsecurity_filedb/lib/DbIndex.cpp

/*
 * 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;
}