// btreebuilder.cpp
/**
* Copyright (C) 2008 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 .
*/
#include "mongo/pch.h"
#include "mongo/db/btreebuilder.h"
#include "mongo/db/btree.h"
#include "mongo/db/client.h"
#include "mongo/db/clientcursor.h"
#include "mongo/db/curop-inl.h"
#include "mongo/db/db.h"
#include "mongo/db/dbhelpers.h"
#include "mongo/db/dur_commitjob.h"
#include "mongo/db/json.h"
#include "mongo/db/kill_current_op.h"
#include "mongo/db/pdfile.h"
#include "mongo/db/stats/counters.h"
namespace mongo {
/* --- BtreeBuilder --- */
template
BtreeBuilder::BtreeBuilder(bool _dupsAllowed, IndexDetails& _idx) :
dupsAllowed(_dupsAllowed),
idx(_idx),
n(0),
order( idx.keyPattern() ),
ordering( Ordering::make(idx.keyPattern()) ) {
first = cur = BtreeBucket::addBucket(idx);
b = cur.btreemod();
committed = false;
}
template
void BtreeBuilder::newBucket() {
DiskLoc L = BtreeBucket::addBucket(idx);
b->setTempNext(L);
cur = L;
b = cur.btreemod();
}
template
void BtreeBuilder::mayCommitProgressDurably() {
if ( getDur().commitIfNeeded() ) {
b = cur.btreemod();
}
}
template
void BtreeBuilder::addKey(BSONObj& _key, DiskLoc loc) {
auto_ptr< KeyOwned > key( new KeyOwned(_key) );
if ( key->dataSize() > BtreeBucket::KeyMax ) {
problem() << "Btree::insert: key too large to index, skipping " << idx.indexNamespace()
<< ' ' << key->dataSize() << ' ' << key->toString() << endl;
return;
}
if( !dupsAllowed ) {
if( n > 0 ) {
int cmp = keyLast->woCompare(*key, ordering);
massert( 10288 , "bad key order in BtreeBuilder - server internal error", cmp <= 0 );
if( cmp == 0 ) {
//if( !dupsAllowed )
uasserted( ASSERT_ID_DUPKEY , BtreeBucket::dupKeyError( idx , *keyLast ) );
}
}
}
if ( ! b->_pushBack(loc, *key, ordering, DiskLoc()) ) {
// bucket was full
newBucket();
b->pushBack(loc, *key, ordering, DiskLoc());
}
keyLast = key;
n++;
mayCommitProgressDurably();
}
template
void BtreeBuilder::buildNextLevel(DiskLoc loc, bool mayInterrupt) {
int levels = 1;
while( 1 ) {
if( loc.btree()->tempNext().isNull() ) {
// only 1 bucket at this level. we are done.
getDur().writingDiskLoc(idx.head) = loc;
break;
}
levels++;
DiskLoc upLoc = BtreeBucket::addBucket(idx);
DiskLoc upStart = upLoc;
BtreeBucket *up = upLoc.btreemod();
DiskLoc xloc = loc;
while( !xloc.isNull() ) {
killCurrentOp.checkForInterrupt( !mayInterrupt );
if ( getDur().commitIfNeeded() ) {
b = cur.btreemod();
up = upLoc.btreemod();
}
BtreeBucket *x = xloc.btreemod();
Key k;
DiskLoc r;
x->popBack(r,k);
bool keepX = ( x->n != 0 );
DiskLoc keepLoc = keepX ? xloc : x->nextChild;
if ( ! up->_pushBack(r, k, ordering, keepLoc) ) {
// current bucket full
DiskLoc n = BtreeBucket::addBucket(idx);
up->setTempNext(n);
upLoc = n;
up = upLoc.btreemod();
up->pushBack(r, k, ordering, keepLoc);
}
DiskLoc nextLoc = x->tempNext(); // get next in chain at current level
if ( keepX ) {
x->parent = upLoc;
}
else {
if ( !x->nextChild.isNull() ) {
DiskLoc ll = x->nextChild;
ll.btreemod()->parent = upLoc;
//(x->nextChild.btreemod())->parent = upLoc;
}
x->deallocBucket( xloc, idx );
}
xloc = nextLoc;
}
loc = upStart;
mayCommitProgressDurably();
}
if( levels > 1 ) {
LOG(2) << "btree levels: " << levels << endl;
}
}
/** when all addKeys are done, we then build the higher levels of the tree */
template
void BtreeBuilder::commit(bool mayInterrupt) {
buildNextLevel(first, mayInterrupt);
committed = true;
}
template class BtreeBuilder;
template class BtreeBuilder;
}