com.sleepycat.je.tree
Class BIN

java.lang.Object
  com.sleepycat.je.tree.Node
      com.sleepycat.je.tree.IN
          com.sleepycat.je.tree.BIN

All Implemented Interfaces:

Loggable, Comparable<IN>

Direct Known Subclasses:

DBIN

public class BIN
extends IN
implements Loggable

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

Field Summary

Fields inherited from class com.sleepycat.je.tree.IN

ACCUMULATED_LIMIT, BIN_LEVEL, databaseImpl, DBMAP_LEVEL, EXACT_MATCH, INSERT_SUCCESS, latch, LEVEL_MASK, MAIN_LEVEL, MAX_LEVEL, MAY_EVICT_LNS, MAY_EVICT_NODE, MAY_NOT_EVICT, MIN_LEVEL

Fields inherited from class com.sleepycat.je.tree.Node

NULL_NODE_ID

Constructor Summary

BIN()

BIN(DatabaseImpl db, byte[] 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.
void	afterLog(LogManager logManager, INLogItem item, INLogContext context) Post-log processing.
void	beforeLog(LogManager logManager, INLogItem item, INLogContext context) Pre-log processing.
String	beginTag()
protected boolean	canBeAncestor(boolean targetContainsDuplicates)
void	clearKnownDeleted(int index) Clear the known deleted flag.
boolean	compress(BINReference binRef, boolean canFetch, LocalUtilizationTracker localTracker) Compress this BIN by removing any entries that are deleted.
static long	computeOverhead(DbConfigManager configManager)
boolean	containsCursor(CursorImpl cursor) For assertions in CursorImpl.
protected IN	createNewInstance(byte[] 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.
void	evictLN(int index) Evict a single LN if allowed and adjust the memory budget.
long	evictLNs() Reduce memory consumption by evicting all LN targets.
Node	fetchTarget(int idx) We require exclusive latches on a BIN, so this method does not need to declare that it throws RelatchRequiredException.
(package private) LogEntryType	getBINDeltaType()
(package private) int	getChildEvictionType() Note that the IN may or may not be latched when this method is called.
byte[]	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) BIN	getCursorBINToBeRemoved(CursorImpl cursor)
(package private) int	getCursorIndex(CursorImpl cursor)
Set<CursorImpl>	getCursorSet()
Comparator<byte[]>	getKeyComparator() Return the relevant user defined comparison function for this type of node.
long	getLastDeltaVersion()
LogEntryType	getLogType()
protected long	getMemoryOverhead(MemoryBudget mb)
long	getTreeAdminMemorySize() Returns the treeAdmin memory in objects referenced by this BIN.
(package private) boolean	hasPinnedChildren() Note that the IN may or may not be latched when this method is called.
void	incEvictStats(Evictor.EvictionSource source) We categorize eviction stats by the type of IN, so IN subclasses update different stats.
void	incFetchStats(EnvironmentImpl envImpl, boolean isMiss) We categorize fetch stats by the type of node, so node subclasses update different stats.
(package private) boolean	isAlwaysLatchedExclusively()
(package private) boolean	isBottomMostNode()
boolean	isCompressible()
(package private) boolean	isEvictionProhibited() Note that the IN may or may not be latched when this method is called.
(package private) boolean	isValidForDelete() Check if this node fits the qualifications for being part of a deletable subtree.
void	logDirtyChildren() When splits and checkpoints intermingle in a deferred write databases, a checkpoint target may appear which has a valid target but a null LSN.
int	nCursors()
void	removeCursor(CursorImpl cursor) Unregister a cursor with this bin.
(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	setKnownDeletedClearAll(int index)
void	setKnownDeletedLeaveTarget(int index) Mark this entry as deleted, using the delete flag.
void	setProhibitNextDelta() If cleaned or compressed, must log full version.
String	shortClassName()
(package private) void	splitSpecial(IN parent, int parentIndex, int maxEntriesPerNode, byte[] key, boolean leftSide, CacheMode cacheMode) 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, clearLsn, clearPendingDeleted, compareTo, compareToKeyPrefix, computeArraysOverhead, computeMemorySize, deleteEntry, deleteEntry, dumpDeletedState, dumpKeys, dumpLog, dumpLogAdditional, dumpString, equals, fetchTargetWithExclusiveLatch, findEntry, findParent, generateLevel, getBudgetedMemorySize, getDatabase, getDatabaseId, getDirty, getDupKey, getDupTreeKey, getEntryInMemorySize, getEntryLsnByteArray, getEntryLsnLongArray, getEvictionType, getGeneration, getIdentifierKey, getInListResident, getInMemorySize, getKey, getKeyPrefix, getLastFullVersion, getLevel, getLogSize, getLsn, getMainTreeKey, getMaxEntries, getMigrate, getNEntries, getRecalcToggle, getState, getTarget, hashCode, hasResidentChildren, init, initEntryLsn, initMemorySize, insertEntry, insertEntry1, isDbRoot, isDirty, isEntryKnownDeleted, isEntryPendingDeleted, isEvictable, isKeyInBounds, isLatchOwnerForRead, isLatchOwnerForWrite, isRoot, isSoughtNode, isStateKnownDeleted, isStatePendingDeleted, latch, latch, latchNoWait, latchNoWait, latchShared, latchShared, log, log, log, logicalEquals, makeFetchErrorMsg, needsSplitting, notOverwritingDeferredWriteEntry, optionalLog, optionalLogProvisional, postFetchInit, postRecoveryInit, readFromLog, rebuildINList, releaseLatch, releaseLatchIfOwner, resetAndGetMemorySize, selectKey, setDatabase, setDirty, setEntry, setGeneration, setGeneration, setIdentifierKey, setInListResident, setIsRoot, setKeyPrefix, setLastFullLsn, setLsnElement, setMigrate, setPendingDeleted, setRecalcToggle, setTarget, split, splitInternal, toString, trackProvisionalObsolete, updateEntry, updateEntry, updateEntry, updateMemorySize, updateMemorySize, updateMemorySize, updateNode, updateNode, updateNode, verify, verifyKeyPrefix, verifyMemorySize, writeToLog

Methods inherited from class com.sleepycat.je.tree.Node

containsDuplicates, dump, getMemorySizeIncludedByParent, getNodeId, getTransactionId, getType, matchLNByNodeId, 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.Loggable

dumpLog, getLogSize, getTransactionId, logicalEquals, readFromLog, writeToLog

Constructor Detail

BIN

public BIN()

BIN

public BIN(DatabaseImpl db,
           byte[] 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(byte[] 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

isAlwaysLatchedExclusively

boolean isAlwaysLatchedExclusively()

Overrides:

isAlwaysLatchedExclusively in class IN

isBottomMostNode

boolean isBottomMostNode()

Overrides:

isBottomMostNode in class IN

Returns:

true if this node cannot contain contain children INs, i.e., if this is a DBIN, or this is a BIN in a non-duplicates DB.

getChildKey

public byte[] getChildKey(IN child)

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

getBINDeltaType

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.

setProhibitNextDelta

public void setProhibitNextDelta()

If cleaned or compressed, must log full version.

Overrides:

setProhibitNextDelta 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

Returns:

true if you can be the ancestor of the target IN. Currently the determining factor is whether the target IN contains duplicates.

isEvictionProhibited

boolean isEvictionProhibited()

Note that the IN may or may not be latched when this method is called. Returning the wrong answer is OK in that case (it will be called again later when latched), but an exception should not occur.

Overrides:

isEvictionProhibited in class IN

hasPinnedChildren

boolean hasPinnedChildren()

Note that the IN may or may not be latched when this method is called. Returning the wrong answer is OK in that case (it will be called again later when latched), but an exception should not occur.

Overrides:

hasPinnedChildren in class IN

getChildEvictionType

int getChildEvictionType()

Note that the IN may or may not be latched when this method is called. Returning the wrong answer is OK in that case (it will be called again later when latched), but an exception should not occur.

Overrides:

getChildEvictionType in class IN

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

setKnownDeletedClearAll

public void setKnownDeletedClearAll(int index)

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)

getMemoryOverhead

protected long getMemoryOverhead(MemoryBudget mb)

Overrides:

getMemoryOverhead in class IN

getTreeAdminMemorySize

public long getTreeAdminMemorySize()

Returns the treeAdmin memory in objects referenced by this BIN. Specifically, this refers to the DbFileSummaryMap held by MapLNs

Overrides:

getTreeAdminMemorySize in class IN

getCursorSet

public Set<CursorImpl> 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.

containsCursor

public boolean containsCursor(CursorImpl cursor)

For assertions in CursorImpl.

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.

getCursorBINToBeRemoved

BIN getCursorBINToBeRemoved(CursorImpl cursor)

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,
                  byte[] key,
                  boolean leftSide,
                  CacheMode cacheMode)
            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.

newSiblingLow, - newSiblingHigh - the low and high entry of "this" that were moved into newSibling.

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,
                        boolean canFetch,
                        LocalUtilizationTracker localTracker)
                 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.

canFetch - if false, don't fetch any non-resident children. We don't want some callers of compress, such as the evictor, to fault in other nodes.

Returns:

true if we had to requeue the entry because we were unable to get locks, false if all entries were processed and therefore any remaining deleted keys in the BINReference must now be in some other BIN because of a split.

Throws:

DatabaseException - from subclasses.

isCompressible

public boolean isCompressible()

Overrides:

isCompressible in class IN

evictLNs

public long evictLNs()
              throws DatabaseException

Reduce memory consumption by evicting all LN targets. Note that this may cause LNs to be logged, which would require marking this BIN dirty. The BIN should be latched by the caller.

Returns:

number of evicted bytes. Note that a 0 return does not necessarily mean that the BIN had no evictable LNs. It's possible that resident, dirty LNs were not lockable.

Throws:

DatabaseException

evictLN

public void evictLN(int index)
             throws DatabaseException

Evict a single LN if allowed and adjust the memory budget.

Throws:

DatabaseException

validateSubtreeBeforeDelete

boolean validateSubtreeBeforeDelete(int index)

Overrides:

validateSubtreeBeforeDelete in class IN

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. We assume that this is only called under an assert.

Overrides:

isValidForDelete in class IN

Returns:

true if you're part of a deletable subtree.

Throws:

DatabaseException

accumulateStats

void accumulateStats(TreeWalkerStatsAccumulator acc)

Overrides:

accumulateStats in class IN

getKeyComparator

public Comparator<byte[]> 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

logDirtyChildren

public void logDirtyChildren()
                      throws DatabaseException

Description copied from class: IN

When splits and checkpoints intermingle in a deferred write databases, a checkpoint target may appear which has a valid target but a null LSN. Deferred write dbs are written out in checkpoint style by either Database.sync() or a checkpoint which has cleaned a file containing deferred write entries. For example, INa | BINb A checkpoint or Database.sync starts The INList is traversed, dirty nodes are selected BINb is bypassed on the INList, since it's not dirty BINb is split, creating a new sibling, BINc, and dirtying INa INa is selected as a dirty node for the ckpt If this happens, INa is in the selected dirty set, but not its dirty child BINb and new child BINc. In a durable db, the existence of BINb and BINc are logged anyway. But in a deferred write db, there is an entry that points to BINc, but no logged version. This will not cause problems with eviction, because INa can't be evicted until BINb and BINc are logged, are non-dirty, and are detached. But it can cause problems at recovery, because INa will have a null LSN for a valid entry, and the LN children of BINc will not find a home. To prevent this, search for all dirty children that might have been missed during the selection phase, and write them out. It's not sufficient to write only null-LSN children, because the existing sibling must be logged lest LN children recover twice (once in the new sibling, once in the old existing sibling.

Overrides:

logDirtyChildren in class IN

Throws:

DatabaseException

See Also:

IN.logDirtyChildren();

incEvictStats

public void incEvictStats(Evictor.EvictionSource source)

Description copied from class: IN

We categorize eviction stats by the type of IN, so IN subclasses update different stats.

Overrides:

incEvictStats in class IN

See Also:

IN.incEvictStats(com.sleepycat.je.evictor.Evictor.EvictionSource)

incFetchStats

public void incFetchStats(EnvironmentImpl envImpl,
                          boolean isMiss)

Description copied from class: Node

We categorize fetch stats by the type of node, so node subclasses update different stats.

Overrides:

incFetchStats in class IN

See Also:

Node.incFetchStats(com.sleepycat.je.dbi.EnvironmentImpl, boolean)

getLogType

public LogEntryType getLogType()

Overrides:

getLogType in class IN

See Also:

Node.getLogType()

shortClassName

public String shortClassName()

Overrides:

shortClassName in class IN

beforeLog

public void beforeLog(LogManager logManager,
                      INLogItem item,
                      INLogContext context)
               throws DatabaseException

Description copied from class: IN

Pre-log processing. Used implicitly for single-item logging and explicitly for multi-item logging. Overridden by subclasses as needed. Decide how to log this node. INs are always logged in full. Cleaner LN migration is never performed since it only applies to BINs.

Overrides:

beforeLog in class IN

Throws:

DatabaseException - from subclasses.

afterLog

public void afterLog(LogManager logManager,
                     INLogItem item,
                     INLogContext context)
              throws DatabaseException

Description copied from class: IN

Post-log processing. Used implicitly for single-item logging and explicitly for multi-item logging. Overridden by subclasses as needed. The last version of this node must be counted obsolete at the correct time. If logging non-provisionally, the last version of this node and any provisionally logged descendants are immediately obsolete and can be flushed. If logging provisionally, the last version isn't obsolete until an ancestor is logged non-provisionally, so propagate obsolete lsns upwards.

Overrides:

afterLog in class IN

Throws:

DatabaseException

fetchTarget

public Node fetchTarget(int idx)
                 throws DatabaseException

We require exclusive latches on a BIN, so this method does not need to declare that it throws RelatchRequiredException.

Overrides:

fetchTarget in class IN

Returns:

the target node or null.

Throws:

DatabaseException