com.sleepycat.je.tree
Class BIN

java.lang.Object
  extended bycom.sleepycat.je.tree.Node
      extended bycom.sleepycat.je.tree.IN
          extended bycom.sleepycat.je.tree.BIN
All Implemented Interfaces:
Comparable, LoggableObject, LogReadable, LogWritable
Direct Known Subclasses:
DBIN

public class BIN
extends IN
implements LoggableObject

A BIN represents a Bottom Internal Node in the JE tree.


Field Summary
protected  Set cursorSet
           
 
Fields inherited from class com.sleepycat.je.tree.IN
DBMAP_LEVEL, evictionProhibited, EXACT_MATCH, INSERT_SUCCESS, MAIN_LEVEL, MAX_LEVEL, MIN_LEVEL
 
Constructor Summary
BIN()
           
BIN(DatabaseImpl db, Key identifierKey, int maxEntriesPerNode, int level)
           
 
Method Summary
(package private)  void accumulateStats(TreeWalkerStatsAccumulator acc)
           
 void addCursor(CursorImpl cursor)
          Register a cursor with this bin.
(package private)  void adjustCursors(IN newSibling, int newSiblingLow, int newSiblingHigh)
          Adjust any cursors that are referring to this BIN.
(package private)  void adjustCursorsForInsert(int insertIndex)
          Adjust cursors referring to this BIN following an insert.
(package private)  void adjustCursorsForMutation(int binIndex, DBIN dupBin, int dupBinIndex, CursorImpl excludeCursor)
          Adjust cursors referring to the given binIndex in this BIN following a mutation of the entry from an LN to a DIN.
 String beginTag()
           
protected  boolean canBeAncestor(boolean targetContainsDuplicates)
           
protected  boolean childrenAreEvictable()
           
 void clearKnownDeleted(int index)
          Clear the known deleted flag.
 boolean compress(BINReference binRef)
          Compress this BIN by removing any entries that are deleted.
static long computeOverhead(DbConfigManager configManager)
           
protected  IN createNewInstance(Key identifierKey, int maxEntries, int level)
          Create a new BIN.
 BINReference createReference()
          Create a holder object that encapsulates information about this BIN for the INCompressor.
protected  void descendOnParentSearch(SearchResult result, boolean targetContainsDuplicates, boolean targetIsRoot, long targetNodeId, Node child, boolean requireExactMatch)
           
 String endTag()
           
(package private)  boolean entryZeroKeyComparesLow()
          Indicates whether entry 0's key is "special" in that it always compares less than any other key.
 long evictLNs()
          Reduce memory consumption by evicting all LN targets.
 LogEntryType getBINDeltaType()
           
 Key getChildKey(IN child)
          Get the key (dupe or identifier) in child that is used to locate it in 'this' node.
(package private)  BIN getCursorBIN(CursorImpl cursor)
          The following four methods access the correct fields in a cursor depending on whether "this" is a BIN or DBIN.
(package private)  int getCursorIndex(CursorImpl cursor)
           
 Set getCursorSet()
           
 Comparator getKeyComparator()
          Return the relevant user defined comparison function for this type of node.
 long getLastDeltaVersion()
           
 LogEntryType getLogType()
          All objects that are reponsible for a generating a type of log entry must implement this.
protected  long getMemoryOverhead(MemoryBudget mb)
           
 boolean isEvictable()
           
(package private)  boolean isValidForDelete()
          Check if this node fits the qualifications for being part of a deletable subtree.
protected  long logInternal(LogManager logManager, boolean allowDeltas, boolean isProvisional)
          Decide how to log this node.
 int nCursors()
           
 void removeCursor(CursorImpl cursor)
          Unregister a cursor with this bin.
 void setCleanedSinceLastLog()
          If cleaned, must log full version.
protected  void setCompressedSinceLastLog()
          If compressed, must log full version.
(package private)  void setCursorBIN(CursorImpl cursor, BIN bin)
           
