Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
   /*
    *  Copyright (c) 2012 Jan Kotek
    *
    *  Licensed under the Apache License, Version 2.0 (the "License");
    *  you may not use this file except in compliance with the License.
    *  You may obtain a copy of the License at
    *
    *    http://www.apache.org/licenses/LICENSE-2.0
    *
   *  Unless required by applicable law or agreed to in writing, software
   *  distributed under the License is distributed on an "AS IS" BASIS,
   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   *  See the License for the specific language governing permissions and
   *  limitations under the License.
   */
  
  /*
   * NOTE: some code (and javadoc) used in this class
   * comes from Apache Harmony with following copyright:
   *
   * Written by Doug Lea with assistance from members of JCP JSR-166
   * Expert Group and released to the public domain, as explained at
   * http://creativecommons.org/licenses/publicdomain
   */
  
  package org.mapdb;
  
  
  import java.io.DataInput;
  import java.util.*;
A scalable concurrent ConcurrentNavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time. Insertion, removal, update, and access operations safely execute concurrently by multiple threads. Iterators are weakly consistent, returning elements reflecting the state of the map at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException, and may proceed concurrently with other operations. Ascending key ordered views and their iterators are faster than descending ones. It is possible to obtain consistent iterator by using snapshot() method. All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method. (Note however that it is possible to change mappings in the associated map using put, putIfAbsent, or replace, depending on exactly which effect you need.) This collection has optional size counter. If this is enabled Map size is kept in Atomic.Long variable. Keeping counter brings considerable overhead on inserts and removals. If the size counter is not enabled the size method is not a constant-time operation. Determining the current number of elements requires a traversal of the elements. Additionally, the bulk operations putAll, equals, and clear are not guaranteed to be performed atomically. For example, an iterator operating concurrently with a putAll operation might view only some of the added elements. NOTE: there is an optional This class and its views and iterators implement all of the optional methods of the Map and Iterator interfaces. Like most other concurrent collections, this class does not permit the use of null keys or values because some null return values cannot be reliably distinguished from the absence of elements. Theoretical design of BTreeMap is based on paper from Philip L. Lehman and S. Bing Yao. More practical aspects of BTreeMap implementation are based on notes and demo application from Thomas Dinsdale-Young. B-Linked-Tree used here does not require locking for read. Updates and inserts locks only one, two or three nodes. This B-Linked-Tree structure does not support removal well, entry deletion does not collapse tree nodes. Massive deletion causes empty nodes and performance lost. There is workaround in form of compaction process, but it is not implemented yet.

