001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
005: *
006: * $Id: DIN.java,v 1.79.2.7 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.cleaner.Cleaner;
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.EnvironmentImpl;
020: import com.sleepycat.je.dbi.MemoryBudget;
021: import com.sleepycat.je.log.LogEntryType;
022: import com.sleepycat.je.log.LogException;
023: import com.sleepycat.je.log.LogManager;
024: import com.sleepycat.je.log.LogUtils;
025: import com.sleepycat.je.txn.LockResult;
026: import com.sleepycat.je.txn.Locker;
027:
028: /**
029: * An DIN represents an Duplicate Internal Node in the JE tree.
030: */
031: public final class DIN extends IN {
032:
033: private static final String BEGIN_TAG = "<din>";
034: private static final String END_TAG = "</din>";
035:
036: /**
037: * Full key for this set of duplicates.
038: */
039: private byte[] dupKey;
040:
041: /**
042: * Reference to DupCountLN which stores the count.
043: */
044: private ChildReference dupCountLNRef;
045:
046: /**
047: * Create an empty DIN, with no node id, to be filled in from the log.
048: */
049: public DIN() {
050: super ();
051:
052: dupCountLNRef = new ChildReference();
053: init(null, Key.EMPTY_KEY, 0, 0);
054: }
055:
056: /**
057: * Create a new DIN.
058: */
059: public DIN(DatabaseImpl db, byte[] identifierKey, int capacity,
060: byte[] dupKey, ChildReference dupCountLNRef, int level) {
061: super (db, identifierKey, capacity, level);
062:
063: this .dupKey = dupKey;
064: this .dupCountLNRef = dupCountLNRef;
065: initMemorySize(); // init after adding Dup Count LN. */
066: }
067:
068: /* Duplicates have no mask on their levels. */
069: protected int generateLevel(DatabaseId dbId, int newLevel) {
070: return newLevel;
071: }
072:
073: /**
074: * Create a new DIN. Need this because we can't call newInstance()
075: * without getting a 0 node.
076: */
077: protected IN createNewInstance(byte[] identifierKey,
078: int maxEntries, int level) {
079: return new DIN(getDatabase(), identifierKey, maxEntries,
080: dupKey, dupCountLNRef, level);
081: }
082:
083: /*
084: * Return whether the shared latch for this kind of node should be of the
085: * "always exclusive" variety. Presently, only IN's are actually latched
086: * shared. BINs, DINs, and DBINs are all latched exclusive only.
087: */
088: boolean isAlwaysLatchedExclusively() {
089: return true;
090: }
091:
092: /**
093: * Return the key for this duplicate set.
094: */
095: public byte[] getDupKey() {
096: return dupKey;
097: }
098:
099: /**
100: * Get the key (dupe or identifier) in child that is used to locate
101: * it in 'this' node.
102: */
103: public byte[] getChildKey(IN child) throws DatabaseException {
104:
105: return child.getIdentifierKey();
106: }
107:
108: /*
109: * A DIN uses the dupTree key in its searches.
110: */
111: public byte[] selectKey(byte[] mainTreeKey, byte[] dupTreeKey) {
112: return dupTreeKey;
113: }
114:
115: /**
116: * Return the key for navigating through the duplicate tree.
117: */
118: public byte[] getDupTreeKey() {
119: return getIdentifierKey();
120: }
121:
122: /**
123: * Return the key for navigating through the main tree.
124: */
125: public byte[] getMainTreeKey() {
126: return dupKey;
127: }
128:
129: public ChildReference getDupCountLNRef() {
130: return dupCountLNRef;
131: }
132:
133: public DupCountLN getDupCountLN() throws DatabaseException {
134:
135: return (DupCountLN) dupCountLNRef.fetchTarget(getDatabase(),
136: this );
137: }
138:
139: /*
140: * All methods that modify the dup count LN must adjust memory sizing.
141: */
142:
143: /**
144: * Assign the Dup Count LN.
145: */
146: void setDupCountLN(ChildReference dupCountLNRef) {
147: updateMemorySize(this .dupCountLNRef, dupCountLNRef);
148: this .dupCountLNRef = dupCountLNRef;
149: }
150:
151: /**
152: * Assign the Dup Count LN node. Does not dirty the DIN.
153: */
154: public void updateDupCountLN(Node target) {
155: long oldSize = getEntryInMemorySize(dupCountLNRef.getKey(),
156: dupCountLNRef.getTarget());
157: dupCountLNRef.setTarget(target);
158: long newSize = getEntryInMemorySize(dupCountLNRef.getKey(),
159: dupCountLNRef.getTarget());
160: updateMemorySize(oldSize, newSize);
161: }
162:
163: /**
164: * Update Dup Count LN.
165: */
166: public void updateDupCountLNRefAndNullTarget(long newLsn) {
167: setDirty(true);
168: long oldSize = getEntryInMemorySize(dupCountLNRef.getKey(),
169: dupCountLNRef.getTarget());
170: dupCountLNRef.setTarget(null);
171: if (notOverwritingDeferredWriteEntry(newLsn)) {
172: dupCountLNRef.setLsn(newLsn);
173: }
174: long newSize = getEntryInMemorySize(dupCountLNRef.getKey(),
175: dupCountLNRef.getTarget());
176: updateMemorySize(oldSize, newSize);
177: }
178:
179: /**
180: * Update dup count LSN.
181: */
182: public void updateDupCountLNRef(long newLsn) {
183: setDirty(true);
184: if (notOverwritingDeferredWriteEntry(newLsn)) {
185: dupCountLNRef.setLsn(newLsn);
186: }
187: }
188:
189: /**
190: * @return true if this node is a duplicate-bearing node type, false
191: * if otherwise.
192: */
193: public boolean containsDuplicates() {
194: return true;
195: }
196:
197: /* Never true for a DIN. */
198: public boolean isDbRoot() {
199: return false;
200: }
201:
202: /**
203: * Return the comparator function to be used for DINs. This is
204: * the user defined duplicate comparison function, if defined.
205: */
206: public final Comparator getKeyComparator() {
207: return getDatabase().getDuplicateComparator();
208: }
209:
210: /**
211: * Increment or decrement the DupCountLN, log the updated LN, and update
212: * the lock result.
213: *
214: * Preconditions: This DIN is latched and the DupCountLN is write locked.
215: * Postconditions: Same as preconditions.
216: */
217: public void incrementDuplicateCount(LockResult lockResult,
218: byte[] key, Locker locker, boolean increment)
219: throws DatabaseException {
220:
221: /* Increment/decrement the dup count and update its owning DIN. */
222: long oldLsn = dupCountLNRef.getLsn();
223: lockResult.setAbortLsn(oldLsn, dupCountLNRef.isKnownDeleted());
224: DupCountLN dupCountLN = getDupCountLN();
225: if (increment) {
226: dupCountLN.incDupCount();
227: } else {
228: dupCountLN.decDupCount();
229: assert dupCountLN.getDupCount() >= 0;
230: }
231: DatabaseImpl db = getDatabase();
232: long newCountLSN = dupCountLN.optionalLogUpdateMemUsage(db,
233: key, oldLsn, locker, this );
234: updateDupCountLNRef(newCountLSN);
235: }
236:
237: /**
238: * Count up the memory usage attributable to this node alone. LNs children
239: * are counted by their BIN/DIN parents, but INs are not counted by
240: * their parents because they are resident on the IN list.
241: */
242: protected long computeMemorySize() {
243: long size = super .computeMemorySize();
244: if (dupCountLNRef != null) {
245: size += getEntryInMemorySize(dupCountLNRef.getKey(),
246: dupCountLNRef.getTarget());
247: }
248: /* XXX Need to update size when changing the dupKey.
249: if (dupKey != null && dupKey.getKey() != null) {
250: size += MemoryBudget.byteArraySize(dupKey.getKey().length);
251: }
252: */
253: return size;
254: }
255:
256: /* Called once at environment startup by MemoryBudget. */
257: public static long computeOverhead(DbConfigManager configManager)
258: throws DatabaseException {
259:
260: /*
261: * Overhead consists of all the fields in this class plus the
262: * entry arrays in the IN class.
263: */
264: return MemoryBudget.DIN_FIXED_OVERHEAD
265: + IN.computeArraysOverhead(configManager);
266: }
267:
268: protected long getMemoryOverhead(MemoryBudget mb) {
269: return mb.getDINOverhead();
270: }
271:
272: /*
273: * Depth first search through a duplicate tree looking for an LN that
274: * has nodeId. When we find it, set location.bin and index and return
275: * true. If we don't find it, return false.
276: *
277: * No latching is performed.
278: */
279: boolean matchLNByNodeId(TreeLocation location, long nodeId)
280: throws DatabaseException {
281:
282: latch();
283: try {
284: for (int i = 0; i < getNEntries(); i++) {
285: Node n = fetchTarget(i);
286: if (n != null) {
287: boolean ret = n.matchLNByNodeId(location, nodeId);
288: if (ret) {
289: return true;
290: }
291: }
292: }
293:
294: return false;
295: } finally {
296: releaseLatch();
297: }
298: }
299:
300: /*
301: * DbStat support.
302: */
303: void accumulateStats(TreeWalkerStatsAccumulator acc) {
304: acc.processDIN(this , new Long(getNodeId()), getLevel());
305: }
306:
307: /*
308: * Logging Support
309: */
310:
311: /**
312: * @see Node#getLogType
313: */
314: public LogEntryType getLogType() {
315: return LogEntryType.LOG_DIN;
316: }
317:
318: /**
319: * Handles lazy migration of DupCountLNs prior to logging a DIN. See
320: * BIN.logInternal for more information.
321: */
322: protected long logInternal(LogManager logManager,
323: boolean allowDeltas, boolean isProvisional,
324: boolean proactiveMigration, boolean backgroundIO, IN parent)
325: throws DatabaseException {
326:
327: if (dupCountLNRef != null) {
328: EnvironmentImpl envImpl = getDatabase().getDbEnvironment();
329: DupCountLN dupCntLN = (DupCountLN) dupCountLNRef
330: .getTarget();
331:
332: if ((dupCntLN != null) && (dupCntLN.isDirty())) {
333:
334: /*
335: * If deferred write, write any dirty LNs now. The old LSN
336: * is NULL_LSN, a no-opt in non-txnal deferred write mode.
337: */
338: long newLsn = dupCntLN.logUpdateMemUsage(getDatabase(),
339: dupKey, dupCountLNRef.getLsn() /*oldLsn*/,
340: null /*locker*/, this , backgroundIO);
341: dupCountLNRef.setLsn(newLsn);
342: } else {
343:
344: /*
345: * Allow the cleaner to migrate the DupCountLN before logging.
346: */
347: Cleaner cleaner = getDatabase().getDbEnvironment()
348: .getCleaner();
349: cleaner.lazyMigrateDupCountLN(this , dupCountLNRef,
350: proactiveMigration);
351: }
352: }
353:
354: return super
355: .logInternal(logManager, allowDeltas, isProvisional,
356: proactiveMigration, backgroundIO, parent);
357: }
358:
359: /**
360: * @see IN#getLogSize
361: */
362: public int getLogSize() {
363: int size = super .getLogSize(); // ancestors
364: size += LogUtils.getByteArrayLogSize(dupKey);// identifier key
365: size += LogUtils.getBooleanLogSize(); // dupCountLNRef null flag
366: if (dupCountLNRef != null) {
367: size += dupCountLNRef.getLogSize();
368: }
369: return size;
370: }
371:
372: /**
373: * @see IN#writeToLog
374: */
375: public void writeToLog(ByteBuffer logBuffer) {
376:
377: // ancestors
378: super .writeToLog(logBuffer);
379:
380: // identifier key
381: LogUtils.writeByteArray(logBuffer, dupKey);
382:
383: /* DupCountLN */
384: boolean dupCountLNRefExists = (dupCountLNRef != null);
385: LogUtils.writeBoolean(logBuffer, dupCountLNRefExists);
386: if (dupCountLNRefExists) {
387: dupCountLNRef.writeToLog(logBuffer);
388: }
389: }
390:
391: /**
392: * @see IN#readFromLog
393: */
394: public void readFromLog(ByteBuffer itemBuffer, byte entryTypeVersion)
395: throws LogException {
396:
397: // ancestors
398: super .readFromLog(itemBuffer, entryTypeVersion);
399:
400: // identifier key
401: dupKey = LogUtils.readByteArray(itemBuffer);
402:
403: /* DupCountLN */
404: boolean dupCountLNRefExists = LogUtils.readBoolean(itemBuffer);
405: if (dupCountLNRefExists) {
406: dupCountLNRef.readFromLog(itemBuffer, entryTypeVersion);
407: } else {
408: dupCountLNRef = null;
409: }
410: }
411:
412: /**
413: * DINS need to dump their dup key
414: */
415: protected void dumpLogAdditional(StringBuffer sb) {
416: super .dumpLogAdditional(sb);
417: sb.append(Key.dumpString(dupKey, 0));
418: if (dupCountLNRef != null) {
419: dupCountLNRef.dumpLog(sb, true);
420: }
421: }
422:
423: /*
424: * Dumping
425: */
426:
427: public String beginTag() {
428: return BEGIN_TAG;
429: }
430:
431: public String endTag() {
432: return END_TAG;
433: }
434:
435: /**
436: * For unit test support:
437: * @return a string that dumps information about this DIN, without
438: */
439: public String dumpString(int nSpaces, boolean dumpTags) {
440: StringBuffer sb = new StringBuffer();
441: if (dumpTags) {
442: sb.append(TreeUtils.indent(nSpaces));
443: sb.append(beginTag());
444: sb.append('\n');
445: }
446:
447: sb.append(TreeUtils.indent(nSpaces + 2));
448: sb.append("<dupkey>");
449: sb.append(dupKey == null ? "" : Key.dumpString(dupKey, 0));
450: sb.append("</dupkey>");
451: sb.append('\n');
452: if (dupCountLNRef == null) {
453: sb.append(TreeUtils.indent(nSpaces + 2));
454: sb.append("<dupCountLN/>");
455: } else {
456: sb.append(dupCountLNRef.dumpString(nSpaces + 4, true));
457: }
458: sb.append('\n');
459: sb.append(super .dumpString(nSpaces, false));
460:
461: if (dumpTags) {
462: sb.append(TreeUtils.indent(nSpaces));
463: sb.append(endTag());
464: }
465: return sb.toString();
466: }
467:
468: public String toString() {
469: return dumpString(0, true);
470: }
471:
472: public String shortClassName() {
473: return "DIN";
474: }
475: }
|