(package private)  void setCursorIndex(CursorImpl cursor, int index)
           
 void setKnownDeleted(int index)
          Mark this entry as deleted, using the delete flag.
 void setKnownDeletedLeaveTarget(int index)
          Mark this entry as deleted, using the delete flag.
 String shortClassName()
           
(package private)  void splitSpecial(IN parent, int parentIndex, int maxEntriesPerNode, Key key, boolean leftSide)
          Called when we know we are about to split on behalf of a key that is the minimum (leftSide) or maximum (!leftSide) of this node.
(package private)  boolean validateSubtreeBeforeDelete(int index)
           
 void verifyCursors()
          For each cursor in this BIN's cursor set, ensure that the cursor is actually referring to this BIN.
 
Methods inherited from class com.sleepycat.je.tree.IN
accountForSubtreeRemoval, clearTarget, compareTo, computeMemorySize, deleteEntry, deleteEntry, dumpKeys, dumpLog, dumpLogAdditional, dumpString, equals, fetchTarget, fetchTargetIgnoreKnownDeleted, findEntry, findParent, generateLevel, getDatabase, getDatabaseId, getDirty, getDupKey, getDupTreeKey, getGeneration, getIdentifierKey, getInMemorySize, getInMemorySize, getInMemorySize, getKey, getLastFullVersion, getLatch, getLevel, getLogSize, getLsn, getMainTreeKey, getMaxEntries, getNEntries, getState, getTarget, getTransactionId, hashCode, init, initMemorySize, insertEntry, insertEntry1, isDbRoot, isDirty, isEntryKnownDeleted, isKeyInBounds, isRoot, isSoughtNode, latch, log, log, logAllowDeltas, logEntryIsTransactional, logProvisional, makeFetchErrorMsg, makePrefixKey, needsSplitting, postFetchInit, postRecoveryInit, readFromLog, rebuildINList, releaseLatch, selectKey, setDatabase, setDirty, setEntry, setEvictionProhibited, setGeneration, setGeneration, setIdentifierKey, setInListResident, setIsRoot, setLastFullLsn, setLsn, setTarget, split, splitInternal, toString, traceSplit, updateEntry, updateEntry, updateEntry, updateEntry, updateEntry, updateMemorySize, updateMemorySize, updateMemorySize, verify, verifyMemorySize, writeToLog
 
Methods inherited from class com.sleepycat.je.tree.Node
containsDuplicates, dump, getLastId, getMemorySizeIncludedByParent, getNextNodeId, getNodeId, getType, marshallOutsideWriteLatch, matchLNByNodeId, postLogWork, setLastNodeId, setNodeId, shortDescription
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface com.sleepycat.je.log.LoggableObject
marshallOutsideWriteLatch, postLogWork
 
Methods inherited from interface com.sleepycat.je.log.LogWritable
getLogSize, writeToLog
 

Field Detail

cursorSet

protected Set cursorSet
Constructor Detail

BIN

public BIN()

BIN

public BIN(DatabaseImpl db,
           Key identifierKey,
           int maxEntriesPerNode,
           int level)
Method Detail

createReference

public BINReference createReference()
Create a holder object that encapsulates information about this BIN for the INCompressor.


createNewInstance

protected IN createNewInstance(Key identifierKey,
                               int maxEntries,
                               int level)
Create a new BIN. Need this because we can't call newInstance() without getting a 0 for nodeid.

Overrides:
createNewInstance in class IN

getChildKey

public Key getChildKey(IN child)
                throws DatabaseException
Get the key (dupe or identifier) in child that is used to locate it in 'this' node. For BIN's, the child node has to be a DIN so we use the Dup Key to cross the main-tree/dupe-tree boundary.

Overrides:
getChildKey in class IN
Throws:
DatabaseException

getBINDeltaType

public LogEntryType getBINDeltaType()
Returns:
the log entry type to use for bin delta log entries.

getLastDeltaVersion

