diff options
Diffstat (limited to 'src/mongo/db/storage/mmap_v1/btree/btree_logic.h')
| -rw-r--r-- | src/mongo/db/storage/mmap_v1/btree/btree_logic.h | 823 |
1 files changed, 403 insertions, 420 deletions
diff --git a/src/mongo/db/storage/mmap_v1/btree/btree_logic.h b/src/mongo/db/storage/mmap_v1/btree/btree_logic.h index 48a307f3b4d..3c742170bcd 100644 --- a/src/mongo/db/storage/mmap_v1/btree/btree_logic.h +++ b/src/mongo/db/storage/mmap_v1/btree/btree_logic.h @@ -41,539 +41,522 @@ namespace mongo { - class RecordStore; - class SavedCursorRegistry; +class RecordStore; +class SavedCursorRegistry; - // Used for unit-testing only - template <class BtreeLayout> class BtreeLogicTestBase; - template <class BtreeLayout> class ArtificialTreeBuilder; - - /** - * This is the logic for manipulating the Btree. It is (mostly) independent of the on-disk - * format. - */ - template <class BtreeLayout> - class BtreeLogic { - public: - // AKA _keyNode - typedef typename BtreeLayout::FixedWidthKeyType KeyHeaderType; - - // AKA Key - typedef typename BtreeLayout::KeyType KeyDataType; +// Used for unit-testing only +template <class BtreeLayout> +class BtreeLogicTestBase; +template <class BtreeLayout> +class ArtificialTreeBuilder; - // AKA KeyOwned - typedef typename BtreeLayout::KeyOwnedType KeyDataOwnedType; +/** + * This is the logic for manipulating the Btree. It is (mostly) independent of the on-disk + * format. + */ +template <class BtreeLayout> +class BtreeLogic { +public: + // AKA _keyNode + typedef typename BtreeLayout::FixedWidthKeyType KeyHeaderType; - // AKA Loc - typedef typename BtreeLayout::LocType LocType; + // AKA Key + typedef typename BtreeLayout::KeyType KeyDataType; - // AKA BucketBasics or BtreeBucket, either one. - typedef typename BtreeLayout::BucketType BucketType; + // AKA KeyOwned + typedef typename BtreeLayout::KeyOwnedType KeyDataOwnedType; - /** - * 'head' manages the catalog information. - * 'store' allocates and frees buckets. - * 'ordering' is meta-information we store in the catalog. - * 'indexName' is a string identifying the index that we use to print errors with. - */ - BtreeLogic(HeadManager* head, - RecordStore* store, - SavedCursorRegistry* cursors, - const Ordering& ordering, - const std::string& indexName) - : _headManager(head), - _recordStore(store), - _cursorRegistry(cursors), - _ordering(ordering), - _indexName(indexName) { - } + // AKA Loc + typedef typename BtreeLayout::LocType LocType; - // - // Public-facing - // + // AKA BucketBasics or BtreeBucket, either one. + typedef typename BtreeLayout::BucketType BucketType; - class Builder { - public: - typedef typename BtreeLayout::KeyOwnedType KeyDataOwnedType; - typedef typename BtreeLayout::KeyType KeyDataType; + /** + * 'head' manages the catalog information. + * 'store' allocates and frees buckets. + * 'ordering' is meta-information we store in the catalog. + * 'indexName' is a string identifying the index that we use to print errors with. + */ + BtreeLogic(HeadManager* head, + RecordStore* store, + SavedCursorRegistry* cursors, + const Ordering& ordering, + const std::string& indexName) + : _headManager(head), + _recordStore(store), + _cursorRegistry(cursors), + _ordering(ordering), + _indexName(indexName) {} + + // + // Public-facing + // + + class Builder { + public: + typedef typename BtreeLayout::KeyOwnedType KeyDataOwnedType; + typedef typename BtreeLayout::KeyType KeyDataType; - Status addKey(const BSONObj& key, const DiskLoc& loc); + Status addKey(const BSONObj& key, const DiskLoc& loc); - private: - friend class BtreeLogic; + private: + friend class BtreeLogic; - class SetRightLeafLocChange; + class SetRightLeafLocChange; - Builder(BtreeLogic* logic, OperationContext* txn, bool dupsAllowed); + Builder(BtreeLogic* logic, OperationContext* txn, bool dupsAllowed); - /** - * Creates and returns a new empty bucket to the right of leftSib, maintaining the - * internal consistency of the tree. leftSib must be the right-most child of its parent - * or it must be the root. - */ - DiskLoc newBucket(BucketType* leftSib, DiskLoc leftSibLoc); + /** + * Creates and returns a new empty bucket to the right of leftSib, maintaining the + * internal consistency of the tree. leftSib must be the right-most child of its parent + * or it must be the root. + */ + DiskLoc newBucket(BucketType* leftSib, DiskLoc leftSibLoc); - BucketType* _getModifiableBucket(DiskLoc loc); - BucketType* _getBucket(DiskLoc loc); + BucketType* _getModifiableBucket(DiskLoc loc); + BucketType* _getBucket(DiskLoc loc); - // Not owned. - BtreeLogic* _logic; + // Not owned. + BtreeLogic* _logic; - DiskLoc _rightLeafLoc; // DiskLoc of right-most (highest) leaf bucket. - bool _dupsAllowed; - std::unique_ptr<KeyDataOwnedType> _keyLast; + DiskLoc _rightLeafLoc; // DiskLoc of right-most (highest) leaf bucket. + bool _dupsAllowed; + std::unique_ptr<KeyDataOwnedType> _keyLast; - // Not owned. - OperationContext* _txn; - }; + // Not owned. + OperationContext* _txn; + }; - /** - * Caller owns the returned pointer. - * 'this' must outlive the returned pointer. - */ - Builder* newBuilder(OperationContext* txn, bool dupsAllowed); + /** + * Caller owns the returned pointer. + * 'this' must outlive the returned pointer. + */ + Builder* newBuilder(OperationContext* txn, bool dupsAllowed); - Status dupKeyCheck(OperationContext* txn, - const BSONObj& key, - const DiskLoc& loc) const; + Status dupKeyCheck(OperationContext* txn, const BSONObj& key, const DiskLoc& loc) const; - Status insert(OperationContext* txn, - const BSONObj& rawKey, - const DiskLoc& value, - bool dupsAllowed); + Status insert(OperationContext* txn, + const BSONObj& rawKey, + const DiskLoc& value, + bool dupsAllowed); - /** - * Navigates down the tree and locates the bucket and position containing a record with - * the specified <key, recordLoc> combination. - * - * @return true if the exact <key, recordLoc> was found. Otherwise, false and the - * bucketLocOut would contain the bucket containing key which is before or after the - * searched one (dependent on the direction). - */ - bool locate(OperationContext* txn, - const BSONObj& key, - const DiskLoc& recordLoc, - const int direction, - int* posOut, - DiskLoc* bucketLocOut) const; + /** + * Navigates down the tree and locates the bucket and position containing a record with + * the specified <key, recordLoc> combination. + * + * @return true if the exact <key, recordLoc> was found. Otherwise, false and the + * bucketLocOut would contain the bucket containing key which is before or after the + * searched one (dependent on the direction). + */ + bool locate(OperationContext* txn, + const BSONObj& key, + const DiskLoc& recordLoc, + const int direction, + int* posOut, + DiskLoc* bucketLocOut) const; - void advance(OperationContext* txn, - DiskLoc* bucketLocInOut, - int* posInOut, - int direction) const; + void advance(OperationContext* txn, + DiskLoc* bucketLocInOut, + int* posInOut, + int direction) const; - bool exists(OperationContext* txn, const KeyDataType& key) const; + bool exists(OperationContext* txn, const KeyDataType& key) const; - bool unindex(OperationContext* txn, - const BSONObj& key, - const DiskLoc& recordLoc); + bool unindex(OperationContext* txn, const BSONObj& key, const DiskLoc& recordLoc); - bool isEmpty(OperationContext* txn) const; + bool isEmpty(OperationContext* txn) const; - long long fullValidate(OperationContext*, - long long *unusedCount, - bool strict, - bool dumpBuckets, - unsigned depth) const; + long long fullValidate(OperationContext*, + long long* unusedCount, + bool strict, + bool dumpBuckets, + unsigned depth) const; - DiskLoc getDiskLoc(OperationContext* txn, - const DiskLoc& bucketLoc, - const int keyOffset) const; + DiskLoc getDiskLoc(OperationContext* txn, const DiskLoc& bucketLoc, const int keyOffset) const; - BSONObj getKey(OperationContext* txn, - const DiskLoc& bucketLoc, - const int keyOffset) const; + BSONObj getKey(OperationContext* txn, const DiskLoc& bucketLoc, const int keyOffset) const; - DiskLoc getHead(OperationContext* txn) const { - return DiskLoc::fromRecordId(_headManager->getHead(txn)); - } + DiskLoc getHead(OperationContext* txn) const { + return DiskLoc::fromRecordId(_headManager->getHead(txn)); + } - Status touch(OperationContext* txn) const; + Status touch(OperationContext* txn) const; - // - // Composite key navigation methods - // + // + // Composite key navigation methods + // - void customLocate(OperationContext* txn, - DiskLoc* locInOut, - int* keyOfsInOut, - const IndexSeekPoint& seekPoint, - int direction) const; + void customLocate(OperationContext* txn, + DiskLoc* locInOut, + int* keyOfsInOut, + const IndexSeekPoint& seekPoint, + int direction) const; - void advanceTo(OperationContext*, - DiskLoc* thisLocInOut, - int* keyOfsInOut, - const IndexSeekPoint& seekPoint, - int direction) const; + void advanceTo(OperationContext*, + DiskLoc* thisLocInOut, + int* keyOfsInOut, + const IndexSeekPoint& seekPoint, + int direction) const; - void restorePosition(OperationContext* txn, - const BSONObj& savedKey, - const DiskLoc& savedLoc, - int direction, - DiskLoc* bucketInOut, - int* keyOffsetInOut) const; + void restorePosition(OperationContext* txn, + const BSONObj& savedKey, + const DiskLoc& savedLoc, + int direction, + DiskLoc* bucketInOut, + int* keyOffsetInOut) const; - // - // Creation and deletion - // + // + // Creation and deletion + // - /** - * Returns OK if the index was uninitialized before, error status otherwise. - */ - Status initAsEmpty(OperationContext* txn); + /** + * Returns OK if the index was uninitialized before, error status otherwise. + */ + Status initAsEmpty(OperationContext* txn); - // - // Size constants - // + // + // Size constants + // - const RecordStore* getRecordStore() const { return _recordStore; } + const RecordStore* getRecordStore() const { + return _recordStore; + } - SavedCursorRegistry* savedCursors() const { return _cursorRegistry; } + SavedCursorRegistry* savedCursors() const { + return _cursorRegistry; + } - static int lowWaterMark(); - - Ordering ordering() const { return _ordering; } + static int lowWaterMark(); - int customBSONCmp(const BSONObj& inIndex_left, - const IndexSeekPoint& seekPoint_right, - int direction) const; + Ordering ordering() const { + return _ordering; + } - private: - friend class BtreeLogic::Builder; + int customBSONCmp(const BSONObj& inIndex_left, + const IndexSeekPoint& seekPoint_right, + int direction) const; - // Used for unit-testing only - friend class BtreeLogicTestBase<BtreeLayout>; - friend class ArtificialTreeBuilder<BtreeLayout>; +private: + friend class BtreeLogic::Builder; - /** - * This is an in memory wrapper for the variable length data associated with a - * KeyHeaderType. It points to on-disk data but is not itself on-disk data. - * - * This object and its BSONObj 'key' will become invalid if the KeyHeaderType data that owns - * this it is moved within the btree. In general, a KeyWrapper should not be expected to be - * valid after a write. - */ - struct FullKey { - FullKey(const BucketType* bucket, int i) - : header(getKeyHeader(bucket, i)), - prevChildBucket(header.prevChildBucket), - recordLoc(header.recordLoc), - data(bucket->data + header.keyDataOfs()) { } + // Used for unit-testing only + friend class BtreeLogicTestBase<BtreeLayout>; + friend class ArtificialTreeBuilder<BtreeLayout>; - // This is actually a reference to something on-disk. - const KeyHeaderType& header; + /** + * This is an in memory wrapper for the variable length data associated with a + * KeyHeaderType. It points to on-disk data but is not itself on-disk data. + * + * This object and its BSONObj 'key' will become invalid if the KeyHeaderType data that owns + * this it is moved within the btree. In general, a KeyWrapper should not be expected to be + * valid after a write. + */ + struct FullKey { + FullKey(const BucketType* bucket, int i) + : header(getKeyHeader(bucket, i)), + prevChildBucket(header.prevChildBucket), + recordLoc(header.recordLoc), + data(bucket->data + header.keyDataOfs()) {} + + // This is actually a reference to something on-disk. + const KeyHeaderType& header; + + // These are actually in 'header'. + const LocType& prevChildBucket; + const LocType& recordLoc; + + // This is *not* memory-mapped but its members point to something on-disk. + KeyDataType data; + }; - // These are actually in 'header'. - const LocType& prevChildBucket; - const LocType& recordLoc; + // + // Functions that depend on the templated type info but nothing in 'this'. + // - // This is *not* memory-mapped but its members point to something on-disk. - KeyDataType data; - }; + static LocType& childLocForPos(BucketType* bucket, int pos); - // - // Functions that depend on the templated type info but nothing in 'this'. - // + static FullKey getFullKey(const BucketType* bucket, int i); - static LocType& childLocForPos(BucketType* bucket, int pos); + static KeyHeaderType& getKeyHeader(BucketType* bucket, int i); - static FullKey getFullKey(const BucketType* bucket, int i); + static const KeyHeaderType& getKeyHeader(const BucketType* bucket, int i); - static KeyHeaderType& getKeyHeader(BucketType* bucket, int i); + static char* dataAt(BucketType* bucket, short ofs); - static const KeyHeaderType& getKeyHeader(const BucketType* bucket, int i); + static void markUnused(BucketType* bucket, int keypos); - static char* dataAt(BucketType* bucket, short ofs); + static int totalDataSize(BucketType* bucket); - static void markUnused(BucketType* bucket, int keypos); + static void init(BucketType* bucket); - static int totalDataSize(BucketType* bucket); + static int _alloc(BucketType* bucket, int bytes); - static void init(BucketType* bucket); + static void _unalloc(BucketType* bucket, int bytes); - static int _alloc(BucketType* bucket, int bytes); + static void _delKeyAtPos(BucketType* bucket, int keypos, bool mayEmpty = false); - static void _unalloc(BucketType* bucket, int bytes); + static void popBack(BucketType* bucket, DiskLoc* recordLocOut, KeyDataType* keyDataOut); - static void _delKeyAtPos(BucketType* bucket, int keypos, bool mayEmpty = false); + static bool mayDropKey(BucketType* bucket, int index, int refPos); - static void popBack(BucketType* bucket, DiskLoc* recordLocOut, KeyDataType *keyDataOut); + static int _packedDataSize(BucketType* bucket, int refPos); - static bool mayDropKey(BucketType* bucket, int index, int refPos); + static void setPacked(BucketType* bucket); - static int _packedDataSize(BucketType* bucket, int refPos); + static void setNotPacked(BucketType* bucket); - static void setPacked(BucketType* bucket); + static BucketType* btreemod(OperationContext* txn, BucketType* bucket); - static void setNotPacked(BucketType* bucket); + static int splitPos(BucketType* bucket, int keypos); - static BucketType* btreemod(OperationContext* txn, BucketType* bucket); + static void reserveKeysFront(BucketType* bucket, int nAdd); - static int splitPos(BucketType* bucket, int keypos); + static void setKey(BucketType* bucket, + int i, + const DiskLoc recordLoc, + const KeyDataType& key, + const DiskLoc prevChildBucket); - static void reserveKeysFront(BucketType* bucket, int nAdd); + static bool isHead(BucketType* bucket); - static void setKey(BucketType* bucket, - int i, - const DiskLoc recordLoc, - const KeyDataType &key, - const DiskLoc prevChildBucket); + static void dumpBucket(const BucketType* bucket, int indentLength = 0); - static bool isHead(BucketType* bucket); + static void assertValid(const std::string& ns, + BucketType* bucket, + const Ordering& ordering, + bool force = false); - static void dumpBucket(const BucketType* bucket, int indentLength = 0); + // + // 'this'-specific helpers (require record store, catalog information, or ordering, or type + // information). + // - static void assertValid(const std::string& ns, - BucketType* bucket, - const Ordering& ordering, - bool force = false); + bool basicInsert(OperationContext* txn, + BucketType* bucket, + const DiskLoc bucketLoc, + int& keypos, + const KeyDataType& key, + const DiskLoc recordLoc); + + void dropFront(BucketType* bucket, int nDrop, int& refpos); + + void _pack(OperationContext* txn, BucketType* bucket, const DiskLoc thisLoc, int& refPos); + + void customLocate(OperationContext* txn, + DiskLoc* locInOut, + int* keyOfsInOut, + const IndexSeekPoint& seekPoint, + int direction, + std::pair<DiskLoc, int>& bestParent) const; + + Status _find(OperationContext* txn, + BucketType* bucket, + const KeyDataType& key, + const DiskLoc& recordLoc, + bool errorIfDup, + int* keyPositionOut, + bool* foundOut) const; + + bool customFind(OperationContext* txn, + int low, + int high, + const IndexSeekPoint& seekPoint, + int direction, + DiskLoc* thisLocInOut, + int* keyOfsInOut, + std::pair<DiskLoc, int>& bestParent) const; + + void advanceToImpl(OperationContext* txn, + DiskLoc* thisLocInOut, + int* keyOfsInOut, + const IndexSeekPoint& seekPoint, + int direction) const; - // - // 'this'-specific helpers (require record store, catalog information, or ordering, or type - // information). - // + bool wouldCreateDup(OperationContext* txn, const KeyDataType& key, const DiskLoc self) const; - bool basicInsert(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc, - int& keypos, - const KeyDataType& key, - const DiskLoc recordLoc); + bool keyIsUsed(OperationContext* txn, const DiskLoc& loc, const int& pos) const; - void dropFront(BucketType* bucket, int nDrop, int& refpos); + void skipUnusedKeys(OperationContext* txn, DiskLoc* loc, int* pos, int direction) const; - void _pack(OperationContext* txn, BucketType* bucket, const DiskLoc thisLoc, int &refPos); + DiskLoc advance(OperationContext* txn, + const DiskLoc& bucketLoc, + int* posInOut, + int direction) const; - void customLocate(OperationContext* txn, - DiskLoc* locInOut, - int* keyOfsInOut, - const IndexSeekPoint& seekPoint, - int direction, - std::pair<DiskLoc, int>& bestParent) const; + DiskLoc _locate(OperationContext* txn, + const DiskLoc& bucketLoc, + const KeyDataType& key, + int* posOut, + bool* foundOut, + const DiskLoc& recordLoc, + const int direction) const; - Status _find(OperationContext* txn, - BucketType* bucket, - const KeyDataType& key, - const DiskLoc& recordLoc, - bool errorIfDup, - int* keyPositionOut, - bool* foundOut) const; - - bool customFind(OperationContext* txn, - int low, - int high, - const IndexSeekPoint& seekPoint, - int direction, - DiskLoc* thisLocInOut, - int* keyOfsInOut, - std::pair<DiskLoc, int>& bestParent) const; - - void advanceToImpl(OperationContext* txn, - DiskLoc* thisLocInOut, - int* keyOfsInOut, - const IndexSeekPoint& seekPoint, - int direction) const; - - bool wouldCreateDup(OperationContext* txn, - const KeyDataType& key, - const DiskLoc self) const; - - bool keyIsUsed(OperationContext* txn, const DiskLoc& loc, const int& pos) const; - - void skipUnusedKeys(OperationContext* txn, - DiskLoc* loc, - int* pos, - int direction) const; - - DiskLoc advance(OperationContext* txn, - const DiskLoc& bucketLoc, - int* posInOut, - int direction) const; - - DiskLoc _locate(OperationContext* txn, - const DiskLoc& bucketLoc, - const KeyDataType& key, - int* posOut, - bool* foundOut, - const DiskLoc& recordLoc, - const int direction) const; + long long _fullValidate(OperationContext* txn, + const DiskLoc bucketLoc, + long long* unusedCount, + bool strict, + bool dumpBuckets, + unsigned depth) const; - long long _fullValidate(OperationContext* txn, - const DiskLoc bucketLoc, - long long *unusedCount, - bool strict, - bool dumpBuckets, - unsigned depth) const ; + DiskLoc _addBucket(OperationContext* txn); - DiskLoc _addBucket(OperationContext* txn); + bool canMergeChildren(OperationContext* txn, + BucketType* bucket, + const DiskLoc bucketLoc, + const int leftIndex); - bool canMergeChildren(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc, - const int leftIndex); + // has to look in children of 'bucket' and requires record store + int _rebalancedSeparatorPos(OperationContext* txn, BucketType* bucket, int leftIndex); - // has to look in children of 'bucket' and requires record store - int _rebalancedSeparatorPos(OperationContext* txn, - BucketType* bucket, - int leftIndex); + void _packReadyForMod(BucketType* bucket, int& refPos); - void _packReadyForMod(BucketType* bucket, int &refPos); + void truncateTo(BucketType* bucket, int N, int& refPos); - void truncateTo(BucketType* bucket, int N, int &refPos); + void split(OperationContext* txn, + BucketType* bucket, + const DiskLoc bucketLoc, + int keypos, + const DiskLoc recordLoc, + const KeyDataType& key, + const DiskLoc lchild, + const DiskLoc rchild); - void split(OperationContext* txn, + Status _insert(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc, - int keypos, - const DiskLoc recordLoc, const KeyDataType& key, - const DiskLoc lchild, - const DiskLoc rchild); - - Status _insert(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc, - const KeyDataType& key, - const DiskLoc recordLoc, - bool dupsAllowed, - const DiskLoc leftChild, - const DiskLoc rightChild); - - // TODO take a BucketType*? - void insertHere(OperationContext* txn, + const DiskLoc recordLoc, + bool dupsAllowed, + const DiskLoc leftChild, + const DiskLoc rightChild); + + // TODO take a BucketType*? + void insertHere(OperationContext* txn, + const DiskLoc bucketLoc, + int pos, + const KeyDataType& key, + const DiskLoc recordLoc, + const DiskLoc leftChild, + const DiskLoc rightChild); + + std::string dupKeyError(const KeyDataType& key) const; + + void setInternalKey(OperationContext* txn, + BucketType* bucket, const DiskLoc bucketLoc, - int pos, - const KeyDataType& key, + int keypos, const DiskLoc recordLoc, - const DiskLoc leftChild, - const DiskLoc rightChild); + const KeyDataType& key, + const DiskLoc lchild, + const DiskLoc rchild); - std::string dupKeyError(const KeyDataType& key) const; + void fixParentPtrs(OperationContext* trans, + BucketType* bucket, + const DiskLoc bucketLoc, + int firstIndex = 0, + int lastIndex = -1); - void setInternalKey(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc, - int keypos, - const DiskLoc recordLoc, - const KeyDataType& key, - const DiskLoc lchild, - const DiskLoc rchild); + bool mayBalanceWithNeighbors(OperationContext* txn, + BucketType* bucket, + const DiskLoc bucketLoc); - void fixParentPtrs(OperationContext* trans, + void doBalanceChildren(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc, - int firstIndex = 0, - int lastIndex = -1); - - bool mayBalanceWithNeighbors(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc); - - void doBalanceChildren(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc, - int leftIndex); - - void doBalanceLeftToRight(OperationContext* txn, - BucketType* bucket, - const DiskLoc thisLoc, - int leftIndex, - int split, - BucketType* l, - const DiskLoc lchild, - BucketType* r, - const DiskLoc rchild); - - void doBalanceRightToLeft(OperationContext* txn, - BucketType* bucket, - const DiskLoc thisLoc, - int leftIndex, - int split, - BucketType* l, - const DiskLoc lchild, - BucketType* r, - const DiskLoc rchild); - - bool tryBalanceChildren(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc, - int leftIndex); - - int indexInParent(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc) const; - - void doMergeChildren(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc, - int leftIndex); + int leftIndex); - void replaceWithNextChild(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc); + void doBalanceLeftToRight(OperationContext* txn, + BucketType* bucket, + const DiskLoc thisLoc, + int leftIndex, + int split, + BucketType* l, + const DiskLoc lchild, + BucketType* r, + const DiskLoc rchild); + + void doBalanceRightToLeft(OperationContext* txn, + BucketType* bucket, + const DiskLoc thisLoc, + int leftIndex, + int split, + BucketType* l, + const DiskLoc lchild, + BucketType* r, + const DiskLoc rchild); + + bool tryBalanceChildren(OperationContext* txn, + BucketType* bucket, + const DiskLoc bucketLoc, + int leftIndex); - void deleteInternalKey(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc, - int keypos); + int indexInParent(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc) const; - void delKeyAtPos(OperationContext* txn, + void doMergeChildren(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc, - int p); + int leftIndex); - void delBucket(OperationContext* txn, - BucketType* bucket, - const DiskLoc bucketLoc); + void replaceWithNextChild(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc); - void deallocBucket(OperationContext* txn, + void deleteInternalKey(OperationContext* txn, BucketType* bucket, - const DiskLoc bucketLoc); + const DiskLoc bucketLoc, + int keypos); - bool _keyIsAt(const BSONObj& savedKey, - const DiskLoc& savedLoc, - BucketType* bucket, - int keyPos) const; + void delKeyAtPos(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc, int p); - /** - * Tries to push key into bucket. Return false if it can't because key doesn't fit. - * - * bucket must be declared as writable by the caller. - * The new key/recordLoc pair must be higher than any others in bucket. - * - * TODO needs 'this' for _ordering for sanity check - */ - bool pushBack(BucketType* bucket, - const DiskLoc recordLoc, - const KeyDataType& key, - const DiskLoc prevChild); + void delBucket(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc); + void deallocBucket(OperationContext* txn, BucketType* bucket, const DiskLoc bucketLoc); - BucketType* childForPos(OperationContext* txn, BucketType* bucket, int pos) const; + bool _keyIsAt(const BSONObj& savedKey, + const DiskLoc& savedLoc, + BucketType* bucket, + int keyPos) const; - BucketType* getBucket(OperationContext* txn, const DiskLoc dl) const { - return getBucket(txn, dl.toRecordId()); - } - BucketType* getBucket(OperationContext* txn, const RecordId dl) const; + /** + * Tries to push key into bucket. Return false if it can't because key doesn't fit. + * + * bucket must be declared as writable by the caller. + * The new key/recordLoc pair must be higher than any others in bucket. + * + * TODO needs 'this' for _ordering for sanity check + */ + bool pushBack(BucketType* bucket, + const DiskLoc recordLoc, + const KeyDataType& key, + const DiskLoc prevChild); - BucketType* getRoot(OperationContext* txn) const; - DiskLoc getRootLoc(OperationContext* txn) const; + BucketType* childForPos(OperationContext* txn, BucketType* bucket, int pos) const; - // - // Data - // + BucketType* getBucket(OperationContext* txn, const DiskLoc dl) const { + return getBucket(txn, dl.toRecordId()); + } + BucketType* getBucket(OperationContext* txn, const RecordId dl) const; - // Not owned here. - HeadManager* _headManager; + BucketType* getRoot(OperationContext* txn) const; - // Not owned here. - RecordStore* _recordStore; + DiskLoc getRootLoc(OperationContext* txn) const; - // Not owned Here. - SavedCursorRegistry* _cursorRegistry; + // + // Data + // - Ordering _ordering; + // Not owned here. + HeadManager* _headManager; - std::string _indexName; - }; + // Not owned here. + RecordStore* _recordStore; + + // Not owned Here. + SavedCursorRegistry* _cursorRegistry; + + Ordering _ordering; + + std::string _indexName; +}; } // namespace mongo |