public final class Tree extends java.lang.Object implements Loggable
Modifier and Type | Class and Description |
---|---|
static class |
Tree.SearchType
Embodies an enum for the type of search being performed.
|
Constructor and Description |
---|
Tree()
Create a tree that's being read in from the log.
|
Tree(DatabaseImpl database)
Create a new tree.
|
Modifier and Type | Method and Description |
---|---|
void |
delete(byte[] idKey,
LocalUtilizationTracker localTracker)
Deletes a BIN specified by key from the tree.
|
void |
deleteDup(byte[] idKey,
byte[] mainKey,
LocalUtilizationTracker localTracker)
Delete a subtree of a duplicate tree.
|
void |
dump() |
void |
dumpLog(java.lang.StringBuffer sb,
boolean verbose)
Write the object into the string buffer for log dumping.
|
java.lang.String |
dumpString(int nSpaces) |
DatabaseImpl |
getDatabase() |
IN |
getFirstNode(CacheMode cacheMode)
Find the leftmost node (IN or BIN) in the tree.
|
DBIN |
getFirstNode(DIN dupRoot,
CacheMode cacheMode)
Find the leftmost node (DBIN) in a duplicate tree.
|
IN |
getLastNode(CacheMode cacheMode)
Find the rightmost node (IN or BIN) in the tree.
|
DBIN |
getLastNode(DIN dupRoot,
CacheMode cacheMode)
Find the rightmost node (DBIN) in a duplicate tree.
|
int |
getLogSize() |
BIN |
getNextBin(BIN bin,
boolean traverseWithinDupTree,
CacheMode cacheMode)
Return a reference to the adjacent BIN.
|
boolean |
getParentBINForChildLN(TreeLocation location,
byte[] mainKey,
byte[] dupKey,
LN ln,
boolean splitsAllowed,
boolean findDeletedEntries,
boolean searchDupTree,
CacheMode cacheMode)
Return a reference to the parent of this LN.
|
SearchResult |
getParentINForChildIN(IN child,
boolean requireExactMatch,
CacheMode cacheMode)
GetParentNode without optional tracking.
|
SearchResult |
getParentINForChildIN(IN child,
boolean requireExactMatch,
CacheMode cacheMode,
int targetLevel,
java.util.List<TrackingInfo> trackingList)
Return a reference to the parent or possible parent of the child.
|
SearchResult |
getParentINForChildIN(long targetNodeId,
boolean targetContainsDuplicates,
boolean targetIsRoot,
byte[] targetMainTreeKey,
byte[] targetDupTreeKey,
boolean requireExactMatch,
CacheMode cacheMode,
int targetLevel,
java.util.List<TrackingInfo> trackingList,
boolean doFetch)
Return a reference to the parent or possible parent of the child.
|
BIN |
getPrevBin(BIN bin,
boolean traverseWithinDupTree,
CacheMode cacheMode)
Return a reference to the previous BIN.
|
IN |
getResidentRootIN(boolean latched) |
IN |
getRootIN(CacheMode cacheMode)
Helper to obtain the root IN with shared root latching.
|
IN |
getRootINLatchedExclusive(CacheMode cacheMode)
Helper to obtain the root IN with exclusive root latching.
|
long |
getRootLsn()
Get LSN of the rootIN.
|
long |
getTransactionId() |
boolean |
insert(LN ln,
byte[] key,
boolean allowDuplicates,
CursorImpl cursor,
LockResult lnLock,
ReplicationContext repContext)
Inserts a new LN into the tree.
|
boolean |
isRootResident()
Perform a fast check to see if the root IN is resident.
|
boolean |
logicalEquals(Loggable other) |
ChildReference |
makeRootChildReference(Node target,
byte[] key,
long lsn) |
void |
readFromLog(java.nio.ByteBuffer itemBuffer,
byte entryVersion)
Initialize this object from the data in itemBuf.
|
void |
rebuildINList()
rebuildINList is used by recovery to add all the resident nodes to the
IN list.
|
boolean |
rootExists() |
IN |
search(byte[] key,
Tree.SearchType searchType,
long nid,
BINBoundary binBoundary,
CacheMode cacheMode)
Search the tree, starting at the root.
|
void |
searchDeletableSubTree(IN parent,
byte[] key,
java.util.ArrayList<com.sleepycat.je.tree.Tree.SplitInfo> nodeLadder)
Search down the tree using a key, but instead of returning the BIN that
houses that key, find the point where we can detach a deletable
subtree.
|
IN |
searchSplitsAllowed(byte[] key,
long nid,
CacheMode cacheMode)
Do a key based search, permitting pre-emptive splits.
|
IN |
searchSubTree(IN parent,
byte[] key,
Tree.SearchType searchType,
long nid,
BINBoundary binBoundary,
CacheMode cacheMode)
Wrapper for searchSubTreeInternal that does a restart if a
RelatchRequiredException is thrown (i.e.
|
void |
setCkptHook(TestHook hook) |
void |
setDatabase(DatabaseImpl database)
Set the database for this tree.
|
void |
setRoot(ChildReference newRoot,
boolean notLatched)
Set the root for the tree.
|
void |
setSearchHook(TestHook hook) |
void |
setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA) |
void |
setWaitHook(TestHook hook) |
void |
validateINList(IN parent)
Debugging check that all resident nodes are on the INList and no stray
nodes are present in the unused portion of the IN arrays.
|
IN |
withRootLatchedExclusive(WithRootLatched wrl) |
IN |
withRootLatchedShared(WithRootLatched wrl) |
void |
writeToLog(java.nio.ByteBuffer logBuffer)
Serialize this object into the buffer.
|
public Tree(DatabaseImpl database) throws DatabaseException
DatabaseException
public Tree() throws DatabaseException
DatabaseException
public void setDatabase(DatabaseImpl database) throws DatabaseException
DatabaseException
public DatabaseImpl getDatabase()
public void setRoot(ChildReference newRoot, boolean notLatched)
public ChildReference makeRootChildReference(Node target, byte[] key, long lsn)
public boolean rootExists()
public boolean isRootResident()
public long getRootLsn()
public void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA)
public IN withRootLatchedExclusive(WithRootLatched wrl) throws DatabaseException
DatabaseException
public IN withRootLatchedShared(WithRootLatched wrl) throws DatabaseException
DatabaseException
public void delete(byte[] idKey, LocalUtilizationTracker localTracker) throws DatabaseException, NodeNotEmptyException, CursorsExistException
idKey
- - the identifier key of the node to delete.localTracker
- is used for tracking obsolete node info.DatabaseException
NodeNotEmptyException
CursorsExistException
public void deleteDup(byte[] idKey, byte[] mainKey, LocalUtilizationTracker localTracker) throws DatabaseException, NodeNotEmptyException, CursorsExistException
idKey
- the identifier key to be used in the duplicate subtree to
find the duplicate path.mainKey
- the key to be used in the main tree to find the
duplicate subtree.localTracker
- is used for tracking obsolete node info.DatabaseException
NodeNotEmptyException
CursorsExistException
public IN getFirstNode(CacheMode cacheMode) throws DatabaseException
DatabaseException
public IN getLastNode(CacheMode cacheMode) throws DatabaseException
DatabaseException
public DBIN getFirstNode(DIN dupRoot, CacheMode cacheMode) throws DatabaseException
DatabaseException
public DBIN getLastNode(DIN dupRoot, CacheMode cacheMode) throws DatabaseException
DatabaseException
public SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, CacheMode cacheMode) throws DatabaseException
DatabaseException
public SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, CacheMode cacheMode, int targetLevel, java.util.List<TrackingInfo> trackingList) throws DatabaseException
child
- The child node for which to find the parent. This node is
latched by the caller and is released by this function before returning
to the caller.requireExactMatch
- if true, we must find the exact parent, not a
potential parent.cacheMode
- The CacheMode for affecting the hotness of the tree.trackingList
- if not null, add the LSNs of the parents visited
along the way, as a debug tracing mechanism. This is meant to stay in
production, to add information to the log.DatabaseException
public SearchResult getParentINForChildIN(long targetNodeId, boolean targetContainsDuplicates, boolean targetIsRoot, byte[] targetMainTreeKey, byte[] targetDupTreeKey, boolean requireExactMatch, CacheMode cacheMode, int targetLevel, java.util.List<TrackingInfo> trackingList, boolean doFetch) throws DatabaseException
requireExactMatch
- if true, we must find the exact parent, not a
potential parent.cacheMode
- The CacheMode for affecting the hotness of the tree.trackingList
- if not null, add the LSNs of the parents visited
along the way, as a debug tracing mechanism. This is meant to stay in
production, to add information to the log.doFetch
- if false, stop the search if we run into a non-resident
child. Used by the checkpointer to avoid conflicting with work done
by the evictor.DatabaseException
public boolean getParentBINForChildLN(TreeLocation location, byte[] mainKey, byte[] dupKey, LN ln, boolean splitsAllowed, boolean findDeletedEntries, boolean searchDupTree, CacheMode cacheMode) throws DatabaseException
When this method returns with location.bin non-null, the BIN is latched and must be unlatched by the caller. Note that location.bin may be non-null even if this method returns false.
location
- a holder class to hold state about the location
of our search. Sort of an internal cursor.mainKey
- key to navigate through main keydupKey
- key to navigate through duplicate tree. May be null, since
deleted lns have no data.ln
- the node instantiated from the logsplitsAllowed
- true if this method is allowed to cause tree splits
as a side effect. In practice, recovery can cause splits, but abort
can't.searchDupTree
- true if a search through the dup tree looking for
a match on the ln's node id should be made (only in the case where
dupKey == null). See SR 8984.cacheMode
- The CacheMode for affecting the hotness of the tree.DatabaseException
public BIN getNextBin(BIN bin, boolean traverseWithinDupTree, CacheMode cacheMode) throws DatabaseException
bin
- The BIN to find the next BIN for. This BIN is latched.traverseWithinDupTree
- if true, only search within the dup tree
and return null when the traversal runs out of duplicates.DatabaseException
public BIN getPrevBin(BIN bin, boolean traverseWithinDupTree, CacheMode cacheMode) throws DatabaseException
bin
- The BIN to find the next BIN for. This BIN is latched.traverseWithinDupTree
- if true, only search within the dup tree
and return null when the traversal runs out of duplicates.DatabaseException
public IN search(byte[] key, Tree.SearchType searchType, long nid, BINBoundary binBoundary, CacheMode cacheMode) throws DatabaseException
key
- - the key to search for, or null if searchType is LEFT or
RIGHT.searchType
- - The type of tree search to perform. NORMAL means
we're searching for key in the tree. LEFT/RIGHT means we're descending
down the left or right side, resp. DELETE means we're descending the
tree and will return the lowest node in the path that has > 1 entries.nid
- - The nodeid to search for in the tree. If found, returns
its parent. If the nodeid of the root is passed, null is returned.binBoundary
- - If non-null, information is returned about whether
the BIN found is the first or last BIN in the database.DatabaseException
public IN searchSplitsAllowed(byte[] key, long nid, CacheMode cacheMode) throws DatabaseException
DatabaseException
public IN searchSubTree(IN parent, byte[] key, Tree.SearchType searchType, long nid, BINBoundary binBoundary, CacheMode cacheMode) throws DatabaseException
DatabaseException
public void searchDeletableSubTree(IN parent, byte[] key, java.util.ArrayList<com.sleepycat.je.tree.Tree.SplitInfo> nodeLadder) throws DatabaseException, NodeNotEmptyException, CursorsExistException
public IN getRootIN(CacheMode cacheMode) throws DatabaseException
DatabaseException
public IN getRootINLatchedExclusive(CacheMode cacheMode) throws DatabaseException
DatabaseException
public IN getResidentRootIN(boolean latched) throws DatabaseException
DatabaseException
public boolean insert(LN ln, byte[] key, boolean allowDuplicates, CursorImpl cursor, LockResult lnLock, ReplicationContext repContext) throws DatabaseException
ln
- The LN to insert into the tree.key
- Key value for the nodeallowDuplicates
- whether to allow duplicates to be insertedcursor
- the cursor to update to point to the newly inserted
key/data pair, or null if no cursor should be updated.DatabaseException
public int getLogSize()
getLogSize
in interface Loggable
Loggable.getLogSize()
public void writeToLog(java.nio.ByteBuffer logBuffer)
Loggable
writeToLog
in interface Loggable
logBuffer
- is the destination bufferLoggable.writeToLog(java.nio.ByteBuffer)
public void readFromLog(java.nio.ByteBuffer itemBuffer, byte entryVersion)
Loggable
readFromLog
in interface Loggable
Loggable.readFromLog(java.nio.ByteBuffer, byte)
public void dumpLog(java.lang.StringBuffer sb, boolean verbose)
Loggable
dumpLog
in interface Loggable
sb
- destination string bufferverbose
- if true, dump the full, verbose versionLoggable.dumpLog(java.lang.StringBuffer, boolean)
public long getTransactionId()
getTransactionId
in interface Loggable
Loggable.getTransactionId()
public boolean logicalEquals(Loggable other)
logicalEquals
in interface Loggable
Always return false, this item should never be compared.
public void rebuildINList() throws DatabaseException
DatabaseException
public void dump() throws DatabaseException
DatabaseException
public java.lang.String dumpString(int nSpaces) throws DatabaseException
DatabaseException
public void validateINList(IN parent) throws DatabaseException
DatabaseException
public void setWaitHook(TestHook hook)
public void setSearchHook(TestHook hook)
public void setCkptHook(TestHook hook)