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