text: /*
   * 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
  