OSX/libsecurity_filedb/lib/DbIndex.h

   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
  28 namespace Security
  29 {
  30
  31 class Table;
  32 class DbConstIndex;
  33 class DbIndex;
  34
  35 typedef constVector<Atom> DbOffsetVector;
  36
  37 typedef DbOffsetVector::const_iterator DbIndexIterator;
  38
  39 //
  40 // An object that represents a key being used as part of a query.
  41 //
  42
  43 class DbQueryKey
  44 {
  45         friend class DbConstIndex;
  46         friend class DbKeyComparator;
  47
  48 public:
  49         DbQueryKey(const DbConstIndex &index);
  50
  51 private:
  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
  64 class DbKeyComparator
  65 {
  66 public:
  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
  75 private:
  76         const DbQueryKey &mKey;
  77 };
  78
  79 //
  80 // A key as stored in an index.
  81 //
  82
  83 class DbIndexKey {
  84 public:
  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
  93 private:
  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
 104 class DbIndex
 105 {
 106         friend class DbIndexKey;
 107
 108 public:
 109         uint32 indexId() const { return mIndexId; }
 110
 111         // append an attribute to the index key
 112         void appendAttribute(uint32 attributeId);
 113
 114 protected:
 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
 130 class DbConstIndex : public DbIndex
 131 {
 132         friend class DbMutableIndex;
 133         friend class DbQueryKey;
 134         friend class DbKeyComparator;
 135
 136 public:
 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
 153 private:
 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
 165 class DbMutableIndex : public DbIndex
 166 {
 167 public:
 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
 181 private:
 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