Author(s):
Jan Kotek
some parts by Doug Lea and JSR-166 group
  
  @SuppressWarnings({ "unchecked""rawtypes" })
  //TODO better tests for BTreeMap without values (set)
  public class BTreeMap<K,V> extends AbstractMap<K,V>
          implements ConcurrentNavigableMap<K,V>, Bind.MapWithModificationListener<K,V>{
  
  
      protected static final int B_TREE_NODE_LEAF_LR = 180;
      protected static final int B_TREE_NODE_LEAF_L = 181;
     protected static final int B_TREE_NODE_LEAF_R = 182;
     protected static final int B_TREE_NODE_LEAF_C = 183;
     protected static final int B_TREE_NODE_DIR_LR = 184;
     protected static final int B_TREE_NODE_DIR_L = 185;
     protected static final int B_TREE_NODE_DIR_R = 186;
     protected static final int B_TREE_NODE_DIR_C = 187;



    
recid under which reference to rootRecid is stored
 
     protected final long rootRecidRef;

    
Serializer used to convert keys from/into binary form. TODO delta packing on BTree key
 
     protected final BTreeKeySerializer keySerializer;
    
Serializer used to convert keys from/into binary for
 
     protected final Serializer<V> valueSerializer;

    
keys are sorted by thi
 
     protected final Comparator comparator;

    
holds node level lock
 
     protected final LongConcurrentHashMap<ThreadnodeLocks = new LongConcurrentHashMap<Thread>();

    
maximal node size allowed in this BTre
 
     protected final int maxNodeSize;

    
DB Engine in which entries are persisted
 
     protected final Engine engine;

    
is this a Map or Set? if false, entries do not have values, only keys are allowe
 
     protected final boolean hasValues;

    
store values as part of BTree nodes
 
     protected final boolean valsOutsideNodes;
 
 
 
     private final KeySet keySet;
 
     private final EntrySet entrySet = new EntrySet(this);
 
     private final Values values = new Values(this);
 
     private final ConcurrentNavigableMap<K,V> descendingMap = new DescendingMap(thisnull,truenullfalse);
 
     protected final Atomic.Long counter;

    
hack used for DB Catalo
 
     protected static SortedMap<StringObjectpreinitCatalog(DB db) {
 
         Long rootRef = db.getEngine().get(..);
 
         if(rootRef==null){
             if(db.getEngine().isReadOnly())
                 return Collections.unmodifiableSortedMap(new TreeMap<StringObject>());
 
             NodeSerializer rootSerializer = new NodeSerializer(false,.,
                     db.getDefaultSerializer(),.);
             BNode root = new LeafNode(new Object[]{nullnull}, new Object[]{}, 0);
             rootRef = db.getEngine().put(rootrootSerializer);
             db.getEngine().update(.,rootRef.);
         }
         return new BTreeMap<StringObject>(db.engine,.,32,false,0,
                 .,
                 db.getDefaultSerializer(),
                 (Comparator).);
     }



    
if valsOutsideNodes is true, this class is used instead of values. It contains reference to actual value. It also supports assertions from preventing it to leak outside of Ma
 
     protected static final class ValRef{
        
reference to actual value
 
         final long recid;
         public ValRef(long recid) {
             this. = recid;
         }
 
         @Override
         public boolean equals(Object obj) {
             throw new InternalError();
         }
 
         @Override
         public int hashCode() {
             throw new InternalError();
         }
 
     }


    
common interface for BTree node
 
     protected interface BNode{
         boolean isLeaf();
         Object[] keys();
         Object[] vals();
         Object highKey();
         long[] child();
         long next();
     }
 
     protected final static class DirNode implements BNode{
         final Object[] keys;
         final long[] child;
 
         DirNode(Object[] keyslong[] child) {
             this. = keys;
             this. = child;
         }
 
         DirNode(Object[] keysList<Longchild) {
             this. = keys;
             this. = new long[child.size()];
             for(int i=0;i<child.size();i++){
                 this.[i] = child.get(i);
             }
         }
 
 
         @Override public boolean isLeaf() { return false;}
 
         @Override public Object[] keys() { return ;}
         @Override public Object[] vals() { return null;}
 
         @Override public Object highKey() {return [.-1];}
 
         @Override public long[] child() { return ;}
 
         @Override public long next() {return [.-1];}
 
         @Override public String toString(){
             return "Dir(K"+Arrays.toString()+", C"+Arrays.toString()+")";
         }
 
     }
 
 
     protected final static class LeafNode implements BNode{
         final Object[] keys;
         final Object[] vals;
         final long next;
 
         LeafNode(Object[] keysObject[] valslong next) {
             this. = keys;
             this. = vals;
             this. = next;
             assert(vals==null||keys.length == vals.length+2);
         }
 
         @Override public boolean isLeaf() { return true;}
 
         @Override public Object[] keys() { return ;}
         @Override public Object[] vals() { return ;}
 
         @Override public Object highKey() {return [.-1];}
 
         @Override public long[] child() { return null;}
         @Override public long next() {return ;}
 
         @Override public String toString(){
             return "Leaf(K"+Arrays.toString()+", V"+Arrays.toString()+", L="++")";
         }
     }
 
 
     protected final Serializer<BNodenodeSerializer;
 
     protected static class NodeSerializer implements  Serializer<BNode>{
 
         protected final boolean hasValues;
         protected final boolean valsOutsideNodes;
         protected final BTreeKeySerializer keySerializer;
         protected final Serializer valueSerializer;
         protected final Comparator comparator;
 
         public NodeSerializer(boolean valsOutsideNodesBTreeKeySerializer keySerializerSerializer valueSerializerComparator comparator) {
             assert(keySerializer!=null);
             assert(comparator!=null);
             this. = valueSerializer!=null;
             this. = valsOutsideNodes;
             this. = keySerializer;
             this. = valueSerializer;
             this. = comparator;
         }
 
         @Override
         public void serialize(DataOutput outBNode valuethrows IOException {
             final boolean isLeaf = value.isLeaf();
 
             //first byte encodes if is leaf (first bite) and length (last seven bites)
             if(value.keys().length>255) throw new InternalError();
             if(!isLeaf && value.child().length!= value.keys().lengththrow new InternalError();
             if(isLeaf &&  && value.vals().length!= value.keys().length-2) throw new InternalError();
 
             //check node integrity in paranoid mode
             if(.){
                 int len = value.keys().length;
                 for(int i=value.keys()[0]==null?2:1;
                   i<(value.keys()[len-1]==null?len-1:len);
                   i++){
                     int comp = .compare(value.keys()[i-1], value.keys()[i]);
                     int limit = i==len-1 ? 1:0 ;
                     if(comp>=limit){
                         throw new AssertionError("BTreeNode format error, wrong key order at #"+i+"\n"+value);
                     }
                 }
 
             }
 
 
             final boolean left = value.keys()[0] == null;
             final boolean right = value.keys()[value.keys().length-1] == null;
 
 
             final int header;
 
             if(isLeaf){
                 if(right){
                     if(left)
                         header = ;
                     else
                         header = ;
                 }else{
                     if(left)
                         header = ;
                     else
                         header = ;
                 }
             }else{
                 if(right){
                     if(left)
                         header = ;
                     else
                         header = ;
                 }else{
                     if(left)
                         header = ;
                     else
                         header = ;
                 }
             }
 
 
 
             out.write(header);
             out.write(value.keys().length);
 
             //longs go first, so it is possible to reconstruct tree without serializer
             if(isLeaf){
                 Utils.packLong(out, ((LeafNodevalue).);
             }else{
                 for(long child : ((DirNode)value).)
                     Utils.packLong(outchild);
             }
 
 
             .serialize(out,left?1:0,
                     right?value.keys().length-1:value.keys().length,
                     value.keys());
 
             if(isLeaf && ){
                 for(Object val:value.vals()){
                     assert(val!=null);
                     if(){
                         long recid = ((ValRef)val).;
                         Utils.packLong(outrecid);
                     }else{
                         .serialize(out,  val);
                     }
                 }
             }
         }
 
         @Override
         public BNode deserialize(DataInput inint availablethrows IOException {
             final int header = in.readUnsignedByte();
             final int size = in.readUnsignedByte();
             //first bite indicates leaf
             final boolean isLeaf =
                     header ==   || header ==  ||
                     header ==  || header == ;
             final int start =
                 (header==  || header ==  || header==  || header == ) ?
                 1:0;
 
             final int end =
                 (header==  || header ==  || header==  || header == ) ?
                 size-1:size;
 
 
             if(isLeaf){
                 long next = Utils.unpackLong(in);
                 Object[] keys = .deserialize(instart,end,size);
                 if(keys.length!=sizethrow new InternalError();
                 Object[] vals  = null;
 
                 if(){
                     vals = new Object[size-2];
                     for(int i=0;i<size-2;i++){
                         if(){
                             long recid = Utils.unpackLong(in);
                             vals[i] = recid==0? nullnew ValRef(recid);
                         }else{
                             vals[i] = .deserialize(in, -1);
                         }
                     }
                 }
                 return new LeafNode(keysvalsnext);
             }else{
                 long[] child = new long[size];
                 for(int i=0;i<size;i++)
                     child[i] = Utils.unpackLong(in);
                 Object[] keys = .deserialize(instart,end,size);
                 if(keys.length!=sizethrow new InternalError();
                 return new DirNode(keyschild);
             }
         }
     };


    
Constructor used to create new BTreeMap.

Parameters:
engine used for persistence
rootRecidRef reference to root recid
maxNodeSize maximal BTree Node size. Node will split if number of entries is higher
valsOutsideNodes Store Values outside of BTree Nodes in separate record?
counterRecid recid under which `Atomic.Long` is stored, or `0` for no counter
keySerializer Serializer used for keys. May be null for default value. TODO delta packing
valueSerializer Serializer used for values. May be null for default value
comparator Comparator to sort keys in this BTree, may be null.
 
     public BTreeMap(Engine enginelong rootRecidRefint maxNodeSizeboolean valsOutsideNodeslong counterRecid,
                     BTreeKeySerializer<K> keySerializerSerializer<V> valueSerializerComparator<K> comparator) {
         if(maxNodeSize%2!=0) throw new IllegalArgumentException("maxNodeSize must be dividable by 2");
         if(maxNodeSize<6) throw new IllegalArgumentException("maxNodeSize too low");
         if(maxNodeSize>126) throw new IllegalArgumentException("maxNodeSize too high");
         if(keySerializer==nullthrow new NullPointerException();
         if(comparator==nullthrow new NullPointerException();
         SerializerBase.assertSerializable(keySerializer);
         SerializerBase.assertSerializable(valueSerializer);
         SerializerBase.assertSerializable(comparator);
 
 
 
         this. = rootRecidRef;
         this. = valueSerializer!=null;
         this. = valsOutsideNodes;
         this. = engine;
         this. = maxNodeSize;
         this. = comparator;
         //TODO when delta packing implemented, add assertion for COMPARABLE_COMPARATOR
         this. = keySerializer;
         this. = valueSerializer;
 
 
         this. = new NodeSerializer(valsOutsideNodes,keySerializer,valueSerializer,comparator);
 
         this. = new KeySet(this);
 
 
         if(counterRecid!=0){
             this. = new Atomic.Long(engine,counterRecid);
             Bind.size(this,);
         }else{
             this. = null;
         }
 
 
     }

    
creates empty root node and returns recid of its referenc
 
     static protected long createRootRef(Engine engineBTreeKeySerializer keySerSerializer valueSerComparator comparator){
         final LeafNode emptyRoot = new LeafNode(new Object[]{nullnull}, new Object[]{}, 0);
         //empty root is serializer simpler way, so we can use dummy values
         long rootRecidVal = engine.put(emptyRoot,  new NodeSerializer(false,keyServalueSercomparator));
         return engine.put(rootRecidVal,.);
     }



    
Find the first children node with a key equal or greater than the given key. If all items are smaller it returns `keys.length`
 
     protected final int findChildren(final Object keyfinal Object[] keys) {
         int left = 0;
         if(keys[0] == nullleft++;
         int right = keys[keys.length-1] == null ? keys.length-1 :  keys.length;
 
         int middle;
 
         // binary search
         while (true) {
             middle = (left + right) / 2;
             if(keys[middle]==nullreturn middle//null is positive infinitive
             if (.compare(keys[middle], key) < 0) {
                 left = middle + 1;
             } else {
                 right = middle;
             }
             if (left >= right) {
                 return  right;
             }
         }
 
     }
 
     @Override
 	public V get(Object key){
         if(key==nullthrow new NullPointerException();
         K v = (K) key;
         final long rootRecid = .get(.);
         long current = rootRecid;
         BNode A = .get(current);
 
         //dive until  leaf
         while(!A.isLeaf()){
             current = nextDir((DirNodeAv);
             A = .get(current);
         }
 
         //now at leaf level
         LeafNode leaf = (LeafNodeA;
         int pos = findChildren(vleaf.keys);
         while(pos == leaf.keys.length){
             //follow next link on leaf until necessary
             leaf = (LeafNode.get(leaf.next);
             pos = findChildren(vleaf.keys);
         }
 
         if(pos==leaf.keys.length-1){
             return null//last key is always deleted
         }
         //finish search
         if(leaf.keys[pos]!=null && 0==.compare(v,leaf.keys[pos])){
             Object ret = (leaf.vals[pos-1] : .);
             return valExpand(ret);
         }else
             return null;
     }
 
     protected V valExpand(Object ret) {
         if( && ret!=null) {
             long recid = ((ValRef)ret).;
             ret = .get(recid);
         }
         return (V) ret;
     }
 
     protected long nextDir(DirNode dObject key) {
         int pos = findChildren(keyd.keys) - 1;
         if(pos<0) pos = 0;
         return d.child[pos];
     }
 
 
     @Override
     public V put(K key, V value){
         if(key==null||value==nullthrow new NullPointerException();
         return put2(key,valuefalse);
     }
 
     protected V put2(K v, V value2final boolean putOnlyIfAbsent){
         if(v == nullthrow new IllegalArgumentException("null key");
         if(value2 == nullthrow new IllegalArgumentException("null value");
         Utils.checkMapValueIsNotCollecion(value2);
 
         V value = value2;
         if(){
             long recid = .put(value2);
             value = (V) new ValRef(recid);
         }
 
         int stackPos = -1;
         long[] stackVals = new long[4];
 
         final long rootRecid = .get(.);
         long current = rootRecid;
 
         BNode A = .get(current);
         while(!A.isLeaf()){
             long t = current;
             current = nextDir((DirNodeAv);
             if(current == A.child()[A.child().length-1]){
                 //is link, do nothing
             }else{
                 //stack push t
                 stackPos++;
                 if(stackVals.length == stackPos//grow if needed
                     stackVals = Arrays.copyOf(stackValsstackVals.length*2);
                 stackVals[stackPos] = t;
             }
             A = .get(current);
         }
         int level = 1;
 
         long p=0;
         try{
         while(true){
             boolean found;
             do{
                 Utils.lock(current);
                 found = true;
                 A = .get(current);
                 int pos = findChildren(vA.keys());
                 if(pos<A.keys().length-1 &&  v!=null && A.keys()[pos]!=null &&
                         0==.compare(v,A.keys()[pos])){
 
                     Object oldVal =   (A.vals()[pos-1] : .);
                     if(putOnlyIfAbsent){
                         //is not absent, so quit
                         Utils.unlock(current);
                         Utils.assertNoLocks();
                         V ret =  valExpand(oldVal);
                         notify(v,retvalue2);
                         return ret;
                     }
                     //insert new
                     Object[] vals = null;
                     if(){
                         vals = Arrays.copyOf(A.vals(), A.vals().length);
                         vals[pos-1] = value;
                     }
 
                     A = new LeafNode(Arrays.copyOf(A.keys(), A.keys().length), vals, ((LeafNode)A).);
                     .update(currentA);
                     //already in here
                     Utils.unlock(current);
                     Utils.assertNoLocks();
                     V ret =  valExpand(oldVal);
                     notify(v,retvalue2);
                     return ret;
                 }
 
                 if(A.highKey() != null && .compare(vA.highKey())>0){
                     //follow link until necessary
                     Utils.unlock(current);
                     found = false;
                     int pos2 = findChildren(vA.keys());
                     while(A!=null && pos2 == A.keys().length){
                         //TODO lock?
                         long next = A.next();
 
                         if(next==0) break;
                         current = next;
                         A = .get(current);
                         pos2 = findChildren(vA.keys());
                     }
 
                 }
 
 
             }while(!found);
 
             // can be new item inserted into A without splitting it?
             if(A.keys().length - (A.isLeaf()?2:1)<){
                 int pos = findChildren(vA.keys());
                 Object[] keys = Utils.arrayPut(A.keys(), posv);
 
                 if(A.isLeaf()){
                     Object[] vals = ? Utils.arrayPut(A.vals(), pos-1, value): null;
                     LeafNode n = new LeafNode(keysvals, ((LeafNode)A).);
                     .update(currentn);
                 }else{
                     if(p==0)
                         throw new InternalError();
                     long[] child = Utils.arrayLongPut(A.child(), posp);
                     DirNode d = new DirNode(keyschild);
                     .update(currentd);
                 }
 
                 Utils.unlock(current);
                 Utils.assertNoLocks();
                 notify(v,  nullvalue2);
                 return null;
             }else{
                 //node is not safe, it requires splitting
                 final boolean isRoot = (current == rootRecid);
 
                 final int pos = findChildren(vA.keys());
                 final Object[] keys = Utils.arrayPut(A.keys(), posv);
                 final Object[] vals = (A.isLeaf() && )? Utils.arrayPut(A.vals(), pos-1, value) : null;
                 final long[] child = A.isLeaf()? null : Utils.arrayLongPut(A.child(), posp);
                 final int splitPos = keys.length/2;
                 BNode B;
                 if(A.isLeaf()){
                     Object[] vals2 = null;
                     if(){
                         vals2 = Arrays.copyOfRange(valssplitPosvals.length);
                     }
 
                     B = new LeafNode(
                                 Arrays.copyOfRange(keyssplitPoskeys.length),
                                 vals2,
                                 ((LeafNode)A).);
                 }else{
                     B = new DirNode(Arrays.copyOfRange(keyssplitPoskeys.length),
                                 Arrays.copyOfRange(childsplitPoskeys.length));
                 }
                 long q = .put(B);
                 if(A.isLeaf()){  //  splitPos+1 is there so A gets new high  value (key)
                     Object[] keys2 = Arrays.copyOf(keyssplitPos+2);
                     keys2[keys2.length-1] = keys2[keys2.length-2];
                     Object[] vals2 = null;
                     if(){
                         vals2 = Arrays.copyOf(valssplitPos);
                     }
                     //TODO check high/low keys overlap
                     A = new LeafNode(keys2vals2q);
                 }else{
                     long[] child2 = Arrays.copyOf(childsplitPos+1);
                     child2[splitPos] = q;
                     A = new DirNode(Arrays.copyOf(keyssplitPos+1), child2);
                 }
                 .update(currentA);
 
                 if(!isRoot){
                     Utils.unlock(current);
                     p = q;
                     v = (K) A.highKey();
                     level = level+1;
                     if(stackPos!=-1){ //if stack is not empty
                         current = stackVals[stackPos--];
                     }else{
                         current = -1; //TODO pointer to left most node at level level
                         throw new InternalError();
                     }
                 }else{
                     BNode R = new DirNode(
                             new Object[]{A.keys()[0], A.highKey(), B.highKey()},
                             new long[]{current,q, 0});
 
 
                     long newRootRecid = .put(R);
 
                     //TODO tree root locking
                     .update(newRootRecid.);
 
 
                     //TODO update tree levels
                     Utils.unlock(current);
                     Utils.assertNoLocks();
                     notify(vnullvalue2);
                     return null;
                 }
             }
         }
         }catch(RuntimeException e){
             Utils.unlockAll();
             throw e;
         }catch(Exception e){
             Utils.unlockAll();
             throw new RuntimeException(e);
         }
     }
 
 
     protected static class BTreeIterator{
         final BTreeMap m;
 
         LeafNode currentLeaf;
         Object lastReturnedKey;
         int currentPos;
         final Object hi;
         final boolean hiInclusive;

        
unbounded iterato
 
         BTreeIterator(BTreeMap m){
             this. = m;
             =null;
             =false;
             pointToStart();
         }

        
bounder iterator, args may be null for partially bounde
 
         BTreeIterator(BTreeMap mObject loboolean loInclusiveObject hiboolean hiInclusive){
             this. = m;
             if(lo==null){
                 pointToStart();
             }else{
                 Fun.Tuple2<IntegerLeafNodel = m.findLargerNode(loloInclusive);
                  = l!=nulll.a : -1;
                  = l!=null ? l.b : null;
             }
 
             this. = hi;
             this. = hiInclusive;
             if(hi!=null && !=null){
                 //check in bounds
                 Object key =  .[];
                 int c = m.comparator.compare(keyhi);
                 if (c > 0 || (c == 0 && !hiInclusive)){
                     //out of high bound
                     =null;
                     =-1;
                 }
             }
 
         }
 
 
         private void pointToStart() {
             //find left-most leaf
             final long rootRecid = ..get(..);
             BNode node = (BNode..get(rootRecid.);
             while(!node.isLeaf()){
                 node = (BNode..get(node.child()[0], .);
             }
              = (LeafNodenode;
              = 1;
 
             while(..==2){
                 //follow link until leaf is not empty
                 if(. == 0){
                      = null;
                     return;
                 }
                  = (LeafNode..get(..);
             }
         }
 
 
         public boolean hasNext(){
             return !=null;
         }
 
         public void remove(){
             if(==nullthrow new IllegalStateException();
             .remove();
              = null;
         }
 
         protected void advance(){
             if(==nullreturn;
              =  .[];
             ++;
             if( == ..-1){
                 //move to next leaf
                 if(.==0){
                      = null;
                     =-1;
                     return;
                 }
                  = 1;
                  = (LeafNode..get(..);
                 while(..==2){
                     if(. ==0){
                          = null;
                         =-1;
                         return;
                     }
                      = (LeafNode..get(..);
                 }
             }
             if(!=null && !=null){
                 //check in bounds
                 Object key =  .[];
                 int c = ..compare(key);
                 if (c > 0 || (c == 0 && !)){
                     //out of high bound
                     =null;
                     =-1;
                 }
             }
         }
     }
 
     @Override
 	public V remove(Object key) {
         return remove2(keynull);
     }
 
     private V remove2(Object keyObject value) {
         final long rootRecid = .get(.);
         long current = rootRecid;
         BNode A = .get(current);
         while(!A.isLeaf()){
             current = nextDir((DirNodeAkey);
             A = .get(current);
         }
 
         try{
         while(true){
 
             Utils.lock(current);
             A = .get(current);
             int pos = findChildren(keyA.keys());
             if(pos<A.keys().length&& key!=null && A.keys()[pos]!=null &&
                     0==.compare(key,A.keys()[pos])){
                 //check for last node which was already deleted
                 if(pos == A.keys().length-1 && value == null){
                     Utils.unlock(current);
                     return null;
                 }
 
                 //delete from node
                 Object oldVal =  A.vals()[pos-1] : .;
                 oldVal = valExpand(oldVal);
                 if(value!=null && !value.equals(oldVal)){
                     Utils.unlock(current);
                     return null;
                 }
 
                 Object[] keys2 = new Object[A.keys().length-1];
                 System.arraycopy(A.keys(),0,keys2, 0, pos);
                 System.arraycopy(A.keys(), pos+1, keys2poskeys2.length-pos);
 
                 Object[] vals2 = null;
                 if(){
                     vals2 = new Object[A.vals().length-1];
                     System.arraycopy(A.vals(),0,vals2, 0, pos-1);
                     System.arraycopy(A.vals(), posvals2pos-1, vals2.length-(pos-1));
                 }
 
                 A = new LeafNode(keys2vals2, ((LeafNode)A).);
                 .update(currentA);
                 Utils.unlock(current);
                 notify((K)key, (V)oldValnull);
                 return (V) oldVal;
             }else{
                 Utils.unlock(current);
                 //follow link until necessary
                 if(A.highKey() != null && .compare(keyA.highKey())>0){
                     int pos2 = findChildren(keyA.keys());
                     while(pos2 == A.keys().length){
                         //TODO lock?
                         current = ((LeafNode)A).;
                         A = .get(current);
                     }
                 }else{
                     return null;
                 }
             }
         }
         }catch(RuntimeException e){
             Utils.unlockAll();
             throw e;
         }catch(Exception e){
             Utils.unlockAll();
             throw new RuntimeException(e);
         }
     }
 
 
     @Override
     public void clear() {
         Iterator iter = keyIterator();
         while(iter.hasNext()){
             iter.next();
             iter.remove();
         }
     }
 
 
     static class BTreeKeyIterator<K> extends BTreeIterator implements Iterator<K>{
 
         BTreeKeyIterator(BTreeMap m) {
             super(m);
         }
 
         BTreeKeyIterator(BTreeMap mObject loboolean loInclusiveObject hiboolean hiInclusive) {
             super(mloloInclusivehihiInclusive);
         }
 
         @Override
         public K next() {
             if( == nullthrow new NoSuchElementException();
             K ret = (K) .[];
             advance();
             return ret;
         }
     }
 
     static  class BTreeValueIterator<V> extends BTreeIterator implements Iterator<V>{
 
         BTreeValueIterator(BTreeMap m) {
             super(m);
         }
 
         BTreeValueIterator(BTreeMap mObject loboolean loInclusiveObject hiboolean hiInclusive) {
             super(mloloInclusivehihiInclusive);
         }
 
         @Override
         public V next() {
             if( == nullthrow new NoSuchElementException();
             Object ret = .[-1];
             advance();
             return (V) .valExpand(ret);
         }
 
     }
 
     static  class BTreeEntryIterator<K,V> extends BTreeIterator implements  Iterator<Entry<K, V>>{
 
         BTreeEntryIterator(BTreeMap m) {
             super(m);
         }
        BTreeEntryIterator(BTreeMap mObject loboolean loInclusiveObject hiboolean hiInclusive) {
            super(mloloInclusivehihiInclusive);
        }
        @Override
        public Entry<K, V> next() {
            if( == nullthrow new NoSuchElementException();
            K ret = (K) .[];
            Object val = .[-1];
            advance();
            return .makeEntry(ret.valExpand(val));
        }
    }
    protected Entry<K, V> makeEntry(Object keyObject value) {
        if(value instanceof ValRefthrow new InternalError();
        return new SimpleImmutableEntry<K, V>((K)key,  (V)value);
    }
    @Override
    public boolean isEmpty() {
        return !keyIterator().hasNext();
    }
    @Override
    public int size() {
        long size = sizeLong();
        if(size>.return .;
        return (intsize;
    }
    @Override
    public long sizeLong() {
        if(!=null)
            return .get();
        long size = 0;
        BTreeIterator iter = new BTreeIterator(this);
        while(iter.hasNext()){
            iter.advance();
            size++;
        }
        return size;
    }
    @Override
    public V putIfAbsent(K key, V value) {
        if(key == null || value == nullthrow new NullPointerException();
        return put2(keyvaluetrue);
    }
    @Override
    public boolean remove(Object keyObject value) {
        if(key == nullthrow new NullPointerException();
        if(value == nullreturn false;
        return remove2(keyvalue)!=null;
    }
    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        if(key == null || oldValue == null || newValue == null ) throw new NullPointerException();
        long rootRecid = .get(.);
        long current = rootRecid;
        BNode node = .get(current);
        //dive until leaf is found
        while(!node.isLeaf()){
            current = nextDir((DirNodenodekey);
            node = .get(current</