private StoredIterator getIteratorForKey(Object key)
  {
    StoredSortedMap subMap = (StoredSortedMap)
      ((StoredSortedMap)_map).subMap(key, true, key, true);
    return ((StoredEntrySet)subMap.entrySet()).storedIterator();
  }
  
  public V putIfAbsent(K key, V value)
  {
    // FIXME
    return null;
  }
 
  public boolean remove(Object key, Object value)
  {
    StoredIterator iter = getIteratorForKey(key);
    try {
      iter.setReadModifyWrite(true);
      if(!iter.hasNext()) {
        return false;
      }
      Map.Entry e = (Map.Entry)iter.next();
      Object curVal = e.getValue();
      if(!ObjectUtils.equals(value, curVal)) {
        // was modified
        return false;
      }
      // good to go (we have the write lock already)
      iter.remove();
    } finally {
      iter.close();
    }
    return true;
  }
 
  @SuppressWarnings("unchecked")
  public boolean replace(K key, V oldValue, V newValue)
  {
    StoredIterator iter = getIteratorForKey(key);
    try {
      iter.setReadModifyWrite(true);
      if(!iter.hasNext()) {
        return false;
      }
      Map.Entry e = (Map.Entry)iter.next();
      Object curVal = e.getValue();
      if(!ObjectUtils.equals(oldValue, curVal)) {
        // was modified
        return false;
      }
      // set new value (we have the write lock already)
      e.setValue(newValue);
    } finally {
      iter.close();
    }
    return true;
  }
 
  @SuppressWarnings("unchecked")
  public V replace(K key, V value)
  {
    Object curValue = null;
    StoredIterator iter = getIteratorForKey(key);
    try {
      iter.setReadModifyWrite(true);
      if(iter.hasNext()) {
        Map.Entry e = (Map.Entry)iter.next();
        curValue = e.getValue();
        // set new value (we have the write lock already)
        e.setValue(value);
      }
    } finally {
      iter.close();
    }
    return (V)curValue;
  }

public class StoredConcurrentMap extends StoredMap
{
 
  public StoredConcurrentMap(
      Database database, EntryBinding keyBinding,
      EntryBinding valueEntityBinding, boolean writeAllowed)
  {
    super(database, keyBinding, valueEntityBinding, writeAllowed);
  }
 
  public Object putIfAbsent(Object key, Object value)
  {
    Object oldValue = null;
    DataCursor cursor = null;
    boolean doAutoCommit = beginAutoCommit();
    try {
      cursor = new DataCursor(view, true);
      while(true) {
        if(OperationStatus.SUCCESS ==
           cursor.putNoOverwrite(key, value, false)) {
          // we succeeded
          break;
        } else if(OperationStatus.SUCCESS ==
                  cursor.getSearchKey(key, null, false)) {
          // someone else beat us to it
          oldValue = cursor.getCurrentValue();
          break;
        }
 
        // we couldn't put and we couldn't get, try again
      }
      closeCursor(cursor);
      commitAutoCommit(doAutoCommit);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, doAutoCommit);
    }
    return oldValue;
  }
 
  public boolean remove(Object key, Object value)
  {
    boolean removed = false;
    DataCursor cursor = null;
    boolean doAutoCommit = beginAutoCommit();
    try {
      cursor = new DataCursor(view, true, key);
      if(OperationStatus.SUCCESS == cursor.getNextNoDup(true)) {
        Object curValue = cursor.getCurrentValue();
        if(ObjectUtils.equals(curValue, value)) {
          cursor.delete();
          removed = true;
        }
      }
      closeCursor(cursor);
      commitAutoCommit(doAutoCommit);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, doAutoCommit);
    }
    return removed;
  }
 
  public boolean replace(Object key, Object oldValue, Object newValue)
  {
    boolean replaced = false;
    DataCursor cursor = null;
    boolean doAutoCommit = beginAutoCommit();
    try {
      cursor = new DataCursor(view, true, key);
      if(OperationStatus.SUCCESS == cursor.getNextNoDup(true)) {
        Object curValue = cursor.getCurrentValue();
        if(ObjectUtils.equals(curValue, oldValue)) {
          cursor.putCurrent(newValue);
          replaced = true;
        }
      }
      closeCursor(cursor);
      commitAutoCommit(doAutoCommit);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, doAutoCommit);
    }
    return replaced;
  }
 
  public Object replace(Object key, Object value)
  {
    Object curValue = null;
    DataCursor cursor = null;
    boolean doAutoCommit = beginAutoCommit();
    try {
      cursor = new DataCursor(view, true, key);
      if(OperationStatus.SUCCESS == cursor.getNextNoDup(true)) {
        curValue = cursor.getCurrentValue();
        cursor.putCurrent(value);
      }
      closeCursor(cursor);
      commitAutoCommit(doAutoCommit);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, doAutoCommit);
    }
    return curValue;
  }
}

