text: /**
   *    Copyright (C) 2012 10gen Inc.
   *
   *    This program is free software: you can redistribute it and/or  modify
   *    it under the terms of the GNU Affero General Public License, version 3,
   *    as published by the Free Software Foundation.
   *
   *    This program is distributed in the hope that it will be useful,
   *    but WITHOUT ANY WARRANTY; without even the implied warranty of
   *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *    GNU Affero General Public License for more details.
   *
   *    You should have received a copy of the GNU Affero General Public License
   *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
   *
   *    As a special exception, the copyright holders give permission to link the
   *    code of portions of this program with the OpenSSL library under certain
   *    conditions as described in each individual source file and distribute
   *    linked combinations including the program with the OpenSSL library. You
   *    must comply with the GNU Affero General Public License in all respects
   *    for all of the code used other than as permitted herein. If you modify
   *    file(s) with this exception, you may extend this exception to your
   *    version of the file(s), but you are not obligated to do so. If you do not
   *    wish to do so, delete this exception statement from your version. If you
   *    delete this exception statement from all source files in the program,
   *    then also delete it in the license file.
   */
  
  #pragma once
  
  
  #include "mongo/base/disallow_copying.h"
  #include "mongo/base/owned_pointer_vector.h"
  #include "mongo/db/field_ref_set.h"
  #include "mongo/db/jsobj.h"
  #include "mongo/db/range_arithmetic.h"
  #include "mongo/s/catalog/type_chunk.h"
  #include "mongo/s/chunk_version.h"
  
  namespace mongo {
  
      class MetadataLoader;
      class CollectionMetadata;
  
      typedef std::shared_ptr<const CollectionMetadata> CollectionMetadataPtr;
  
      /**
       * The collection metadata has metadata information about a collection, in particular the
       * sharding information. It's main goal in life is to be capable of answering if a certain
       * document belongs to it or not. (In some scenarios such as chunk migration, a given
       * document is in a shard but cannot be accessed.)
       *
       * To build a collection from config data, please check the MetadataLoader. The methods
       * here allow building a new incarnation of a collection's metadata based on an existing
       * one (e.g, we're splitting in a given collection.).
       *
       * This class is immutable once constructed.
       */
      class CollectionMetadata {
          MONGO_DISALLOW_COPYING(CollectionMetadata);
      public:
  
          ~CollectionMetadata();
  
          //
          // cloning support
          //
  
          /**
           * Returns a new metadata's instance based on 'this's state by removing a 'pending' chunk.
           *
           * The shard and collection version of the new metadata are unaffected.  The caller owns the
           * new metadata.
           *
           * If a new metadata can't be created, returns NULL and fills in 'errMsg', if it was
           * provided.
           */
          CollectionMetadata* cloneMinusPending( const ChunkType& pending, std::string* errMsg ) const;
  
          /**
           * Returns a new metadata's instance based on 'this's state by adding a 'pending' chunk.
           *
           * The shard and collection version of the new metadata are unaffected.  The caller owns the
           * new metadata.
           *
           * If a new metadata can't be created, returns NULL and fills in 'errMsg', if it was
           * provided.
           */
          CollectionMetadata* clonePlusPending( const ChunkType& pending, std::string* errMsg ) const;
  
          /**
           * Returns a new metadata's instance based on 'this's state by removing 'chunk'.
           * When cloning away the last chunk, 'newShardVersion' must be zero. In any case,
           * the caller owns the new metadata when the cloning is successful.
           *
           * If a new metadata can't be created, returns NULL and fills in 'errMsg', if it was
           * provided.
           */
          CollectionMetadata* cloneMigrate( const ChunkType& chunk,
                                            const ChunkVersion& newShardVersion,
                                            std::string* errMsg ) const;
  
          /**
           * Returns a new metadata's instance by splitting an existing 'chunk' at the points
           * described by 'splitKeys'. The first resulting chunk will have 'newShardVersion' and
           * subsequent one would have that with the minor version incremented at each chunk. The
           * caller owns the metadata.
           *
           * If a new metadata can't be created, returns NULL and fills in 'errMsg', if it was
           * provided.
           *
           * Note: 'splitKeys' must be sorted in ascending order.
           */
          CollectionMetadata* cloneSplit( const ChunkType& chunk,
                                          const std::vector<BSONObj>& splitKeys,
                                          const ChunkVersion& newShardVersion,
                                          std::string* errMsg ) const;
  
          /**
           * Returns a new metadata instance by merging a key range which starts and ends at existing
           * chunks into a single chunk.  The range may not have holes.  The resulting metadata will
           * have the 'newShardVersion'.  The caller owns the new metadata.
           *
           * If a new metadata can't be created, returns NULL and fills in 'errMsg', if it was
           * provided.
           */
          CollectionMetadata* cloneMerge( const BSONObj& minKey,
                                          const BSONObj& maxKey,
                                          const ChunkVersion& newShardVersion,
                                          std::string* errMsg ) const;
  
          //
          // verification logic
          //
  
          /**
           * Returns true if the document key 'key' is a valid instance of a shard key for this
           * metadata.  The 'key' must contain exactly the same fields as the shard key pattern.
           */
          bool isValidKey( const BSONObj& key ) const;
  
          /**
           * Returns true if the document key 'key' belongs to this chunkset. Recall that documents of
           * an in-flight chunk migration may be present and should not be considered part of the
           * collection / chunkset yet. Key must be the full shard key.
           */
          bool keyBelongsToMe( const BSONObj& key ) const;
  
          /**
           * Returns true if the document key 'key' is or has been migrated to this shard, and may
           * belong to us after a subsequent config reload.  Key must be the full shard key.
           */
          bool keyIsPending( const BSONObj& key ) const;
  
          /**
           * Given a key 'lookupKey' in the shard key range, get the next chunk which overlaps or is
           * greater than this key.  Returns true if a chunk exists, false otherwise.
           *
           * Passing a key that is not a valid shard key for this range results in undefined behavior.
           */
          bool getNextChunk( const BSONObj& lookupKey, ChunkType* chunk ) const;
  
          /**
           * Given a key in the shard key range, get the next range which overlaps or is greater than
           * this key.
           *
           * This allows us to do the following to iterate over all orphan ranges:
           *
           * KeyRange range;
           * BSONObj lookupKey = metadata->getMinKey();
           * while( metadata->getNextOrphanRange( lookupKey, &orphanRange ) ) {
           *   // Do stuff with range
           *   lookupKey = orphanRange.maxKey;
           * }
           *
           * @param lookupKey passing a key that does not belong to this metadata is undefined.
           * @param orphanRange the output range. Note that the NS is not set.
           */
          bool getNextOrphanRange( const BSONObj& lookupKey, KeyRange* orphanRange ) const;
  
          //
          // accessors
          //
  
          ChunkVersion getCollVersion() const {
              return _collVersion;
          }
  
          ChunkVersion getShardVersion() const {
              return _shardVersion;
          }
  
          BSONObj getKeyPattern() const {
              return _keyPattern;
          }
  
          const std::vector<FieldRef*>& getKeyPatternFields() const {
              return _keyFields.vector();
          }
  
          BSONObj getMinKey() const;
  
          BSONObj getMaxKey() const;
  
          std::size_t getNumChunks() const {
              return _chunksMap.size();
          }
  
          std::size_t getNumPending() const {
              return _pendingMap.size();
          }
  
          //
          // reporting
          //
  
          /**
           * BSON output of the metadata information.
           */
          BSONObj toBSON() const;
  
          /**
           * BSON output of the metadata information, into a builder.
           */
          void toBSON( BSONObjBuilder& bb ) const;
  
          /**
           * BSON output of the chunks metadata into a BSONArray
           */
          void toBSONChunks( BSONArrayBuilder& bb ) const;
  
          /**
           * BSON output of the pending metadata into a BSONArray
           */
          void toBSONPending( BSONArrayBuilder& bb ) const;
  
          /**
           * std::string output of the metadata information.
           */
          std::string toString() const;
  
          /**
           * Use the MetadataLoader to fill the empty metadata from the config server, or use
           * clone*() methods to use existing metadatas to build new ones.
           *
           * Unless you are the MetadataLoader or a test you should probably not be using this
           * directly.
           */
          CollectionMetadata();
  
          /**
           * TESTING ONLY
           *
           * Returns a new metadata's instance based on 'this's state by adding 'chunk'. The new
           * metadata can never be zero, though (see cloneMinus). The caller owns the new metadata.
           *
           * If a new metadata can't be created, returns NULL and fills in 'errMsg', if it was
           * provided.
           */
          CollectionMetadata* clonePlusChunk( const ChunkType& chunk,
                                              const ChunkVersion& newShardVersion,
                                              std::string* errMsg ) const;
  
      private:
          // Effectively, the MetadataLoader is this class's builder. So we open an exception
          // and grant it friendship.
          friend class MetadataLoader;
  
          // a version for this collection that identifies the collection incarnation (ie, a
          // dropped and recreated collection with the same name would have a different version)
          ChunkVersion _collVersion;
  
          //
          // sharded state below, for when the collection gets sharded
          //
  
          // highest ChunkVersion for which this metadata's information is accurate
          ChunkVersion _shardVersion;
  
          // key pattern for chunks under this range
          BSONObj _keyPattern;
  
          // A vector owning the FieldRefs parsed from the shard-key pattern of field names.
          OwnedPointerVector<FieldRef> _keyFields;
  
          //
          // RangeMaps represent chunks by mapping the min key to the chunk's max key, allowing
          // efficient lookup and intersection.
          //
  
          // Map of ranges of chunks that are migrating but have not been confirmed added yet
          RangeMap _pendingMap;
  
          // Map of chunks tracked by this shard
          RangeMap _chunksMap;
  
          // A second map from a min key into a range or contiguous chunks. The map is redundant
          // w.r.t. _chunkMap but we expect high chunk contiguity, especially in small
          // installations.
          RangeMap _rangesMap;
  
          /**
           * Returns true if this metadata was loaded with all necessary information.
           */
          bool isValid() const;
  
          /**
           * Try to find chunks that are adjacent and record these intervals in the _rangesMap
           */
          void fillRanges();
  
          /**
           * Creates the _keyField* local data
           */
          void fillKeyPatternFields();
      };
  
  } // namespace mongo
  