KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sleepycat > je > tree > DIN


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: DIN.java,v 1.78 2006/11/17 23:47:27 mark Exp $
7  */
8
9 package com.sleepycat.je.tree;
10
11 import java.nio.ByteBuffer JavaDoc;
12 import java.util.Comparator JavaDoc;
13
14 import com.sleepycat.je.DatabaseException;
15 import com.sleepycat.je.cleaner.Cleaner;
16 import com.sleepycat.je.dbi.DatabaseId;
17 import com.sleepycat.je.dbi.DatabaseImpl;
18 import com.sleepycat.je.dbi.DbConfigManager;
19 import com.sleepycat.je.dbi.EnvironmentImpl;
20 import com.sleepycat.je.dbi.MemoryBudget;
21 import com.sleepycat.je.log.LogEntryType;
22 import com.sleepycat.je.log.LogException;
23 import com.sleepycat.je.log.LogManager;
24 import com.sleepycat.je.log.LogUtils;
25 import com.sleepycat.je.txn.LockResult;
26 import com.sleepycat.je.txn.Locker;
27 import com.sleepycat.je.utilint.DbLsn;
28
29 /**
30  * An DIN represents an Duplicate Internal Node in the JE tree.
31  */
32 public final class DIN extends IN {
33
34     private static final String JavaDoc BEGIN_TAG = "<din>";
35     private static final String JavaDoc END_TAG = "</din>";
36
37     /**
38      * Full key for this set of duplicates.
39      */
40     private byte[] dupKey;
41
42     /**
43      * Reference to DupCountLN which stores the count.
44      */
45     private ChildReference dupCountLNRef;
46
47     /**
48      * Create an empty DIN, with no node id, to be filled in from the log.
49      */
50     public DIN() {
51         super();
52
53         dupCountLNRef = new ChildReference();
54         init(null, Key.EMPTY_KEY, 0, 0);
55     }
56
57     /**
58      * Create a new DIN.
59      */
60     public DIN(DatabaseImpl db,
61            byte[] identifierKey,
62            int capacity,
63                byte[] dupKey,
64            ChildReference dupCountLNRef,
65            int level) {
66         super(db, identifierKey, capacity, level);
67
68         this.dupKey = dupKey;
69         this.dupCountLNRef = dupCountLNRef;
70         initMemorySize(); // init after adding Dup Count LN. */
71 }
72
73     /* Duplicates have no mask on their levels. */
74     protected int generateLevel(DatabaseId dbId, int newLevel) {
75         return newLevel;
76     }
77
78     /**
79      * Create a new DIN. Need this because we can't call newInstance()
80      * without getting a 0 node.
81      */
82     protected IN createNewInstance(byte[] identifierKey,
83                                    int maxEntries,
84                                    int level) {
85         return new DIN(getDatabase(),
86                        identifierKey,
87                        maxEntries,
88                        dupKey,
89                        dupCountLNRef,
90                        level);
91     }
92
93     /*
94      * Return whether the shared latch for this kind of node should be of the
95      * "always exclusive" variety. Presently, only IN's are actually latched
96      * shared. BINs, DINs, and DBINs are all latched exclusive only.
97      */
98     boolean isAlwaysLatchedExclusively() {
99     return true;
100     }
101
102     /**
103      * Return the key for this duplicate set.
104      */
105     public byte[] getDupKey() {
106         return dupKey;
107     }
108
109     /**
110      * Get the key (dupe or identifier) in child that is used to locate
111      * it in 'this' node.
112      */
113     public byte[] getChildKey(IN child)
114         throws DatabaseException {
115
116         return child.getIdentifierKey();
117     }
118
119     /*
120      * A DIN uses the dupTree key in its searches.
121      */
122     public byte[] selectKey(byte[] mainTreeKey, byte[] dupTreeKey) {
123         return dupTreeKey;
124     }
125
126     /**
127      * Return the key for navigating through the duplicate tree.
128      */
129     public byte[] getDupTreeKey() {
130         return getIdentifierKey();
131     }
132
133     /**
134      * Return the key for navigating through the main tree.
135      */
136     public byte[] getMainTreeKey() {
137         return dupKey;
138     }
139
140     public ChildReference getDupCountLNRef() {
141         return dupCountLNRef;
142     }
143
144     public DupCountLN getDupCountLN()
145         throws DatabaseException {
146
147         return (DupCountLN) dupCountLNRef.fetchTarget(getDatabase(), this);
148     }
149
150     /*
151      * All methods that modify the dup count LN must adjust memory sizing.
152      */
153
154     /**
155      * Assign the Dup Count LN.
156      */
157     void setDupCountLN(ChildReference dupCountLNRef) {
158         updateMemorySize(this.dupCountLNRef, dupCountLNRef);
159         this.dupCountLNRef = dupCountLNRef;
160     }
161
162     /**
163      * Assign the Dup Count LN node. Does not dirty the DIN.
164      */
165     public void updateDupCountLN(Node target) {
166         long oldSize = getEntryInMemorySize(dupCountLNRef.getKey(),
167                             dupCountLNRef.getTarget());
168         dupCountLNRef.setTarget(target);
169         long newSize = getEntryInMemorySize(dupCountLNRef.getKey(),
170                             dupCountLNRef.getTarget());
171         updateMemorySize(oldSize, newSize);
172     }
173
174     /**
175      * Update Dup Count LN.
176      */
177     public void updateDupCountLNRefAndNullTarget(long newLsn) {
178         setDirty(true);
179         long oldSize = getEntryInMemorySize(dupCountLNRef.getKey(),
180                             dupCountLNRef.getTarget());
181         dupCountLNRef.setTarget(null);
182         if (notOverwritingDeferredWriteEntry(newLsn)) {
183             dupCountLNRef.setLsn(newLsn);
184         }
185         long newSize = getEntryInMemorySize(dupCountLNRef.getKey(),
186                             dupCountLNRef.getTarget());
187         updateMemorySize(oldSize, newSize);
188     }
189
190     /**
191      * Update dup count LSN.
192      */
193     public void updateDupCountLNRef(long newLsn) {
194         setDirty(true);
195         if (notOverwritingDeferredWriteEntry(newLsn)) {
196             dupCountLNRef.setLsn(newLsn);
197         }
198     }
199
200     /**
201      * @return true if this node is a duplicate-bearing node type, false
202      * if otherwise.
203      */
204     public boolean containsDuplicates() {
205         return true;
206     }
207
208     /* Never true for a DIN. */
209     public boolean isDbRoot() {
210     return false;
211     }
212
213     /**
214      * Return the comparator function to be used for DINs. This is
215      * the user defined duplicate comparison function, if defined.
216      */
217     public final Comparator JavaDoc getKeyComparator() {
218         return getDatabase().getDuplicateComparator();
219     }
220
221     /**
222      * Increment or decrement the DupCountLN, log the updated LN, and update
223      * the lock result.
224      *
225      * Preconditions: This DIN is latched and the DupCountLN is write locked.
226      * Postconditions: Same as preconditions.
227      */
228     public void incrementDuplicateCount(LockResult lockResult,
229                                         byte[] key,
230                                         Locker locker,
231                                         boolean increment)
232         throws DatabaseException {
233
234         /* Increment/decrement the dup count and update its owning DIN. */
235         long oldLsn = dupCountLNRef.getLsn();
236         lockResult.setAbortLsn(oldLsn, dupCountLNRef.isKnownDeleted());
237         DupCountLN dupCountLN = getDupCountLN();
238         int oldSize = dupCountLN.getTotalLastLoggedSize(key);
239         if (increment) {
240             dupCountLN.incDupCount();
241         } else {
242             dupCountLN.decDupCount();
243         assert dupCountLN.getDupCount() >= 0;
244         }
245         DatabaseImpl db = getDatabase();
246         long newCountLSN = dupCountLN.optionalLog
247             (db.getDbEnvironment(), db, key, oldLsn, oldSize, locker);
248         updateDupCountLNRef(newCountLSN);
249             
250     }
251
252     /**
253      * Count up the memory usage attributable to this node alone. LNs children
254      * are counted by their BIN/DIN parents, but INs are not counted by
255      * their parents because they are resident on the IN list.
256      */
257     protected long computeMemorySize() {
258         long size = super.computeMemorySize();
259         if (dupCountLNRef != null) {
260             size += getEntryInMemorySize(dupCountLNRef.getKey(),
261                          dupCountLNRef.getTarget());
262         }
263         /* XXX Need to update size when changing the dupKey.
264        if (dupKey != null && dupKey.getKey() != null) {
265        size += MemoryBudget.byteArraySize(dupKey.getKey().length);
266        }
267         */
268         return size;
269     }
270
271     /* Called once at environment startup by MemoryBudget. */
272     public static long computeOverhead(DbConfigManager configManager)
273         throws DatabaseException {
274
275         /*
276      * Overhead consists of all the fields in this class plus the
277      * entry arrays in the IN class.
278          */
279         return MemoryBudget.DIN_FIXED_OVERHEAD +
280         IN.computeArraysOverhead(configManager);
281     }
282     
283     protected long getMemoryOverhead(MemoryBudget mb) {
284         return mb.getDINOverhead();
285     }
286
287     /*
288      * Depth first search through a duplicate tree looking for an LN that
289      * has nodeId. When we find it, set location.bin and index and return
290      * true. If we don't find it, return false.
291      *
292      * No latching is performed.
293      */
294     boolean matchLNByNodeId(TreeLocation location, long nodeId)
295     throws DatabaseException {
296
297     latch();
298     try {
299         for (int i = 0; i < getNEntries(); i++) {
300         Node n = fetchTarget(i);
301         if (n != null) {
302             boolean ret = n.matchLNByNodeId(location, nodeId);
303             if (ret) {
304             return true;
305             }
306         }
307         }
308
309         return false;
310     } finally {
311         releaseLatch();
312     }
313     }
314
315     /*
316      * DbStat support.
317      */
318     void accumulateStats(TreeWalkerStatsAccumulator acc) {
319     acc.processDIN(this, new Long JavaDoc(getNodeId()), getLevel());
320     }
321
322     /*
323      * Logging Support
324      */
325
326     /**
327      * @see IN#getLogType
328      */
329     public LogEntryType getLogType() {
330         return LogEntryType.LOG_DIN;
331     }
332
333     /**
334      * Handles lazy migration of DupCountLNs prior to logging a DIN. See
335      * BIN.logInternal for more information.
336      */
337     protected long logInternal(LogManager logManager,
338                    boolean allowDeltas,
339                    boolean isProvisional,
340                                boolean proactiveMigration,
341                                boolean backgroundIO,
342                                IN parent)
343         throws DatabaseException {
344
345
346         if (dupCountLNRef != null) {
347             EnvironmentImpl envImpl = getDatabase().getDbEnvironment();
348             DupCountLN dupCntLN = (DupCountLN) dupCountLNRef.getTarget();
349
350             if ((dupCntLN != null) && (dupCntLN.isDirty())) {
351
352                 /*
353                  * If deferred write, write any dirty LNs now. The old LSN
354                  * is NULL_LSN, a no-opt in non-txnal deferred write mode.
355                  */
356                 long newLsn = dupCntLN.log(envImpl,
357                                            getDatabaseId(),
358                                            dupKey,
359                                            DbLsn.NULL_LSN,// old lsn
360 0, // obsolete size
361 null, // locker
362 false); // backgroundIO
363 dupCountLNRef.setLsn(newLsn);
364             } else {
365
366                 /*
367                  * Allow the cleaner to migrate the DupCountLN before logging.
368                  */
369                 Cleaner cleaner =
370                     getDatabase().getDbEnvironment().getCleaner();
371                 cleaner.lazyMigrateDupCountLN
372                     (this, dupCountLNRef, proactiveMigration);
373             }
374         }
375
376         return super.logInternal
377             (logManager, allowDeltas, isProvisional, proactiveMigration,
378              backgroundIO, parent);
379     }
380
381     /**
382      * @see IN#getLogSize
383      */
384     public int getLogSize() {
385         int size = super.getLogSize(); // ancestors
386 size += LogUtils.getByteArrayLogSize(dupKey);// identifier key
387 size += LogUtils.getBooleanLogSize(); // dupCountLNRef null flag
388 if (dupCountLNRef != null) {
389             size += dupCountLNRef.getLogSize();
390         }
391         return size;
392     }
393
394     /**
395      * @see IN#writeToLog
396      */
397     public void writeToLog(ByteBuffer JavaDoc logBuffer) {
398
399         // ancestors
400 super.writeToLog(logBuffer);
401
402         // identifier key
403 LogUtils.writeByteArray(logBuffer, dupKey);
404
405         /* DupCountLN */
406         boolean dupCountLNRefExists = (dupCountLNRef != null);
407         LogUtils.writeBoolean(logBuffer, dupCountLNRefExists);
408         if (dupCountLNRefExists) {
409             dupCountLNRef.writeToLog(logBuffer);
410         }
411     }
412
413     /**
414      * @see IN#readFromLog
415      */
416     public void readFromLog(ByteBuffer JavaDoc itemBuffer, byte entryTypeVersion)
417         throws LogException {
418
419         // ancestors
420 super.readFromLog(itemBuffer, entryTypeVersion);
421
422         // identifier key
423 dupKey = LogUtils.readByteArray(itemBuffer);
424
425         /* DupCountLN */
426         boolean dupCountLNRefExists = LogUtils.readBoolean(itemBuffer);
427         if (dupCountLNRefExists) {
428             dupCountLNRef.readFromLog(itemBuffer, entryTypeVersion);
429         } else {
430             dupCountLNRef = null;
431         }
432     }
433     
434     /**
435      * DINS need to dump their dup key
436      */
437     protected void dumpLogAdditional(StringBuffer JavaDoc sb) {
438         super.dumpLogAdditional(sb);
439         sb.append(Key.dumpString(dupKey, 0));
440         if (dupCountLNRef != null) {
441             dupCountLNRef.dumpLog(sb, true);
442         }
443     }
444
445     /*
446      * Dumping
447      */
448
449     public String JavaDoc beginTag() {
450         return BEGIN_TAG;
451     }
452
453     public String JavaDoc endTag() {
454         return END_TAG;
455     }
456
457     /**
458      * For unit test support:
459      * @return a string that dumps information about this DIN, without
460      */
461     public String JavaDoc dumpString(int nSpaces, boolean dumpTags) {
462         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
463         if (dumpTags) {
464             sb.append(TreeUtils.indent(nSpaces));
465             sb.append(beginTag());
466             sb.append('\n');
467         }
468
469         sb.append(TreeUtils.indent(nSpaces+2));
470         sb.append("<dupkey>");
471         sb.append(dupKey == null ? "" :
472                   Key.dumpString(dupKey, 0));
473         sb.append("</dupkey>");
474         sb.append('\n');
475         if (dupCountLNRef == null) {
476         sb.append(TreeUtils.indent(nSpaces+2));
477             sb.append("<dupCountLN/>");
478         } else {
479             sb.append(dupCountLNRef.dumpString(nSpaces + 4, true));
480         }
481         sb.append('\n');
482         sb.append(super.dumpString(nSpaces, false));
483
484         if (dumpTags) {
485             sb.append(TreeUtils.indent(nSpaces));
486             sb.append(endTag());
487         }
488         return sb.toString();
489     }
490
491     public String JavaDoc toString() {
492         return dumpString(0, true);
493     }
494
495     public String JavaDoc shortClassName() {
496         return "DIN";
497     }
498 }
499
Popular Tags