Object key;
try {
  Object value = map.getForUpdate(key);
  // ... run concurrent ops on value ...
  map.replace(key, value, newValue);
  map.completeUpdate(key);
} finally {
  map.closeUpdate(key);
}

public class StoredConcurrentMap extends StoredMap
{
  private final ThreadLocal<UpdateState> _updateState =
    new ThreadLocal<UpdateState>();
 
  public StoredConcurrentMap(
      Database database, EntryBinding keyBinding,
      EntryBinding valueEntityBinding, boolean writeAllowed)
  {
    super(database, keyBinding, valueEntityBinding, writeAllowed);
  }
  
  public Object getForUpdate(Object key)
  {
    if(_updateState.get() != null) {
      throw new IllegalStateException(
          "previous update still outstanding for key " +
          _updateState.get()._key);
    }
    UpdateState updateState = new UpdateState(key, beginAutoCommit());
    _updateState.set(updateState);
    
    DataCursor cursor = null;
    Object value = null;
    try {
      cursor = new DataCursor(view, true, key);
      if(OperationStatus.SUCCESS == cursor.getNextNoDup(true)) {
        // takeover ownership of the cursor
        value = updateState.loadCurrentValue(cursor);
        cursor = null;
      }
      closeCursor(cursor);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, false);
    }
    return value;
  }
 
  public void completeUpdate(Object key)
  {
    UpdateState updateState = getUpdateState(key);
    if(updateState != null) {
      try {
        updateState.clearCurrentValue(this);
        commitAutoCommit(updateState._doAutoCommit);
        // only clear the reference if everything succeeds
        _updateState.set(null);
      } catch(DatabaseException e) {
        throw new RuntimeExceptionWrapper(e);
      }
    }
  }
 
  public void closeUpdate(Object key)
  {
    UpdateState updateState = getUpdateState(key);
    if(updateState != null) {
      // this op failed, abort (clear the reference regardless of what happens
      // below)
      _updateState.set(null);
      try {
        updateState.clearCurrentValue(this);
        view.getCurrentTxn().abortTransaction();
      } catch(DatabaseException ignored) {
      }
    }
  }
  
  public Object putIfAbsent(Object key, Object value)
  {
    UpdateState updateState = getUpdateState(key);
    if(valueExists(updateState)) {
      return updateState._curValue;
    }
    
    Object oldValue = null;
    DataCursor cursor = null;
    boolean doAutoCommit = beginAutoCommit();
    try {
      cursor = new DataCursor(view, true);
      while(true) {
        if(OperationStatus.SUCCESS ==
           cursor.putNoOverwrite(key, value, false)) {
          // we succeeded
          break;
        } else if(OperationStatus.SUCCESS ==
                  cursor.getSearchKey(key, null, false)) {
          // someone else beat us to it
          oldValue = cursor.getCurrentValue();
          break;
        }
 
        // we couldn't put and we couldn't get, try again
      }
      closeCursor(cursor);
      commitAutoCommit(doAutoCommit);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, doAutoCommit);
    }
    return oldValue;
  }
 
  public boolean remove(Object key, Object value)
  {
    UpdateState updateState = getUpdateState(key);
    if(valueExists(updateState)) {
      if(ObjectUtils.equals(updateState._curValue, value)) {
        try {
          updateState._cursor.delete();
          updateState.clearCurrentValue(this);
          return true;
        } catch (Exception e) {
          throw handleException(e, false);
        }
      } else {
        return false;
      }
    }
 
    boolean removed = false;
    DataCursor cursor = null;
    boolean doAutoCommit = beginAutoCommit();
    try {
      cursor = new DataCursor(view, true, key);
      if(OperationStatus.SUCCESS == cursor.getNextNoDup(true)) {
        Object curValue = cursor.getCurrentValue();
        if(ObjectUtils.equals(curValue, value)) {
          cursor.delete();
          removed = true;
        }
      }
      closeCursor(cursor);
      commitAutoCommit(doAutoCommit);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, doAutoCommit);
    }
    return removed;
  }
 
  public boolean replace(Object key, Object oldValue, Object newValue)
  {
    UpdateState updateState = getUpdateState(key);
    if(valueExists(updateState)) {
      if(ObjectUtils.equals(updateState._curValue, oldValue)) {
        try {
          updateState.replaceCurrentValue(newValue);
          return true;
        } catch (Exception e) {
          throw handleException(e, false);
        }
      } else {
        return false;
      }
    }
    
    boolean replaced = false;
    DataCursor cursor = null;
    boolean doAutoCommit = beginAutoCommit();
    try {
      cursor = new DataCursor(view, true, key);
      if(OperationStatus.SUCCESS == cursor.getNextNoDup(true)) {
        Object curValue = cursor.getCurrentValue();
        if(ObjectUtils.equals(curValue, oldValue)) {
          cursor.putCurrent(newValue);
          replaced = true;
        }
      }
      closeCursor(cursor);
      commitAutoCommit(doAutoCommit);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, doAutoCommit);
    }
    return replaced;
  }
 
  public Object replace(Object key, Object value)
  {
    UpdateState updateState = getUpdateState(key);
    if(valueExists(updateState)) {
      try {
        return updateState.replaceCurrentValue(value);
      } catch (Exception e) {
        throw handleException(e, false);
      }
    }
 
    Object curValue = null;
    DataCursor cursor = null;
    boolean doAutoCommit = beginAutoCommit();
    try {
      cursor = new DataCursor(view, true, key);
      if(OperationStatus.SUCCESS == cursor.getNextNoDup(true)) {
        curValue = cursor.getCurrentValue();
        cursor.putCurrent(value);
      }
      closeCursor(cursor);
      commitAutoCommit(doAutoCommit);
    } catch (Exception e) {
      closeCursor(cursor);
      throw handleException(e, doAutoCommit);
    }
    return curValue;
  }
 
  
  /**
   * @return the current UpdateState for the given key, if any, {@code null}
   *         otherwise.
   */
  private UpdateState getUpdateState(Object key)
  {
    UpdateState updateState = _updateState.get();
    if((updateState != null) && (ObjectUtils.equals(updateState._key, key))) {
      return updateState;
    }
    return null;
  }
  
  /**
   * @return {@code true} if the update state exists and found a value (which
   *         is currently locked)
   */
  private boolean valueExists(UpdateState updateState)
  {
    return((updateState != null) && (updateState._cursor != null));
  }
 
 
  /**
   * Maintains state about an object loaded in a
   * {@link StoredConcurrentMap#getForUpdate} call.
   */
  private static class UpdateState
  {
    public final Object _key;
    public final boolean _doAutoCommit;
    public DataCursor _cursor;
    public Object _curValue;
 
    private UpdateState(Object key, boolean doAutoCommit) {
      _key = key;
      _doAutoCommit = doAutoCommit;
    }
 
    /**
     * Loads the current value from the given cursor, and maintains a
     * reference to the given cursor and the loaded value.
     */
    public Object loadCurrentValue(DataCursor cursor)
      throws DatabaseException
    {
      _cursor = cursor;
      _curValue = _cursor.getCurrentValue();
      return _curValue;
    }
 
    /**
     * Replaces the current value in the current cursor with the given value.
     * @return the old value
     */
    public Object replaceCurrentValue(Object newValue)
      throws DatabaseException
    {
      Object oldValue = _curValue;
      _cursor.putCurrent(newValue);
      _curValue = newValue;
      return oldValue;
    }
 
    /**
     * Closes the current curstor and clears the references to the cursor and
     * current value.
     */
    public void clearCurrentValue(StoredConcurrentMap map) {
      try {
        map.closeCursor(_cursor);
      } finally {
        _cursor = null;
        _curValue = null;
      }
    }
    
  }
  
}