X-Git-Url: https://git.saurik.com/apple/security.git/blobdiff_plain/80e2389990082500d76eb566d4946be3e786c3ef..d8f41ccd20de16f8ebe2ccc84d47bf1cb2b26bbb:/Security/libsecurity_filedb/lib/DbIndex.h?ds=inline

diff --git a/Security/libsecurity_filedb/lib/DbIndex.h b/Security/libsecurity_filedb/lib/DbIndex.h
new file mode 100644
index 00000000..d178b26d
--- /dev/null
+++ b/Security/libsecurity_filedb/lib/DbIndex.h
@@ -0,0 +1,198 @@
+/*
+ * Copyright (c) 2000-2001,2011,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.h
+//
+
+#ifndef _H_APPLEDL_DBINDEX
+#define _H_APPLEDL_DBINDEX
+
+#include "MetaRecord.h"
+
+namespace Security
+{
+
+class Table;
+class DbConstIndex;
+class DbIndex;
+
+typedef constVector<Atom> DbOffsetVector;
+
+typedef DbOffsetVector::const_iterator DbIndexIterator;
+
+//
+// An object that represents a key being used as part of a query.
+//
+
+class DbQueryKey
+{
+	friend class DbConstIndex;
+	friend class DbKeyComparator;
+	
+public:
+	DbQueryKey(const DbConstIndex &index);
+	
+private:
+	WriteSection mKeyData;
+	uint32 mNumKeyValues;
+	const DbConstIndex &mIndex;
+	const ReadSection &mTableSection;
+	CSSM_DB_OPERATOR mOp;
+};
+
+//
+// An object which performs comparison between keys, either stored
+// in a database or provided as part of a query.
+//
+
+class DbKeyComparator
+{
+public:
+	DbKeyComparator(const DbQueryKey &key) : mKey(key) {}
+
+	bool operator () (uint32 keyOffset1, uint32 keyOffset2) const;
+
+	// Pass this value as an argument to
+	// operator()(uint32,uint32) to compare against mKey.
+	static const uint32 kUseQueryKeyOffset = 0;
+
+private:
+	const DbQueryKey &mKey;
+};
+
+//
+// A key as stored in an index.
+//
+
+class DbIndexKey {
+public:
+	DbIndexKey(const ReadSection &key, const Range &keyRange, const DbIndex &index)
+		: mKeySection(key), mKeyRange(keyRange), mIndex(index) {}
+
+	bool operator < (const DbIndexKey &other) const;
+	
+	uint32 keySize() const { return mKeyRange.mSize; }
+	const uint8 *keyData() const { return mKeySection.range(mKeyRange); }
+	
+private:
+	// the key data, expressed as a subsection of a read section
+	const ReadSection &mKeySection;
+	Range mKeyRange;
+	
+	// the index that knows how to interpret the key data
+	const DbIndex &mIndex;
+};
+
+// Base class containing stuff shared between const and mutable indexes.
+
+class DbIndex
+{
+	friend class DbIndexKey;
+	
+public:
+	uint32 indexId() const { return mIndexId; }
+
+	// append an attribute to the index key
+	void appendAttribute(uint32 attributeId);
+
+protected:
+	DbIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex);
+
+	// meta record for table associated with this index
+	const MetaRecord &mMetaRecord;
+
+	// vector of indexed attributes
+	typedef vector<const MetaAttribute *> AttributeVector;
+	AttributeVector mAttributes;
+	
+	uint32 mIndexId;
+	bool mIsUniqueIndex;
+};
+
+// Read-only index.
+
+class DbConstIndex : public DbIndex
+{
+	friend class DbMutableIndex;
+	friend class DbQueryKey;
+	friend class DbKeyComparator;
+
+public:
+	DbConstIndex(const Table &table, uint32 indexId, bool isUniqueIndex);
+	DbConstIndex(const Table &table, const ReadSection &indexSection);
+	
+	const Table &table() const { return mTable; }
+
+	// check if this index can be used for a given query, and if so, generate
+	// the appropriate index key from the query
+	bool matchesQuery(const CSSM_QUERY &query, DbQueryKey *&queryKey) const;
+
+	// perform a query on the index
+	void performQuery(const DbQueryKey &queryKey,
+		DbIndexIterator &begin, DbIndexIterator &end) const;
+		
+	// given an iterator as returned by performQuery(), return the read section for the record
+	ReadSection getRecordSection(DbIndexIterator iter) const;
+
+private:
+	// sorted vector of offsets to index key data
+	DbOffsetVector mKeyOffsetVector;
+	
+	// vector, in same order as key vector, of corresponding record numbers
+	DbOffsetVector mRecordNumberVector;
+
+	const Table &mTable;
+};
+
+// A memory-resident index that can be modified, but not used for a query.
+
+class DbMutableIndex : public DbIndex
+{
+public:
+	DbMutableIndex(const DbConstIndex &index);
+	DbMutableIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex);
+	~DbMutableIndex();
+	
+	// insert a record into the index
+	void insertRecord(uint32 recordNumber, const ReadSection &packedRecord);
+	
+	// remove a record from the index
+	void removeRecord(uint32 recordNumber);
+	
+	// write the index
+	uint32 writeIndex(WriteSection &ws, uint32 offset);
+	
+private:
+	// helper methods called by insertRecord()
+	void insertRecordSingle(uint32 recordOffset, const ReadSection &packedRecord);
+	void insertRecordMulti(uint32 recordOffset, const ReadSection &packedRecord,
+		uint32 attributeIndex, WriteSection &keyData, uint32 keySize);
+
+	// a single write section which stores generated index key data
+	WriteSection mIndexData;
+	uint32 mIndexDataSize;
+	
+	// a map from index keys to record numbers
+	typedef multimap<DbIndexKey, uint32> IndexMap;
+	IndexMap mMap;
+};
+
+} // end namespace Security
+
+#endif // _H_APPLEDL_DBINDEX