public long getLastDeltaVersion()
Returns:
location of last logged delta version. If never set, return null.

setCompressedSinceLastLog

protected void setCompressedSinceLastLog()
If compressed, must log full version. Overrides base class method.

Overrides:
setCompressedSinceLastLog in class IN

setCleanedSinceLastLog

public void setCleanedSinceLastLog()
If cleaned, must log full version. Overrides base class method.

Overrides:
setCleanedSinceLastLog in class IN

descendOnParentSearch

protected void descendOnParentSearch(SearchResult result,
                                     boolean targetContainsDuplicates,
                                     boolean targetIsRoot,
                                     long targetNodeId,
                                     Node child,
                                     boolean requireExactMatch)
                              throws DatabaseException
Overrides:
descendOnParentSearch in class IN
Throws:
DatabaseException

canBeAncestor

protected boolean canBeAncestor(boolean targetContainsDuplicates)
Overrides:
canBeAncestor in class IN

isEvictable

public boolean isEvictable()
Overrides:
isEvictable in class IN

childrenAreEvictable

protected boolean childrenAreEvictable()

entryZeroKeyComparesLow

boolean entryZeroKeyComparesLow()
Indicates whether entry 0's key is "special" in that it always compares less than any other key. BIN's don't have the special key, but IN's do.

Overrides:
entryZeroKeyComparesLow in class IN

setKnownDeleted

public void setKnownDeleted(int index)
Mark this entry as deleted, using the delete flag. Only BINS may do this.

Overrides:
setKnownDeleted in class IN
Parameters:
index - indicates target entry

setKnownDeletedLeaveTarget

public void setKnownDeletedLeaveTarget(int index)
Mark this entry as deleted, using the delete flag. Only BINS may do this. Don't null the target field. This is used so that an LN can still be locked by the compressor even if the entry is knownDeleted. See BIN.compress.

Parameters:
index - indicates target entry

clearKnownDeleted

public void clearKnownDeleted(int index)
Clear the known deleted flag. Only BINS may do this.

Overrides:
clearKnownDeleted in class IN
Parameters:
index - indicates target entry

computeOverhead

public static long computeOverhead(DbConfigManager configManager)
                            throws DatabaseException
Throws:
DatabaseException

getMemoryOverhead

protected long getMemoryOverhead(MemoryBudget mb)
Overrides:
getMemoryOverhead in class IN

getCursorSet

public Set getCursorSet()

addCursor

public void addCursor(CursorImpl cursor)
Register a cursor with this bin. Caller has this bin already latched.

Parameters:
cursor - Cursor to register.

removeCursor

public void removeCursor(CursorImpl cursor)
Unregister a cursor with this bin. Caller has this bin already latched.

Parameters:
cursor - Cursor to unregister.

nCursors

public int nCursors()
Returns:
the number of cursors currently referring to this BIN.

getCursorBIN

BIN getCursorBIN(CursorImpl cursor)
The following four methods access the correct fields in a cursor depending on whether "this" is a BIN or DBIN. For BIN's, the CursorImpl.index and CursorImpl.bin fields should be used. For DBIN's, the CursorImpl.dupIndex and CursorImpl.dupBin fields should be used.


getCursorIndex

int getCursorIndex(CursorImpl cursor)

setCursorBIN

void setCursorBIN(CursorImpl cursor,
                  BIN bin)

setCursorIndex

void setCursorIndex(CursorImpl cursor,
                    int index)

splitSpecial

void splitSpecial(IN parent,
                  int parentIndex,
                  int maxEntriesPerNode,
                  Key key,
                  boolean leftSide)
            throws DatabaseException
Called when we know we are about to split on behalf of a key that is the minimum (leftSide) or maximum (!leftSide) of this node. This is achieved by just forcing the split to occur either one element in from the left or the right (i.e. splitIndex is 1 or nEntries - 1).

Overrides:
splitSpecial in class IN
Throws:
DatabaseException

adjustCursors

