Tree


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: Tree.java,v 1.417 2006/12/04 18:47:41 cwl Exp $
7    */
8   
9   package com.sleepycat.je.tree;
10  
11  import java.nio.ByteBuffer  ;
12  import java.util.ArrayList  ;
13  import java.util.List  ;
14  import java.util.ListIterator  ;
15  import java.util.logging.Level  ;
16  import java.util.logging.Logger  ;
17  
18  import com.sleepycat.je.DatabaseException;
19  import com.sleepycat.je.cleaner.UtilizationTracker;
20  import com.sleepycat.je.config.EnvironmentParams;
21  import com.sleepycat.je.dbi.CursorImpl;
22  import com.sleepycat.je.dbi.DatabaseImpl;
23  import com.sleepycat.je.dbi.DbConfigManager;
24  import com.sleepycat.je.dbi.DbTree;
25  import com.sleepycat.je.dbi.EnvironmentImpl;
26  import com.sleepycat.je.dbi.INList;
27  import com.sleepycat.je.latch.LatchSupport;
28  import com.sleepycat.je.latch.SharedLatch;
29  import com.sleepycat.je.log.LogManager;
30  import com.sleepycat.je.log.LogReadable;
31  import com.sleepycat.je.log.LogUtils;
32  import com.sleepycat.je.log.LogWritable;
33  import com.sleepycat.je.recovery.RecoveryManager;
34  import com.sleepycat.je.txn.BasicLocker;
35  import com.sleepycat.je.txn.LockGrantType;
36  import com.sleepycat.je.txn.LockResult;
37  import com.sleepycat.je.txn.LockType;
38  import com.sleepycat.je.txn.Locker;
39  import com.sleepycat.je.txn.WriteLockInfo;
40  import com.sleepycat.je.utilint.DbLsn;
41  import com.sleepycat.je.utilint.TestHook;
42  import com.sleepycat.je.utilint.TestHookExecute;
43  import com.sleepycat.je.utilint.Tracer;
44  
45  /**
46   * Tree implements the JE B+Tree.
47   * 
48   * A note on tree search patterns: 
49   * There's a set of Tree.search* methods. Some clients of the tree use
50   * those search methods directly, whereas other clients of the tree
51   * tend to use methods built on top of search.
52   *
53   * The semantics of search* are
54   *   they leave you pointing at a BIN or IN
55   *   they don't tell you where the reference of interest is.
56   *   they traverse a single tree, to jump into the duplicate tree, the 
57   *   caller has to take explicit action.
58   * The semantics of the get* methods are:
59   *   they leave you pointing at a BIN or IN
60   *   they return the index of the slot of interest
61   *   they traverse down to whatever level is needed -- they'll take care of
62   *   jumping into the duplicate tree.
63   *   they are built on top of search* methods.
64   * For the future:
65   * Over time, we need to clarify which methods are to be used by clients
66   * of the tree. Preferably clients that call the tree use get*, although 
67   * their are cases where they need visibility into the tree structure. For 
68   * example, tee cursors use search* because they want to add themselves to 
69   * BIN before jumping into the duplicate tree.
70   * 
71   * Also, search* should return the location of the slot to save us a 
72   * second binary search.
73   */
74  public final class Tree implements LogWritable, LogReadable {
75  
76      /* For debug tracing */
77      private static final String   TRACE_ROOT_SPLIT = "RootSplit:";
78      private static final String   TRACE_DUP_ROOT_SPLIT = "DupRootSplit:";
79      private static final String   TRACE_MUTATE = "Mut:";
80      private static final String   TRACE_INSERT = "Ins:";
81      private static final String   TRACE_INSERT_DUPLICATE = "InsD:";
82  
83      private DatabaseImpl database;
84      private ChildReference root;
85      private int maxMainTreeEntriesPerNode;
86      private int maxDupTreeEntriesPerNode;
87      private boolean purgeRoot;
88  
89      /*
90       * Indicates whether the root ChildReference was last logged, and used for
91       * calculating the last logged size.  Not persistent.
92       * @see #getLastLoggedSize
93       */
94      private boolean rootLastLogged;
95  
96      /* 
97       * Latch that must be held when using/accessing the root node.  Protects
98       * against the root being changed out from underneath us by splitRoot.
99       */
100     private SharedLatch rootLatch;
101 
102     private TreeStats treeStats;
103 
104     private ThreadLocal   treeStatsAccumulatorTL = new ThreadLocal  ();
105 
106     /*
107      * We don't need the stack trace on this so always throw a static and
108      * avoid the cost of Throwable.fillInStack() every time it's thrown.
109      * [#13354].
110      */
111     private static SplitRequiredException splitRequiredException =
112     new SplitRequiredException();
113 
114     /**
115      * Embodies an enum for the type of search being performed.  NORMAL means
116      * do a regular search down the tree.  LEFT/RIGHT means search down the
117      * left/right side to find the first/last node in the tree. 
118      */
119     public static class SearchType {
120         /* Search types */
121         public static final SearchType NORMAL = new SearchType();
122         public static final SearchType LEFT   = new SearchType();
123         public static final SearchType RIGHT  = new SearchType();
124 
125         /* No lock types can be defined outside this class. */
126         private SearchType() {
127         }
128     }
129 
130     /* For unit tests */
131     private TestHook waitHook; // used for generating race conditions
132     private TestHook searchHook; // [#12736]
133     private TestHook ckptHook; // [#13897]
134 
135     /**
136      * Create a new tree.
137      */
138     public Tree(DatabaseImpl database)
139         throws DatabaseException {
140 
141         init(database);
142         setDatabase(database);
143     }
144     
145     /**
146      * Create a tree that's being read in from the log.
147      */
148     public Tree()
149         throws DatabaseException {
150 
151         init(null);
152         maxMainTreeEntriesPerNode = 0;
153         maxDupTreeEntriesPerNode = 0;
154     }
155 
156     /**
157      * constructor helper
158      */
159     private void init(DatabaseImpl database) {
160         rootLatch =
161         LatchSupport.makeSharedLatch
162         ("RootLatch",
163          (database != null) ? database.getDbEnvironment() : null);
164         treeStats = new TreeStats();
165         this.root = null;
166         this.database = database;
167     }
168 
169     /**
170      * Set the database for this tree. Used by recovery when recreating an
171      * existing tree.
172      */
173     public void setDatabase(DatabaseImpl database)
174         throws DatabaseException {
175 
176         this.database = database;
177         maxMainTreeEntriesPerNode = database.getNodeMaxEntries();
178     maxDupTreeEntriesPerNode = database.getNodeMaxDupTreeEntries();
179         DbConfigManager configManager =
180             database.getDbEnvironment().getConfigManager();
181         purgeRoot = configManager.getBoolean
182             (EnvironmentParams.COMPRESSOR_PURGE_ROOT);
183     }
184     
185     /**
186      * @return the database for this Tree.
187      */
188     public DatabaseImpl getDatabase() {
189         return database;
190     }
191 
192     /**
193      * Set the root for the tree. Should only be called within the root latch.
194      */
195     public void setRoot(ChildReference newRoot, boolean notLatched) {
196     assert (notLatched || rootLatch.isWriteLockedByCurrentThread());
197         root = newRoot;
198     }
199 
200     public ChildReference makeRootChildReference(Node target,
201                          byte[] key,
202                          long lsn) {
203     return new RootChildReference(target, key, lsn);
204     }
205 
206     private ChildReference makeRootChildReference() {
207     return new RootChildReference();
208     }
209 
210     /* 
211      * A tree doesn't have a root if (a) the root field is null, or (b)
212      * the root is non-null, but has neither a valid target nor a valid 
213      * LSN. Case (b) can happen if the dataabase is or was previously opened in
214      * deferred write mode.
215      * @return false if there is no real root.
216      */
217     public boolean rootExists() {
218         if (root == null) {
219             return false;
220         } 
221         
222         if ((root.getTarget() == null) && 
223             (root.getLsn() == DbLsn.NULL_LSN)) {
224             return false;
225         }
226 
227         return true;
228     }
229 
230     /*
231      * Class that overrides fetchTarget() so that if the rootLatch is not
232      * held exclusively when the root is fetched, we upgrade it to exclusive.
233      */
234     private class RootChildReference extends ChildReference {
235 
236     private RootChildReference() {
237         super();
238     }
239 
240     private RootChildReference(Node target, byte[] key, long lsn) {
241         super(target, key, lsn);
242     }
243 
244     /* Not used. */
245     private RootChildReference(Node target,
246                    byte[] key,
247                    long lsn,
248                    byte existingState) {
249         super(target, key, lsn, existingState);
250     }
251 
252     /* Caller is responsible for releasing rootLatch. */
253     public Node fetchTarget(DatabaseImpl database, IN in)
254         throws DatabaseException {
255 
256         if (getTarget() == null &&
257         !rootLatch.isWriteLockedByCurrentThread()) {
258         rootLatch.release();
259         rootLatch.acquireExclusive();
260         }
261 
262         return super.fetchTarget(database, in);
263     }
264 
265     public void setTarget(Node target) {
266         assert rootLatch.isWriteLockedByCurrentThread();
267         super.setTarget(target);
268     }
269 
270     public void clearTarget() {
271         assert rootLatch.isWriteLockedByCurrentThread();
272         super.clearTarget();
273     }
274 
275     public void setLsn(long lsn) {
276         assert rootLatch.isWriteLockedByCurrentThread();
277         super.setLsn(lsn);
278     }
279 
280     void updateLsnAfterOptionaLog(DatabaseImpl dbImpl, long lsn) {
281         assert rootLatch.isWriteLockedByCurrentThread();
282         super.updateLsnAfterOptionalLog(dbImpl, lsn);
283     }
284     }
285 
286     /**
287      * Get LSN of the rootIN. Obtained without latching, should only be
288      * accessed while quiescent.
289      */
290     public long getRootLsn() {
291         if (root == null) {
292             return DbLsn.NULL_LSN;
293         } else {
294             return root.getLsn();
295         }
296     }
297 
298     /**
299      * @return the TreeStats for this tree.
300      */
301     TreeStats getTreeStats() {
302         return treeStats;
303     }
304 
305     private TreeWalkerStatsAccumulator getTreeStatsAccumulator() {
306     if (EnvironmentImpl.getThreadLocalReferenceCount() > 0) {
307         return (TreeWalkerStatsAccumulator) treeStatsAccumulatorTL.get();
308     } else {
309         return null;
310     }
311     }
312 
313     public void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA) {
314     treeStatsAccumulatorTL.set(tSA);
315     }
316 
317     public IN withRootLatchedExclusive(WithRootLatched wrl)
318         throws DatabaseException {
319 
320         try {
321             rootLatch.acquireExclusive();
322             return wrl.doWork(root);
323         } finally {
324             rootLatch.release();
325         }
326     }
327 
328     public IN withRootLatchedShared(WithRootLatched wrl)
329         throws DatabaseException {
330 
331         try {
332             rootLatch.acquireShared();
333             return wrl.doWork(root);
334         } finally {
335             rootLatch.release();
336         }
337     }
338 
339     /**
340      * Deletes a BIN specified by key from the tree. If the BIN resides in a 
341      * subtree that can be pruned away, prune as much as possible, so we 
342      * don't leave a branch that has no BINs.
343      *
344      * It's possible that the targeted BIN will now have entries, or will
345      * have resident cursors. Either will prevent deletion.
346      *
347      * @param idKey - the identifier key of the node to delete.
348      * @param tracker is used for tracking obsolete node info.
349      */
350     public void delete(byte[] idKey,
351                        UtilizationTracker tracker)
352         throws DatabaseException,
353                NodeNotEmptyException,
354                CursorsExistException {
355 
356         IN subtreeRootIN = null;
357 
358         /* 
359          * A delete is a reverse split that must be propagated up to the root.
360          * [#13501] Keep all nodes from the rootIN to the parent of the
361          * deletable subtree latched as we descend so we can log the
362          * IN deletion and cascade the logging up the tree. The latched
363          * nodes are kept in order in the nodeLadder.
364          */
365         ArrayList   nodeLadder = new ArrayList  ();
366 
367         IN rootIN = null;
368         boolean rootNeedsUpdating = false;
369         rootLatch.acquireExclusive();
370         try {
371             if (!rootExists()) {
372                 /* no action, tree is deleted or was never persisted. */
373                 return; 
374             } 
375 
376             rootIN = (IN) root.fetchTarget(database, null);
377             rootIN.latch(false);
378 
379             searchDeletableSubTree(rootIN, idKey, nodeLadder);
380             if (nodeLadder.size() == 0) {
381 
382                 /*
383                  * The root is the top of the deletable subtree. Delete the
384                  * whole tree if the purge root je property is set.
385                  * In general, there's no reason to delete this last
386                  * IN->...IN->BIN subtree since we're likely to to add more
387                  * nodes to this tree again.  Deleting the subtree also
388                  * adds to the space used by the log since a MapLN needs to
389                  * be written when the root is nulled, and a MapLN, IN
390                  * (root), BIN needs to be written when the root is
391                  * recreated.
392                  *
393                  * Consider a queue application which frequently inserts
394                  * and deletes entries and often times leaves the tree
395                  * empty, but will insert new records again.
396                  *
397                  * An optimization might be to prune the multiple IN path
398                  * to the last BIN (if it even exists) to just a root IN
399                  * pointing to the single BIN, but this doesn't feel like
400                  * it's worth the trouble since the extra depth doesn't
401                  * matter all that much.
402                  */
403 
404                 if (purgeRoot) {
405                     subtreeRootIN = logTreeRemoval(rootIN);
406                     if (subtreeRootIN != null) {
407                         rootNeedsUpdating = true;
408                     }
409                 }
410             } else {
411                 /* Detach this subtree. */
412                 SplitInfo detachPoint = 
413                     (SplitInfo) nodeLadder.get(nodeLadder.size() - 1);
414                 boolean deleteOk =
415                     detachPoint.parent.deleteEntry(detachPoint.index,
416                                                    true);
417                 assert deleteOk;
418 
419                 /* Cascade updates upward, including writing the root IN. */
420                 rootNeedsUpdating = cascadeUpdates(nodeLadder, null, -1);
421                 subtreeRootIN = detachPoint.child;
422             }
423         } finally {
424             releaseNodeLadderLatches(nodeLadder);
425 
426             if (rootIN != null) {
427                 rootIN.releaseLatch();
428             }
429 
430             rootLatch.release();
431         }
432 
433 
434         if (subtreeRootIN != null) {
435 
436             EnvironmentImpl envImpl = database.getDbEnvironment();
437             if (rootNeedsUpdating) {
438                 /*
439                  * modifyDbRoot will grab locks and we can't have the INList
440                  * latches or root latch held while it tries to acquire locks.
441                  */
442                 DbTree dbTree = envImpl.getDbMapTree();
443                 dbTree.optionalModifyDbRoot(database);
444                 RecoveryManager.traceRootDeletion(Level.FINE, database);
445             } 
446 
447             /* 
448              * Count obsolete nodes after logging the delete. We can do
449              * this without having the nodes of the subtree latched because the
450              * subtree has been detached from the tree.
451              */
452             INList inList = envImpl.getInMemoryINs();
453             accountForSubtreeRemoval(inList, subtreeRootIN, tracker);
454         }
455     }
456 
457     private void releaseNodeLadderLatches(ArrayList   nodeLadder) 
458         throws DatabaseException {
459 
460         /*
461          * Clear any latches left in the node ladder. Release from the
462          * bottom up.
463          */
464         ListIterator   iter = nodeLadder.listIterator(nodeLadder.size());
465         while (iter.hasPrevious()) {
466             SplitInfo info = (SplitInfo) iter.previous();
467             info.child.releaseLatch();
468         }
469     }
470                 
471     /**
472      * This entire tree is empty, clear the root and log a new MapLN
473      * @return the rootIN that has been detached, or null if there
474      * hasn't been any removal.
475      */
476     private IN logTreeRemoval(IN rootIN)
477         throws DatabaseException {
478 
479     assert rootLatch.isWriteLockedByCurrentThread();
480         IN detachedRootIN = null;
481 
482         /**
483          * XXX: Suspect that validateSubtree is no longer needed, now that we
484          * hold all latches.
485          */
486         if ((rootIN.getNEntries() <= 1) &&
487             (rootIN.validateSubtreeBeforeDelete(0))) {
488 
489             root = null;
490 
491             /*
492              * Record the root deletion for recovery. Do this within
493              * the root latch. We need to put this log entry into the
494              * log before another thread comes in and creates a new
495              * rootIN for this database.
496              *
497              * For example,
498              * LSN 1000 IN delete info entry
499              * LSN 1010 new IN, for next set of inserts
500              * LSN 1020 new BIN, for next set of inserts.
501              *
502              * The entry at 1000 is needed so that LSN 1010 will
503              * properly supercede all previous IN entries in the tree.
504              * Without the INDelete, we may not use the new root, because
505              * it has a different node id.
506              */
507             INDeleteInfo info = new INDeleteInfo(rootIN.getNodeId(),
508                                                  rootIN.getIdentifierKey(),
509                                                  database.getId());
510             info.optionalLog(database.getDbEnvironment().getLogManager(),
511                      database);
512 
513         
514             detachedRootIN = rootIN;
515         }
516         return detachedRootIN;
517     }
518 
519     /**
520      * Update nodes for a delete, going upwards. For example, suppose a
521      * node ladder holds:
522      * INa, INb, index for INb in INa
523      * INb, INc, index for INc in INb
524      * INc, BINd, index for BINd in INc
525      *
526      * When we enter this method, BINd has already been removed from INc. We
527      * need to 
528      *  - log INc
529      *  - update INb, log INb
530      *  - update INa, log INa
531      *
532      * @param nodeLadder List of SplitInfos describing each node pair on the
533      * downward path
534      * @param binRoot parent of the dup tree, or null if this is not for
535      * dups.
536      * @param index slot occupied by this din tree.
537      * @return whether the DB root needs updating.
538      */
539     private boolean cascadeUpdates(ArrayList   nodeLadder, 
540                                    BIN binRoot,
541                                    int index) 
542         throws DatabaseException {
543 
544         ListIterator   iter = nodeLadder.listIterator(nodeLadder.size());
545         EnvironmentImpl envImpl = database.getDbEnvironment();
546         LogManager logManager = envImpl.getLogManager();
547 
548         long newLsn = DbLsn.NULL_LSN;
549         SplitInfo info = null;
550         while (iter.hasPrevious()) {
551             info = (SplitInfo) iter.previous();
552 
553             if (newLsn != DbLsn.NULL_LSN) {
554                 info.parent.updateEntry(info.index, newLsn);
555         }
556             newLsn = info.parent.optionalLog(logManager);
557         }
558 
559         boolean rootNeedsUpdating = false;
560         if (info != null) {
561             /* We've logged the top of this subtree, record it properly. */
562             if (info.parent.isDbRoot()) {
563                 /* We updated the rootIN of the database. */
564                 assert rootLatch.isWriteLockedByCurrentThread();
565                 root.updateLsnAfterOptionalLog(database, newLsn);
566                 rootNeedsUpdating = true;
567             } else if ((binRoot != null) && info.parent.isRoot()) {
568                 /* We updated the DIN root of the database. */
569                 binRoot.updateEntry(index, newLsn);
570             } else {
571                 assert false;
572             }
573         }
574         return rootNeedsUpdating;
575     }
576 
577     /**
578      * Delete a subtree of a duplicate tree.  Find the duplicate tree using
579      * mainKey in the top part of the tree and idKey in the duplicate tree.
580      *
581      * @param idKey the identifier key to be used in the duplicate subtree to
582      * find the duplicate path.
583      * @param mainKey the key to be used in the main tree to find the
584      * duplicate subtree.
585      * @param tracker is used for tracking obsolete node info.
586      *
587      * @return true if the delete succeeded, false if there were still cursors
588      * present on the leaf DBIN of the subtree that was located.
589      */
590     public void deleteDup(byte[] idKey,
591                           byte[] mainKey,
592                           UtilizationTracker tracker)
593         throws DatabaseException,
594                NodeNotEmptyException,
595                CursorsExistException {
596 
597         /* Find the BIN that is the parent of this duplicate tree. */
598         IN in = search(mainKey, SearchType.NORMAL, -1, null,
599                        false /*updateGeneration*/);
600 
601         IN deletedSubtreeRoot = null;
602         try {
603             assert in.isLatchOwnerForWrite();
604             assert in instanceof BIN;
605             assert in.getNEntries() > 0;
606 
607             /* Find the appropriate entry in this BIN. */
608             int index = in.findEntry(mainKey, false, true);
609             if (index >= 0) {
610                 deletedSubtreeRoot = deleteDupSubtree(idKey, (BIN) in, index);
611             }
612         } finally {
613             in.releaseLatch();
614         }
615 
616         if (deletedSubtreeRoot != null) {
617             EnvironmentImpl envImpl = database.getDbEnvironment();
618             accountForSubtreeRemoval(envImpl.getInMemoryINs(),
619                                      deletedSubtreeRoot, tracker);
620         }
621     }
622 
623     /**
624      * We enter and leave this method with 'bin' latched.
625      * @return the root of the subtree we have deleted, so it can be
626      * properly accounted for. May be null if nothing was deleted.
627      */
628     private IN deleteDupSubtree(byte[] idKey,
629                                 BIN bin,
630                                 int index)
631         throws DatabaseException,
632                NodeNotEmptyException, 
633                CursorsExistException {
634 
635         EnvironmentImpl envImpl = database.getDbEnvironment();
636     boolean dupCountLNLocked = false;
637     DupCountLN dcl = null;
638         BasicLocker locker = new BasicLocker(envImpl);
639 
640         /*  Latch the DIN root. */
641         DIN duplicateRoot = (DIN) bin.fetchTarget(index);
642         duplicateRoot.latch(false);
643         
644         ArrayList   nodeLadder = new ArrayList  ();
645         IN subtreeRootIN = null;
646 
647     try {
648 
649             /* 
650              * Read lock the dup count LN to ascertain whether there are any
651              * writers in the tree. XXX: This seems unnecessary now, revisit.
652              */
653             ChildReference dclRef = duplicateRoot.getDupCountLNRef();
654             dcl = (DupCountLN) dclRef.fetchTarget(database, duplicateRoot);
655             
656             LockResult lockResult = locker.nonBlockingLock(dcl.getNodeId(),
657                                                            LockType.READ,
658                                                            database);
659             if (lockResult.getLockGrant() == LockGrantType.DENIED) {
660                 throw CursorsExistException.CURSORS_EXIST;
661             } else {
662                 dupCountLNLocked = true;
663             }
664 
665             /*
666              * We don't release the latch on bin before we search the
667              * duplicate tree below because we might be deleting the whole
668              * subtree from the IN and we want to keep it latched until we
669              * know.
670              */
671             searchDeletableSubTree(duplicateRoot, idKey, nodeLadder);
672 
673 
674             if (nodeLadder.size() == 0) {
675                 /* We're deleting the duplicate root. */
676                 if (bin.nCursors() == 0) {
677                     boolean deleteOk = bin.deleteEntry(index, true);
678                     assert deleteOk;
679 
680                     /*
681                      * Use an INDupDeleteInfo to make it clear that
682                      * this duplicate tree has been eradicated. This 
683                      * is analagous to deleting a root; we must be sure
684                      * that we can overlay another subtree onto this slot
685                      * at recovery redo.
686                      */
687                     INDupDeleteInfo info =
688                         new INDupDeleteInfo(duplicateRoot.getNodeId(),
689                                             duplicateRoot.getMainTreeKey(),
690                                             duplicateRoot.getDupTreeKey(),
691                                             database.getId());
692                     info.optionalLog(envImpl.getLogManager(), database);
693 
694                     subtreeRootIN = duplicateRoot;
695 
696                     if (bin.getNEntries() == 0) {
697                         database.getDbEnvironment().
698                             addToCompressorQueue(bin, null, false);
699                     }
700                 } else {
701 
702                     /*
703                      * Cursors prevent us from deleting this dup tree, we'll
704                      * have to retry.
705                      */
706                     throw CursorsExistException.CURSORS_EXIST;
707                 }
708             } else {
709 
710                 /* We're deleting a portion of the duplicate tree. */
711                 SplitInfo detachPoint = 
712                     (SplitInfo) nodeLadder.get(nodeLadder.size() - 1);
713                 boolean deleteOk =
714                     detachPoint.parent.deleteEntry(detachPoint.index,
715                                                    true);
716                 assert deleteOk;
717 
718                 /* 
719                  * Cascade updates upward, including writing the root
720                  * DIN and parent BIN.
721                  */
722                 cascadeUpdates(nodeLadder, bin, index);
723                 subtreeRootIN = detachPoint.child;
724         }
725     } finally {
726             releaseNodeLadderLatches(nodeLadder);
727 
728         /* FindBugs -- ignore dcl possibly null warning. */
729         if (dupCountLNLocked) {
730         locker.releaseLock(dcl.getNodeId());
731         }
732 
733         duplicateRoot.releaseLatch();
734     }
735 
736         return subtreeRootIN;
737     }
738 
739     /**
740      * Find the leftmost node (IN or BIN) in the tree.  Do not descend into a
741      * duplicate tree if the leftmost entry of the first BIN refers to one.
742      *
743      * @return the leftmost node in the tree, null if the tree is empty.  The
744      * returned node is latched and the caller must release it.
745      */
746     public IN getFirstNode()
747         throws DatabaseException {
748 
749         return search
750             (null, SearchType.LEFT, -1, null, true /*updateGeneration*/);
751     }
752 
753     /**
754      * Find the rightmost node (IN or BIN) in the tree.  Do not descend into a
755      * duplicate tree if the rightmost entry of the last BIN refers to one.
756      *
757      * @return the rightmost node in the tree, null if the tree is empty.  The
758      * returned node is latched and the caller must release it.
759      */
760     public IN getLastNode()
761         throws DatabaseException {
762 
763         return search
764             (null, SearchType.RIGHT, -1, null, true /*updateGeneration*/);
765     }
766 
767     /**
768      * Find the leftmost node (DBIN) in a duplicate tree.
769      *
770      * @return the leftmost node in the tree, null if the tree is empty.  The
771      * returned node is latched and the caller must release it.
772      */
773     public DBIN getFirstNode(DIN dupRoot)
774         throws DatabaseException {
775 
776         if (dupRoot == null) {
777             throw new IllegalArgumentException  
778                 ("getFirstNode passed null root");
779         }
780 
781         assert dupRoot.isLatchOwnerForWrite();
782 
783         IN ret = searchSubTree
784             (dupRoot, null, SearchType.LEFT, -1, null,
785              true /*updateGeneration*/);
786         return (DBIN) ret;
787     }
788 
789     /**
790      * Find the rightmost node (DBIN) in a duplicate tree.
791      *
792      * @return the rightmost node in the tree, null if the tree is empty.  The
793      * returned node is latched and the caller must release it.
794      */
795     public DBIN getLastNode(DIN dupRoot)
796         throws DatabaseException {
797 
798         if (dupRoot == null) {
799             throw new IllegalArgumentException  
800                 ("getLastNode passed null root");
801         }
802 
803         assert dupRoot.isLatchOwnerForWrite();
804 
805         IN ret = searchSubTree
806             (dupRoot, null, SearchType.RIGHT, -1, null,
807              true /*updateGeneration*/);
808         return (DBIN) ret;
809     }
810 
811     /**
812      * GetParentNode without optional tracking.
813      */
814     public SearchResult getParentINForChildIN(IN child,
815                           boolean requireExactMatch,
816                           boolean updateGeneration)
817         throws DatabaseException {
818 
819         return getParentINForChildIN
820             (child, requireExactMatch, updateGeneration, -1, null);
821     }
822 
823     /**
824      * Return a reference to the parent or possible parent of the child.  Used
825      * by objects that need to take a standalone node and find it in the tree,
826      * like the evictor, checkpointer, and recovery.
827      *
828      * @param child The child node for which to find the parent.  This node is
829      * latched by the caller and is released by this function before returning
830      * to the caller.
831      *
832      * @param requireExactMatch if true, we must find the exact parent, not a
833      * potential parent.
834      *
835      * @param updateGeneration if true, set the generation count during
836      * latching.  Pass false when the LRU should not be impacted, such as
837      * during eviction and checkpointing.
838      *
839      * @param trackingList if not null, add the LSNs of the parents visited
840      * along the way, as a debug tracing mechanism. This is meant to stay in
841      * production, to add information to the log.
842      *
843      * @return a SearchResult object. If the parent has been found,
844      * result.foundExactMatch is true. If any parent, exact or potential has
845      * been found, result.parent refers to that node.
846      */
847     public SearchResult getParentINForChildIN(IN child,
848                           boolean requireExactMatch,
849                           boolean updateGeneration,
850                                               int targetLevel,
851                           List   trackingList)
852         throws DatabaseException {
853 
854         /* Sanity checks */
855         if (child == null) {
856             throw new IllegalArgumentException  ("getParentNode passed null");
857         }
858 
859         assert child.isLatchOwnerForWrite();
860 
861         /* 
862          * Get information from child before releasing latch. 
863          */
864         byte[] mainTreeKey = child.getMainTreeKey();
865         byte[] dupTreeKey = child.getDupTreeKey();
866         boolean isRoot = child.isRoot();
867         child.releaseLatch();
868 
869         return getParentINForChildIN(child.getNodeId(),
870                                      child.containsDuplicates(),
871                                      isRoot,
872                                      mainTreeKey,
873                                      dupTreeKey,
874                                      requireExactMatch,
875                                      updateGeneration,
876                                      targetLevel,
877                                      trackingList,
878                                      true);
879     }
880 
881     /**
882      * Return a reference to the parent or possible parent of the child.  Used
883      * by objects that need to take a node id and find it in the tree,
884      * like the evictor, checkpointer, and recovery.
885      *
886      * @param requireExactMatch if true, we must find the exact parent, not a
887      * potential parent.
888      *
889      * @param updateGeneration if true, set the generation count during
890      * latching.  Pass false when the LRU should not be impacted, such as
891      * during eviction and checkpointing.
892      * 
893      * @param trackingList if not null, add the LSNs of the parents visited
894      * along the way, as a debug tracing mechanism. This is meant to stay in
895      * production, to add information to the log.
896      *
897      * @param doFetch if false, stop the search if we run into a non-resident 
898      * child. Used by the checkpointer to avoid conflicting with work done
899      * by the evictor.
900      *
901      * @param child The child node for which to find the parent.  This node is
902      * latched by the caller and is released by this function before returning
903      * to the caller.
904      *
905      * @return a SearchResult object. If the parent has been found,
906      * result.foundExactMatch is true. If any parent, exact or potential has
907      * been found, result.parent refers to that node.
908      */
909     public SearchResult getParentINForChildIN(long targetNodeId,
910                                               boolean targetContainsDuplicates,
911                                               boolean targetIsRoot,
912                                               byte[] targetMainTreeKey,
913                                               byte[] targetDupTreeKey,
914                           boolean requireExactMatch,
915                           boolean updateGeneration,
916                                               int targetLevel,
917                           List   trackingList,
918                                               boolean doFetch)
919         throws DatabaseException {
920 
921         IN rootIN = getRootINLatchedExclusive(updateGeneration);
922 
923         SearchResult result = new SearchResult();
924         if (rootIN != null) {
925             /* The tracking list is a permanent tracing aid. */
926             if (trackingList != null) {
927                 trackingList.add(new TrackingInfo(root.getLsn(),
928                                                   rootIN.getNodeId()));
929             }
930                 
931             IN potentialParent = rootIN;
932 
933             try {
934                 while (result.keepSearching) {
935 
936             /*
937              * [12736] Prune away oldBin.  Assert has intentional
938              * side effect.
939              */
940             assert TestHookExecute.doHookIfSet(searchHook);
941 
942                     potentialParent.findParent(SearchType.NORMAL,
943                                                targetNodeId,
944                                                targetContainsDuplicates,
945                                                targetIsRoot,
946                                                targetMainTreeKey,
947                                                targetDupTreeKey,
948                                                result,
949                                                requireExactMatch,
950                            updateGeneration,
951                                                targetLevel,
952                                                trackingList,
953                                                doFetch);
954                     potentialParent = result.parent;
955                 }
956             } catch (Exception   e) {
957                 potentialParent.releaseLatchIfOwner();
958 
959                 throw new DatabaseException(e);
960             }
961         } 
962         return result;
963     }
964 
965     /**
966      * Return a reference to the parent of this LN. This searches through the
967      * main and duplicate tree and allows splits. Set the tree location to the
968      * proper BIN parent whether or not the LN child is found. That's because
969      * if the LN is not found, recovery or abort will need to place it within
970      * the tree, and so we must point at the appropriate position.
971      *
972      * <p>When this method returns with location.bin non-null, the BIN is
973      * latched and must be unlatched by the caller.  Note that location.bin may
974      * be non-null even if this method returns false.</p>
975      *
976      * @param location a holder class to hold state about the location 
977      * of our search. Sort of an internal cursor.
978      *
979      * @param mainKey key to navigate through main key
980      *
981      * @param dupKey key to navigate through duplicate tree. May be null, since
982      * deleted lns have no data.
983      *
984      * @param ln the node instantiated from the log
985      *
986      * @param splitsAllowed true if this method is allowed to cause tree splits
987      * as a side effect. In practice, recovery can cause splits, but abort
988      * can't.
989      *
990      * @param searchDupTree true if a search through the dup tree looking for
991      * a match on the ln's node id should be made (only in the case where
992      * dupKey == null).  See SR 8984.
993      *
994      * @param updateGeneration if true, set the generation count during
995      * latching.  Pass false when the LRU should not be impacted, such as
996      * during eviction and checkpointing.
997      *
998      * @return true if node found in tree.
999      * If false is returned and there is the possibility that we can insert 
1000     * the record into a plausible parent we must also set
1001     * - location.bin (may be null if no possible parent found)
1002     * - location.lnKey (don't need to set if no possible parent).
1003     */
1004    public boolean getParentBINForChildLN(TreeLocation location,
1005                                          byte[] mainKey,
1006                                          byte[] dupKey,
1007                                          LN ln,
1008                                          boolean splitsAllowed,
1009                      boolean findDeletedEntries,
1010                      boolean searchDupTree,
1011                                          boolean updateGeneration)
1012        throws DatabaseException {
1013
1014        /* 
1015         * Find the BIN that either points to this LN or could be its
1016         * ancestor.
1017         */
1018        IN searchResult = null;
1019        try {
1020            if (splitsAllowed) {
1021                searchResult = searchSplitsAllowed
1022                    (mainKey, -1, updateGeneration);
1023            } else {
1024                searchResult = search
1025                    (mainKey, SearchType.NORMAL, -1, null, updateGeneration);
1026            }
1027            location.bin = (BIN) searchResult;
1028        } catch (Exception   e) {
1029            /* SR 11360 tracing. */
1030            StringBuffer   msg = new StringBuffer  ();
1031            if (searchResult != null) {
1032                searchResult.releaseLatchIfOwner();
1033                msg.append("searchResult=" + searchResult.getClass() +
1034                           " nodeId=" + searchResult.getNodeId() +
1035                           " nEntries=" + searchResult.getNEntries());
1036            }
1037            throw new DatabaseException(msg.toString(), e);
1038        }
1039
1040    if (location.bin == null) {
1041        return false;
1042    }
1043
1044    /*
1045     * If caller wants us to consider knownDeleted entries then do an
1046     * inexact search in findEntry since that will find knownDeleted
1047     * entries.  If caller doesn't want us to consider knownDeleted entries
1048     * then do an exact search in findEntry since that will not return
1049     * knownDeleted entries.
1050     */
1051    boolean exactSearch = false;
1052    boolean indicateIfExact = true;
1053    if (!findDeletedEntries) {
1054        exactSearch = true;
1055        indicateIfExact = false;
1056    }
1057        location.index =
1058        location.bin.findEntry(mainKey, indicateIfExact, exactSearch);
1059
1060    boolean match = false;
1061    if (findDeletedEntries) {
1062        match = (location.index >= 0 &&
1063             (location.index & IN.EXACT_MATCH) != 0);
1064        location.index &= ~IN.EXACT_MATCH;
1065    } else {
1066        match = (location.index >= 0);
1067    }
1068
1069        if (match) {
1070
1071            /*
1072             * A BIN parent was found and a slot matches the key. See if
1073             * we have to search further into what may be a dup tree.
1074             */
1075        if (!location.bin.isEntryKnownDeleted(location.index)) {
1076                
1077                /*
1078                 * If this database doesn't support duplicates, no point in
1079                 * incurring the potentially large cost of fetching in
1080                 * the child to check for dup trees. In the future, we could
1081                 * optimize further by storing state per slot as to whether
1082                 * a dup tree hangs below.
1083                 */
1084                if (database.getSortedDuplicates()) {
1085
1086                    Node childNode = location.bin.fetchTarget(location.index);
1087                    try {
1088
1089                        /* 
1090                         * Is our target LN a regular record or a dup count?
1091                         */
1092                        if (childNode == null) {
1093                            /* Child is a deleted cleaned LN. */
1094                        } else if (ln.containsDuplicates()) {
1095                            /* This is a duplicate count LN. */
1096                            return searchDupTreeForDupCountLNParent
1097                                (location, mainKey, childNode);
1098                        } else {
1099
1100                            /* 
1101                             * This is a regular LN. If this is a dup tree,
1102                             * descend and search. If not, we've found the
1103                             * parent.
1104                             */
1105                            if (childNode.containsDuplicates()) {
1106                                if (dupKey == null) {
1107
1108                                    /*
1109                                     * We are at a dup tree but our target LN
1110                                     * has no dup key because it's a deleted
1111                                     * LN.  We've encountered the case of SR
1112                                     * 8984 where we are searching for an LN
1113                                     * that was deleted before the conversion
1114                                     * to a duplicate tree.
1115                                     */
1116                    return searchDupTreeByNodeId
1117                                        (location, childNode, ln,
1118                                         searchDupTree, updateGeneration);
1119                                } else {
1120                                    return searchDupTreeForDBIN
1121                                        (location, dupKey, (DIN) childNode,
1122                                         ln, findDeletedEntries,
1123                                         indicateIfExact, exactSearch,
1124                                         splitsAllowed, updateGeneration);
1125                                }
1126                            }
1127                        }
1128                    } catch (DatabaseException e) {
1129                        location.bin.releaseLatchIfOwner();
1130                        throw e;
1131                    }
1132                }
1133            }
1134
1135            /* We had a match, we didn't need to search the duplicate tree. */
1136            location.childLsn = location.bin.getLsn(location.index);
1137            return true;
1138        } else {
1139            location.lnKey = mainKey;
1140            return false;
1141        }
1142    }
1143
1144    /**
1145     * For SR [#8984]: our prospective child is a deleted LN, and
1146     * we're facing a dup tree. Alas, the deleted LN has no data, and
1147     * therefore nothing to guide the search in the dup tree. Instead,
1148     * we search by node id.  This is very expensive, but this
1149     * situation is a very rare case.
1150     */
1151    private boolean searchDupTreeByNodeId(TreeLocation location,
1152                                          Node childNode,
1153                                          LN ln,
1154                                          boolean searchDupTree,
1155                                          boolean updateGeneration)
1156        throws DatabaseException {
1157
1158        if (searchDupTree) {
1159            BIN oldBIN = location.bin;
1160            if (childNode.matchLNByNodeId
1161                (location, ln.getNodeId())) {
1162                location.index &= ~IN.EXACT_MATCH;
1163                if (oldBIN != null) {
1164                    oldBIN.releaseLatch();
1165                }
1166                location.bin.latch(updateGeneration);
1167                return true;
1168            } else {
1169                return false;
1170            }
1171        } else {
1172            
1173            /*
1174             * This is called from undo() so this LN can
1175             * just be ignored.
1176             */
1177            return false;
1178        }
1179    }
1180    
1181    /**
1182     * @return true if childNode is the DIN parent of this DupCountLN
1183     */
1184    private boolean searchDupTreeForDupCountLNParent(TreeLocation location,
1185                                                     byte[] mainKey,
1186                                                     Node childNode) 
1187        throws DatabaseException {
1188        location.lnKey = mainKey;
1189        if (childNode instanceof DIN) {
1190            DIN dupRoot = (DIN) childNode;
1191            location.childLsn = dupRoot.getDupCountLNRef().getLsn();
1192            return true;
1193        } else {
1194
1195            /*
1196             * If we're looking for a DupCountLN but don't find a
1197             * duplicate tree, then the key now refers to a single
1198             * datum.  This can happen when all dups for a key are
1199             * deleted, the compressor runs, and then a single
1200             * datum is inserted.  [#10597]
1201             */
1202            return false;
1203        }
1204    }
1205
1206    /**
1207     * Search the dup tree for the DBIN parent of this ln.
1208     */
1209    private boolean searchDupTreeForDBIN(TreeLocation location,
1210                                         byte[] dupKey,
1211                                         DIN dupRoot,
1212                                         LN ln,
1213                                         boolean findDeletedEntries,
1214                                         boolean indicateIfExact,
1215                                         boolean exactSearch,
1216                                         boolean splitsAllowed,
1217                                         boolean updateGeneration)
1218        throws DatabaseException {                                     
1219
1220        assert dupKey != null;
1221
1222        dupRoot.latch();
1223
1224        try {
1225            /* Make sure there's room for inserts. */
1226            if (maybeSplitDuplicateRoot(location.bin, location.index)) {
1227                dupRoot = (DIN) location.bin.fetchTarget(location.index);
1228            }
1229
1230            /* 
1231             * Wait until after any duplicate root splitting to unlatch the
1232             * bin.
1233             */
1234            location.bin.releaseLatch();       
1235             
1236            /*
1237             * The dupKey is going to be the key that represents the LN in this
1238             * BIN parent.
1239             */
1240            location.lnKey = dupKey;
1241
1242            /* Search the dup tree */
1243            if (splitsAllowed) {
1244                try {
1245                    location.bin = (BIN) searchSubTreeSplitsAllowed
1246                        (dupRoot, location.lnKey, ln.getNodeId(),
1247                         updateGeneration);
1248                } catch (SplitRequiredException e) {
1249
1250                    /* 
1251                     * Shouldn't happen; the only caller of this method which
1252                     * allows splits is from recovery, which is single
1253                     * threaded.
1254                     */
1255                    throw new DatabaseException(e);
1256                }
1257            } else {
1258                location.bin = (BIN) searchSubTree
1259                    (dupRoot, location.lnKey, SearchType.NORMAL,
1260                     ln.getNodeId(), null, updateGeneration);
1261            }
1262
1263            /* Search for LN w/exact key. */
1264            location.index = location.bin.findEntry
1265                (location.lnKey, indicateIfExact, exactSearch);
1266            boolean match;
1267            if (findDeletedEntries) {
1268                match = (location.index >= 0 &&
1269                         (location.index & IN.EXACT_MATCH) != 0);
1270                location.index &= ~IN.EXACT_MATCH;
1271            } else {
1272                match = (location.index >= 0);
1273            }
1274
1275            if (match) {
1276                location.childLsn = location.bin.getLsn(location.index);
1277                return true;
1278            } else {
1279                return false;
1280            }
1281        } catch (DatabaseException e) {
1282            dupRoot.releaseLatchIfOwner();
1283            throw e;
1284        }
1285    }
1286
1287
1288    /**
1289     * Return a reference to the adjacent BIN.
1290     *
1291     * @param bin The BIN to find the next BIN for.  This BIN is latched.
1292     * @param traverseWithinDupTree if true, only search within the dup tree
1293     * and return null when the traversal runs out of duplicates.
1294     *
1295     * @return The next BIN, or null if there are no more.  The returned node
1296     * is latched and the caller must release it.  If null is returned, the
1297     * argument BIN remains latched.
1298     */
1299    public BIN getNextBin(BIN bin, boolean traverseWithinDupTree)
1300        throws DatabaseException {
1301
1302        return getNextBinInternal(traverseWithinDupTree, bin, true);
1303    }
1304
1305    /**
1306     * Return a reference to the previous BIN.
1307     *
1308     * @param bin The BIN to find the next BIN for.  This BIN is latched.
1309     * @param traverseWithinDupTree if true, only search within the dup tree
1310     * and return null when the traversal runs out of duplicates.
1311     *
1312     * @return The previous BIN, or null if there are no more.  The returned
1313     * node is latched and the caller must release it.  If null is returned,
1314     * the argument bin remains latched.
1315     */
1316    public BIN getPrevBin(BIN bin, boolean traverseWithinDupTree)
1317        throws DatabaseException {
1318
1319        return getNextBinInternal(traverseWithinDupTree, bin, false);
1320    }
1321
1322    /**
1323     * Helper routine for above two routines to iterate through BIN's.
1324     */
1325    private BIN getNextBinInternal(boolean traverseWithinDupTree,
1326                   BIN bin,
1327                   boolean forward)
1328        throws DatabaseException {
1329
1330        /*
1331         * Use the right most key (for a forward progressing cursor) or the
1332         * left most key (for a backward progressing cursor) as the idkey.  The
1333         * reason is that the BIN may get split while finding the next BIN so
1334         * it's not safe to take the BIN's identifierKey entry.  If the BIN
1335         * gets splits, then the right (left) most key will still be on the
1336         * resultant node.  The exception to this is that if there are no
1337         * entries, we just use the identifier key.
1338         */
1339        byte[] idKey = null;
1340
1341    if (bin.getNEntries() == 0) {
1342        idKey = bin.getIdentifierKey();
1343    } else if (forward) {
1344        idKey = bin.getKey(bin.getNEntries() - 1);
1345    } else {
1346        idKey = bin.getKey(0);
1347    }
1348
1349        IN next = bin;
1350    boolean nextIsLatched = false;
1351
1352        assert LatchSupport.countLatchesHeld() == 1:
1353            LatchSupport.latchesHeldToString();
1354
1355        /* 
1356         * Ascend the tree until we find a level that still has nodes to the
1357         * right (or left if !forward) of the path that we're on.  If we reach
1358         * the root level, we're done. If we're searching within a duplicate
1359         * tree, stay within the tree.
1360         */
1361        IN parent = null;
1362        IN nextIN = null;
1363    boolean nextINIsLatched = false;
1364        try {
1365            while (true) {
1366
1367                /* 
1368                 * Move up a level from where we are now and check to see if we
1369                 * reached the top of the tree.
1370                 */
1371                SearchResult result = null;
1372                if (!traverseWithinDupTree) {
1373                    /* Operating on a regular tree -- get the parent. */
1374            nextIsLatched = false;
1375                    result = getParentINForChildIN
1376                        (next, true /* requireExactMatch */,
1377                         true /* updateGeneration */);
1378                    if (result.exactParentFound) {
1379                        parent = result.parent;
1380                    } else {
1381                        /* We've reached the root of the tree. */
1382                        assert (LatchSupport.countLatchesHeld() == 0):
1383                            LatchSupport.latchesHeldToString();
1384                        return null;
1385                    }
1386                } else {
1387                    /* This is a duplicate tree, stay within the tree.*/
1388                    if (next.isRoot()) {
1389                        /* We've reached the top of the dup tree. */
1390                        next.releaseLatch();
1391            nextIsLatched = false;
1392                        return null;
1393                    } else {
1394                        result = getParentINForChildIN
1395                            (next, true /* requireExactMatch */,
1396                             true /* updateGeneration */);
1397            nextIsLatched = false;
1398                        if (result.exactParentFound) {
1399                            parent = result.parent;
1400                        } else {
1401                            return null;
1402                        }
1403                    }
1404                }
1405
1406                assert (LatchSupport.countLatchesHeld() == 1) :
1407                    LatchSupport.latchesHeldToString();
1408
1409                /* 
1410                 * Figure out which entry we are in the parent.  Add (subtract)
1411                 * 1 to move to the next (previous) one and check that we're
1412                 * still pointing to a valid child.  Don't just use the result
1413                 * of the parent.findEntry call in getParentNode, because we
1414                 * want to use our explicitly chosen idKey.
1415                 */
1416                int index = parent.findEntry(idKey, false, false);
1417                boolean moreEntriesThisBin = false;
1418                if (forward) {
1419                    index++;
1420                    if (index < parent.getNEntries()) {
1421                        moreEntriesThisBin = true;
1422                    }
1423                } else {
1424                    if (index > 0) {
1425                        moreEntriesThisBin = true;
1426                    }
1427                    index--;
1428                }
1429
1430                if (moreEntriesThisBin) {
1431
1432                    /* 
1433                     * There are more entries to the right of the current path
1434                     * in parent.  Get the entry, and then descend down the
1435                     * left most path to a BIN.
1436                     */
1437                    nextIN = (IN) parent.fetchTarget(index);
1438                    nextIN.latch();
1439            nextINIsLatched = true;
1440
1441                    assert (LatchSupport.countLatchesHeld() == 2):
1442                        LatchSupport.latchesHeldToString();
1443
1444                    if (nextIN instanceof BIN) {
1445                        /* We landed at a leaf (i.e. a BIN). */
1446                        parent.releaseLatch();
1447                        TreeWalkerStatsAccumulator treeStatsAccumulator =
1448                            getTreeStatsAccumulator();
1449                        if (treeStatsAccumulator != null) {
1450                            nextIN.accumulateStats(treeStatsAccumulator);
1451                        }
1452
1453                        return (BIN) nextIN;
1454                    } else {
1455
1456                        /* 
1457                         * We landed at an IN.  Descend down to the appropriate
1458                         * leaf (i.e. BIN) node.
1459                         */
1460            nextINIsLatched = false;
1461                        IN ret = searchSubTree(nextIN, null,
1462                                               (forward ?
1463                                                SearchType.LEFT :
1464                                                SearchType.RIGHT),
1465                                               -1,
1466                                               null,
1467                                               true /*updateGeneration*/);
1468                        parent.releaseLatch();
1469
1470                        assert LatchSupport.countLatchesHeld() == 1:
1471                            LatchSupport.latchesHeldToString();
1472
1473                        if (ret instanceof BIN) {
1474                            return (BIN) ret;
1475                        } else {
1476                            throw new InconsistentNodeException
1477                                ("subtree did not have a BIN for leaf");
1478                        }
1479                    }
1480                }
1481                next = parent;
1482        nextIsLatched = true;
1483            }
1484        } catch (DatabaseException e) {
1485        if (nextIsLatched) {
1486        next.releaseLatchIfOwner();
1487        nextIsLatched = false;
1488        }
1489            if (parent != null) {
1490                parent.releaseLatchIfOwner();
1491            }
1492            if (nextIN != null &&
1493        nextINIsLatched) {
1494                nextIN.releaseLatchIfOwner();
1495            }
1496            throw e;
1497        }
1498    }
1499
1500    /**
1501     * Split the root of the tree.
1502     */
1503    private void splitRoot()
1504        throws DatabaseException {
1505
1506        /* 
1507         * Create a new root IN, insert the current root IN into it, and then
1508         * call split.
1509         */
1510        EnvironmentImpl env = database.getDbEnvironment();
1511        LogManager logManager = env.getLogManager();
1512        INList inMemoryINs = env.getInMemoryINs();
1513
1514        IN curRoot = null;
1515        curRoot = (IN) root.fetchTarget(database, null);
1516        curRoot.latch();
1517        long curRootLsn = 0;
1518        long logLsn = 0;
1519        IN newRoot = null;
1520        try {
1521
1522            /*
1523             * Make a new root IN, giving it an id key from the previous root.
1524             */
1525            byte[] rootIdKey = curRoot.getKey(0);
1526            newRoot = new IN(database, rootIdKey, maxMainTreeEntriesPerNode,
1527                 curRoot.getLevel() + 1);
1528        newRoot.latch();
1529            newRoot.setIsRoot(true);
1530            curRoot.setIsRoot(false);
1531
1532            /*
1533             * Make the new root IN point to the old root IN. Log the old root
1534             * provisionally, because we modified it so it's not the root
1535             * anymore, then log the new root. We are guaranteed to be able to
1536             * insert entries, since we just made this root.
1537             */
1538            try {
1539                curRootLsn =
1540                    curRoot.optionalLogProvisional(logManager, newRoot);
1541                boolean insertOk = newRoot.insertEntry
1542                    (new ChildReference(curRoot, rootIdKey, curRootLsn));
1543                assert insertOk;
1544
1545                logLsn = newRoot.optionalLog(logManager);
1546            } catch (DatabaseException e) {
1547                /* Something went wrong when we tried to log. */
1548                curRoot.setIsRoot(true);
1549                throw e;
1550            }
1551            inMemoryINs.add(newRoot);
1552
1553            /*
1554             * Make the tree's root reference point to this new node. Now the
1555             * MapLN is logically dirty, but the change hasn't been logged.  Be
1556             * sure to flush the MapLN if we ever evict the root.
1557             */
1558            root.setTarget(newRoot);
1559            root.updateLsnAfterOptionalLog(database, logLsn);
1560            curRoot.split(newRoot, 0, maxMainTreeEntriesPerNode);
1561            root.setLsn(newRoot.getLastFullVersion());
1562
1563        } finally {
1564        /* FindBugs ignore possible null pointer dereference of newRoot. */
1565        newRoot.releaseLatch();
1566            curRoot.releaseLatch();
1567        }
1568        treeStats.nRootSplits++;
1569        traceSplitRoot(Level.FINE, TRACE_ROOT_SPLIT, newRoot, logLsn,
1570                       curRoot, curRootLsn);
1571    }
1572
1573    /**
1574     * Search the tree, starting at the root.  Depending on search type either
1575     * search using key, or search all the way down the right or left sides.
1576     * Stop the search either when the bottom of the tree is reached, or a node
1577     * matching nid is found (see below) in which case that node's parent is
1578     * returned. 
1579     *
1580     * Preemptive splitting is not done during the search.
1581     *
1582     * @param key - the key to search for, or null if searchType is LEFT or
1583     * RIGHT.
1584     *
1585     * @param searchType - The type of tree search to perform.  NORMAL means
1586     * we're searching for key in the tree.  LEFT/RIGHT means we're descending
1587     * down the left or right side, resp.  DELETE means we're descending the
1588     * tree and will return the lowest node in the path that has > 1 entries.
1589     *
1590     * @param nid - The nodeid to search for in the tree.  If found, returns
1591     * its parent.  If the nodeid of the root is passed, null is returned.
1592     *
1593     * @param binBoundary - If non-null, information is returned about whether
1594     * the BIN found is the first or last BIN in the database.
1595     *
1596     * @return - the Node that matches the criteria, if any.  This is the node
1597     * that is farthest down the tree with a match.  Returns null if the root
1598     * is null.  Node is latched (unless it's null) and must be unlatched by
1599     * the caller.  Only IN's and BIN's are returned, not LN's.  In a NORMAL
1600     * search, It is the caller's responsibility to do the findEntry() call on
1601     * the key and BIN to locate the entry that matches key.  The return value
1602     * node is latched upon return and it is the caller's responsibility to
1603     * unlatch it.
1604     */
1605    public IN search(byte[] key,
1606                     SearchType searchType,
1607                     long nid,
1608                     BINBoundary binBoundary,
1609                     boolean updateGeneration)
1610        throws DatabaseException {
1611
1612        IN rootIN = getRootIN(true /* updateGeneration */);
1613
1614        if (rootIN != null) {
1615            return searchSubTree
1616                (rootIN, key, searchType, nid, binBoundary, updateGeneration);
1617        } else {
1618            return null;
1619        }
1620    }
1621
1622    /**
1623     * Do a key based search, permitting pre-emptive splits. Returns the 
1624     * target node's parent.
1625     */
1626    public IN searchSplitsAllowed(byte[] key,
1627                                  long nid,
1628                                  boolean updateGeneration)
1629        throws DatabaseException {
1630
1631        IN insertTarget = null;
1632        while (insertTarget == null) {
1633            rootLatch.acquireShared();
1634            boolean rootLatched = true;
1635        boolean rootLatchedExclusive = false;
1636        boolean rootINLatched = false;
1637        boolean success = false;
1638            IN rootIN = null;
1639        try {
1640        while (true) {
1641            if (rootExists()) {
1642            rootIN = (IN) root.fetchTarget(database, null);
1643
1644            /* Check if root needs splitting. */
1645            if (rootIN.needsSplitting()) {
1646                if (!rootLatchedExclusive) {
1647                rootIN = null;
1648                rootLatch.release();
1649                rootLatch.acquireExclusive();
1650                rootLatchedExclusive = true;
1651                continue;
1652                }
1653                splitRoot();
1654
1655                /*
1656                 * We can't hold any latches while we lock.  If the
1657                 * root splits again between latch release and
1658                 * DbTree.db lock, no problem.  The latest root
1659                 * will still get written out.
1660                 */
1661                rootLatch.release();
1662                rootLatched = false;
1663                EnvironmentImpl env = database.getDbEnvironment();
1664                env.getDbMapTree().optionalModifyDbRoot(database);
1665                rootLatched = true;
1666                rootLatch.acquireExclusive();
1667                rootIN = (IN) root.fetchTarget(database, null);
1668            }
1669            rootIN.latch();
1670            rootINLatched = true;
1671            }
1672            break;
1673        }
1674        success = true;
1675        } finally {
1676        if (!success && rootINLatched) {
1677            rootIN.releaseLatch();
1678        }
1679        if (rootLatched) {
1680            rootLatch.release();    
1681        }
1682        }
1683
1684            /* Don't loop forever if the root is null. [#13897] */
1685            if (rootIN == null) {
1686                break;
1687            } 
1688
1689            try {
1690        success = false;
1691                insertTarget =
1692            searchSubTreeSplitsAllowed(rootIN, key, nid,
1693                           updateGeneration);
1694        success = true;
1695            } catch (SplitRequiredException e) {
1696
1697        success = true;
1698
1699                /* 
1700                 * The last slot in the root was used at the point when this
1701                 * thread released the rootIN latch in order to force splits.
1702                 * Retry. SR [#11147].
1703                 */
1704                continue;
1705            } finally {
1706        if (!success) {
1707            rootIN.releaseLatchIfOwner();
1708            if (insertTarget != null) {
1709            insertTarget.releaseLatchIfOwner();
1710            }
1711        }
1712        }
1713        }
1714
1715        return insertTarget;
1716    }
1717
1718    /* 
1719     * Singleton class to indicate that root IN needs to be relatched for
1720     * exclusive access due to a fetch occurring.
1721     */
1722    private static class RelatchRequiredException extends DatabaseException {
1723    public synchronized Throwable   fillInStackTrace() {
1724        return this;
1725    }
1726    }
1727
1728    private static RelatchRequiredException relatchRequiredException =
1729    new RelatchRequiredException();
1730
1731    /**
1732     * Wrapper for searchSubTreeInternal that does a restart if a
1733     * RelatchRequiredException is thrown (i.e. a relatch of the root is
1734     * needed.
1735     */
1736    public IN searchSubTree(IN parent,
1737                byte[] key,
1738                SearchType searchType,
1739                            long nid,
1740                            BINBoundary binBoundary,
1741                            boolean updateGeneration)
1742        throws DatabaseException {
1743
1744    /* 
1745     * Max of two iterations required.  First is root latched shared, and
1746     * second is root latched exclusive.
1747     */
1748    for (int i = 0; i < 2; i++) {
1749        try {
1750        return searchSubTreeInternal(parent, key, searchType, nid,
1751                         binBoundary, updateGeneration);
1752        } catch (RelatchRequiredException RRE) {
1753        parent = getRootINLatchedExclusive(updateGeneration);
1754        }
1755    }
1756
1757    throw new DatabaseException
1758        ("searchSubTreeInternal should have completed in two tries");
1759    }
1760
1761    /**
1762     * Searches a portion of the tree starting at parent using key.  If during
1763     * the search a node matching a non-null nid argument is found, its parent
1764     * is returned.  If searchType is NORMAL, then key must be supplied to
1765     * guide the search.  If searchType is LEFT (or RIGHT), then the tree is
1766     * searched down the left (or right) side to find the first (or last) leaf,
1767     * respectively.  
1768     * <p>
1769     * Enters with parent latched, assuming it's not null.  Exits with the
1770     * return value latched, assuming it's not null.
1771     * <p>
1772     * @param parent - the root of the subtree to start the search at.  This
1773     * node should be latched by the caller and will be unlatched prior to
1774     * return.
1775     * 
1776     * @param key - the key to search for, unless searchType is LEFT or RIGHT
1777     *
1778     * @param searchType - NORMAL means search using key and, optionally, nid.
1779     *                     LEFT means find the first (leftmost) leaf
1780     *                     RIGHT means find the last (rightmost) leaf
1781     *
1782     * @param nid - The nodeid to search for in the tree.  If found, returns
1783     * its parent.  If the nodeid of the root is passed, null is returned.
1784     * Pass -1 if no nodeid based search is desired.
1785     *
1786     * @return - the node matching the argument criteria, or null.  The node is
1787     * latched and must be unlatched by the caller.  The parent argument and
1788     * any other nodes that are latched during the search are unlatched prior
1789     * to return.
1790     *
1791     * @throws RelatchRequiredException if the root node (parent) must be
1792     * relatched exclusively because a null target was encountered (i.e. a
1793     * fetch must be performed on parent's child and the parent is latched
1794     * shared.
1795     */
1796    public IN searchSubTreeInternal(IN parent,
1797                    byte[] key,
1798                    SearchType searchType,
1799                    long nid,
1800                    BINBoundary binBoundary,
1801                    boolean updateGeneration)
1802        throws DatabaseException {
1803
1804        /* Return null if we're passed a null arg. */
1805        if (parent == null) {
1806            return null;
1807        }
1808
1809        if ((searchType == SearchType.LEFT ||
1810             searchType == SearchType.RIGHT) &&
1811            key != null) {
1812
1813            /* 
1814         * If caller is asking for a right or left search, they shouldn't
1815         * be passing us a key.
1816         */
1817            throw new IllegalArgumentException  
1818                ("searchSubTree passed key and left/right search");
1819        }
1820
1821        assert parent.isLatchOwnerForRead();
1822
1823        if (parent.getNodeId() == nid) {
1824            parent.releaseLatch();
1825            return null;
1826        }
1827
1828        if (binBoundary != null) {
1829            binBoundary.isLastBin = true;
1830            binBoundary.isFirstBin = true;
1831        }
1832
1833        int index;
1834        IN child = null;
1835    IN grandParent = null;
1836    boolean childIsLatched = false;
1837    boolean grandParentIsLatched = false;
1838    boolean maintainGrandParentLatches = !parent.isLatchOwnerForWrite();
1839
1840        TreeWalkerStatsAccumulator treeStatsAccumulator =
1841            getTreeStatsAccumulator();
1842
1843        try {
1844            do {
1845                if (treeStatsAccumulator != null) {
1846                    parent.accumulateStats(treeStatsAccumulator);
1847                }
1848
1849                if (parent.getNEntries() == 0) {
1850                    /* No more children, can't descend anymore. */
1851                    return parent;
1852                } else if (searchType == SearchType.NORMAL) {
1853                    /* Look for the entry matching key in the current node. */
1854                    index = parent.findEntry(key, false, false);
1855                } else if (searchType == SearchType.LEFT) {
1856                    /* Left search, always take the 0th entry. */
1857                    index = 0;
1858                } else if (searchType == SearchType.RIGHT) {
1859                    /* Right search, always take the highest entry. */
1860                    index = parent.getNEntries() - 1;
1861                } else {
1862                    throw new IllegalArgumentException  
1863                        ("Invalid value of searchType: " + searchType);
1864                }
1865
1866                assert index >= 0;
1867
1868                if (binBoundary != null) {
1869                    if (index != parent.getNEntries() - 1) {
1870                        binBoundary.isLastBin = false;
1871                    }
1872                    if (index != 0) {
1873                        binBoundary.isFirstBin = false;
1874                    }
1875                }
1876
1877        /*
1878         * Get the child node.  If target is null, and we don't have
1879         * parent latched exclusively, then we need to relatch this
1880         * parent so that we can fill in the target.  Fetching a target
1881         * is a write to a node so it must be exclusively latched.
1882         * Once we have the parent relatched exclusively, then we can
1883         * release the grand parent.
1884         */
1885        if (maintainGrandParentLatches &&
1886            parent.getTarget(index) == null &&
1887            !parent.isAlwaysLatchedExclusively()) {
1888
1889            if (grandParent == null) {
1890
1891            /* 
1892             * grandParent is null which implies parent is the root
1893             * so throw RelatchRequiredException.
1894             */
1895            throw relatchRequiredException;
1896            } else {
1897            /* Release parent shared and relatch exclusive. */
1898            parent.releaseLatch();
1899            parent.latch();
1900            }
1901
1902            /*
1903             * Once parent has been re-latched exclusive we can release
1904             * grandParent now (sooner), rather than after the
1905             * fetchTarget (later).
1906             */
1907            if (grandParent != null) {
1908            grandParent.releaseLatch();
1909            grandParentIsLatched = false;
1910            grandParent = null;
1911            }
1912        }
1913                child = (IN) parent.fetchTarget(index);
1914
1915        /*
1916         * We know we're done with grandParent for sure, so release
1917         * now.
1918         */
1919        if (grandParent != null) {
1920            grandParent.releaseLatch();
1921            grandParentIsLatched = false;
1922        }
1923
1924        /* See if we're even using shared latches. */
1925        if (maintainGrandParentLatches) {
1926            child.latchShared(updateGeneration);
1927        } else {
1928            child.latch(updateGeneration);
1929        }
1930        childIsLatched = true;
1931
1932                if (treeStatsAccumulator != null) {
1933                    child.accumulateStats(treeStatsAccumulator);
1934                }
1935
1936                /* 
1937                 * If this child matches nid, then stop the search and return
1938                 * the parent.
1939                 */
1940                if (child.getNodeId() == nid) {
1941                    child.releaseLatch();
1942            childIsLatched = false;
1943                    return parent;
1944                }
1945
1946                /* Continue down a level */
1947        if (maintainGrandParentLatches) {
1948            grandParent = parent;
1949            grandParentIsLatched = true;
1950        } else {
1951            parent.releaseLatch();
1952        }
1953                parent = child;
1954            } while (!(parent instanceof BIN));
1955
1956            return child;
1957        } catch (Throwable   t) {
1958
1959            /*
1960             * In [#14903] we encountered a latch exception below and the
1961             * original exception t was lost.  Print the stack trace and
1962             * rethrow the original exception if this happens again, to get
1963             * more information about the problem.
1964             */
1965            try {
1966                if (child != null &&
1967                    childIsLatched) {
1968                    child.releaseLatchIfOwner();
1969                }
1970
1971                if (parent != child) {
1972                    parent.releaseLatchIfOwner();
1973                }
1974            } catch (Throwable   t2) {
1975                t2.printStackTrace();
1976            }
1977
1978            if (t instanceof DatabaseException) {
1979                /* don't re-wrap a DatabaseException; we may need its type. */
1980                throw (DatabaseException) t;
1981            } else {
1982                throw new DatabaseException(t);
1983            }
1984        } finally {
1985            if (grandParent != null &&
1986        grandParentIsLatched) {
1987                grandParent.releaseLatch();
1988        grandParentIsLatched = false;
1989            }
1990    }
1991    }
1992
1993    /**
1994     * Search down the tree using a key, but instead of returning the BIN that
1995     * houses that key, find the point where we can detach a deletable
1996     * subtree. A deletable subtree is a branch where each IN has one child,
1997     * and the bottom BIN has no entries and no resident cursors. That point
1998     * can be found by saving a pointer to the lowest node in the path with
1999     * more than one entry.
2000     *
2001     *              INa
2002     *             /   \
2003     *          INb    INc
2004     *          |       |
2005     *         INd     ..
2006     *         / \
2007     *      INe  ..
2008     *       |
2009     *     BINx (suspected of being empty)
2010     *
2011     * In this case, we'd like to prune off the subtree headed by INe. INd
2012     * is the parent of this deletable subtree. As we descend, we must keep
2013     * latches for all the nodes that will be logged. In this case, we
2014     * will need to keep INa, INb and INd latched when we return from this
2015     * method.
2016     *
2017     * The method returns a list of parent/child/index structures. In this
2018     * example, the list will hold:
2019     *  INa/INb/index
2020     *  INb/INd/index
2021     *  INd/INe/index
2022     * Every node is latched, and every node except for the bottom most child
2023     * (INe) must be logged. 
2024     */
2025    public void searchDeletableSubTree(IN parent,
2026                                       byte[] key,
2027                                       ArrayList   nodeLadder)
2028        throws DatabaseException,
2029               NodeNotEmptyException,
2030               CursorsExistException {
2031
2032        assert (parent!=null);
2033        assert (key!= null);
2034        assert parent.isLatchOwnerForWrite();
2035
2036        int index;
2037        IN child = null;
2038
2039        /* Save the lowest IN in the path that has multiple entries. */
2040        IN lowestMultipleEntryIN = null;
2041
2042        do {
2043            if (parent.getNEntries() == 0) {
2044                break;
2045            }
2046 
2047            /* Remember if this is the lowest multiple point. */
2048            if (parent.getNEntries() > 1) {
2049                lowestMultipleEntryIN = parent;
2050            }
2051
2052            index = parent.findEntry(key, false, false);
2053            assert index >= 0;
2054
2055            /* Get the child node that matches. */
2056            child = (IN) parent.fetchTarget(index);
2057            child.latch(false);
2058            nodeLadder.add(new SplitInfo(parent, child, index));
2059
2060            /* Continue down a level */
2061            parent = child;
2062        } while (!(parent instanceof BIN));
2063
2064        /*
2065         * See if there is a reason we can't delete this BIN -- i.e.
2066         * new items have been inserted, or a cursor exists on it.
2067         */
2068        if ((child != null) && (child instanceof BIN)) {
2069            if (child.getNEntries() != 0) {
2070                throw NodeNotEmptyException.NODE_NOT_EMPTY;
2071            }
2072
2073            /* 
2074             * This case can happen if we are keeping a BIN on an empty
2075             * cursor as we traverse.
2076             */
2077            if (((BIN) child).nCursors() > 0) {
2078                throw CursorsExistException.CURSORS_EXIST;
2079            }
2080        }
2081            
2082        if (lowestMultipleEntryIN != null) {
2083
2084            /* 
2085             * Release all nodes up to the pair that holds the detach 
2086             * point. We won't be needing those nodes, since they'll be 
2087             * pruned and won't need to be updated.
2088             */
2089            ListIterator   iter = nodeLadder.listIterator(nodeLadder.size());
2090            while (iter.hasPrevious()) {
2091                SplitInfo info = (SplitInfo) iter.previous();
2092                if (info.parent == lowestMultipleEntryIN) {
2093                    break;
2094                } else {
2095                    info.child.releaseLatch();
2096                    iter.remove();
2097                }
2098            }
2099        } else {
2100
2101            /* 
2102             * We actually have to prune off the entire tree. Release
2103             * all latches, and clear the node ladder. 
2104             */
2105            releaseNodeLadderLatches(nodeLadder);
2106            nodeLadder.clear();
2107        }
2108    }
2109
2110    /**
2111     * Search the portion of the tree starting at the parent, permitting 
2112     * preemptive splits. 
2113     */
2114    private IN searchSubTreeSplitsAllowed(IN parent,
2115                                          byte[] key,
2116                                          long nid,
2117                                          boolean updateGeneration)
2118        throws DatabaseException, SplitRequiredException {
2119
2120        if (parent != null) {
2121
2122            /*
2123             * Search downward until we hit a node that needs a split. In
2124             * that case, retreat to the top of the tree and force splits
2125             * downward.
2126             */
2127            while (true) {
2128                try {
2129                    return searchSubTreeUntilSplit
2130                        (parent, key, nid, updateGeneration);
2131                } catch (SplitRequiredException e) {
2132                    /* SR [#11144]*/
2133                    if (waitHook != null) {
2134                        waitHook.doHook();
2135                    }
2136
2137                    /* 
2138                     * ForceSplit may itself throw SplitRequiredException if it
2139                     * finds that the parent doesn't have room to hold an extra
2140                     * entry. Allow the exception to propagate up to a place
2141                     * where it's safe to split the parent. We do this rather
2142                     * than
2143                     */
2144                    forceSplit(parent, key);
2145                }
2146            }
2147        } else {
2148            return null;
2149        }
2150    }
2151
2152    /**
2153     * Search the subtree, but throw an exception when we see a node 
2154     * that has to be split.
2155     */
2156    private IN searchSubTreeUntilSplit(IN parent,
2157                                       byte[] key,
2158                                       long nid,
2159                                       boolean updateGeneration)
2160        throws DatabaseException, SplitRequiredException {
2161
2162        /* Return null if we're passed a null arg. */
2163        if (parent == null) {
2164            return null;
2165        }
2166
2167        assert parent.isLatchOwnerForWrite();
2168
2169        if (parent.getNodeId() == nid) {
2170            parent.releaseLatch();
2171            return null;
2172        }
2173
2174        int index;
2175        IN child = null;
2176    boolean childIsLatched = false;
2177    boolean success = false;
2178
2179        try {
2180            do {
2181                if (parent.getNEntries() == 0) {
2182                    /* No more children, can't descend anymore. */
2183            success = true;
2184                    return parent;
2185                } else {
2186                    /* Look for the entry matching key in the current node. */
2187                    index = parent.findEntry(key, false, false);
2188                }
2189
2190                assert index >= 0;
2191
2192                /* Get the child node that matches. */
2193        child = (IN) parent.fetchTarget(index);
2194                child.latch(updateGeneration);
2195        childIsLatched = true;
2196
2197                /* Throw if we need to split. */
2198                if (child.needsSplitting()) {
2199                    child.releaseLatch();
2200            childIsLatched = false;
2201                    parent.releaseLatch();
2202            success = true;
2203                    throw splitRequiredException;
2204                }
2205
2206                /* 
2207                 * If this child matches nid, then stop the search and return
2208                 * the parent.
2209                 */
2210                if (child.getNodeId() == nid) {
2211                    child.releaseLatch();
2212            childIsLatched = false;
2213            success = true;
2214                    return parent;
2215                }
2216
2217                /* Continue down a level */
2218                parent.releaseLatch();
2219                parent = child;
2220            } while (!(parent instanceof BIN));
2221
2222        success = true;
2223            return parent;
2224        } finally {
2225        if (!success) {
2226        if (child != null &&
2227            childIsLatched) {
2228            child.releaseLatchIfOwner();
2229        }
2230        if (parent != child) {
2231            parent.releaseLatchIfOwner();
2232        }
2233        }
2234        }
2235    }
2236
2237    /**
2238     * Do pre-emptive splitting in the subtree topped by the "parent" node.
2239     * Search down the tree until we get to the BIN level, and split any nodes
2240     * that fit the splittable requirement.
2241     * 
2242     * Note that more than one node in the path may be splittable. For example,
2243     * a tree might have a level2 IN and a BIN that are both splittable, and 
2244     * would be encountered by the same insert operation.
2245     */
2246    private void forceSplit(IN parent,
2247                            byte[] key)
2248        throws DatabaseException, SplitRequiredException {
2249
2250        ArrayList   nodeLadder = new ArrayList  ();
2251
2252    boolean allLeftSideDescent = true;
2253    boolean allRightSideDescent = true;
2254        int index;
2255        IN child = null;
2256        IN originalParent = parent;
2257        ListIterator   iter = null;
2258
2259        boolean isRootLatched = false;
2260        boolean success = false;
2261        try {
2262
2263            /*
2264             * Latch the root in order to update the root LSN when we're done.
2265             * Latch order must be: root, root IN.  We'll leave this method
2266             * with the original parent latched.
2267             */
2268            if (originalParent.isDbRoot()) {
2269                rootLatch.acquireExclusive();
2270                isRootLatched = true;
2271            }
2272            originalParent.latch();
2273
2274            /* 
2275             * Another thread may have crept in and 
2276             *  - used the last free slot in the parent, making it impossible 
2277             *    to correctly progagate the split. 
2278             *  - actually split the root, in which case we may be looking at 
2279             *    the wrong subtree for this search. 
2280             * If so, throw and retry from above. SR [#11144]
2281             */
2282            if (originalParent.needsSplitting() || !originalParent.isRoot()) {
2283                throw splitRequiredException;
2284            }
2285
2286            /* 
2287             * Search downward to the BIN level, saving the information
2288             * needed to do a split if necessary.
2289             */
2290            do {
2291                if (parent.getNEntries() == 0) {
2292                    /* No more children, can't descend anymore. */
2293                    break;
2294                } else {
2295                    /* Look for the entry matching key in the current node. */
2296                    index = parent.findEntry(key, false, false);
2297                    if (index != 0) {
2298                        allLeftSideDescent = false;
2299                    }
2300                    if (index != (parent.getNEntries() - 1)) {
2301                        allRightSideDescent = false;
2302                    }
2303                }
2304
2305                assert index >= 0;
2306
2307                /* 
2308                 * Get the child node that matches. We only need to work on
2309                 * nodes in residence.
2310                 */
2311                child = (IN) parent.getTarget(index);
2312                if (child == null) {
2313                    break;
2314                } else {
2315                    child.latch();
2316                    nodeLadder.add(new SplitInfo(parent, child, index));
2317                } 
2318
2319                /* Continue down a level */
2320                parent = child;
2321            } while (!(parent instanceof BIN));
2322
2323            boolean startedSplits = false;
2324            LogManager logManager =
2325                database.getDbEnvironment().getLogManager();
2326
2327            /* 
2328             * Process the accumulated nodes from the bottom up. Split each
2329             * node if required. If the node should not split, we check if
2330             * there have been any splits on the ladder yet. If there are none,
2331             * we merely release the node, since there is no update.  If splits
2332             * have started, we need to propagate new LSNs upward, so we log
2333             * the node and update its parent.
2334             *
2335             * Start this iterator at the end of the list.
2336             */
2337            iter = nodeLadder.listIterator(nodeLadder.size());
2338            long lastParentForSplit = -1;
2339            while (iter.hasPrevious()) {
2340                SplitInfo info = (SplitInfo) iter.previous();
2341                child = info.child;
2342                parent = info.parent;
2343                index = info.index;
2344
2345                /* Opportunistically split the node if it is full. */
2346                if (child.needsSplitting()) {
2347            int maxEntriesPerNode = (child.containsDuplicates() ?
2348                         maxDupTreeEntriesPerNode :
2349                         maxMainTreeEntriesPerNode);
2350                    if (allLeftSideDescent || allRightSideDescent) {
2351                        child.splitSpecial(parent,
2352                                           index,
2353                                           maxEntriesPerNode,
2354                                           key,
2355                                           allLeftSideDescent);
2356                    } else {
2357                        child.split(parent, index, maxEntriesPerNode);
2358                    }
2359                    lastParentForSplit = parent.getNodeId();
2360                    startedSplits = true;
2361
2362                    /*
2363                     * If the DB root IN was logged, update the DB tree's child
2364                     * reference.  Now the MapLN is logically dirty, but the
2365                     * change hasn't been logged. Set the rootIN to be dirty
2366                     * again, to force flushing the rootIN and mapLN in the 
2367                     * next checkpoint. Be sure to flush the MapLN
2368                     * if we ever evict the root.
2369                     */
2370                    if (parent.isDbRoot()) {
2371                        assert isRootLatched;
2372                        root.setLsn(parent.getLastFullVersion());
2373                        parent.setDirty(true);
2374                    }
2375                } else {
2376                    if (startedSplits) {
2377                        long newLsn = 0;
2378
2379                        /* 
2380                         * If this child was the parent of a split, it's
2381                         * already logged by the split call. We just need to
2382                         * propagate the logging upwards. If this child is just
2383                         * a link in the chain upwards, log it.
2384                         */
2385                        if (lastParentForSplit == child.getNodeId()) {
2386                            newLsn = child.getLastFullVersion();
2387                        } else {
2388                            newLsn = child.optionalLog(logManager);
2389                        }
2390                        parent.updateEntry(index, newLsn);
2391                    } 
2392                }
2393                child.releaseLatch();
2394                child = null;
2395                iter.remove();
2396            }
2397
2398            success = true;
2399        } finally {
2400
2401            if (!success) {
2402                if (child != null) {
2403                    child.releaseLatchIfOwner();
2404                }
2405                originalParent.releaseLatchIfOwner();
2406            }
2407
2408            /*
2409             * Unlatch any remaining children. There should only be remainders
2410             * in the event of an exception.
2411             */
2412            if (nodeLadder.size() > 0) {
2413                iter = nodeLadder.listIterator(nodeLadder.size());
2414                while (iter.hasPrevious()) {
2415                    SplitInfo info = (SplitInfo) iter.previous();
2416                    info.child.releaseLatchIfOwner();
2417                }
2418            }
2419
2420            if (isRootLatched) {
2421                rootLatch.release();
2422            }
2423        }
2424    }
2425
2426    /**
2427     * Helper to obtain the root IN with shared root latching.  Optionally
2428     * updates the generation of the root when latching it.
2429     */
2430    public IN getRootIN(boolean updateGeneration) 
2431        throws DatabaseException {
2432
2433    return getRootINInternal(updateGeneration, false);
2434    }
2435
2436    /**
2437     * Helper to obtain the root IN with exclusive root latching.  Optionally
2438     * updates the generation of the root when latching it.
2439     */
2440    public IN getRootINLatchedExclusive(boolean updateGeneration) 
2441        throws DatabaseException {
2442
2443    return getRootINInternal(updateGeneration, true);
2444    }
2445
2446    private IN getRootINInternal(boolean updateGeneration, boolean exclusive)
2447        throws DatabaseException {
2448
2449    rootLatch.acquireShared();
2450        IN rootIN = null;
2451        try {
2452            if (rootExists()) {
2453                rootIN = (IN) root.fetchTarget(database, null);
2454        if (exclusive) {
2455            rootIN.latch(updateGeneration);
2456        } else {
2457            rootIN.latchShared(updateGeneration);
2458        }
2459            }
2460            return rootIN;
2461        } finally {
2462        rootLatch.release();
2463        }
2464    }
2465
2466    /**
2467     * Inserts a new LN into the tree.
2468     * @param ln The LN to insert into the tree.
2469     * @param key Key value for the node
2470     * @param allowDuplicates whether to allow duplicates to be inserted
2471     * @param cursor the cursor to update to point to the newly inserted
2472     * key/data pair, or null if no cursor should be updated.
2473     * @return true if LN was inserted, false if it was a duplicate
2474     * duplicate or if an attempt was made to insert a duplicate when
2475     * allowDuplicates was false.
2476     */
2477    public boolean insert(LN ln,
2478                          byte[] key,
2479                          boolean allowDuplicates,
2480                          CursorImpl cursor,
2481              LockResult lnLock)
2482        throws DatabaseException {
2483
2484        validateInsertArgs(allowDuplicates);
2485
2486        EnvironmentImpl env = database.getDbEnvironment();
2487        LogManager logManager = env.getLogManager();
2488        INList inMemoryINs = env.getInMemoryINs();
2489
2490        /* Find and latch the relevant BIN. */
2491        BIN bin = null;
2492        try {
2493            bin = findBinForInsert(key, logManager, inMemoryINs, cursor);
2494            assert bin.isLatchOwnerForWrite();
2495            
2496            /* Make a child reference as a candidate for insertion. */
2497            ChildReference newLNRef =
2498        new ChildReference(ln, key, DbLsn.NULL_LSN);
2499
2500        /*
2501         * If we're doing a put that is not a putCurrent, then the cursor
2502         * passed in may not be pointing to BIN (it was set to the BIN that
2503         * the search landed on which may be different than BIN).  Set the
2504         * BIN correctly here so that adjustCursorsForInsert doesn't blow
2505         * an assertion.  We'll finish the job by setting the index below.
2506         */
2507        cursor.setBIN(bin);
2508
2509            int index = bin.insertEntry1(newLNRef);
2510            if ((index & IN.INSERT_SUCCESS) != 0) {
2511
2512                /* 
2513                 * Update the cursor to point to the entry that has been
2514                 * successfully inserted.
2515                 */
2516                index &= ~IN.INSERT_SUCCESS;
2517        cursor.updateBin(bin, index);
2518
2519                /* Log the new LN. */
2520                long newLsn = DbLsn.NULL_LSN;
2521
2522        try {
2523            newLsn = ln.optionalLog
2524                        (env, database, key, DbLsn.NULL_LSN, 0,
2525                         cursor.getLocker());
2526        } finally {
2527                    if ((newLsn == DbLsn.NULL_LSN) &&
2528                    !database.isDeferredWrite()) {
2529
2530                        /*
2531                         * Possible buffer overflow, out-of-memory, or I/O
2532                         * exception during logging.  The BIN entry will
2533                         * contain a NULL_LSN.  To prevent an exception during
2534                         * a fetch, we set the KnownDeleted flag.  We do not
2535                         * call BIN.deleteEntry because cursors will not be
2536                         * adjusted.  We do not add this entry to the
2537                         * compressor queue to avoid complexity (this is rare).
2538                         * [13126, 12605, 11271]
2539                         */
2540                        bin.setKnownDeleted(index);
2541                    }
2542        }
2543        lnLock.setAbortLsn(DbLsn.NULL_LSN, true, true);
2544                bin.updateEntry(index, newLsn);
2545
2546                traceInsert(Level.FINER, env, bin, ln, newLsn, index);
2547                return true;
2548            } else {
2549
2550                /* 
2551         * Entry may have been a duplicate. Insertion was not
2552         * successful.
2553         */
2554                index &= ~IN.EXACT_MATCH;
2555        cursor.updateBin(bin, index);
2556
2557                LN currentLN = null;
2558        boolean isDup = false;
2559        Node n = bin.fetchTarget(index);
2560        if (n == null || n instanceof LN) {
2561            currentLN = (LN) n;
2562        } else {
2563                    isDup = true;
2564        }
2565
2566                /* If an LN is present, lock it and check deleted-ness. */
2567        boolean isDeleted = false;
2568                LockResult currentLock = null;
2569
2570                if (!isDup) {
2571                    if (currentLN == null) {
2572                        /* The LN was cleaned. */
2573                        isDeleted = true;
2574                    } else {
2575                        currentLock = cursor.lockLNDeletedAllowed
2576                            (currentLN, LockType.WRITE);
2577                        currentLN = currentLock.getLN();
2578                        /* The BIN/index may have changed while locking. */
2579                        bin = cursor.getBIN();
2580                        index = cursor.getIndex();
2581                        if (cursor.getDupBIN() != null) {
2582
2583                            /*
2584                             * A dup tree appeared during locking.  We will
2585                             * position to a different dup tree entry later in
2586                             * insertDuplicate, so we must remove the cursor
2587                             * from this dup tree entry.  This is a rare case
2588                             * so performance is not an issue.
2589                             */
2590                            cursor.clearDupBIN(true /*alreadyLatched*/);
2591                            isDup = true;
2592                        } else if (bin.isEntryKnownDeleted(index) ||
2593                                   currentLN == null ||
2594                                   currentLN.isDeleted()) {
2595                            /* The current LN is deleted/cleaned. */
2596                            isDeleted = true;
2597                        }
2598                    }
2599                }
2600
2601                if (isDeleted) {
2602
2603                    /*
2604                     * Set the abort LSN to that of the lock held on the
2605                     * current LN, if the current LN was previously locked by
2606                     * this txn.  This is needed when we change the node ID of
2607                     * this slot.
2608                     *
2609                     * If reusing a slot with a deleted LN deleted in a prior
2610                     * transaction (the LockGrantType is NEW or UPGRADE),
2611                     * always set abortKnownDeleted=true.  It may be that the
2612                     * existing slot is PENDING_DELETED, but we restore to
2613                     * KNOWN_DELETED in the event of an abort.
2614                     */
2615                    long abortLsn = bin.getLsn(index);
2616                    boolean abortKnownDeleted = true;
2617                    if (currentLN != null &&
2618                        currentLock.getLockGrant() == LockGrantType.EXISTING) {
2619                        long nodeId = currentLN.getNodeId();
2620                        Locker locker = cursor.getLocker();
2621            WriteLockInfo info = locker.getWriteLockInfo(nodeId);
2622            abortLsn = info.getAbortLsn();
2623            abortKnownDeleted = info.getAbortKnownDeleted();
2624                    }
2625            lnLock.setAbortLsn(abortLsn, abortKnownDeleted);
2626
2627                    /*
2628                     * Current entry is a deleted entry. Replace it with LN.
2629                     * Pass NULL_LSN for the oldLsn parameter of the log()
2630                     * method because the old LN was counted obsolete when it
2631                     * was deleted.
2632                     */
2633                    long newLsn = ln.optionalLog(env, database,
2634                     key, DbLsn.NULL_LSN, 0,
2635                     cursor.getLocker());
2636
2637                    bin.updateEntry(index, ln, newLsn, key);
2638                    bin.clearKnownDeleted(index);
2639                    bin.clearPendingDeleted(index);
2640
2641                    traceInsert(Level.FINER, env, bin, ln, newLsn, index);
2642                    return true;
2643                } else {
2644
2645            /* 
2646             * Attempt to insert a duplicate in an exception dup tree
2647                     * or create a dup tree if none exists.
2648             */            
2649            return insertDuplicate
2650                        (key, bin, ln, logManager, inMemoryINs, cursor, lnLock,
2651                         allowDuplicates);
2652                }
2653            }
2654        } finally {
2655            cursor.releaseBIN();
2656        }
2657    }
2658
2659    /**
2660     * Attempts to insert a duplicate at the current cursor BIN position.  If
2661     * an existing dup tree exists, insert into it; otherwise, create a new
2662     * dup tree and place the new LN and the existing LN into it.  If the
2663     * current BIN entry contains an LN, the caller guarantees that it is not
2664     * deleted.
2665     *
2666     * @return true if duplicate inserted successfully, false if it was a
2667     * duplicate duplicate, false if a there is an existing LN and
2668     * allowDuplicates is false.
2669     */
2670    private boolean insertDuplicate(byte[] key,
2671                    BIN bin,
2672                                    LN newLN,
2673                                    LogManager logManager,
2674                                    INList inMemoryINs,
2675                                    CursorImpl cursor,
2676                    LockResult lnLock,
2677                                    boolean allowDuplicates)
2678        throws DatabaseException {
2679
2680        EnvironmentImpl env = database.getDbEnvironment();
2681    int index = cursor.getIndex();
2682        boolean successfulInsert = false;
2683
2684        DIN dupRoot = null;
2685        Node n = bin.fetchTarget(index);
2686    long binNid = bin.getNodeId();
2687
2688        if (n instanceof DIN) {
2689            DBIN dupBin = null;
2690
2691            /*
2692             * A duplicate tree exists.  Find the relevant DBIN and insert the
2693             * new entry into it.
2694             */
2695            try {
2696                dupRoot = (DIN) n;
2697                dupRoot.latch();
2698
2699                /* Lock the DupCountLN before logging any LNs. */
2700                LockResult dclLockResult =
2701                    cursor.lockDupCountLN(dupRoot, LockType.WRITE);
2702                /* The BIN/index may have changed during locking. */
2703                bin = cursor.getBIN();
2704                index = cursor.getIndex();
2705
2706                /*
2707                 * Do not proceed if duplicates are not allowed and there are
2708                 * one or more duplicates already present.  Note that if the
2709                 * dup count is zero, we allow the insert.
2710                 */
2711                if (!allowDuplicates) {
2712                    DupCountLN dcl = (DupCountLN) dclLockResult.getLN();
2713                    if (dcl.getDupCount() > 0) {
2714                        return false;
2715                    }
2716                }
2717
2718                /*
2719                 * Split the dup root if necessary.  The dup root may have
2720                 * changed during locking above or by the split, so refetch it.
2721                 * In either case it will be latched.
2722                 */
2723                maybeSplitDuplicateRoot(bin, index);
2724                dupRoot = (DIN) bin.fetchTarget(index);
2725
2726                /* 
2727                 * Search the duplicate tree for the right place to insert this
2728                 * new record. Releases the latch on duplicateRoot. If the
2729                 * duplicateRoot got logged as a result of some splitting,
2730                 * update the BIN's LSN information. The SortedLSNTreeWalker
2731                 * relies on accurate LSNs in the in-memory tree.
2732                 */
2733                byte[] newLNKey = newLN.getData();
2734                long previousLsn = dupRoot.getLastFullVersion();
2735                try {
2736                    dupBin = (DBIN) searchSubTreeSplitsAllowed
2737                        (dupRoot, newLNKey, -1, true /*updateGeneration*/);
2738                } catch (SplitRequiredException e) {
2739
2740                    /* 
2741                     * Shouldn't happen -- we have the DIN in the root of the
2742                     * dup tree latched during this insert, so there should be
2743                     * no possibility of being unable to insert a new entry
2744                     * into the DIN root of the dup tree.
2745                     */
2746                    throw new DatabaseException(e) ;
2747                }
2748
2749                long currentLsn = dupRoot.getLastFullVersion();
2750                if (currentLsn != previousLsn) {
2751                    bin.updateEntry(index, currentLsn);
2752                }
2753
2754                /* Release the BIN latch to increase concurrency. */
2755                cursor.releaseBIN();
2756                bin = null;
2757
2758                /* The search above released the dup root latch. */
2759                dupRoot = null;
2760
2761                /* 
2762                 * Try to insert a new reference object. If successful, we'll
2763                 * log the LN and update the LSN in the reference.
2764                 */
2765                ChildReference newLNRef = 
2766                    new ChildReference(newLN, newLNKey, DbLsn.NULL_LSN);
2767                                       
2768                int dupIndex = dupBin.insertEntry1(newLNRef);
2769                if ((dupIndex & IN.INSERT_SUCCESS) != 0) {
2770
2771                    /* 
2772                     * Update the cursor to point to the entry that has been
2773                     * successfully inserted.
2774                     */
2775            dupIndex &= ~IN.INSERT_SUCCESS;
2776            cursor.updateDBin(dupBin, dupIndex);
2777
2778                    /* Log the new LN. */
2779                    long newLsn = DbLsn.NULL_LSN;
2780            try {
2781            newLsn = newLN.optionalLog
2782                            (env, database, key, DbLsn.NULL_LSN, 0,
2783                             cursor.getLocker());
2784                    } finally {
2785                        if ((newLsn == DbLsn.NULL_LSN) &&
2786                            (!database.isDeferredWrite())) {
2787
2788                            /* 
2789                             * See Tree.insert for an explanation of handling
2790                             * of IOException and OOME.
2791                             */
2792                            dupBin.setKnownDeleted(dupIndex);
2793                        }
2794            }
2795
2796            lnLock.setAbortLsn(DbLsn.NULL_LSN, true, true);
2797
2798            /* 
2799                     * Use updateEntry to be sure to mark the dupBin as dirty. 
2800                     */
2801            dupBin.updateEntry(dupIndex, newLsn);
2802
2803                    traceInsertDuplicate(Level.FINER,
2804                                         database.getDbEnvironment(),
2805                                         dupBin, newLN, newLsn, binNid);
2806                    successfulInsert = true;
2807                } else {
2808
2809                    /* 
2810                     * The insert was not successful. Either this is a
2811                     * duplicate duplicate or there is an existing entry but
2812                     * that entry is deleted.
2813                     */
2814                    dupIndex &= ~IN.EXACT_MATCH;
2815            cursor.updateDBin(dupBin, dupIndex);
2816                    LN currentLN = (LN) dupBin.fetchTarget(dupIndex);
2817
2818                    /* If an LN is present, lock it and check deleted-ness. */
2819                    boolean isDeleted = false;
2820                    LockResult currentLock = null;
2821                    if (currentLN == null) {
2822                        /* The LN was cleaned. */
2823                        isDeleted = true;
2824                    } else {
2825                        currentLock = cursor.lockLNDeletedAllowed
2826                            (currentLN, LockType.WRITE);
2827                        currentLN = currentLock.getLN();
2828                        /* The DBIN/index may have changed while locking. */
2829                        dupBin = cursor.getDupBIN();
2830            dupIndex = cursor.getDupIndex();
2831                        if (dupBin.isEntryKnownDeleted(dupIndex) ||
2832                            currentLN == null ||
2833                            currentLN.isDeleted()) {
2834                            /* The current LN is deleted/cleaned. */
2835                            isDeleted = true;
2836                        }
2837                    }
2838
2839                    if (isDeleted) {
2840                        /* See Tree.insert for an explanation. */
2841                        long abortLsn = dupBin.getLsn(dupIndex);
2842                        boolean abortKnownDeleted = true;
2843                        if (currentLN != null &&
2844                            currentLock.getLockGrant() ==
2845                            LockGrantType.EXISTING) {
2846                            long nodeId = currentLN.getNodeId();
2847                            Locker locker = cursor.getLocker();
2848                WriteLockInfo info =
2849                locker.getWriteLockInfo(nodeId);
2850                abortLsn = info.getAbortLsn();
2851                abortKnownDeleted = info.getAbortKnownDeleted();
2852            }
2853            lnLock.setAbortLsn(abortLsn, abortKnownDeleted);
2854
2855                        /*
2856                         * Current entry is a deleted entry. Replace it with
2857                         * LN.  Pass NULL_LSN for the oldLsn parameter of the
2858                         * log() method because the old LN was counted obsolete
2859                         * when it was deleted.
2860                         */
2861                        long newLsn =
2862                newLN.optionalLog(env, database, key,
2863                      DbLsn.NULL_LSN, 0, cursor.getLocker());
2864
2865                        dupBin.updateEntry(dupIndex, newLN, newLsn, newLNKey);
2866                        dupBin.clearKnownDeleted(dupIndex);
2867                        dupBin.clearPendingDeleted(dupIndex);
2868
2869                        traceInsertDuplicate(Level.FINER,
2870                                             database.getDbEnvironment(),
2871                                             dupBin, newLN, newLsn, binNid);
2872                        successfulInsert = true;
2873                    } else {
2874                        /* Duplicate duplicate. */
2875                        successfulInsert = false;
2876                    }
2877                }
2878
2879                /*
2880                 * To avoid latching out of order (up the tree), release the
2881                 * DBIN latch before latching the BIN and dup root.
2882                 */
2883                dupBin.releaseLatch();
2884                dupBin = null;
2885
2886        if (successfulInsert) {
2887                    cursor.latchBIN();
2888                    dupRoot =
2889                        cursor.getLatchedDupRoot(false /*isDBINLatched*/);
2890                    cursor.releaseBIN();
2891                    dupRoot.incrementDuplicateCount
2892                        (dclLockResult, key, cursor.getLocker(),
2893                         true /*increment*/);
2894        }
2895            } finally {
2896                if (dupBin != null) {
2897                    dupBin.releaseLatchIfOwner();
2898                }
2899        
2900                if (dupRoot != null) {
2901                    dupRoot.releaseLatchIfOwner();
2902                }
2903            }
2904        } else if (n instanceof LN) {
2905
2906            /*
2907             * There is no duplicate tree yet.  The existing LN is guaranteed
2908             * to be non-deleted, so to insert we must create a dup tree.
2909             */
2910            if (!allowDuplicates) {
2911                return false;
2912            }
2913
2914            /*
2915             * Mutate the current BIN/LN pair into a BIN/DupCountLN/DIN/DBIN/LN
2916             * duplicate tree.  Log the new entries.
2917             */
2918            try {
2919        lnLock.setAbortLsn(DbLsn.NULL_LSN, true, true);
2920                dupRoot = createDuplicateTree
2921                    (key, logManager, inMemoryINs, newLN, cursor);
2922            } finally {
2923                if (dupRoot != null) {
2924                    dupRoot.releaseLatch();
2925                    successfulInsert = true;
2926                } else {
2927                    successfulInsert = false;
2928                }
2929            }
2930        } else {
2931            throw new InconsistentNodeException
2932                ("neither LN or DIN found in BIN");
2933        }
2934
2935        return successfulInsert;
2936    }
2937
2938    /**
2939     * Check if the duplicate root needs to be split.  The current duplicate
2940     * root is latched.  Exit with the new root (even if it's unchanged)
2941     * latched and the old root (unless the root is unchanged) unlatched.
2942     * 
2943     * @param bin the BIN containing the duplicate root.
2944     * @param index the index of the duplicate root in bin.
2945     * @return true if the duplicate root was split.
2946     */
2947    private boolean maybeSplitDuplicateRoot(BIN bin,
2948                                            int index)
2949        throws DatabaseException {
2950
2951        DIN curRoot = (DIN) bin.fetchTarget(index);
2952
2953        if (curRoot.needsSplitting()) {
2954
2955            EnvironmentImpl env = database.getDbEnvironment();
2956            LogManager logManager = env.getLogManager();
2957            INList inMemoryINs = env.getInMemoryINs();
2958
2959            /* 
2960             * Make a new root DIN, giving it an id key from the previous root.
2961             */
2962            byte[] rootIdKey = curRoot.getKey(0);
2963            DIN newRoot = new DIN(database,
2964                                  rootIdKey,
2965                                  maxDupTreeEntriesPerNode,
2966                                  curRoot.getDupKey(),
2967                                  curRoot.getDupCountLNRef(),
2968                                  curRoot.getLevel() + 1);
2969
2970            newRoot.latch();
2971            long curRootLsn = 0;
2972            long logLsn = 0;
2973            try {
2974                newRoot.setIsRoot(true);
2975                curRoot.setDupCountLN(null);
2976                curRoot.setIsRoot(false);
2977
2978                /* 
2979                 * Make the new root DIN point to the old root DIN, and then
2980                 * log. We should be able to insert into the root because the
2981                 * root is newly created.
2982                 */
2983                try {
2984                    curRootLsn =
2985                        curRoot.optionalLogProvisional(logManager, newRoot);
2986                    boolean insertOk = newRoot.insertEntry
2987                        (new ChildReference(curRoot, rootIdKey,
2988                                            bin.getLsn(index)));
2989                    assert insertOk;
2990
2991                    logLsn = newRoot.optionalLog(logManager);
2992                } catch (DatabaseException e) {
2993
2994                    /* Something went wrong when we tried to log. */
2995                    curRoot.setIsRoot(true);
2996                    throw e;
2997                }
2998
2999                inMemoryINs.add(newRoot);
3000                bin.updateEntry(index, newRoot, logLsn);
3001                curRoot.split(newRoot, 0, maxDupTreeEntriesPerNode);
3002            } finally {
3003                curRoot.releaseLatch();
3004            }
3005            traceSplitRoot(Level.FINE, TRACE_DUP_ROOT_SPLIT,
3006               newRoot, logLsn, curRoot, curRootLsn);
3007            return true;
3008        } else {
3009            return false;
3010        }
3011    }
3012
3013    /**
3014     * Convert an existing BIN entry from a single (non-duplicate) LN to a new
3015     * DIN/DupCountLN->DBIN->LN subtree.
3016     *
3017     * @param key the key of the entry which will become the duplicate key
3018     * for the duplicate subtree.
3019     * @param logManager the logManager
3020     * @param inMemoryINs the in memory IN list
3021     * @param newLN the new record to be inserted
3022     * @param cursor points to the target position for this new dup tree.
3023     * @return the new duplicate subtree root (a DIN).  It is latched
3024     * when it is returned and the caller should unlatch it.  If new entry
3025     * to be inserted is a duplicate of the existing LN, null is returned.
3026     */
3027    private DIN createDuplicateTree(byte[] key,
3028                                    LogManager logManager,
3029                                    INList inMemoryINs,
3030                                    LN newLN,
3031                                    CursorImpl cursor)
3032        throws DatabaseException {
3033
3034        EnvironmentImpl env = database.getDbEnvironment();
3035        DIN dupRoot = null;
3036        DBIN dupBin = null;
3037        BIN bin = cursor.getBIN();
3038        int index = cursor.getIndex();
3039
3040        /*
3041         * fetchTarget returned an LN before this method was called, and we're
3042         * still latched, so the target should never be null here.
3043         */
3044        LN existingLN = (LN) bin.fetchTarget(index);
3045    boolean existingLNIsDeleted = bin.isEntryKnownDeleted(index) ||
3046        existingLN.isDeleted();
3047        assert existingLN != null;
3048
3049        byte[] existingKey = existingLN.getData();
3050        byte[] newLNKey = newLN.getData();
3051
3052        /* Check for duplicate duplicates. */
3053        boolean keysEqual = Key.compareKeys
3054            (newLNKey, existingKey, database.getDuplicateComparator()) == 0;
3055        if (keysEqual) {
3056            return null;
3057        }
3058
3059        /* 
3060         * Replace the existing LN with a duplicate tree. 
3061         * 
3062         * Once we create a dup tree, we don't revert back to the LN.  Create
3063         * a DupCountLN to hold the count for this dup tree. Since we don't
3064         * roll back the internal nodes of a duplicate tree, we need to create
3065         * a pre-transaction version of the DupCountLN. This version must hold
3066         * a count of either 0 or 1, depending on whether the current
3067         * transaction created the exising lN or not. If the former, the count
3068         * must roll back to 0, if the latter, the count must roll back to 1.
3069         *
3070         * Note that we are logging a sequence of nodes and must make sure the
3071         * log can be correctly recovered even if the entire sequence doesn't
3072         * make it to the log. We need to make all children provisional to the
3073         * DIN. This works:
3074         *
3075         * Entry 1: (provisional) DupCountLN (first version)
3076         * Entry 2: (provisional) DupBIN 
3077         * Entry 3: DIN
3078         * Entry 4: DupCountLN (second version, incorporating the new count.
3079         *           This can't be provisional because we need to possibly
3080         *            roll it back.)
3081         * Entry 5: new LN.
3082         * See [SR #10203] for a description of the bug that existed before
3083         * this change.
3084         */
3085
3086        /* Create the first version of DupCountLN and log it. (Entry 1). */
3087        Locker locker = cursor.getLocker();
3088    long nodeId = existingLN.getNodeId();
3089 
3090    /*
3091     * If the existing entry is known to be deleted or was created by this
3092     * transaction, then the DCL should get rolled back to 0, not 1.
3093     * [13726].
3094     */
3095    int startingCount =
3096        (locker.createdNode(nodeId) ||
3097         existingLNIsDeleted ||
3098         locker.getWriteLockInfo(nodeId).getAbortKnownDeleted()) ?
3099        0 : 1;
3100
3101        DupCountLN dupCountLN = new DupCountLN(startingCount);
3102        long firstDupCountLNLsn =
3103            dupCountLN.optionalLogProvisional(env, database,
3104                      key, DbLsn.NULL_LSN, 0);
3105        int firstDupCountLNSize = dupCountLN.getTotalLastLoggedSize(key);
3106
3107        /* Make the duplicate root and DBIN. */
3108        dupRoot = new DIN(database,
3109                          existingKey,                   // idkey
3110                          maxDupTreeEntriesPerNode,
3111                          key,                           // dup key
3112                          new ChildReference
3113                          (dupCountLN, key, firstDupCountLNLsn),
3114                          2);                            // level
3115        dupRoot.latch();
3116        dupRoot.setIsRoot(true);
3117
3118        dupBin = new DBIN(database,
3119                          existingKey,                   // idkey
3120                          maxDupTreeEntriesPerNode,
3121                          key,                           // dup key
3122                          1);                            // level
3123        dupBin.latch();
3124
3125        /* 
3126         * Attach the existing LN child to the duplicate BIN. Since this is a
3127         * newly created BIN, insertEntry will be successful.
3128         */
3129        ChildReference newExistingLNRef = new ChildReference
3130            (existingLN, existingKey, bin.getLsn(index), bin.getState(index));
3131
3132        boolean insertOk = dupBin.insertEntry(newExistingLNRef);
3133        assert insertOk;
3134
3135        try {
3136
3137            /* Entry 2: DBIN. */
3138            long dbinLsn = dupBin.optionalLogProvisional(logManager, dupRoot);
3139            inMemoryINs.add(dupBin);
3140        
3141            /* Attach the duplicate BIN to the duplicate IN root. */
3142            dupRoot.setEntry(0, dupBin, dupBin.getKey(0),
3143                             dbinLsn, dupBin.getState(0));
3144
3145            /* Entry 3:  DIN */
3146            long dinLsn = dupRoot.optionalLog(logManager);
3147            inMemoryINs.add(dupRoot);
3148
3149            /*
3150             * Now that the DIN is logged, we've created a duplicate tree that
3151             * holds the single, preexisting LN. We can safely create the non
3152             * provisional LNs that pertain to this insert -- the new LN and
3153             * the new DupCountLN.
3154             *
3155             * We request a lock while holding latches which is usually
3156             * forbidden, but safe in this case since we know it will be
3157             * immediately granted (we just created dupCountLN above).
3158             */
3159            LockResult lockResult = locker.lock
3160                (dupCountLN.getNodeId(), LockType.WRITE, false /*noWait*/,
3161                 database);
3162            lockResult.setAbortLsn(firstDupCountLNLsn, false);
3163
3164            dupCountLN.setDupCount(2);
3165            long dupCountLsn = dupCountLN.optionalLog
3166                (env, database, key, firstDupCountLNLsn, firstDupCountLNSize,
3167                 locker);
3168            dupRoot.updateDupCountLNRef(dupCountLsn);
3169        
3170            /* Add the newly created LN. */
3171            long newLsn = newLN.optionalLog
3172                (env, database, key, DbLsn.NULL_LSN, 0, locker);
3173            int dupIndex = dupBin.insertEntry1
3174                (new ChildReference(newLN, newLNKey, newLsn));
3175            dupIndex &= ~IN.INSERT_SUCCESS;
3176            cursor.updateDBin(dupBin, dupIndex);
3177
3178            /*
3179             * Adjust any cursors positioned on the mutated BIN entry to point
3180             * to the DBIN at the location of the entry we moved there.  The
3181             * index of the moved entry is 1 or 0, the XOR of the index of the
3182             * new entry.
3183             */
3184            bin.adjustCursorsForMutation(index, dupBin, dupIndex ^ 1, cursor);
3185            dupBin.releaseLatch();
3186
3187            /* 
3188             * Update the "regular" BIN to point to the new duplicate tree
3189             * instead of the existing LN.  Clear the MIGRATE flag since it
3190             * applies only to the original LN.
3191             */
3192            bin.updateEntry(index, dupRoot, dinLsn);
3193            bin.setMigrate(index, false);
3194
3195            traceMutate(Level.FINE, bin, existingLN, newLN, newLsn,
3196                        dupCountLN, dupCountLsn, dupRoot, dinLsn,
3197                        dupBin, dbinLsn);
3198        } catch (DatabaseException e) {
3199
3200            /* 
3201             * Strictly speaking, not necessary to release latches, because if
3202             * we fail to log the entries, we just throw them away, but our
3203             * unit tests check for 0 latches held in the event of a logging
3204             * error.
3205             */
3206            dupBin.releaseLatchIfOwner();
3207            dupRoot.releaseLatchIfOwner();
3208            throw e;
3209        }
3210        return dupRoot;
3211    }
3212
3213    /**
3214     * Validate args passed to insert.  Presently this just means making sure
3215     * that if they say duplicates are allowed that the database supports
3216     * duplicates.
3217     */
3218    private void validateInsertArgs(boolean allowDuplicates)
3219        throws DatabaseException {
3220        if (allowDuplicates && !database.getSortedDuplicates()) {
3221            throw new DatabaseException
3222                ("allowDuplicates passed to insert but database doesn't " +
3223                 "have allow duplicates set.");
3224        }
3225    }
3226
3227    /**
3228     * Find the BIN that is relevant to the insert.  If the tree doesn't exist
3229     * yet, then create the first IN and BIN.
3230     * @return the BIN that was found or created and return it latched.
3231     */
3232    private BIN findBinForInsert(byte[] key,
3233                                 LogManager logManager,
3234                                 INList inMemoryINs,
3235                                 CursorImpl cursor)
3236        throws DatabaseException {
3237
3238    BIN bin;
3239
3240        /* First try using the BIN at the cursor position to avoid a search. */
3241        bin = cursor.latchBIN();
3242        if (bin != null) {
3243            if (!bin.needsSplitting() && bin.isKeyInBounds(key)) {
3244                return bin;
3245            } else {
3246                bin.releaseLatch();
3247            }
3248        }
3249
3250    boolean rootLatchIsHeld = false;
3251        try {
3252        long logLsn;
3253
3254        /* 
3255         * We may have to try several times because of a small
3256         * timing window, explained below.
3257         */
3258        while (true) {
3259        rootLatchIsHeld = true;
3260        rootLatch.acquireShared();
3261        if (!rootExists()) {
3262            rootLatch.release();
3263            rootLatch.acquireExclusive();
3264            if (rootExists()) {
3265            rootLatch.release();
3266            rootLatchIsHeld = false;
3267            continue;
3268            }
3269
3270            /* 
3271             * This is an empty tree, either because it's brand new
3272             * tree or because everything in it was deleted. Create an
3273             * IN and a BIN.  We could latch the rootIN here, but
3274             * there's no reason to since we're just creating the
3275             * initial tree and we have the rootLatch held. Log the
3276             * nodes as soon as they're created, but remember that
3277             * referred-to children must come before any references to
3278             * their LSNs.
3279             */
3280                    /* First BIN in the tree, log provisionally right away. */
3281                    bin = new BIN(database, key, maxMainTreeEntriesPerNode, 1);
3282                    bin.latch();
3283                    logLsn = bin.optionalLogProvisional(logManager, null);
3284
3285            /* 
3286                     * Log the root right away. Leave the root dirty, because
3287                     * the MapLN is not being updated, and we want to avoid
3288                     * this scenario from [#13897], where the LN has no
3289                     * possible parent.
3290                     *  provisional BIN
3291                     *  root IN
3292                     *  checkpoint start
3293                     *  LN is logged
3294                     *  checkpoint end
3295                     *  BIN is dirtied, but is not part of checkpoint
3296                     */
3297
3298            IN rootIN =
3299            new IN(database, key, maxMainTreeEntriesPerNode, 2);
3300
3301            /* 
3302             * OK to latch the root after a child BIN because it's
3303             * during creation.
3304             */
3305            rootIN.latch();
3306            rootIN.setIsRoot(true);
3307
3308            boolean insertOk = rootIN.insertEntry
3309            (new ChildReference(bin, key, logLsn));
3310            assert insertOk;
3311
3312                    logLsn = rootIN.optionalLog(logManager);
3313                    rootIN.setDirty(true);  /*force re-logging, see [#13897]*/
3314
3315                    root = makeRootChildReference(rootIN,
3316                                                  new byte[0], 
3317                                                  logLsn);
3318
3319            rootIN.releaseLatch();
3320
3321            /* Add the new nodes to the in memory list. */
3322            inMemoryINs.add(bin);
3323            inMemoryINs.add(rootIN);
3324            rootLatch.release();
3325            rootLatchIsHeld = false;
3326
3327            break;
3328        } else {
3329            rootLatch.release();
3330            rootLatchIsHeld = false;
3331
3332            /* 
3333             * There's a tree here, so search for where we should
3334             * insert. However, note that a window exists after we
3335             * release the root latch. We release the latch because the
3336             * search method expects to take the latch. After the
3337             * release and before search, the INCompressor may come in
3338             * and delete the entire tree, so search may return with a
3339             * null.
3340             */
3341            IN in = searchSplitsAllowed
3342                        (key, -1, true /*updateGeneration*/);
3343            if (in == null) {
3344            /* The tree was deleted by the INCompressor. */
3345            continue;
3346            } else {
3347            /* search() found a BIN where this key belongs. */
3348            bin = (BIN) in;
3349            break;
3350            } 
3351        } 
3352        }
3353        } finally {
3354        if (rootLatchIsHeld) {
3355        rootLatch.release();
3356        }
3357        }
3358
3359        /* testing hook to insert item into log. */
3360        if (ckptHook != null) {
3361            ckptHook.doHook();
3362        }
3363
3364        return bin;
3365    }
3366
3367    /*
3368     * Given a subtree root (an IN), remove it and all of its children from the
3369     * in memory IN list. Also count removed nodes as obsolete and gather the
3370     * set of file summaries that should be logged. The tracker will be flushed
3371     * to the log later.
3372     */
3373    private void accountForSubtreeRemoval(INList inList,
3374                                          IN subtreeRoot,
3375                                          UtilizationTracker tracker)
3376        throws DatabaseException {
3377
3378        inList.latchMajor(); 
3379        try {
3380            subtreeRoot.accountForSubtreeRemoval(inList, tracker);
3381        } finally {
3382            inList.releaseMajorLatch();
3383        }
3384
3385        Tracer.trace(Level.FINE, database.getDbEnvironment(),
3386             "SubtreeRemoval: subtreeRoot = " +
3387             subtreeRoot.getNodeId());
3388    }
3389
3390    /*
3391     * Logging support
3392     */
3393
3394    /**
3395     * Returns the true last logged size by taking into account whether the
3396     * root was null when last logged.  This is necessary because the
3397     * persistent state is changed (the root is set to non-null) after being
3398     * logged and before MapLN.modify is called.
3399     *
3400     * @see DatabaseImpl#getLastLoggedSize
3401     * @see MapLN#getLastLoggedSize
3402     */
3403    public int getLastLoggedSize() {
3404        return getLogSizeInternal(true);
3405    }
3406
3407    /**
3408     * @see LogWritable#getLogSize
3409     */
3410    public int getLogSize() {
3411        return getLogSizeInternal(false);
3412    }
3413
3414    private int getLogSizeInternal(boolean lastLogged) {
3415        int size = LogUtils.getBooleanLogSize();  // root exists?
3416
3417        /*
3418         * Use ChildReference.ROOT_LOG_SIZE because the root field may be null
3419         * even if non-null when last logged.
3420         */
3421        if (lastLogged) {
3422            if (rootLastLogged) {      
3423                size += ChildReference.ROOT_LOG_SIZE;
3424            }
3425        } else {
3426            if (root != null) {      
3427                size += ChildReference.ROOT_LOG_SIZE;
3428            }
3429        }
3430        return size;
3431    }
3432
3433    /**
3434     * @see LogWritable#writeToLog
3435     */
3436    public void writeToLog(ByteBuffer   logBuffer) {
3437        LogUtils.writeBoolean(logBuffer, (root != null));
3438        if (root != null) {
3439            root.writeToLog(logBuffer);
3440            rootLastLogged = true;
3441        } else {
3442            rootLastLogged = false;
3443        }
3444    }
3445
3446    /**
3447     * @see LogReadable#readFromLog
3448     */
3449    public void readFromLog(ByteBuffer   itemBuffer, byte entryTypeVersion) {
3450        boolean rootExists = LogUtils.readBoolean(itemBuffer);
3451        if (rootExists) {
3452            root = makeRootChildReference();
3453            root.readFromLog(itemBuffer, entryTypeVersion);
3454            rootLastLogged = true;
3455        } else {
3456            rootLastLogged = false;
3457        }
3458    }
3459
3460    /**
3461     * @see LogReadable#dumpLog
3462     */
3463    public void dumpLog(StringBuffer   sb, boolean verbose) {
3464        sb.append("<root>");
3465        if (root != null) {
3466            root.dumpLog(sb, verbose);
3467        }
3468        sb.append("</root>");
3469    }
3470
3471    /**
3472     * @see LogReadable#isTransactional
3473     */
3474    public boolean logEntryIsTransactional() {
3475    return false;
3476    }
3477
3478    /**
3479     * @see LogReadable#getTransactionId
3480     */
3481    public long getTransactionId() {
3482    return 0;
3483    }
3484
3485    /** 
3486     * rebuildINList is used by recovery to add all the resident nodes to the
3487     * IN list.
3488     */
3489    public void rebuildINList()
3490        throws DatabaseException {
3491
3492        INList inMemoryList = database.getDbEnvironment().getInMemoryINs();
3493
3494        if (root != null) {
3495            rootLatch.acquireShared();
3496            try {
3497                Node rootIN = root.getTarget();
3498                if (rootIN != null) {
3499                    rootIN.rebuildINList(inMemoryList);
3500                }
3501            } finally {
3502                rootLatch.release();
3503            }
3504        }
3505    }
3506
3507    /*
3508     * Debugging stuff.
3509     */
3510    public void dump()
3511        throws DatabaseException {
3512
3513        System.out.println(dumpString(0));
3514    }   
3515
3516    public String   dumpString(int nSpaces)
3517        throws DatabaseException {
3518
3519        StringBuffer   sb = new StringBuffer  ();
3520        sb.append(TreeUtils.indent(nSpaces));
3521        sb.append("<tree>");
3522        sb.append('\n');
3523        if (root != null) {
3524            sb.append(DbLsn.dumpString(root.getLsn(), nSpaces));
3525            sb.append('\n');
3526            IN rootIN = (IN) root.getTarget();
3527            if (rootIN == null) {
3528                sb.append("<in/>");
3529            } else {
3530                sb.append(rootIN.toString());
3531            }
3532            sb.append('\n');
3533        }
3534        sb.append(TreeUtils.indent(nSpaces));
3535        sb.append("</tree>");
3536        return sb.toString();
3537    }   
3538
3539    /**
3540     * Unit test support to validate subtree pruning. Didn't want to make root
3541     * access public.
3542     */
3543    boolean validateDelete(int index)
3544        throws DatabaseException {
3545
3546        rootLatch.acquireShared();
3547        try {
3548            IN rootIN = (IN) root.fetchTarget(database, null);
3549            return rootIN.validateSubtreeBeforeDelete(index);
3550        } finally {
3551            rootLatch.release();
3552        }
3553    }
3554
3555    /**
3556     * Debugging check that all resident nodes are on the INList and no stray
3557     * nodes are present in the unused portion of the IN arrays.
3558     */
3559    public void validateINList(IN parent)
3560        throws DatabaseException {
3561
3562        if (parent == null) {
3563            parent = (IN) root.getTarget();
3564        }
3565        if (parent != null) {
3566            INList inList = database.getDbEnvironment().getInMemoryINs();
3567            if (!inList.getINs().contains(parent)) {
3568                throw new DatabaseException
3569                    ("IN " + parent.getNodeId() + " missing from INList");
3570            }
3571            for (int i = 0;; i += 1) {
3572                try {
3573                    Node node = parent.getTarget(i);
3574                    if (i >= parent.getNEntries()) {
3575                        if (node != null) {
3576                            throw new DatabaseException
3577                                ("IN " + parent.getNodeId() +
3578                                 " has stray node " + node.getNodeId() + 
3579                                 " at index " + i);
3580                        }
3581                        byte[] key = parent.getKey(i);
3582                        if (key != null) {
3583                            throw new DatabaseException
3584                                ("IN " + parent.getNodeId() +
3585                                 " has stray key " + key + 
3586                                 " at index " + i);
3587                        }
3588                    }
3589                    if (node instanceof IN) {
3590                        validateINList((IN) node);
3591                    }
3592                } catch (ArrayIndexOutOfBoundsException   e) {
3593                    break;
3594                }
3595            }
3596        }
3597    }
3598
3599    /* For unit testing only. */
3600    public void setWaitHook(TestHook hook) {
3601        waitHook = hook;
3602    }
3603
3604    /* For unit testing only. */
3605    public void setSearchHook(TestHook hook) {
3606        searchHook = hook;
3607    }
3608
3609    /* For unit testing only. */
3610    public void setCkptHook(TestHook hook) {
3611        ckptHook = hook;
3612    }
3613
3614    /**
3615     * Send trace messages to the java.util.logger. Don't rely on the logger
3616     * alone to conditionalize whether we send this message, we don't even want
3617     * to construct the message if the level is not enabled.
3618     */
3619    private void traceSplitRoot(Level   level,
3620                                String   splitType,
3621                                IN newRoot,
3622                                long newRootLsn,
3623                                IN oldRoot,
3624                                long oldRootLsn) {
3625        Logger   logger = database.getDbEnvironment().getLogger();
3626        if (logger.isLoggable(level)) {
3627            StringBuffer   sb = new StringBuffer  ();
3628            sb.append(splitType);
3629            sb.append(" newRoot=").append(newRoot.getNodeId());
3630            sb.append(" newRootLsn=").
3631        append(DbLsn.getNoFormatString(newRootLsn));
3632            sb.append(" oldRoot=").append(oldRoot.getNodeId());
3633            sb.append(" oldRootLsn=").
3634        append(DbLsn.getNoFormatString(oldRootLsn));
3635            logger.log(level, sb.toString());
3636        }
3637    }
3638
3639    /**
3640     * Send trace messages to the java.util.logger. Don't rely on the logger
3641     * alone to conditionalize whether we send this message, we don't even want
3642     * to construct the message if the level is not enabled.
3643     */
3644    private void traceMutate(Level   level,
3645                             BIN theBin,
3646                             LN existingLn,
3647                             LN newLn,
3648                             long newLsn,
3649                             DupCountLN dupCountLN,
3650                             long dupRootLsn,
3651                             DIN dupRoot,
3652                             long ddinLsn,
3653                             DBIN dupBin,
3654                             long dbinLsn) {
3655        Logger   logger = database.getDbEnvironment().getLogger();
3656        if (logger.isLoggable(level)) {
3657            StringBuffer   sb = new StringBuffer  ();
3658            sb.append(TRACE_MUTATE);
3659            sb.append(" existingLn=");
3660            sb.append(existingLn.getNodeId());
3661            sb.append(" newLn=");
3662            sb.append(newLn.getNodeId());
3663            sb.append(" newLnLsn=");
3664            sb.append(DbLsn.getNoFormatString(newLsn));
3665            sb.append(" dupCountLN=");
3666            sb.append(dupCountLN.getNodeId());
3667            sb.append(" dupRootLsn=");
3668            sb.append(DbLsn.getNoFormatString(dupRootLsn));
3669            sb.append(" rootdin=");
3670            sb.append(dupRoot.getNodeId());
3671            sb.append(" ddinLsn=");
3672            sb.append(DbLsn.getNoFormatString(ddinLsn));
3673            sb.append(" dbin=");
3674            sb.append(dupBin.getNodeId());
3675            sb.append(" dbinLsn=");
3676            sb.append(DbLsn.getNoFormatString(dbinLsn));
3677            sb.append(" bin=");
3678            sb.append(theBin.getNodeId());
3679    
3680            logger.log(level, sb.toString());
3681        }
3682    }
3683
3684    /**
3685     * Send trace messages to the java.util.logger. Don't rely on the logger
3686     * alone to conditionalize whether we send this message, we don't even want
3687     * to construct the message if the level is not enabled.
3688     */
3689    private void traceInsert(Level   level,
3690                             EnvironmentImpl env,
3691                             BIN insertingBin,
3692                             LN ln,
3693                             long lnLsn,
3694                 int index) {
3695        Logger   logger = env.getLogger();
3696        if (logger.isLoggable(level)) {
3697            StringBuffer   sb = new StringBuffer  ();
3698            sb.append(TRACE_INSERT);
3699            sb.append(" bin=");
3700            sb.append(insertingBin.getNodeId());
3701            sb.append(" ln=");
3702            sb.append(ln.getNodeId());
3703            sb.append(" lnLsn=");
3704            sb.append(DbLsn.getNoFormatString(lnLsn));
3705            sb.append(" index=");
3706        sb.append(index);
3707    
3708            logger.log(level, sb.toString());
3709        }
3710    }
3711
3712    /**
3713     * Send trace messages to the java.util.logger. Don't rely on the logger
3714     * alone to conditionalize whether we send this message, we don't even want
3715     * to construct the message if the level is not enabled.
3716     */
3717    private void traceInsertDuplicate(Level   level,
3718                                      EnvironmentImpl env,
3719                                      BIN insertingDBin,
3720                                      LN ln,
3721                                      long lnLsn,
3722                                      long binNid) {
3723        Logger   logger = env.getLogger();
3724        if (logger.isLoggable(level)) {
3725            StringBuffer   sb = new StringBuffer  ();
3726            sb.append(TRACE_INSERT_DUPLICATE);
3727            sb.append(" dbin=");
3728            sb.append(insertingDBin.getNodeId());
3729            sb.append(" bin=");
3730            sb.append(binNid);
3731            sb.append(" ln=");
3732            sb.append(ln.getNodeId());
3733            sb.append(" lnLsn=");
3734            sb.append(DbLsn.getNoFormatString(lnLsn));
3735    
3736            logger.log(level, sb.toString());
3737        }
3738    }
3739
3740    private static class SplitInfo {
3741        IN parent;
3742        IN child;
3743        int index;
3744
3745        SplitInfo(IN parent, IN child, int index) {
3746            this.parent = parent;
3747            this.child = child;
3748            this.index = index;
3749        }
3750    }
3751}
3752
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags