docs: private Token put(Object key,
                        Token value,
                        Transaction transaction,
                        boolean allowDuplicates)
                      throws ObjectManagerException
      {
          final String methodName = "put";
          if (Tracing.isAnyTracingEnabled() && trace.isEntryEnabled())
              trace.entry(this, cclass, methodName, new Object[] { key,
                                                                  value,
                                                                  transaction,
                                                                  new Boolean(allowDuplicates) });
  
          Token returnValue = null; // The returned value.
          // The following set to true if the existing entry is replaced but was added by the same transaction.
          // (state of replaced entry is mustBeDeleted)
          boolean mustBeDeleted = false;
  
          // We could to follow a scheme like the one in LinkedList.addEntry where we do a composite add
          // with no window for another thread ( eg the checkpoint thread) to backout the transaction between add
          // optimistic replace. We don't do this because removing a node from a binary tree will not always restore
          // it to exactly the same state as before it was added. Instead we synchronize on InternalTransaction
          // through this code. A backout thread would lock transaction then managed object in the 
          // preBackout callback.
          synchronized (transaction.internalTransaction) {
              synchronized (this) {
                  // Prevent other transactions using the tree until its creation is committed.
                  if (!(state == stateReady)
                      && !((state == stateAdded) && lockedBy(transaction))) {
  
                      if (Tracing.isAnyTracingEnabled() && trace.isEntryEnabled())
                          trace.exit(this, cclass, methodName, new Object[] { new Integer(state),
                                                                             stateNames[state] });
                      throw new InvalidStateException(this, state, stateNames[state]);
                  }
  
                  managedObjectsToReplace.clear(); // Reset from last time.
                  // Assume we will delete a duplicate entry as well as adding a new one.
                  reservedSpaceInStore = storeSpaceForAdd() + storeSpaceForRemove();
                  owningToken.objectStore.reserve((int) reservedSpaceInStore, false);
  
                  try {
                      // Search for the insertion point starting at the root.
                      if (root == null) { // Is the tree empty?
                          Entry newEntry = new Entry(this,
                                                     key,
                                                     value,
                                                     null,
                                                     transaction);
  
                          // If the add fails, because the log is full, no harm done because we will not have affected the
                          // structure of the tree. We now also need to reserve log space for the optimistic replace
                          // log records needed needed to reflect the modified structure of the tree and also for another
                          // set in case we need to roll back the changes if backout is executed.
                          transaction.add(newEntry,
                                          logSpaceForAdd + logSpaceForDelete);
                          setRoot(newEntry);
                          size++;
  
                      } else { // if (root != null).
  
                          Entry currentEntry = (Entry) getRoot();
  
                          // Search the tree looking for a free leaf.
                          keySearch: while (true) {
  
                              int comparison = compare(key,
                                                       currentEntry.key);
                              if (Tracing.isAnyTracingEnabled() && trace.isDebugEnabled())
                                  trace.debug(this, cclass, methodName, new Object[] { currentEntry });
                              if (comparison == 0) { // Matching entry found?
                                  if (allowDuplicates) {
                                      // We allow duplicate keys so just add the new entry after the equal key.
                                      add(key,
                                          value,
                                          currentEntry,
                                          transaction,
                                          logSpaceForAdd + logSpaceForDelete);
                                      break keySearch; // Now included in the tree.
  
                                  } else if (currentEntry.state == Entry.stateAdded
                                             || (currentEntry.state == Entry.stateToBeAdded && currentEntry.lockedBy(transaction))) {
  
                                      // We want to replace the value at an existing key with a new one.
                                      // Mark the existing entry for deletion and insert a new entry. Until the transaction
                                      // reaches commit both of these will exist in the tree, but will only be visible to
                                      // this transaction.
                                      transaction.delete(currentEntry,
                                                         logSpaceForAdd
                                                                         + 2 * logSpaceForDelete
                                                                         + TransactionAddLogRecord.maximumSerializedSize()); // Log what we intend to do.
                                      currentEntry.requestDelete(transaction);
  
                                      if (currentEntry.state == Entry.stateToBeDeleted) {
                                          // In the case where we delete an entry added by the same transaction we have not incremented
                                          // the available size yet because we have not yet committed so we would not decrement it.
                                          availableSize--;
                                      } else {
                                          // We don't need to reserve space in the store for removal of the entry if the
                                          // transaction backs out because this was done when the entry was added by
                                          // the same transaction.
                                          mustBeDeleted = true;
                                      }
  
                                      returnValue = currentEntry.getValue();
                                      // Add the new entry after the current one.
                                      add(key,
                                          value,
                                          currentEntry,
                                          transaction,
                                          -TransactionAddLogRecord.maximumSerializedSize());
                                      break keySearch; // Now included in the tree.
  
                                  } else if (currentEntry.willBeDeleted(transaction)) {
                                      // Skip over a deleted Entry with the same key if it is followed by another duplicate.
                                      Entry nextEntry = (Entry) successor(currentEntry);
                                      if (nextEntry != null && (compare(key, nextEntry.key) == 0)) {
                                          currentEntry = nextEntry;
                                      } else {
                                          // Add the new value.
                                          add(key,
                                              value,
                                              currentEntry,
                                              transaction,
                                              logSpaceForAdd + logSpaceForDelete);
                                          break keySearch;
                                      } // if (nextEntry...
  
                                  } else { // Put cannot replace this value.
                                      InternalTransaction lockingTransaction = null;
                                      TransactionLock transactionLock = currentEntry.getTransactionLock();
                                      if (transactionLock != null)
                                          if (transactionLock.isLocked())
                                              lockingTransaction = transactionLock.getLockingTransaction();
                                      undoPut();
                                      if (Tracing.isAnyTracingEnabled() && trace.isEntryEnabled())
                                          trace.exit(this,
                                                     cclass,
                                                     methodName,
                                                     "via DuplicateKeyException"
                                                                     + " currentEntry.state ="
                                                                     + currentEntry.state
                                                                     + "(int) "
                                                                     + stateNames[currentEntry.state]
                                                                     + "(String)");
                                      throw new DuplicateKeyException(this,
                                                                      key,
                                                                      currentEntry,
                                                                      lockingTransaction);
                                  } // if OK to replace.
  
                              } else if (comparison < 0) { // Are we in the less than branch?
                                  if (currentEntry.left == null) {// We have reached a less than leaf.
                                      Entry newEntry = new Entry(this,
                                                                 key,
                                                                 value,
                                                                 currentEntry,
                                                                 transaction);
                                      transaction.add(newEntry,
                                                      logSpaceForAdd + logSpaceForDelete);
                                      size++;
                                      currentEntry.setLeft(newEntry);
                                      balance(newEntry);
                                      break keySearch; // Now included in the tree.
                                  } // if (currentEntry.left == null).
                                    // Look further into the less than tree.
                                  currentEntry = (Entry) currentEntry.getLeft();
  
                              } else { // So its the greater than branch.
                                  if (currentEntry.right == null) { // We have reached a greater than than leaf.
                                      Entry newEntry = new Entry(this,
                                                                 key,
                                                                 value,
                                                                 currentEntry,
                                                                 transaction);
                                      transaction.add(newEntry,
                                                      logSpaceForAdd + logSpaceForDelete);
                                      size++;
                                      currentEntry.setRight(newEntry);
                                      balance(newEntry);
                                      break keySearch; // Now included in the tree.
                                  } // if (currentEntry.right == null).
                                    // Look further into the greater than tree.
                                  currentEntry = (Entry) currentEntry.getRight();
  
                              } // if (comparator...
                          } // keySearch: while...
                      } // else (current == null).
  
                      managedObjectsToReplace.add(this); // The anchor has changed.
                      // Harden the updates. This will not fail due to lack of log space because we reserved
                      // the space for the logRecord earlier.
                      transaction.optimisticReplace(null,
                                                    new java.util.ArrayList(managedObjectsToReplace),
                                                    null, // No tokens to delete.
                                                    null, // No tokens to notify.
                                                    -logSpaceForAdd);
                      // Give up reserved space, but keep back enough to remove the added entry if we have to.
                      // Also give back the space needed to delete the duplicate entry if there is no duplicate.
                      if (returnValue == null || mustBeDeleted)
                      {
                          // nothing replaced or if there was it was added in the same transaction.
                          // keep back enough to backout the add
                          owningToken.objectStore.reserve((int) (storeSpaceForRemove() - reservedSpaceInStore), false);
                      }
                      else
                      {
                          // something was replaced, keep back 2 * space for remove, 1 for backing out the add,
                          // 1 for actually doing the remove. Either commit or backout direction will give this back
                          // for each of the added and deleted entries.
                          owningToken.objectStore.reserve((int) (storeSpaceForRemove() * 2 - reservedSpaceInStore), false);
                      }
  
                  } catch (InvalidStateException exception) {
                      // No FFDC Code Needed, user error.
                      // Remove the link we just added.
                      undoPut();
  
                      if (Tracing.isAnyTracingEnabled() && trace.isEntryEnabled())
                          trace.exit(this, cclass, methodName, exception);
                      throw exception;
  
                  } catch (LogFileFullException exception) {
                      // No FFDC Code Needed, InternalTransaction has already done this.
                      // Remove the link we just added.
                      undoPut();
  
                      if (Tracing.isAnyTracingEnabled() && trace.isEntryEnabled())
                          trace.exit(this, cclass, methodName, exception);
                      throw exception;
  
                      // We should not see ObjectStoreFullException because we have preReserved 
                      // the ObjectStore space.
  //        } catch (ObjectStoreFullException exception) {
  //          // No FFDC Code Needed, InternalTransaction has already done this.
  //          // Remove the link we just added.
  //          undoPut();
  //          
  //          if (Tracing.isAnyTracingEnabled() && trace.isEntryEnabled())
  //            trace.exit(this, cclass, methodName, exception);
  //          throw exception;
                  } // try.
              } // synchronized (this).
          } // synchronized (transaction.internalTransaction).
  
          if (Tracing.isAnyTracingEnabled() && trace.isEntryEnabled())
              trace.exit(this, cclass, methodName, new Object[] { returnValue });
          return returnValue;
      }