void adjustCursors(IN newSibling,
                   int newSiblingLow,
                   int newSiblingHigh)
Adjust any cursors that are referring to this BIN. This method is called during a split operation. "this" is the BIN being split. newSibling is the new BIN into which the entries from "this" between newSiblingLow and newSiblingHigh have been copied.

Overrides:
adjustCursors in class IN
Parameters:
newSibling - - the newSibling into which "this" has been split.

verifyCursors

public void verifyCursors()
For each cursor in this BIN's cursor set, ensure that the cursor is actually referring to this BIN.


adjustCursorsForInsert

void adjustCursorsForInsert(int insertIndex)
Adjust cursors referring to this BIN following an insert.

Overrides:
adjustCursorsForInsert in class IN
Parameters:
insertIndex - - The index of the new entry.

adjustCursorsForMutation

void adjustCursorsForMutation(int binIndex,
                              DBIN dupBin,
                              int dupBinIndex,
                              CursorImpl excludeCursor)
Adjust cursors referring to the given binIndex in this BIN following a mutation of the entry from an LN to a DIN. The entry was moved from a BIN to a newly created DBIN so each cursor must be added to the new DBIN.

Parameters:
binIndex - - The index of the DIN (previously LN) entry in the BIN.
dupBin - - The DBIN into which the LN entry was moved.
dupBinIndex - - The index of the moved LN entry in the DBIN.
excludeCursor - - The cursor being used for insertion and that should not be updated.

compress

public boolean compress(BINReference binRef)
                 throws DatabaseException
Compress this BIN by removing any entries that are deleted. Deleted entries are those that have LN's marked deleted or if the knownDeleted flag is set. Caller is responsible for latching and unlatching this node.

Overrides:
compress in class IN
Parameters:
binRef - is used to determine the set of keys to be checked for deletedness, or is null to check all keys.
Returns:
true if there are no more entries in this BIN and it should be removed from the parent, false if more entries remain.
Throws:
DatabaseException

evictLNs

public long evictLNs()
              throws DatabaseException
Reduce memory consumption by evicting all LN targets. Note that the targets are not persistent, so this doesn't affect node dirtiness. The BIN should be latched by the caller.

Returns:
number of evicted bytes
Throws:
DatabaseException

validateSubtreeBeforeDelete

boolean validateSubtreeBeforeDelete(int index)
                              throws DatabaseException
Overrides:
validateSubtreeBeforeDelete in class IN
Throws:
DatabaseException

isValidForDelete

boolean isValidForDelete()
                   throws DatabaseException
Check if this node fits the qualifications for being part of a deletable subtree. It can only have one IN child and no LN children.

Overrides:
isValidForDelete in class IN
Throws:
DatabaseException

accumulateStats

void accumulateStats(TreeWalkerStatsAccumulator acc)
Overrides:
accumulateStats in class IN

getKeyComparator

public Comparator getKeyComparator()
Return the relevant user defined comparison function for this type of node. For IN's and BIN's, this is the BTree Comparison function. Overriden by DBIN.

Overrides:
getKeyComparator in class IN

beginTag

public String beginTag()
Overrides:
beginTag in class IN

endTag

public String endTag()
Overrides:
endTag in class IN

getLogType

public LogEntryType getLogType()
Description copied from interface: LoggableObject
All objects that are reponsible for a generating a type of log entry must implement this.

Specified by:
getLogType in interface LoggableObject
Overrides:
getLogType in class IN
See Also:
LoggableObject.getLogType()

shortClassName

public String shortClassName()
Overrides:
shortClassName in class IN

logInternal

protected long logInternal(LogManager logManager,
                           boolean allowDeltas,
                           boolean isProvisional)
                    throws DatabaseException
Decide how to log this node. BINs may be logged provisionally. If logging a delta, return an null for the LSN.

Overrides:
logInternal in class IN
Throws:
DatabaseException


Copyright 2004 Sleepycat, Inc. All Rights Reserved.