cdsa/cdsa_utilities/DbIndex.h

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