mongo::BtreeBucket Class Reference

#include <btree.h>

Inheritance diagram for mongo::BtreeBucket:
Inheritance graph
[legend]

List of all members.

Public Member Functions

DiskLoc advance (const DiskLoc &thisLoc, int &keyOfs, int direction, const char *caller) const
void advanceTo (DiskLoc &thisLoc, int &keyOfs, const BSONObj &keyBegin, int keyBeginLen, bool afterKey, const vector< const BSONElement * > &keyEnd, const vector< bool > &keyEndInclusive, const Ordering &order, int direction) const
int bt_insert (const DiskLoc thisLoc, const DiskLoc recordLoc, const BSONObj &key, const Ordering &order, bool dupsAllowed, IndexDetails &idx, bool toplevel=true) const
string bucketSummary () const
void customLocate (DiskLoc &thisLoc, int &keyOfs, const BSONObj &keyBegin, int keyBeginLen, bool afterKey, const vector< const BSONElement * > &keyEnd, const vector< bool > &keyEndInclusive, const Ordering &order, int direction, pair< DiskLoc, int > &bestParent) const
void deallocBucket (const DiskLoc thisLoc, const IndexDetails &id)
void dump () const
void dumpTree (const DiskLoc &thisLoc, const BSONObj &order) const
bool exists (const IndexDetails &idx, const DiskLoc &thisLoc, const BSONObj &key, const Ordering &order) const
DiskLoc findSingle (const IndexDetails &indexdetails, const DiskLoc &thisLoc, const BSONObj &key) const
int fullValidate (const DiskLoc &thisLoc, const BSONObj &order, int *unusedCount=0, bool strict=false) const
const DiskLoc getHead (const DiskLoc &thisLoc) const
bool isHead () const
bool isUsed (int i) const
DiskLoc locate (const IndexDetails &idx, const DiskLoc &thisLoc, const BSONObj &key, const Ordering &order, int &pos, bool &found, const DiskLoc &recordLoc, int direction=1) const
void shape (stringstream &) const
bool unindex (const DiskLoc thisLoc, IndexDetails &id, const BSONObj &key, const DiskLoc recordLoc) const
bool wouldCreateDup (const IndexDetails &idx, const DiskLoc &thisLoc, const BSONObj &key, const Ordering &order, const DiskLoc &self) const

Static Public Member Functions

static void a_test (IndexDetails &)
static DiskLoc addBucket (const IndexDetails &)
static string dupKeyError (const IndexDetails &idx, const BSONObj &key)
static int getKeyMax ()
static int getLowWaterMark ()
static void renameIndexNamespace (const char *oldNs, const char *newNs)

Protected Member Functions

int _insert (const DiskLoc thisLoc, const DiskLoc recordLoc, const BSONObj &key, const Ordering &order, bool dupsAllowed, const DiskLoc lChild, const DiskLoc rChild, IndexDetails &idx) const
bool canMergeChildren (const DiskLoc &thisLoc, int leftIndex) const
bool customFind (int l, int h, const BSONObj &keyBegin, int keyBeginLen, bool afterKey, const vector< const BSONElement * > &keyEnd, const vector< bool > &keyEndInclusive, const Ordering &order, int direction, DiskLoc &thisLoc, int &keyOfs, pair< DiskLoc, int > &bestParent) const
void delBucket (const DiskLoc thisLoc, const IndexDetails &)
void deleteInternalKey (const DiskLoc thisLoc, int keypos, IndexDetails &id, const Ordering &order)
void delKeyAtPos (const DiskLoc thisLoc, IndexDetails &id, int p, const Ordering &order)
void doBalanceChildren (const DiskLoc thisLoc, int leftIndex, IndexDetails &id, const Ordering &order)
void doBalanceLeftToRight (const DiskLoc thisLoc, int leftIndex, int split, BtreeBucket *l, const DiskLoc lchild, BtreeBucket *r, const DiskLoc rchild, IndexDetails &id, const Ordering &order)
void doBalanceRightToLeft (const DiskLoc thisLoc, int leftIndex, int split, BtreeBucket *l, const DiskLoc lchild, BtreeBucket *r, const DiskLoc rchild, IndexDetails &id, const Ordering &order)
void doMergeChildren (const DiskLoc thisLoc, int leftIndex, IndexDetails &id, const Ordering &order)
bool find (const IndexDetails &idx, const BSONObj &key, const DiskLoc &recordLoc, const Ordering &order, int &pos, bool assertIfDup) const
void fixParentPtrs (const DiskLoc thisLoc, int firstIndex=0, int lastIndex=-1) const
int indexInParent (const DiskLoc &thisLoc) const
void insertHere (const DiskLoc thisLoc, int keypos, const DiskLoc recordLoc, const BSONObj &key, const Ordering &order, const DiskLoc lchild, const DiskLoc rchild, IndexDetails &idx) const
BSONObj keyAt (int keyOfs) const
bool mayBalanceWithNeighbors (const DiskLoc thisLoc, IndexDetails &id, const Ordering &order) const
int rebalancedSeparatorPos (const DiskLoc &thisLoc, int leftIndex) const
void replaceWithNextChild (const DiskLoc thisLoc, IndexDetails &id)
void setInternalKey (const DiskLoc thisLoc, int keypos, const DiskLoc recordLoc, const BSONObj &key, const Ordering &order, const DiskLoc lchild, const DiskLoc rchild, IndexDetails &idx)
void split (const DiskLoc thisLoc, int keypos, const DiskLoc recordLoc, const BSONObj &key, const Ordering &order, const DiskLoc lchild, const DiskLoc rchild, IndexDetails &idx)
bool tryBalanceChildren (const DiskLoc thisLoc, int leftIndex, IndexDetails &id, const Ordering &order) const

