001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
005: *
006: * $Id: DBIN.java,v 1.70.2.4 2008/01/07 15:14:16 cwl Exp $
007: */
008:
009: package com.sleepycat.je.tree;
010:
011: import java.nio.ByteBuffer;
012: import java.util.Comparator;
013:
014: import com.sleepycat.je.DatabaseException;
015: import com.sleepycat.je.dbi.CursorImpl;
016: import com.sleepycat.je.dbi.DatabaseId;
017: import com.sleepycat.je.dbi.DatabaseImpl;
018: import com.sleepycat.je.dbi.DbConfigManager;
019: import com.sleepycat.je.dbi.MemoryBudget;
020: import com.sleepycat.je.log.LogEntryType;
021: import com.sleepycat.je.log.LogException;
022: import com.sleepycat.je.log.LogUtils;
023: import com.sleepycat.je.log.Loggable;
024:
025: /**
026: * A DBIN represents an Duplicate Bottom Internal Node in the JE tree.
027: */
028: public final class DBIN extends BIN implements Loggable {
029: private static final String BEGIN_TAG = "<dbin>";
030: private static final String END_TAG = "</dbin>";
031:
032: /**
033: * Full key for this set of duplicates.
034: */
035: private byte[] dupKey;
036:
037: public DBIN() {
038: super ();
039: }
040:
041: public DBIN(DatabaseImpl db, byte[] identifierKey,
042: int maxEntriesPerNode, byte[] dupKey, int level) {
043: super (db, identifierKey, maxEntriesPerNode, level);
044: this .dupKey = dupKey;
045: }
046:
047: /**
048: * Create a new DBIN. Need this because we can't call newInstance()
049: * without getting a 0 node.
050: */
051: protected IN createNewInstance(byte[] identifierKey,
052: int maxEntries, int level) {
053: return new DBIN(getDatabase(), identifierKey, maxEntries,
054: dupKey, level);
055: }
056:
057: /*
058: * Return whether the shared latch for this kind of node should be of the
059: * "always exclusive" variety. Presently, only IN's are actually latched
060: * shared. BINs, DINs, and DBINs are all latched exclusive only.
061: */
062: boolean isAlwaysLatchedExclusively() {
063: return true;
064: }
065:
066: /* Duplicates have no mask on their levels. */
067: protected int generateLevel(DatabaseId dbId, int newLevel) {
068: return newLevel;
069: }
070:
071: /**
072: * Return the comparator function to be used for DBINs. This is
073: * the user defined duplicate comparison function, if defined.
074: */
075: public final Comparator getKeyComparator() {
076: return getDatabase().getDuplicateComparator();
077: }
078:
079: /**
080: * Return the key for this duplicate set.
081: */
082: public byte[] getDupKey() {
083: return dupKey;
084: }
085:
086: /**
087: * Get the key (dupe or identifier) in child that is used to locate
088: * it in 'this' node.
089: */
090: public byte[] getChildKey(IN child) throws DatabaseException {
091:
092: return child.getIdentifierKey();
093: }
094:
095: /*
096: * A DBIN uses the dupTree key in its searches.
097: */
098: public byte[] selectKey(byte[] mainTreeKey, byte[] dupTreeKey) {
099: return dupTreeKey;
100: }
101:
102: /**
103: * Return the key for navigating through the duplicate tree.
104: */
105: public byte[] getDupTreeKey() {
106: return getIdentifierKey();
107: }
108:
109: /**
110: * Return the key for navigating through the main tree.
111: */
112: public byte[] getMainTreeKey() {
113: return dupKey;
114: }
115:
116: /**
117: * @return true if this node is a duplicate-bearing node type, false
118: * if otherwise.
119: */
120: public boolean containsDuplicates() {
121: return true;
122: }
123:
124: /**
125: * @return the log entry type to use for bin delta log entries.
126: */
127: LogEntryType getBINDeltaType() {
128: return LogEntryType.LOG_DUP_BIN_DELTA;
129: }
130:
131: public BINReference createReference() {
132: return new DBINReference(getNodeId(), getDatabase().getId(),
133: getIdentifierKey(), dupKey);
134: }
135:
136: /**
137: * Count up the memory usage attributable to this node alone.
138: */
139: protected long computeMemorySize() {
140: long size = super .computeMemorySize();
141: /* XXX Need to update size when changing the dupKey.
142: if (dupKey != null && dupKey.getKey() != null) {
143: size += MemoryBudget.byteArraySize(dupKey.getKey().length);
144: }
145: */
146: return size;
147: }
148:
149: /* Called once at environment startup by MemoryBudget. */
150: public static long computeOverhead(DbConfigManager configManager)
151: throws DatabaseException {
152:
153: /*
154: * Overhead consists of all the fields in this class plus the
155: * entry arrays in the IN class.
156: */
157: return MemoryBudget.DBIN_FIXED_OVERHEAD
158: + IN.computeArraysOverhead(configManager);
159: }
160:
161: protected long getMemoryOverhead(MemoryBudget mb) {
162: return mb.getDBINOverhead();
163: }
164:
165: /*
166: * A DBIN cannot be the ancestor of any IN.
167: */
168: protected boolean canBeAncestor(boolean targetContainsDuplicates) {
169: return false;
170: }
171:
172: /**
173: * @Override
174: */
175: boolean hasPinnedChildren() {
176: return false;
177: }
178:
179: /**
180: * The following four methods access the correct fields in a
181: * cursor depending on whether "this" is a BIN or DBIN. For
182: * BIN's, the CursorImpl.index and CursorImpl.bin fields should be
183: * used. For DBIN's, the CursorImpl.dupIndex and CursorImpl.dupBin
184: * fields should be used.
185: */
186: BIN getCursorBIN(CursorImpl cursor) {
187: return cursor.getDupBIN();
188: }
189:
190: BIN getCursorBINToBeRemoved(CursorImpl cursor) {
191: return cursor.getDupBINToBeRemoved();
192: }
193:
194: int getCursorIndex(CursorImpl cursor) {
195: return cursor.getDupIndex();
196: }
197:
198: void setCursorBIN(CursorImpl cursor, BIN bin) {
199: cursor.setDupBIN((DBIN) bin);
200: }
201:
202: void setCursorIndex(CursorImpl cursor, int index) {
203: cursor.setDupIndex(index);
204: }
205:
206: /*
207: * Depth first search through a duplicate tree looking for an LN that
208: * has nodeId. When we find it, set location.bin and index and return
209: * true. If we don't find it, return false.
210: *
211: * No latching is performed.
212: */
213: boolean matchLNByNodeId(TreeLocation location, long nodeId)
214: throws DatabaseException {
215:
216: latch();
217: try {
218: for (int i = 0; i < getNEntries(); i++) {
219: LN ln = (LN) fetchTarget(i);
220: if (ln != null) {
221: if (ln.getNodeId() == nodeId) {
222: location.bin = this ;
223: location.index = i;
224: location.lnKey = getKey(i);
225: location.childLsn = getLsn(i);
226: return true;
227: }
228: }
229: }
230:
231: return false;
232: } finally {
233: releaseLatch();
234: }
235: }
236:
237: /*
238: * DbStat support.
239: */
240: void accumulateStats(TreeWalkerStatsAccumulator acc) {
241: acc.processDBIN(this , new Long(getNodeId()), getLevel());
242: }
243:
244: public String beginTag() {
245: return BEGIN_TAG;
246: }
247:
248: public String endTag() {
249: return END_TAG;
250: }
251:
252: /**
253: * For unit test support:
254: * @return a string that dumps information about this IN, without
255: */
256: public String dumpString(int nSpaces, boolean dumpTags) {
257: StringBuffer sb = new StringBuffer();
258: sb.append(TreeUtils.indent(nSpaces));
259: sb.append(beginTag());
260: sb.append('\n');
261:
262: sb.append(TreeUtils.indent(nSpaces + 2));
263: sb.append("<dupkey>");
264: sb.append(dupKey == null ? "" : Key.dumpString(dupKey, 0));
265: sb.append("</dupkey>");
266: sb.append('\n');
267:
268: sb.append(super .dumpString(nSpaces, false));
269:
270: sb.append(TreeUtils.indent(nSpaces));
271: sb.append(endTag());
272: return sb.toString();
273: }
274:
275: /**
276: * @see Node#getLogType()
277: */
278: public LogEntryType getLogType() {
279: return LogEntryType.LOG_DBIN;
280: }
281:
282: /*
283: * Logging support
284: */
285:
286: /**
287: * @see Loggable#getLogSize
288: */
289: public int getLogSize() {
290: int size = super .getLogSize(); // ancestors
291: size += LogUtils.getByteArrayLogSize(dupKey); // identifier key
292: return size;
293: }
294:
295: /**
296: * @see Loggable#writeToLog
297: */
298: public void writeToLog(ByteBuffer logBuffer) {
299:
300: // ancestors
301: super .writeToLog(logBuffer);
302:
303: // identifier key
304: LogUtils.writeByteArray(logBuffer, dupKey);
305: }
306:
307: /**
308: * @see BIN#readFromLog
309: */
310: public void readFromLog(ByteBuffer itemBuffer, byte entryTypeVersion)
311: throws LogException {
312:
313: // ancestors
314: super .readFromLog(itemBuffer, entryTypeVersion);
315:
316: // identifier key
317: dupKey = LogUtils.readByteArray(itemBuffer);
318: }
319:
320: /**
321: * DBINS need to dump their dup key
322: */
323: protected void dumpLogAdditional(StringBuffer sb) {
324: super .dumpLogAdditional(sb);
325: sb.append(Key.dumpString(dupKey, 0));
326: }
327:
328: public String shortClassName() {
329: return "DBIN";
330: }
331: }
|