KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: LN.java,v 1.124 2006/11/17 23:47:28 mark Exp $
7  */
8
9 package com.sleepycat.je.tree;
10
11 import java.nio.ByteBuffer JavaDoc;
12
13 import com.sleepycat.je.DatabaseEntry;
14 import com.sleepycat.je.DatabaseException;
15 import com.sleepycat.je.cleaner.UtilizationTracker;
16 import com.sleepycat.je.dbi.DatabaseId;
17 import com.sleepycat.je.dbi.DatabaseImpl;
18 import com.sleepycat.je.dbi.EnvironmentImpl;
19 import com.sleepycat.je.dbi.INList;
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.LogReadable;
25 import com.sleepycat.je.log.LogUtils;
26 import com.sleepycat.je.log.LoggableObject;
27 import com.sleepycat.je.log.entry.DeletedDupLNLogEntry;
28 import com.sleepycat.je.log.entry.LNLogEntry;
29 import com.sleepycat.je.txn.Locker;
30 import com.sleepycat.je.txn.Txn;
31 import com.sleepycat.je.txn.WriteLockInfo;
32 import com.sleepycat.je.utilint.DbLsn;
33
34 /**
35  * An LN represents a Leaf Node in the JE tree.
36  */
37 public class LN extends Node implements LoggableObject, LogReadable {
38     private static final String JavaDoc BEGIN_TAG = "<ln>";
39     private static final String JavaDoc END_TAG = "</ln>";
40
41     private byte[] data;
42
43     /*
44      * States: bit fields
45      *
46      * Dirty means that the in-memory version is not present on disk.
47      *
48      * Transactional means that the LN was logged in a transactional log entry.
49      */
50     private static final byte DIRTY_BIT = 0x1;
51     private static final byte CLEAR_DIRTY_BIT = ~0x1;
52     private static final byte TXN_BIT = 0x2;
53     private static final byte CLEAR_TXN_BIT = ~0x2;
54     private byte state; // not persistent
55
56     /**
57      * Create an empty LN, to be filled in from the log.
58      */
59     public LN() {
60         super(false);
61         this.data = null;
62     }
63     
64     /**
65      * Create a new LN from a byte array.
66      */
67     public LN(byte[] data) {
68         super(true);
69         if (data == null) {
70             this.data = null;
71         } else {
72             init(data, 0, data.length);
73         }
74         setDirty();
75     }
76     
77     /**
78      * Create a new LN from a DatabaseEntry.
79      */
80     public LN(DatabaseEntry dbt) {
81         super(true);
82         byte[] data = dbt.getData();
83         if (data == null) {
84             this.data = null;
85         } else if (dbt.getPartial()) {
86             init(data,
87                  dbt.getOffset(),
88                  dbt.getPartialOffset() + dbt.getSize(),
89                  dbt.getPartialOffset(),
90                  dbt.getSize());
91         } else {
92             init(data, dbt.getOffset(), dbt.getSize());
93         }
94         setDirty();
95     }
96
97     private void init(byte[] data, int off, int len, int doff, int dlen) {
98     if (len == 0) {
99         this.data = LogUtils.ZERO_LENGTH_BYTE_ARRAY;
100     } else {
101         this.data = new byte[len];
102         System.arraycopy(data, off, this.data, doff, dlen);
103     }
104     }
105
106     private void init(byte[] data, int off, int len) {
107         init(data, off, len, 0, len);
108     }
109
110     public byte[] getData() {
111         return data;
112     }
113     
114     public byte[] copyData() {
115         int len = data.length;
116         byte[] ret = new byte[len];
117         System.arraycopy(data, 0, ret, 0, len);
118         return ret;
119     }
120
121     public boolean isDeleted() {
122         return (data == null);
123     }
124
125     void makeDeleted() {
126         data = null;
127     }
128
129     boolean isDirty() {
130         return ((state & DIRTY_BIT) != 0);
131     }
132
133     void setDirty() {
134         state |= DIRTY_BIT;
135     }
136
137     private void clearDirty() {
138         state &= CLEAR_DIRTY_BIT;
139     }
140
141     private boolean wasLastLoggedTransactionally() {
142         return ((state & TXN_BIT) != 0);
143     }
144
145     public void setLastLoggedTransactionally() {
146         state |= TXN_BIT;
147     }
148
149     public void clearLastLoggedTransactionally() {
150         state &= CLEAR_TXN_BIT;
151     }
152
153     /*
154      * If you get to an LN, this subtree isn't valid for delete. True, the LN
155      * may have been deleted, but you can't be sure without taking a lock, and
156      * the validate -subtree-for-delete process assumes that bin compressing
157      * has happened and there are no committed, deleted LNS hanging off the
158      * BIN.
159      */
160     boolean isValidForDelete() {
161         return false;
162     }
163
164     /**
165      * A LN can never be a child in the search chain.
166      */
167     protected boolean isSoughtNode(long nid, boolean updateGeneration) {
168         return false;
169     }
170
171     /**
172      * A LN can never be the ancestor of another node.
173      */
174     protected boolean canBeAncestor(boolean targetContainsDuplicates) {
175         return false;
176     }
177
178     /**
179      * Delete this LN's data and log the new version.
180      */
181     public long delete(DatabaseImpl database,
182                byte[] lnKey,
183                byte[] dupKey,
184                long oldLsn,
185                Locker locker)
186         throws DatabaseException {
187
188         int oldSize = getTotalLastLoggedSize(lnKey);
189         makeDeleted();
190         setDirty();
191
192         /* Log if necessary */
193         EnvironmentImpl env = database.getDbEnvironment();
194         long newLsn = DbLsn.NULL_LSN;
195         if (dupKey != null) {
196
197             /*
198              * If this is a deferred write database, and the LN has
199              * never been logged, we don't need to log the delete either,
200              * since we are currently running in non-txnal mode. This
201              * will have to be adapted when we support txnal mode.
202              */
203             if (database.isDeferredWrite() &&
204                 oldLsn == DbLsn.NULL_LSN) {
205                 clearDirty();
206             } else {
207                 /* Log as a deleted duplicate LN by passing dupKey. */
208                 newLsn = log(env, database.getId(), lnKey, dupKey, oldLsn,
209                              oldSize, locker,
210                              false, // isProvisional
211 false); // backgroundIO
212 }
213         } else {
214
215             /*
216              * Non duplicate LN, just log the normal way.
217              */
218             newLsn = optionalLog(env, database, lnKey, oldLsn, oldSize, locker);
219         }
220         return newLsn;
221     }
222
223     /**
224      * Modify the LN's data and log the new version.
225      */
226     public long modify(byte[] newData,
227                DatabaseImpl database,
228                byte[] lnKey,
229                long oldLsn,
230                Locker locker)
231         throws DatabaseException {
232
233         int oldSize = getTotalLastLoggedSize(lnKey);
234         data = newData;
235         setDirty();
236
237         /* Log the new LN. */
238         EnvironmentImpl env = database.getDbEnvironment();
239         long newLsn =
240             optionalLog(env, database, lnKey, oldLsn, oldSize, locker);
241         return newLsn;
242     }
243
244     /**
245      * Add yourself to the in memory list if you're a type of node that should
246      * belong.
247      */
248     void rebuildINList(INList inList) {
249         // don't add, LNs don't belong on the list.
250 }
251
252     /**
253      * No need to do anything, stop the search.
254      */
255     void accountForSubtreeRemoval(INList inList,
256                                   UtilizationTracker tracker) {
257         /* Don't remove, LNs not on this list. */
258     }
259
260     /**
261      * Compute the approximate size of this node in memory for evictor
262      * invocation purposes.
263      */
264     public long getMemorySizeIncludedByParent() {
265         int size = MemoryBudget.LN_OVERHEAD;
266         if (data != null) {
267             size += MemoryBudget.byteArraySize(data.length);
268         }
269         return size;
270     }
271
272     /*
273      * Dumping
274      */
275
276     public String JavaDoc beginTag() {
277         return BEGIN_TAG;
278     }
279
280     public String JavaDoc endTag() {
281         return END_TAG;
282     }
283
284     public String JavaDoc dumpString(int nSpaces, boolean dumpTags) {
285         StringBuffer JavaDoc self = new StringBuffer JavaDoc();
286         if (dumpTags) {
287         self.append(TreeUtils.indent(nSpaces));
288             self.append(beginTag());
289             self.append('\n');
290         }
291
292         self.append(super.dumpString(nSpaces + 2, true));
293         self.append('\n');
294         if (data != null) {
295             self.append(TreeUtils.indent(nSpaces+2));
296             self.append("<data>");
297             self.append(TreeUtils.dumpByteArray(data));
298             self.append("</data>");
299             self.append('\n');
300         }
301         if (dumpTags) {
302             self.append(TreeUtils.indent(nSpaces));
303             self.append(endTag());
304         }
305         return self.toString();
306     }
307
308     /*
309      * Logging Support
310      */
311
312     /**
313      * Log this LN and clear the dirty flag. Whether it's logged as a
314      * transactional entry or not depends on the type of locker.
315      * @param env the environment.
316      * @param dbId database id of this node. (Not stored in LN)
317      * @param key key of this node. (Not stored in LN)
318      * @param oldLsn is the LSN of the previous version or null.
319      * @param oldSize is the size of the previous version or zero.
320      * @param locker owning locker.
321      */
322     public long log(EnvironmentImpl env,
323             DatabaseId dbId,
324             byte[] key,
325             long oldLsn,
326                     int oldSize,
327             Locker locker,
328                     boolean backgroundIO)
329         throws DatabaseException {
330
331         return log(env, dbId, key,
332                    null, // delDupKey
333 oldLsn, oldSize, locker, backgroundIO,
334                    false); // provisional
335 }
336
337     /**
338      * Log this LN if it's not part of a deferred-write db. Whether it's
339      * logged as a transactional entry or not depends on the type of locker.
340      * @param env the environment.
341      * @param dbId database id of this node. (Not stored in LN)
342      * @param key key of this node. (Not stored in LN)
343      * @param oldLsn is the LSN of the previous version or NULL_LSN.
344      * @param oldSize is the size of the previous version or zero.
345      * @param locker owning locker.
346      */
347     public long optionalLog(EnvironmentImpl env,
348                             DatabaseImpl databaseImpl,
349                             byte[] key,
350                             long oldLsn,
351                             int oldSize,
352                             Locker locker)
353         throws DatabaseException {
354
355         if (databaseImpl.isDeferredWrite()) {
356             return DbLsn.NULL_LSN;
357         } else {
358             return log
359                 (env, databaseImpl.getId(), key,
360                  null, // delDupKey
361 oldLsn, oldSize, locker,
362                  false, // backgroundIO
363 false); // provisional
364 }
365     }
366
367     /**
368      * Log a provisional, non-txnal version of an LN.
369      * @param env the environment.
370      * @param dbId database id of this node. (Not stored in LN)
371      * @param key key of this node. (Not stored in LN)
372      * @param oldLsn is the LSN of the previous version or NULL_LSN.
373      * @param oldSize is the size of the previous version or zero.
374      */
375     public long optionalLogProvisional(EnvironmentImpl env,
376                                        DatabaseImpl databaseImpl,
377                                        byte[] key,
378                                        long oldLsn,
379                                        int oldSize)
380         throws DatabaseException {
381
382         if (databaseImpl.isDeferredWrite()) {
383             return DbLsn.NULL_LSN;
384         } else {
385             return log
386                 (env, databaseImpl.getId(), key,
387                  null, // delDupKey
388 oldLsn, oldSize,
389                  null, // locker
390 false, // backgroundIO
391 true); // provisional
392 }
393     }
394
395     /**
396      * Log this LN. Clear dirty bit. Whether it's logged as a transactional
397      * entry or not depends on the type of locker.
398      * @param env the environment.
399      * @param dbId database id of this node. (Not stored in LN)
400      * @param key key of this node. (Not stored in LN)
401      * @param delDupKey if non-null, the dupKey for deleting the LN.
402      * @param oldLsn is the LSN of the previous version or NULL_LSN.
403      * @param oldSize is the size of the previous version or zero.
404      * @param locker owning locker.
405      */
406     long log(EnvironmentImpl env,
407              DatabaseId dbId,
408              byte[] key,
409              byte[] delDupKey,
410              long oldLsn,
411              int oldSize,
412              Locker locker,
413              boolean backgroundIO,
414              boolean isProvisional)
415         throws DatabaseException {
416
417         boolean isDelDup = (delDupKey != null);
418         LogEntryType entryType;
419         long logAbortLsn;
420     boolean logAbortKnownDeleted;
421         Txn logTxn;
422         if (locker != null && locker.isTransactional()) {
423             entryType = isDelDup ? LogEntryType.LOG_DEL_DUPLN_TRANSACTIONAL
424                                  : getTransactionalLogType();
425         WriteLockInfo info = locker.getWriteLockInfo(getNodeId());
426         logAbortLsn = info.getAbortLsn();
427         logAbortKnownDeleted = info.getAbortKnownDeleted();
428             logTxn = locker.getTxnLocker();
429             assert logTxn != null;
430             if (oldLsn == logAbortLsn) {
431                 info.setAbortLogSize(oldSize);
432             }
433         } else {
434             entryType = isDelDup ? LogEntryType.LOG_DEL_DUPLN
435                                  : getLogType();
436             logAbortLsn = DbLsn.NULL_LSN;
437         logAbortKnownDeleted = false;
438             logTxn = null;
439         }
440
441         /* Don't count abortLsn as obsolete, this is done during commit. */
442         if (oldLsn == logAbortLsn) {
443             oldLsn = DbLsn.NULL_LSN;
444         }
445
446         LNLogEntry logEntry;
447         if (isDelDup) {
448
449             /*
450              * Deleted Duplicate LNs are logged with two keys -- the one
451              * that identifies the main tree (the dup key) and the one that
452              * places them in the duplicate tree (really the data) since we
453              * can't recreate the latter because the data field has been
454              * nulled. Note that the dupKey is passed to the log manager
455              * FIRST, because the dup key is the one that navigates us in
456              * the main tree. The "key" is the one that navigates us in the
457              * duplicate tree.
458              */
459             logEntry =
460                 new DeletedDupLNLogEntry(entryType,
461                                          this,
462                                          dbId,
463                                          delDupKey,
464                                          key,
465                                          logAbortLsn,
466                                          logAbortKnownDeleted,
467                                          logTxn);
468         } else {
469             /* Not a deleted duplicate LN -- use a regular LNLogEntry. */
470             logEntry = new LNLogEntry(entryType,
471                                       this,
472                                       dbId,
473                                       key,
474                                       logAbortLsn,
475                                       logAbortKnownDeleted,
476                                       logTxn);
477         }
478
479         LogManager logManager = env.getLogManager();
480         long lsn = logManager.log(logEntry, isProvisional,
481                                   backgroundIO, oldLsn, oldSize);
482         clearDirty();
483         return lsn;
484     }
485
486     /**
487      * Log type for transactional entries
488      */
489     protected LogEntryType getTransactionalLogType() {
490         return LogEntryType.LOG_LN_TRANSACTIONAL;
491     }
492
493     /**
494      * @see LoggableObject#countAsObsoleteWhenLogged
495      */
496     public boolean countAsObsoleteWhenLogged() {
497         return false;
498     }
499
500     /**
501      * @see LoggableObject#getLogType
502      */
503     public LogEntryType getLogType() {
504         return LogEntryType.LOG_LN;
505     }
506
507     /**
508      * Returns the total last logged log size, including the LNLogEntry
509      * overhead of this LN when it was last logged and the fixed log entry
510      * header. Used for computing obsolete size when an LNLogEntry is not in
511      * hand.
512      */
513     public int getTotalLastLoggedSize(byte[] lnKey) {
514
515         /*
516          * This method is never called for a deleted LN. We assert if this
517          * occurs by mistake, because we do not calculate the size of a
518          * DeletedDupLNLogEntry.
519          */
520         assert !isDeleted();
521
522         return LNLogEntry.getStaticLogSize
523                     (getLastLoggedSize(), lnKey,
524                      wasLastLoggedTransactionally()) +
525                LogManager.HEADER_BYTES;
526     }
527
528     /**
529      * Return the size of this LN as last logged, when called before modifying
530      * the persistent state in modify() and delete(). By default this method
531      * return getLogSize(), but sometimes the size last logged is not the same
532      * value returned by getLogSize(), if the state of the persistent data is
533      * changed before calling modify() or delete(). In those cases (e.g.,
534      * MapLN) this method can be overidden.
535      */
536     public int getLastLoggedSize() {
537         return getLogSize();
538     }
539
540     /**
541      * @see LoggableObject#getLogSize
542      */
543     public int getLogSize() {
544         int size = super.getLogSize();
545
546         // data
547 size += LogUtils.getBooleanLogSize(); // isDeleted flag
548 if (!isDeleted()) {
549             size += LogUtils.getByteArrayLogSize(data);
550         }
551
552         return size;
553     }
554
555     /**
556      * @see LoggableObject#writeToLog
557      */
558     public void writeToLog(ByteBuffer JavaDoc logBuffer) {
559         /* Ask ancestors to write to log. */
560         super.writeToLog(logBuffer);
561
562         /* data: isData null flag, then length, then data. */
563         boolean dataExists = !isDeleted();
564         LogUtils.writeBoolean(logBuffer, dataExists);
565         if (dataExists) {
566             LogUtils.writeByteArray(logBuffer, data);
567         }
568     }
569
570     /**
571      * @see LogReadable#readFromLog
572      */
573     public void readFromLog(ByteBuffer JavaDoc itemBuffer, byte entryTypeVersion)
574         throws LogException {
575
576         super.readFromLog(itemBuffer, entryTypeVersion);
577
578         boolean dataExists = LogUtils.readBoolean(itemBuffer);
579         if (dataExists) {
580             data = LogUtils.readByteArray(itemBuffer);
581         }
582     }
583
584     /**
585      * @see LogReadable#dumpLog
586      */
587     public void dumpLog(StringBuffer JavaDoc sb, boolean verbose) {
588         sb.append(beginTag());
589         super.dumpLog(sb, verbose);
590
591         if (data != null) {
592             sb.append("<data>");
593             sb.append(TreeUtils.dumpByteArray(data));
594             sb.append("</data>");
595         }
596         
597         dumpLogAdditional(sb, verbose);
598
599         sb.append(endTag());
600     }
601
602     /**
603      * Never called.
604      * @see LogReadable#logEntryIsTransactional.
605      */
606     public boolean logEntryIsTransactional() {
607     return false;
608     }
609
610     /**
611      * Never called.
612      * @see LogReadable#getTransactionId
613      */
614     public long getTransactionId() {
615     return 0;
616     }
617
618     /*
619      * Allows subclasses to add additional fields before the end tag.
620      */
621     protected void dumpLogAdditional(StringBuffer JavaDoc sb, boolean verbose) {
622     }
623 }
624
Popular Tags