Static Protected Member Functions

static BtreeBucket * allocTemp ()
static int customBSONCmp (const BSONObj &l, const BSONObj &rBegin, int rBeginLen, bool rSup, const vector< const BSONElement * > &rEnd, const vector< bool > &rEndInclusive, const Ordering &o, int direction)
static void findLargestKey (const DiskLoc &thisLoc, DiskLoc &largestLoc, int &largestKey)
static void fix (const DiskLoc thisLoc, const DiskLoc child)

Friends

class BtreeCursor

Detailed Description

This class adds functionality for manipulating buckets that are assembled in a tree. The requirements for const and non const functions and arguments are generally the same as in BtreeBucket. Because this class deals with tree structure, some functions that are marked const may trigger modification of another node in the btree or potentially of the current node. In such cases, the function's implementation explicitly casts away const when indicating an intent to write to the durability layer. The DiskLocs provided to such functions should be passed by value if they shadow pointers within the btree.

To clarify enforcement of referential integrity in this implementation, we use the following pattern when deleting data we have a persistent pointer to. The pointer is cleared or removed explicitly, then the data it pointed to is cleaned up with a helper function.

TODO It might make sense to put some of these functions in a class representing a full btree instead of a single btree bucket. That would allow us to use the const qualifier in a manner more consistent with standard usage. Right now the interface is for both a node and a tree, so assignment of const is sometimes nonideal.

TODO There are several cases in which the this pointer is invalidated as a result of deallocation. A seperate class representing a btree would alleviate some fragile cases where the implementation must currently behave correctly if the this pointer is suddenly invalidated by a callee.

Definition at line 281 of file btree.h.

Member Function Documentation

int mongo::BtreeBucket::_insert ( const DiskLoc  thisLoc,
const DiskLoc  recordLoc,
const BSONObj &  key,
const Ordering &  order,
bool  dupsAllowed,
const DiskLoc  lChild,
const DiskLoc  rChild,
IndexDetails &  idx 
) const [protected]
static void mongo::BtreeBucket::a_test ( IndexDetails &   )  [static]
static DiskLoc mongo::BtreeBucket::addBucket ( const IndexDetails &   )  [static]
DiskLoc mongo::BtreeBucket::advance ( const DiskLoc &  thisLoc,
int &  keyOfs,
int  direction,
const char *  caller 
) const

advance one key position in the index:

void mongo::BtreeBucket::advanceTo ( DiskLoc &  thisLoc,
int &  keyOfs,
const BSONObj &  keyBegin,
int  keyBeginLen,
bool  afterKey,
const vector< const BSONElement * > &  keyEnd,
const vector< bool > &  keyEndInclusive,
const Ordering &  order,
int  direction 
) const
static BtreeBucket* mongo::BtreeBucket::allocTemp (  )  [static, protected]
int mongo::BtreeBucket::bt_insert ( const DiskLoc  thisLoc,
const DiskLoc  recordLoc,
const BSONObj &  key,
const Ordering &  order,
bool  dupsAllowed,
IndexDetails &  idx,
bool  toplevel = true 
) const

This function may change the btree root

