1/*
2 * Copyright (c) 2000-2001,2011,2014 Apple 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.h
21//
22
23#ifndef _H_APPLEDL_DBINDEX
24#define _H_APPLEDL_DBINDEX
25
26#include "MetaRecord.h"
27
28namespace Security
29{
30
31class Table;
32class DbConstIndex;
33class DbIndex;
34
35typedef constVector<Atom> DbOffsetVector;
36
37typedef DbOffsetVector::const_iterator DbIndexIterator;
38
39//
40// An object that represents a key being used as part of a query.
41//
42
43class DbQueryKey
44{
45	friend class DbConstIndex;
46	friend class DbKeyComparator;
47
48public:
49	DbQueryKey(const DbConstIndex &index);
50
51private:
52	WriteSection mKeyData;
53	uint32 mNumKeyValues;
54	const DbConstIndex &mIndex;
55	const ReadSection &mTableSection;
56	CSSM_DB_OPERATOR mOp;
57};
58
59//
60// An object which performs comparison between keys, either stored
61// in a database or provided as part of a query.
62//
63
64class DbKeyComparator
65{
66public:
67	DbKeyComparator(const DbQueryKey &key) : mKey(key) {}
68
69	bool operator () (uint32 keyOffset1, uint32 keyOffset2) const;
70
71	// Pass this value as an argument to
72	// operator()(uint32,uint32) to compare against mKey.
73	static const uint32 kUseQueryKeyOffset = 0;
74
75private:
76	const DbQueryKey &mKey;
77};
78
79//
80// A key as stored in an index.
81//
82
83class DbIndexKey {
84public:
85	DbIndexKey(const ReadSection &key, const Range &keyRange, const DbIndex &index)
86		: mKeySection(key), mKeyRange(keyRange), mIndex(index) {}
87
88	bool operator < (const DbIndexKey &other) const;
89
90	uint32 keySize() const { return mKeyRange.mSize; }
91	const uint8 *keyData() const { return mKeySection.range(mKeyRange); }
92
93private:
94	// the key data, expressed as a subsection of a read section
95	const ReadSection &mKeySection;
96	Range mKeyRange;
97
98	// the index that knows how to interpret the key data
99	const DbIndex &mIndex;
100};
101
102// Base class containing stuff shared between const and mutable indexes.
103
104class DbIndex
105{
106	friend class DbIndexKey;
107
108public:
109	uint32 indexId() const { return mIndexId; }
110
111	// append an attribute to the index key
112	void appendAttribute(uint32 attributeId);
113
114protected:
115	DbIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex);
116
117	// meta record for table associated with this index
118	const MetaRecord &mMetaRecord;
119
120	// vector of indexed attributes
121	typedef vector<const MetaAttribute *> AttributeVector;
122	AttributeVector mAttributes;
123
124	uint32 mIndexId;
125	bool mIsUniqueIndex;
126};
127
128// Read-only index.
129
130class DbConstIndex : public DbIndex
131{
132	friend class DbMutableIndex;
133	friend class DbQueryKey;
134	friend class DbKeyComparator;
135
136public:
137	DbConstIndex(const Table &table, uint32 indexId, bool isUniqueIndex);
138	DbConstIndex(const Table &table, const ReadSection &indexSection);
139
140	const Table &table() const { return mTable; }
141
142	// check if this index can be used for a given query, and if so, generate
143	// the appropriate index key from the query
144	bool matchesQuery(const CSSM_QUERY &query, DbQueryKey *&queryKey) const;
145
146	// perform a query on the index
147	void performQuery(const DbQueryKey &queryKey,
148		DbIndexIterator &begin, DbIndexIterator &end) const;
149
150	// given an iterator as returned by performQuery(), return the read section for the record
151	ReadSection getRecordSection(DbIndexIterator iter) const;
152
153private:
154	// sorted vector of offsets to index key data
155	DbOffsetVector mKeyOffsetVector;
156
157	// vector, in same order as key vector, of corresponding record numbers
158	DbOffsetVector mRecordNumberVector;
159
160	const Table &mTable;
161};
162
163// A memory-resident index that can be modified, but not used for a query.
164
165class DbMutableIndex : public DbIndex
166{
167public:
168	DbMutableIndex(const DbConstIndex &index);
169	DbMutableIndex(const MetaRecord &metaRecord, uint32 indexId, bool isUniqueIndex);
170	~DbMutableIndex();
171
172	// insert a record into the index
173	void insertRecord(uint32 recordNumber, const ReadSection &packedRecord);
174
175	// remove a record from the index
176	void removeRecord(uint32 recordNumber);
177
178	// write the index
179	uint32 writeIndex(WriteSection &ws, uint32 offset);
180
181private:
182	// helper methods called by insertRecord()
183	void insertRecordSingle(uint32 recordOffset, const ReadSection &packedRecord);
184	void insertRecordMulti(uint32 recordOffset, const ReadSection &packedRecord,
185		uint32 attributeIndex, WriteSection &keyData, uint32 keySize);
186
187	// a single write section which stores generated index key data
188	WriteSection mIndexData;
189	uint32 mIndexDataSize;
190
191	// a map from index keys to record numbers
192	typedef multimap<DbIndexKey, uint32> IndexMap;
193	IndexMap mMap;
194};
195
196} // end namespace Security
197
198#endif // _H_APPLEDL_DBINDEX
199