001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
005: *
006: * $Id: Node.java,v 1.94.2.3 2008/01/07 15:14:16 cwl Exp $
007: */
008:
009: package com.sleepycat.je.tree;
010:
011: import java.nio.ByteBuffer;
012:
013: import com.sleepycat.je.DatabaseException;
014: import com.sleepycat.je.cleaner.UtilizationTracker;
015: import com.sleepycat.je.dbi.DatabaseImpl;
016: import com.sleepycat.je.dbi.INList;
017: import com.sleepycat.je.latch.LatchNotHeldException;
018: import com.sleepycat.je.log.LogEntryType;
019: import com.sleepycat.je.log.LogException;
020: import com.sleepycat.je.log.LogUtils;
021: import com.sleepycat.je.log.Loggable;
022:
023: /**
024: * A Node contains all the common base information for any JE B-Tree node.
025: */
026: public abstract class Node implements Loggable {
027:
028: /*
029: * The last allocated id. Note that nodeids will be shared
030: * across db environments. lastAllocatedId must be initialized at
031: * startup by Recovery.
032: */
033: public synchronized static void setLastNodeId(long id) {
034: if (lastAllocatedId < id) {
035: lastAllocatedId = id;
036: }
037: }
038:
039: private static long lastAllocatedId = 0;
040:
041: private static final String BEGIN_TAG = "<node>";
042: private static final String END_TAG = "</node>";
043:
044: // The unique id of this node
045: private long nodeId;
046:
047: /**
048: * Disallow use
049: */
050: private Node() {
051: }
052:
053: /**
054: * Create a new node, assigning it the next available node id.
055: */
056: protected Node(boolean init) {
057: if (init) {
058: nodeId = getNextNodeId();
059: }
060: }
061:
062: /**
063: * Increment and return the next usable id. Must be synchronized.
064: */
065: public static synchronized long getNextNodeId() {
066: return ++lastAllocatedId;
067: }
068:
069: /**
070: * Get the latest id, for checkpointing.
071: */
072: public static synchronized long getLastId() {
073: return lastAllocatedId;
074: }
075:
076: /**
077: * Initialize a node that has been faulted in from the log
078: */
079: public void postFetchInit(DatabaseImpl db, long sourceLsn)
080: throws DatabaseException {
081:
082: /* Nothing to do. */
083: }
084:
085: public long getNodeId() {
086: return nodeId;
087: }
088:
089: /* For unit tests only. */
090: void setNodeId(long nid) {
091: nodeId = nid;
092: }
093:
094: public void latchShared() throws DatabaseException {
095:
096: }
097:
098: public void releaseLatch() throws LatchNotHeldException {
099:
100: }
101:
102: public void verify(byte[] maxKey) throws DatabaseException {
103: }
104:
105: /**
106: * @return true if this node is a duplicate-bearing node type, false
107: * if otherwise.
108: */
109: public boolean containsDuplicates() {
110: return false;
111: }
112:
113: /**
114: * Cover for LN's and just return 0 since they'll always be at the bottom
115: * of the tree.
116: */
117: int getLevel() {
118: return 0;
119: }
120:
121: /*
122: * Depth first search through a duplicate tree looking for an LN that
123: * has nodeId. When we find it, set location.bin and index and return
124: * true. If we don't find it, return false.
125: *
126: * No latching is performed.
127: */
128: boolean matchLNByNodeId(TreeLocation location, long nodeId)
129: throws DatabaseException {
130:
131: throw new DatabaseException(
132: "matchLNByNodeId called on non DIN/DBIN");
133: }
134:
135: /**
136: * Add yourself to the in memory list if you're a type of node that
137: * should belong.
138: */
139: abstract void rebuildINList(INList inList) throws DatabaseException;
140:
141: /**
142: * Remove yourself from the in memory list if you're a type of node that
143: * is put there.
144: */
145: abstract void accountForSubtreeRemoval(INList inList,
146: UtilizationTracker tracker) throws DatabaseException;
147:
148: /**
149: * @return true if you're part of a deletable subtree.
150: */
151: abstract boolean isValidForDelete() throws DatabaseException;
152:
153: /**
154: * @return true if you're an IN in the search path
155: */
156: abstract protected boolean isSoughtNode(long nid,
157: boolean updateGeneration) throws DatabaseException;
158:
159: /**
160: * @return true if you can be the ancestor of the target IN.
161: * Currently the determining factor is whether the target IN contains
162: * duplicates.
163: */
164: abstract protected boolean canBeAncestor(
165: boolean targetContainsDuplicates);
166:
167: /**
168: * Return the approximate size of this node in memory, if this
169: * size should be included in it's parents memory accounting.
170: * For example, all INs return 0, because they are accounted for
171: * individually. LNs must return a count, they're not counted on
172: * the INList.
173: */
174: protected long getMemorySizeIncludedByParent() {
175: return 0;
176: }
177:
178: /*
179: * Dumping
180: */
181:
182: /**
183: * Default toString method at the root of the tree.
184: */
185: public String toString() {
186: return this .dumpString(0, true);
187: }
188:
189: private String beginTag() {
190: return BEGIN_TAG;
191: }
192:
193: private String endTag() {
194: return END_TAG;
195: }
196:
197: public void dump(int nSpaces) {
198: System.out.print(dumpString(nSpaces, true));
199: }
200:
201: String dumpString(int nSpaces, boolean dumpTags) {
202: StringBuffer self = new StringBuffer();
203: self.append(TreeUtils.indent(nSpaces));
204: if (dumpTags) {
205: self.append(beginTag());
206: }
207: self.append(nodeId);
208: if (dumpTags) {
209: self.append(endTag());
210: }
211: return self.toString();
212: }
213:
214: public String shortDescription() {
215: return "<" + getType() + "/" + getNodeId();
216: }
217:
218: public String getType() {
219: return getClass().getName();
220: }
221:
222: /**
223: */
224: public abstract LogEntryType getLogType();
225:
226: /*
227: * Logging support
228: */
229:
230: /**
231: * @see Loggable#getLogSize
232: */
233: public int getLogSize() {
234: return LogUtils.LONG_BYTES;
235: }
236:
237: /**
238: * @see Loggable#writeToLog
239: */
240: public void writeToLog(ByteBuffer logBuffer) {
241: LogUtils.writeLong(logBuffer, nodeId);
242: }
243:
244: /**
245: * @see Loggable#readFromLog
246: */
247: public void readFromLog(ByteBuffer itemBuffer, byte entryTypeVersion)
248: throws LogException {
249:
250: nodeId = LogUtils.readLong(itemBuffer);
251: }
252:
253: /**
254: * @see Loggable#dumpLog
255: */
256: public void dumpLog(StringBuffer sb, boolean verbose) {
257: sb.append(BEGIN_TAG);
258: sb.append(nodeId);
259: sb.append(END_TAG);
260: }
261:
262: /**
263: * @see Loggable#getTransactionId
264: */
265: public long getTransactionId() {
266: return 0;
267: }
268: }
|