string mongo::BtreeBucket::bucketSummary (  )  const
bool mongo::BtreeBucket::canMergeChildren ( const DiskLoc &  thisLoc,
int  leftIndex 
) const [protected]
Returns:
true iff left and right child can be merged into one node
static int mongo::BtreeBucket::customBSONCmp ( const BSONObj &  l,
const BSONObj &  rBegin,
int  rBeginLen,
bool  rSup,
const vector< const BSONElement * > &  rEnd,
const vector< bool > &  rEndInclusive,
const Ordering &  o,
int  direction 
) [static, protected]
bool mongo::BtreeBucket::customFind ( int  l,
int  h,
const BSONObj &  keyBegin,
int  keyBeginLen,
bool  afterKey,
const vector< const BSONElement * > &  keyEnd,
const vector< bool > &  keyEndInclusive,
const Ordering &  order,
int  direction,
DiskLoc &  thisLoc,
int &  keyOfs,
pair< DiskLoc, int > &  bestParent 
) const [protected]
void mongo::BtreeBucket::customLocate ( DiskLoc &  thisLoc,
int &  keyOfs,
const BSONObj &  keyBegin,
int  keyBeginLen,
bool  afterKey,
const vector< const BSONElement * > &  keyEnd,
const vector< bool > &  keyEndInclusive,
const Ordering &  order,
int  direction,
pair< DiskLoc, int > &  bestParent 
) const
void mongo::BtreeBucket::deallocBucket ( const DiskLoc  thisLoc,
const IndexDetails &  id 
)

invalidates 'this' and thisLoc

void mongo::BtreeBucket::delBucket ( const DiskLoc  thisLoc,
const IndexDetails &   
) [protected]

invalidates this and thisLoc

void mongo::BtreeBucket::deleteInternalKey ( const DiskLoc  thisLoc,
int  keypos,
IndexDetails &  id,
const Ordering &  order 
) [protected]

Deletes the specified key, replacing it with the key immediately preceding or succeeding it in the btree. Either the left or right child of the specified key must be non null.

void mongo::BtreeBucket::delKeyAtPos ( const DiskLoc  thisLoc,
IndexDetails &  id,
int  p,
const Ordering &  order 
) [protected]

may invalidate this and thisLoc

void mongo::BtreeBucket::doBalanceChildren ( const DiskLoc  thisLoc,
int  leftIndex,
IndexDetails &  id,
const Ordering &  order 
) [protected]
void mongo::BtreeBucket::doBalanceLeftToRight ( const DiskLoc  thisLoc,
int  leftIndex,
int  split,
BtreeBucket *  l,
const DiskLoc  lchild,
BtreeBucket *  r,
const DiskLoc  rchild,
IndexDetails &  id,
const Ordering &  order 
) [protected]
void mongo::BtreeBucket::doBalanceRightToLeft ( const DiskLoc  thisLoc,
int  leftIndex,
int  split,
BtreeBucket *  l,
const DiskLoc  lchild,
BtreeBucket *  r,
const DiskLoc  rchild,
IndexDetails &  id,
const Ordering &  order 
) [protected]
void mongo::BtreeBucket::doMergeChildren ( const DiskLoc  thisLoc,
int  leftIndex,
IndexDetails &  id,
const Ordering &  order 
) [protected]

may invalidate this and thisLoc

void mongo::BtreeBucket::dump (  )  const
void mongo::BtreeBucket::dumpTree ( const DiskLoc &  thisLoc,
const BSONObj &  order 
) const
static string mongo::BtreeBucket::dupKeyError ( const IndexDetails &  idx,
const BSONObj &  key 
) [static]

simply builds and returns a dup key error message string

bool mongo::BtreeBucket::exists ( const IndexDetails &  idx,
const DiskLoc &  thisLoc,
const BSONObj &  key,
const Ordering &  order 
) const
Returns:
true if key exists in index

- indicates order of keys in the index. this is basically the index's key pattern, e.g.: BSONObj order = ((IndexDetails&)idx).keyPattern(); likewise below in bt_insert() etc.

bool mongo::BtreeBucket::find ( const IndexDetails &  idx,
const BSONObj &  key,
const DiskLoc &  recordLoc,
const Ordering &  order,
int &  pos,
bool  assertIfDup 
) const [protected]
static void mongo::BtreeBucket::findLargestKey ( const DiskLoc &  thisLoc,
DiskLoc &  largestLoc,
int &  largestKey 
) [static, protected]
DiskLoc mongo::BtreeBucket::findSingle ( const IndexDetails &  indexdetails,
const DiskLoc &  thisLoc,
const BSONObj &  key 
) const

find the first instance of the key does not handle dups returned DiskLoc isNull if can't find anything with that

Returns:
the record location of the first match
static void mongo::BtreeBucket::fix ( const DiskLoc  thisLoc,
const DiskLoc  child 
) [static, protected]
void mongo::BtreeBucket::fixParentPtrs ( const DiskLoc  thisLoc,
int  firstIndex = 0,
int  lastIndex = -1 
) const [protected]

Fix parent pointers for children first index to modify last index to modify (-1 means last index is n)

int mongo::BtreeBucket::fullValidate ( const DiskLoc &  thisLoc,
const BSONObj &  order,
int *  unusedCount = 0,
bool  strict = false 
) const
const DiskLoc mongo::BtreeBucket::getHead ( const DiskLoc &  thisLoc  )  const
static int mongo::BtreeBucket::getKeyMax (  )  [static]
static int mongo::BtreeBucket::getLowWaterMark (  )  [static]
int mongo::BtreeBucket::indexInParent ( const DiskLoc &  thisLoc  )  const [protected]
void mongo::BtreeBucket::insertHere ( const DiskLoc  thisLoc,
int  keypos,
const DiskLoc  recordLoc,
const BSONObj &  key,
const Ordering &  order,
const DiskLoc  lchild,
const DiskLoc  rchild,
IndexDetails &  idx 
) const [protected]
bool mongo::BtreeBucket::isHead (  )  const [inline]

Definition at line 284 of file btree.h.

bool mongo::BtreeBucket::isUsed ( int  i  )  const [inline]

Definition at line 288 of file btree.h.

BSONObj mongo::BtreeBucket::keyAt ( int  keyOfs  )  const [inline, protected]

Definition at line 408 of file btree.h.

DiskLoc mongo::BtreeBucket::locate ( const IndexDetails &  idx,
const DiskLoc &  thisLoc,
const BSONObj &  key,
const Ordering &  order,
int &  pos,
bool &  found,
const DiskLoc &  recordLoc,
int  direction = 1 
) const

locate may return an "unused" key that is just a marker. so be careful. looks for a key:recordloc pair.

- returns true if exact match found. note you can get back a position result even if found is false.

bool mongo::BtreeBucket::mayBalanceWithNeighbors ( const DiskLoc  thisLoc,
IndexDetails &  id,
const Ordering &  order 
) const [protected]

May balance utilization of this bucket with a neighbor, either by merging the buckets or shifting nodes.

Returns:
true iff balancing was performed. NOTE This function may invalidate thisLoc.
int mongo::BtreeBucket::rebalancedSeparatorPos ( const DiskLoc &  thisLoc,
int  leftIndex 
) const [protected]
Returns:
index of the rebalanced separator; the index value is determined as if we had an array <left bucket="" keys="" array>="">.push( <old separator> ).concat( <right bucket keys array> ) This is only expected to be called if the left and right child cannot be merged. This function is expected to be called on packed buckets, see also comments for splitPos().
static void mongo::BtreeBucket::renameIndexNamespace ( const char *  oldNs,
const char *  newNs 
) [static]
void mongo::BtreeBucket::replaceWithNextChild ( const DiskLoc  thisLoc,
IndexDetails &  id 
) [protected]

will invalidate this and thisLoc

void mongo::BtreeBucket::setInternalKey ( const DiskLoc  thisLoc,
int  keypos,
const DiskLoc  recordLoc,
const BSONObj &  key,
const Ordering &  order,
const DiskLoc  lchild,
const DiskLoc  rchild,
IndexDetails &  idx 
) [protected]

Replaces an existing key with the new specified key, splitting if necessary

void mongo::BtreeBucket::shape ( stringstream &   )  const

get tree shape

void mongo::BtreeBucket::split ( const DiskLoc  thisLoc,
int  keypos,
const DiskLoc  recordLoc,
const BSONObj &  key,
const Ordering &  order,
const DiskLoc  lchild,
const DiskLoc  rchild,
IndexDetails &  idx 
) [protected]

split bucket

bool mongo::BtreeBucket::tryBalanceChildren ( const DiskLoc  thisLoc,
int  leftIndex,
IndexDetails &  id,
const Ordering &  order 
) const [protected]
Returns:
true if balance succeeded
bool mongo::BtreeBucket::unindex ( const DiskLoc  thisLoc,
IndexDetails &  id,
const BSONObj &  key,
const DiskLoc  recordLoc 
) const

This function may change the btree root

bool mongo::BtreeBucket::wouldCreateDup ( const IndexDetails &  idx,
const DiskLoc &  thisLoc,
const BSONObj &  key,
const Ordering &  order,
const DiskLoc &  self 
) const

Friends And Related Function Documentation

friend class BtreeCursor [friend]

Definition at line 282 of file btree.h.

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

mongodb
Author(s): Nate Koenig
autogenerated on Fri Jan 11 12:15:53 2013