Changeset 19680


Ignore:
Timestamp:
02/08/12 23:46:12 (4 months ago)
Author:
sys
Message:

Tree en cours...

Location:
trunk/Jav_Orient
Files:
4 added
16 edited
4 moved

Legend:

Unmodified
Added
Removed

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/IValueList.java

    r19672 r19680  
    4646public interface IValueList<E> extends IValue<List<E>>, List<E> { 
    4747 
     48        /** 
     49         *  
     50         */ 
     51        public boolean isConcurrentReadAccessAware(); 
    4852} 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/lib/base/ValueList.java

    r19672 r19680  
    252252        } 
    253253 
     254        public boolean isConcurrentReadAccessAware() { 
     255                return false; 
     256        } 
     257 
    254258        @Override 
    255259        public void onPersist(PersistStep pStep, IRecordStruct<?> pRecord, boolean pRemovedValue) { 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/lib/tree/ITreeStorageConfig.java

    r19672 r19680  
    6060 
    6161        /** 
     62         * Is tree is accessed by multi-thread. 
     63         */ 
     64        public boolean isTreeThreadSafe(); 
     65 
     66        /** 
    6267         * The maximum number of entries a rake should contain. 
    6368         */ 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/lib/tree/TreeStorageConfig.java

    r19672 r19680  
    5454        //protected boolean fAverageCapacityStored = false; 
    5555 
     56        protected boolean fTreeThreadSafe; 
     57 
    5658        protected int fRakeCapacity = 64; 
    5759 
    … …  
    8284        public boolean isAverageCapacityStored() { 
    8385                return false; 
     86        } 
     87 
     88        public boolean isTreeThreadSafe() { 
     89                return fTreeThreadSafe; 
    8490        } 
    8591 
    … …  
    133139        //      } 
    134140 
     141        public <RET extends TreeStorageConfig> RET setTreeThreadSafe(boolean pTreeThreadSafe) { 
     142                fTreeThreadSafe = pTreeThreadSafe; 
     143                return (RET) this; 
     144        } 
     145 
    135146        public <RET extends TreeStorageConfig> RET setRakeCapacity(int pRakeCapacity) { 
    136147                fRakeCapacity = pRakeCapacity; 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/lib/tree/ValueTree.java

    r19678 r19680  
    5858import eu.scenari.orient.recordstruct.types.TypesBase; 
    5959import eu.scenari.orient.recordstruct.value.ValueUpdatableAbstract; 
    60 import eu.scenari.orient.tree.impl.Tree; 
     60import eu.scenari.orient.tree.impl.RSTree; 
     61import eu.scenari.orient.tree.impl.RSTreeConcurrent; 
    6162import eu.scenari.orient.tree.provider.ITreeNodeProvider; 
    6263import eu.scenari.orient.tree.provider.ITreeProvider; 
    … …  
    7071        protected StructTree fStruct; 
    7172 
    72         protected Tree fPojo; 
     73        protected RSTree fPojo; 
    7374 
    7475        protected ValueRID fRootEntry; 
    7576 
    7677        protected int fSize; 
     78 
     79        protected boolean fConcurrReadAccesAware; 
    7780 
    7881        protected ArrayList<IRecordStruct<?>> fNodesToSave; 
    … …  
    8588                fRootEntry = new ValueRID(); 
    8689                fSize = 0; 
    87                 fPojo = new Tree(this, getTreeStorageConfig().getKeyComparator(), getTreeStorageConfig().getBalancingLayout()); 
     90                if (getTreeStorageConfig().isTreeThreadSafe()) { 
     91                        fPojo = new RSTreeConcurrent(this, getTreeStorageConfig().getKeyComparator(), getTreeStorageConfig().getBalancingLayout(), 5000); 
     92                } else { 
     93                        fPojo = new RSTree(this, getTreeStorageConfig().getKeyComparator(), getTreeStorageConfig().getBalancingLayout()); 
     94                } 
    8895        } 
    8996 
    … …  
    94101                fSize = pReader.getAsInteger(); 
    95102                if (!getTreeStorageConfig().isSizeStored()) fSize = SIZE_UNKNOWN; 
    96                 fPojo = new Tree(this, getTreeStorageConfig().getKeyComparator(), getTreeStorageConfig().getBalancingLayout()); 
     103                fPojo = new RSTree(this, getTreeStorageConfig().getKeyComparator(), getTreeStorageConfig().getBalancingLayout()); 
    97104        } 
    98105 
    … …  
    106113 
    107114        // ############# 
     115 
     116        public void setConcurrReadAccess(boolean pMultithreadContext) { 
     117                fConcurrReadAccesAware = pMultithreadContext; 
     118        } 
    108119 
    109120        public int getSize() { 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/lib/tree/ValueTreeNode.java

    r19678 r19680  
    7070 
    7171        public int getSize() { 
     72                if (fTree.fConcurrReadAccesAware && !fKeys.isConcurrentReadAccessAware()) { 
     73                        synchronized (fKeys) { 
     74                                return fKeys.size(); 
     75                        } 
     76                } 
    7277                return fKeys.size(); 
    7378        } 
    … …  
    7580        public K getKey(int pOffset) { 
    7681                assert (pOffset >= 0 && pOffset < getSize()) : "Out of bounds: " + pOffset + "/" + getSize(); 
     82                if (fTree.fConcurrReadAccesAware && !fKeys.isConcurrentReadAccessAware()) { 
     83                        synchronized (fKeys) { 
     84                                return fKeys.get(pOffset); 
     85                        } 
     86                } 
    7787                return fKeys.get(pOffset); 
    7888        } 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/lib/tree/ValueTreeRake.java

    r19678 r19680  
    148148 
    149149        public ITreeNodeProvider<K, V> loadNode(int pOffset) { 
    150                 ValueTreeNode<?, K, V> vNode = getDb().loadValue(fSubNodes.get(pOffset)); 
     150                ORID vId; 
     151                if (fTree.fConcurrReadAccesAware && !fSubNodes.isConcurrentReadAccessAware()) { 
     152                        synchronized (fSubNodes) { 
     153                                vId = fSubNodes.get(pOffset); 
     154                        } 
     155                } else { 
     156                        vId = fSubNodes.get(pOffset); 
     157                } 
     158                ValueTreeNode<?, K, V> vNode = getDb().loadValue(vId); 
    151159                vNode.initNode(fTree); 
    152160                return vNode; 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/lib/tree/ValueTreeSlotKV.java

    r19678 r19680  
    142142 
    143143        public V getValue(int pOffset) { 
     144                if (fTree.fConcurrReadAccesAware && !fValues.isConcurrentReadAccessAware()) { 
     145                        synchronized (fValues) { 
     146                                return fValues.get(pOffset); 
     147                        } 
     148                } 
    144149                return fValues.get(pOffset); 
    145150        } 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/value/ValueListImmutableFixed.java

    r19678 r19680  
    383383        } 
    384384 
     385        public boolean isConcurrentReadAccessAware() { 
     386                return true; 
     387        } 
     388 
    385389        //############# 
    386390 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/impl/BalancedLayout.java

    r19678 r19680  
    2222        protected float fTargetFillRateForNewRightNode = 0.5f; 
    2323 
     24        protected class GcVisitor implements IRSTreeNodeVisitor { 
     25 
     26                protected int fCount = 0; 
     27 
     28                protected int fLimit = 0; 
     29 
     30                public GcVisitor(int pLimit) { 
     31                        super(); 
     32                        fLimit = pLimit; 
     33                } 
     34 
     35                public <K, V> Result visitNode(RSTreeNode<K, V> pNode) { 
     36                        if (fLimit < fCount) { 
     37                                if (pNode.getParent() != null) pNode.getParent().removeChildFromMemory(pNode); 
     38                                return Result.skipChildren; 
     39                        } else { 
     40                                fCount++; 
     41                        } 
     42                        return Result.gotoNext; 
     43                } 
     44 
     45        } 
     46 
    2447        public BalancedLayout() { 
    2548                super(); 
    … …  
    3659         * @param pOffset replace position (if>=0) or insert position if negative value. 
    3760         */ 
    38         public <K, V> void addSpaceAndPut(TreeSlot<K, V> pSlot, int pOffset, K pKey, V pValue) { 
    39                 Tree<K, V> vTree = pSlot.fTree; 
    40                 TreeSlot<K, V> vSlot = pSlot; 
     61        public <K, V> void addSpaceAndPut(RSTreeSlot<K, V> pSlot, int pOffset, K pKey, V pValue) { 
     62                RSTree<K, V> vTree = pSlot.fTree; 
     63                RSTreeSlot<K, V> vSlot = pSlot; 
    4164                ITreeSlotProvider<K, V> vSlotProvider = vSlot.getProvider(); 
    4265                int vCurrentOffset = pOffset; 
    4366                if (fFillingThreshold > 0) { 
    4467                        //First step : try to move entries in right slot. 
    45                         TreeSlot<K, V> vRightSlot = vSlot.findRightSlot(); 
     68                        RSTreeSlot<K, V> vRightSlot = vSlot.findRightSlot(); 
    4669                        if (vRightSlot != null && vRightSlot.getProvider().getFillRate() < fFillingThreshold) { 
    4770                                int vMoved = vRightSlot.adoptEntriesFromLeft(vSlot, (vRightSlot.getProvider().getFillRate() + vSlotProvider.getFillRate()) / 2); 
    … …  
    6992                        //Second step : try to move entries in left slot if current slot has not change. 
    7093                        if (vSlot == pSlot) { 
    71                                 TreeSlot<K, V> vLeftSlot = vSlot.findLeftSlot(); 
     94                                RSTreeSlot<K, V> vLeftSlot = vSlot.findLeftSlot(); 
    7295                                if (vLeftSlot != null && vLeftSlot.getProvider().getFillRate() < fFillingThreshold) { 
    7396                                        ITreeSlotProvider<K, V> vLeftSlotProvider = vLeftSlot.getProvider(); 
    … …  
    100123 
    101124                //Third step : need to insert new slot. 
    102                 TreeSlot<K, V> vNewSlot; 
     125                RSTreeSlot<K, V> vNewSlot; 
    103126                if (vSlot.fParent == null) { 
    104127                        vTree.createRakeAsRoot(vSlot); 
    105                         TreeRake<K, V> vParent = (TreeRake) vTree.fRoot; 
     128                        RSTreeRake<K, V> vParent = (RSTreeRake) vTree.fRoot; 
    106129                        vNewSlot = vParent.insertNewSlot(1); 
    107130                } else { 
    … …  
    146169        } 
    147170 
    148         public <K, V> void onRemovedEntry(TreeNode<K, V> pNode) { 
     171        public <K, V> void onRemovedEntry(RSTreeNode<K, V> pNode) { 
    149172                if (pNode.fParent != null && pNode.fProvider.getFillRate() < fOptimizeThreshold) { 
    150173                        //pNode become too empty, try to merge with a neighbour 
    151174                        if (pNode.isRake()) { 
    152                                 tryToDeleteRake((TreeRake<K, V>) pNode); 
     175                                tryToDeleteRake((RSTreeRake<K, V>) pNode); 
    153176                        } else { 
    154                                 tryToDeleteSlot((TreeSlot<K, V>) pNode); 
    155                         } 
    156                 } 
    157         } 
    158  
    159         public <K, V> void onNewRoot(TreeNode<K, V> pNode) { 
    160  
    161         } 
    162  
    163         protected <K, V> void tryToDeleteSlot(TreeSlot<K, V> pNode) { 
    164                 TreeSlot<K, V> vLeftNode = pNode.findLeftSlot(); 
     177                                tryToDeleteSlot((RSTreeSlot<K, V>) pNode); 
     178                        } 
     179                } 
     180        } 
     181 
     182        public <K, V> void freeMemory(RSTreeNode<K, V> pRoot, float pRate) { 
     183                int vCountNodes = pRoot.countNodesInMemory(); 
     184                int vLimit = vCountNodes / 2; 
     185                pRoot.accept(new GcVisitor(vLimit), true); 
     186        } 
     187 
     188        protected <K, V> void tryToDeleteSlot(RSTreeSlot<K, V> pNode) { 
     189                RSTreeSlot<K, V> vLeftNode = pNode.findLeftSlot(); 
    165190                if (vLeftNode != null && vLeftNode.getProvider().getFillRate() < fFillingThreshold) { 
    166191                        //Try to merge 
    … …  
    170195                        } 
    171196                } 
    172                 TreeSlot<K, V> vRightNode = pNode.findRightSlot(); 
     197                RSTreeSlot<K, V> vRightNode = pNode.findRightSlot(); 
    173198                if (vRightNode != null && vRightNode.getProvider().getFillRate() < fFillingThreshold) { 
    174199                        //Try to merge 
    … …  
    180205        } 
    181206 
    182         protected <K, V> void tryToDeleteRake(TreeRake<K, V> pNode) { 
    183                 TreeNode<K, V> vLeftNode = pNode.fParent.findLeftCousin(pNode.getOffsetInParent()); 
     207        protected <K, V> void tryToDeleteRake(RSTreeRake<K, V> pNode) { 
     208                RSTreeNode<K, V> vLeftNode = pNode.fParent.findLeftCousin(pNode.getOffsetInParent()); 
    184209                if (vLeftNode != null && vLeftNode.getProvider().getFillRate() < fFillingThreshold && vLeftNode.isRake()) { 
    185210                        //Try to merge 
    … …  
    189214                        } 
    190215                } 
    191                 TreeNode<K, V> vRightNode = pNode.fParent.findRightCousin(pNode.getOffsetInParent()); 
     216                RSTreeNode<K, V> vRightNode = pNode.fParent.findRightCousin(pNode.getOffsetInParent()); 
    192217                if (vRightNode != null && vRightNode.getProvider().getFillRate() < fFillingThreshold && vRightNode.isRake()) { 
    193218                        //Try to merge 
    … …  
    199224        } 
    200225 
    201         protected <K, V> int getDepthRake(Tree<K, V> pTree) { 
    202                 return pTree.fRoot.getDepthRake(); 
    203         } 
    204  
    205         protected <K, V> TreeRake<K, V> splitRakeAndInsertNewRake(TreeRake<K, V> pRakeToSplit, int pInsertPoint) { 
    206                 Tree<K, V> vTree = pRakeToSplit.fTree; 
    207                 TreeRake<K, V> vRake = pRakeToSplit; 
     226        protected <K, V> RSTreeRake<K, V> splitRakeAndInsertNewRake(RSTreeRake<K, V> pRakeToSplit, int pInsertPoint) { 
     227                RSTree<K, V> vTree = pRakeToSplit.fTree; 
     228                RSTreeRake<K, V> vRake = pRakeToSplit; 
    208229                ITreeRakeProvider<K, V> vRakeProvider = vRake.getProvider(); 
    209230                int vInsertPoint = pInsertPoint; 
    210231                if (fFillingThreshold > 0) { 
    211232                        //First step : try to move entries in right cousin rake. 
    212                         TreeNode<K, V> vCousin = vRake.findRightCousin(vInsertPoint); 
     233                        RSTreeNode<K, V> vCousin = vRake.findRightCousin(vInsertPoint); 
    213234                        if (vCousin != null && vCousin.isRake() && vCousin.getProvider().getFillRate() < fFillingThreshold) { 
    214                                 TreeRake<K, V> vRightRake = (TreeRake) vCousin; 
     235                                RSTreeRake<K, V> vRightRake = (RSTreeRake) vCousin; 
    215236                                int vMoved = vRightRake.adoptEntriesFromLeft(vRake, (vRightRake.getProvider().getFillRate() + vRakeProvider.getFillRate()) / 2); 
    216237                                if (vMoved > 0) { 
    … …  
    222243                                                vRake = vRightRake; 
    223244                                        } 
    224                                         TreeRake<K, V> vNewRake = vRake.insertNewRake(vInsertPoint); 
     245                                        RSTreeRake<K, V> vNewRake = vRake.insertNewRake(vInsertPoint); 
    225246                                        if (vNewRake != null) return vNewRake; 
    226247                                } 
    … …  
    230251                                vCousin = vRake.findLeftCousin(vInsertPoint); 
    231252                                if (vCousin != null && vCousin.isRake() && vCousin.getProvider().getFillRate() < fFillingThreshold) { 
    232                                         TreeRake<K, V> vLeftRake = (TreeRake) vCousin; 
     253                                        RSTreeRake<K, V> vLeftRake = (RSTreeRake) vCousin; 
    233254                                        ITreeRakeProvider<K, V> vLeftProvider = vLeftRake.getProvider(); 
    234255                                        int vMoved = vLeftRake.adoptEntriesFromRight(vRake, (vLeftProvider.getFillRate() + vRakeProvider.getFillRate()) / 2); 
    … …  
    242263                                                        vRake = vLeftRake; 
    243264                                                } 
    244                                                 TreeRake<K, V> vNewRake = vRake.insertNewRake(vInsertPoint); 
     265                                                RSTreeRake<K, V> vNewRake = vRake.insertNewRake(vInsertPoint); 
    245266                                                if (vNewRake != null) return vNewRake; 
    246267                                        } 
    … …  
    250271 
    251272                //Third step : need to insert new rake in parent context. 
    252                 TreeRake<K, V> vNewRake; 
     273                RSTreeRake<K, V> vNewRake; 
    253274                if (vRake.fParent == null) { 
    254275                        vTree.createRakeAsRoot(vRake); 
    255                         TreeRake<K, V> vParent = (TreeRake) vTree.fRoot; 
     276                        RSTreeRake<K, V> vParent = (RSTreeRake) vTree.fRoot; 
    256277                        vNewRake = vParent.insertNewRake(1); 
    257278                } else { 
    … …  
    283304        } 
    284305 
    285         protected <K, V> TreeSlot<K, V> splitRakeAndInsertNewSlot(TreeRake<K, V> pRakeToSplit, int pInsertPoint) { 
    286                 Tree<K, V> vTree = pRakeToSplit.fTree; 
    287                 TreeRake<K, V> vRake = pRakeToSplit; 
     306        protected <K, V> RSTreeSlot<K, V> splitRakeAndInsertNewSlot(RSTreeRake<K, V> pRakeToSplit, int pInsertPoint) { 
     307                RSTree<K, V> vTree = pRakeToSplit.fTree; 
     308                RSTreeRake<K, V> vRake = pRakeToSplit; 
    288309                ITreeRakeProvider<K, V> vRakeProvider = vRake.getProvider(); 
    289310                int vInsertPoint = pInsertPoint; 
    290311                if (fFillingThreshold > 0) { 
    291312                        //First step : try to move entries in right cousin rake. 
    292                         TreeNode<K, V> vCousin = vRake.findRightCousin(vInsertPoint); 
     313                        RSTreeNode<K, V> vCousin = vRake.findRightCousin(vInsertPoint); 
    293314                        if (vCousin != null && vCousin.isRake() && vCousin.getProvider().getFillRate() < fFillingThreshold) { 
    294                                 TreeRake<K, V> vRightRake = (TreeRake) vCousin; 
     315                                RSTreeRake<K, V> vRightRake = (RSTreeRake) vCousin; 
    295316                                int vMoved = vRightRake.adoptEntriesFromLeft(vRake, (vRightRake.getProvider().getFillRate() + vRakeProvider.getFillRate()) / 2); 
    296317                                if (vMoved > 0) { 
    … …  
    302323                                                vRake = vRightRake; 
    303324                                        } 
    304                                         TreeSlot<K, V> vNewSlot = vRake.insertNewSlot(vInsertPoint); 
     325                                        RSTreeSlot<K, V> vNewSlot = vRake.insertNewSlot(vInsertPoint); 
    305326                                        if (vNewSlot != null) return vNewSlot; 
    306327                                } 
    … …  
    310331                                vCousin = vRake.findLeftCousin(vInsertPoint); 
    311332                                if (vCousin != null && vCousin.isRake() && vCousin.getProvider().getFillRate() < fFillingThreshold) { 
    312                                         TreeRake<K, V> vLeftRake = (TreeRake) vCousin; 
     333                                        RSTreeRake<K, V> vLeftRake = (RSTreeRake) vCousin; 
    313334                                        ITreeRakeProvider<K, V> vLeftProvider = vLeftRake.getProvider(); 
    314335                                        int vMoved = vLeftRake.adoptEntriesFromRight(vRake, (vLeftProvider.getFillRate() + vRakeProvider.getFillRate()) / 2); 
    … …  
    322343                                                        vRake = vLeftRake; 
    323344                                                } 
    324                                                 TreeSlot<K, V> vNewSlot = vRake.insertNewSlot(vInsertPoint); 
     345                                                RSTreeSlot<K, V> vNewSlot = vRake.insertNewSlot(vInsertPoint); 
    325346                                                if (vNewSlot != null) return vNewSlot; 
    326347                                        } 
    … …  
    330351 
    331352                //Third step : need to insert new rake in parent context. 
    332                 TreeRake<K, V> vNewRake; 
     353                RSTreeRake<K, V> vNewRake; 
    333354                if (vRake.fParent == null) { 
    334355                        vTree.createRakeAsRoot(vRake); 
    335                         TreeRake<K, V> vParent = (TreeRake) vTree.fRoot; 
     356                        RSTreeRake<K, V> vParent = (RSTreeRake) vTree.fRoot; 
    336357                        vNewRake = vParent.insertNewRake(1); 
    337358                } else { 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/impl/IBalancingLayout.java

    r19675 r19680  
    88 
    99        /** Call on a put if the target slot is full. */ 
    10         public <K, V> void addSpaceAndPut(TreeSlot<K, V> pSlot, int pOffset, K pKey, V pValue); 
     10        public <K, V> void addSpaceAndPut(RSTreeSlot<K, V> pSlot, int pOffset, K pKey, V pValue); 
    1111 
    1212        /** Call when an entry is removed from a node. */ 
    13         public <K, V> void onRemovedEntry(TreeNode<K, V> pNode); 
     13        public <K, V> void onRemovedEntry(RSTreeNode<K, V> pNode); 
    1414 
    15         /** Call when the root is changed. */ 
    16         public <K, V> void onNewRoot(TreeNode<K, V> pNode); 
     15        /**  
     16         * Free memory. 
     17         *   
     18         * @param pRate Example : 0.5 try to divide by 2 the memory used by this tree.  
     19         **/ 
     20        public <K, V> void freeMemory(RSTreeNode<K, V> pRoot, float pRate); 
    1721} 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/impl/RSTree.java

    r19678 r19680  
    5353import eu.scenari.orient.tree.provider.ITreeSlotProvider; 
    5454 
    55 public class Tree<K, V> extends AbstractMap<K, V> { 
     55public class RSTree<K, V> extends AbstractMap<K, V> { 
    5656 
    5757        protected static final Comparator DEFAULT_COMPARARTOR = new Comparator() { 
    … …  
    6565        protected ITreeProvider<K, V> fProvider; 
    6666 
    67         protected TreeNode<K, V> fRoot; 
     67        protected RSTreeNode<K, V> fRoot; 
    6868 
    6969        protected EntrySet fEntrySet; 
    … …  
    8585        protected abstract class IteratorBase<T> implements Iterator<T> { 
    8686 
    87                 protected TreeSlot<K, V> fSlot; 
     87                protected RSTreeSlot<K, V> fSlot; 
    8888 
    8989                protected int fOffset = -1; 
    … …  
    9292 
    9393                public IteratorBase() { 
    94                         fExpectedModCount = Tree.this.fModCount; 
    95                         fSlot = Tree.this.findFirstSlot(); 
     94                        fExpectedModCount = RSTree.this.fModCount; 
     95                        fSlot = RSTree.this.findFirstSlot(); 
    9696                } 
    9797 
    … …  
    109109                protected void check() { 
    110110                        if (fSlot == null) throw new NoSuchElementException(); 
    111                         if (Tree.this.fModCount != fExpectedModCount) throw new ConcurrentModificationException(); 
     111                        if (RSTree.this.fModCount != fExpectedModCount) throw new ConcurrentModificationException(); 
    112112                } 
    113113 
    … …  
    142142        } 
    143143 
    144         protected class IteratorKey extends IteratorBase<K> { 
    145                 public K next() { 
    146                         check(); 
    147                         return fSlot.getProvider().getKey(fOffset); 
    148                 } 
    149         } 
    150  
    151         protected class IteratorValue extends IteratorBase<V> { 
    152                 public V next() { 
    153                         check(); 
    154                         return fSlot.getProvider().getValue(fOffset); 
    155                 } 
    156         } 
     144        //      protected class IteratorKey extends IteratorBase<K> { 
     145        //              public K next() { 
     146        //                      check(); 
     147        //                      return fSlot.getProvider().getKey(fOffset); 
     148        //              } 
     149        //      } 
     150        // 
     151        //      protected class IteratorValue extends IteratorBase<V> { 
     152        //              public V next() { 
     153        //                      check(); 
     154        //                      return fSlot.getProvider().getValue(fOffset); 
     155        //              } 
     156        //      } 
    157157 
    158158        /** 
    … …  
    180180                @Override 
    181181                public int size() { 
    182                         return Tree.this.size(); 
     182                        return RSTree.this.size(); 
    183183                } 
    184184 
    185185                @Override 
    186186                public void clear() { 
    187                         Tree.this.clear(); 
    188                 } 
    189         } 
    190  
    191         public Tree(ITreeProvider<K, V> pProvider) { 
     187                        RSTree.this.clear(); 
     188                } 
     189        } 
     190 
     191        public RSTree(ITreeProvider<K, V> pProvider) { 
    192192                this(pProvider, null, null); 
    193193        } 
    194194 
    195         public Tree(ITreeProvider<K, V> pProvider, Comparator<? super K> pComparator, IBalancingLayout pBalancingLayout) { 
     195        public RSTree(ITreeProvider<K, V> pProvider, Comparator<? super K> pComparator, IBalancingLayout pBalancingLayout) { 
    196196                super(); 
    197197                fProvider = pProvider; 
     198                fProvider.setConcurrReadAccess(isThreadSafe()); 
    198199                fComparator = pComparator != null ? pComparator : DEFAULT_COMPARARTOR; 
    199200                fBalancingLayout = pBalancingLayout != null ? pBalancingLayout : new BalancedLayout(); 
    … …  
    205206        } 
    206207 
    207         public Comparator<? super K> comparator() { 
     208        public Comparator<? super K> getComparator() { 
    208209                return fComparator; 
     210        } 
     211 
     212        public boolean isThreadSafe() { 
     213                return false; 
    209214        } 
    210215 
    … …  
    214219                //Size unknown, we compute size. 
    215220                vSize = 0; 
    216                 for (TreeSlot<K, V> vSlot = findFirstSlot(); vSlot != null; vSlot = vSlot.findRightSlot()) { 
     221                for (RSTreeSlot<K, V> vSlot = findFirstSlot(); vSlot != null; vSlot = vSlot.findRightSlot()) { 
    217222                        vSize += vSlot.getSize(); 
    218223                } 
    … …  
    227232                if (vSize == 0) return true; 
    228233                //Size unknown 
    229                 TreeSlot<K, V> vSlot = findFirstSlot(); 
     234                RSTreeSlot<K, V> vSlot = findFirstSlot(); 
    230235                while (vSlot != null && vSlot.getSize() == 0) { 
    231236                        vSlot = vSlot.findRightSlot(); 
    … …  
    235240 
    236241        public Set<Entry<K, V>> entrySet() { 
    237                 final EntrySet vResult = fEntrySet; 
     242                EntrySet vResult = fEntrySet; 
    238243                return (vResult != null) ? vResult : (fEntrySet = new EntrySet()); 
    239244        } 
    240245 
    241246        public V get(Object pKey) { 
    242                 TreeSlot<K, V> vSlot = fRoot.findSlot(pKey); 
     247                RSTreeSlot<K, V> vSlot = fRoot.findSlot(pKey); 
    243248                return vSlot != null ? vSlot.get(pKey) : null; 
    244249        } 
    245250 
    246251        public boolean containsKey(Object pKey) { 
    247                 TreeSlot<K, V> vSlot = fRoot.findSlot(pKey); 
     252                RSTreeSlot<K, V> vSlot = fRoot.findSlot(pKey); 
    248253                return vSlot != null ? vSlot.indexOf(pKey) >= 0 : false; 
    249254        } 
    250255 
    251256        public V put(K pKey, V pValue) { 
    252                 TreeSlot<K, V> vSlot = fRoot.findSlot(pKey); 
     257                RSTreeSlot<K, V> vSlot = fRoot.findSlot(pKey); 
    253258                if (vSlot == null) vSlot = fRoot.findFirstSlot(); 
    254259                ITreeSlotProvider<K, V> vSlotProvider = vSlot.getProvider(); 
    … …  
    273278 
    274279        public V remove(Object pKey) { 
    275                 TreeSlot<K, V> vSlot = fRoot.findSlot(pKey); 
     280                RSTreeSlot<K, V> vSlot = fRoot.findSlot(pKey); 
    276281                if (vSlot == null) return null; 
    277282                int vOffset = vSlot.indexOf(pKey); 
    … …  
    284289        } 
    285290 
    286         protected TreeSlot<K, V> findFirstSlot() { 
     291        protected RSTreeSlot<K, V> findFirstSlot() { 
    287292                return fRoot.findFirstSlot(); 
    288293        } 
    289294 
    290         protected TreeSlot<K, V> findSlot(Object pKey) { 
     295        protected RSTreeSlot<K, V> findSlot(Object pKey) { 
    291296                return fRoot.findSlot(pKey); 
    292297        } 
    … …  
    305310        } 
    306311 
    307         protected void createRakeAsRoot(TreeNode<K, V> pChild) { 
     312        protected void createRakeAsRoot(RSTreeNode<K, V> pChild) { 
    308313                ITreeRakeProvider<K, V> vRoot = fProvider.createRakeAsRoot(pChild.getProvider()); 
    309                 fRoot = new TreeRake<K, V>(this, vRoot, pChild); 
    310                 pChild.setParent((TreeRake) fRoot, 0); 
     314                fRoot = new RSTreeRake<K, V>(this, vRoot, pChild); 
     315                pChild.setParent((RSTreeRake) fRoot, 0); 
    311316        } 
    312317 
    313318        protected void setRootNode(ITreeNodeProvider<K, V> pRootProvider) { 
    314319                if (pRootProvider.isRake()) { 
    315                         fRoot = new TreeRake<K, V>(this, (ITreeRakeProvider<K, V>) pRootProvider); 
     320                        fRoot = new RSTreeRake<K, V>(this, (ITreeRakeProvider<K, V>) pRootProvider); 
    316321                } else { 
    317                         fRoot = new TreeSlot<K, V>(this, (ITreeSlotProvider<K, V>) pRootProvider); 
    318                 } 
    319         } 
    320  
    321         protected void setRoot(TreeNode<K, V> pNode) { 
     322                        fRoot = new RSTreeSlot<K, V>(this, (ITreeSlotProvider<K, V>) pRootProvider); 
     323                } 
     324        } 
     325 
     326        protected void setRoot(RSTreeNode<K, V> pNode) { 
    322327                fRoot = pNode; 
    323328                fProvider.setRoot(pNode.getProvider()); 
    324                 fBalancingLayout.onNewRoot(fRoot); 
    325329        } 
    326330} 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/impl/RSTreeNode.java

    r19678 r19680  
    33import eu.scenari.orient.tree.provider.ITreeNodeProvider; 
    44 
    5 public abstract class TreeNode<K, V> { 
     5public abstract class RSTreeNode<K, V> { 
    66 
    7         protected Tree<K, V> fTree; 
     7        protected final RSTree<K, V> fTree; 
    88 
    9         protected TreeRake<K, V> fParent; 
     9        protected RSTreeRake<K, V> fParent; 
    1010 
    1111        protected int fOffsetInParent; 
    … …  
    1313        protected ITreeNodeProvider<K, V> fProvider; 
    1414 
    15         public TreeNode(Tree<K, V> pTree, ITreeNodeProvider<K, V> pProvider) { 
     15        public RSTreeNode(RSTree<K, V> pTree, ITreeNodeProvider<K, V> pProvider) { 
    1616                fTree = pTree; 
    1717                fProvider = pProvider; 
    1818        } 
    1919 
    20         public TreeNode(TreeRake<K, V> pParent, int pOffsetInParent, ITreeNodeProvider<K, V> pProvider) { 
     20        public RSTreeNode(RSTreeRake<K, V> pParent, int pOffsetInParent, ITreeNodeProvider<K, V> pProvider) { 
    2121                fTree = pParent.getTree(); 
    2222                fProvider = pProvider; 
    … …  
    3030        } 
    3131 
    32         public Tree<K, V> getTree() { 
     32        public RSTree<K, V> getTree() { 
    3333                return fTree; 
    3434        } 
    3535 
    36         public TreeRake<K, V> getParent() { 
     36        public RSTreeRake<K, V> getParent() { 
    3737                return fParent; 
    3838        } 
    … …  
    4646        } 
    4747 
    48         public abstract TreeSlot<K, V> findFirstSlot(); 
     48        public abstract RSTreeSlot<K, V> findFirstSlot(); 
    4949 
    50         public abstract TreeSlot<K, V> findLastSlot(); 
     50        public abstract RSTreeSlot<K, V> findLastSlot(); 
    5151 
    52         public abstract TreeSlot<K, V> findSlot(Object pKey); 
     52        public abstract RSTreeSlot<K, V> findSlot(Object pKey); 
    5353 
    54         public abstract int getDepthRake(); 
    55  
    56         public void setParent(TreeRake<K, V> pParent, int pOffsetInParent) { 
     54        public void setParent(RSTreeRake<K, V> pParent, int pOffsetInParent) { 
    5755                fParent = pParent; 
    5856                fOffsetInParent = pOffsetInParent; 
    … …  
    6866        } 
    6967 
    70         public int adoptEntriesFromLeft(TreeNode<K, V> pLeftNode, float pTargetFillRate) { 
     68        public int adoptEntriesFromLeft(RSTreeNode<K, V> pLeftNode, float pTargetFillRate) { 
    7169                ITreeNodeProvider<K, V> vLeftNodeProvider = pLeftNode.getProvider(); 
    7270                int vMoved = fProvider.adoptEntriesFromLeft(vLeftNodeProvider, pTargetFillRate); 
    … …  
    7876        } 
    7977 
    80         public int adoptEntriesFromRight(TreeNode<K, V> pRightNode, float pTargetFillRate) { 
     78        public int adoptEntriesFromRight(RSTreeNode<K, V> pRightNode, float pTargetFillRate) { 
    8179                ITreeNodeProvider<K, V> vRightSlotProvider = pRightNode.getProvider(); 
    8280                int vOldSize = getProvider().getSize(); 
    … …  
    8482                if (vMoved > 0) { 
    8583                        //Some entries have been moved. 
    86                         TreeRake<K, V> vParent = pRightNode.getParent(); 
     84                        RSTreeRake<K, V> vParent = pRightNode.getParent(); 
    8785                        if (vParent != null) vParent.updateKey(pRightNode.getOffsetInParent(), vRightSlotProvider.getKey(0)); 
    8886                        if (vOldSize == 0 && fParent != null) fParent.updateKey(fOffsetInParent, getProvider().getKey(0)); 
    … …  
    9189        } 
    9290 
    93         public boolean adoptAllEntriesFromLeft(TreeNode<K, V> pLeftNodeToKill) { 
     91        public boolean adoptAllEntriesFromLeft(RSTreeNode<K, V> pLeftNodeToKill) { 
    9492                if (fProvider.adoptAllEntriesFromLeft(pLeftNodeToKill.getProvider())) { 
    9593                        if (fParent != null) fParent.updateKey(fOffsetInParent, getKey(0)); 
    … …  
    9997        } 
    10098 
    101         public boolean adoptAllEntriesFromRight(TreeNode<K, V> pRightNodeToKill) { 
     99        public boolean adoptAllEntriesFromRight(RSTreeNode<K, V> pRightNodeToKill) { 
    102100                if (fProvider.adoptAllEntriesFromRight(pRightNodeToKill.getProvider())) { 
    103101                        int vOldSize = getProvider().getSize(); 
    … …  
    108106        } 
    109107 
     108        /** 
     109         *  
     110         */ 
     111        public abstract int countNodesInMemory(); 
     112 
     113        /** 
     114         *  
     115         */ 
     116        public abstract IRSTreeNodeVisitor.Result accept(IRSTreeNodeVisitor pVisitor, boolean pVisitOnlyInMemoryNodes); 
     117 
    110118} 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/impl/RSTreeRake.java

    r19678 r19680  
    22 
    33import eu.scenari.commons.util.lang.ScException; 
     4import eu.scenari.orient.tree.impl.IRSTreeNodeVisitor.Result; 
    45import eu.scenari.orient.tree.provider.ITreeNodeProvider; 
    56import eu.scenari.orient.tree.provider.ITreeRakeProvider; 
    67import eu.scenari.orient.tree.provider.ITreeSlotProvider; 
    78 
    8 public class TreeRake<K, V> extends TreeNode<K, V> { 
    9  
    10         protected TreeNode<K, V>[] fChildren; 
     9public class RSTreeRake<K, V> extends RSTreeNode<K, V> { 
     10 
     11        protected RSTreeNode<K, V>[] fChildren; 
    1112 
    1213        /** Constructor for root tree node. */ 
    13         public TreeRake(Tree<K, V> pTree, ITreeRakeProvider<K, V> pProvider) { 
     14        public RSTreeRake(RSTree<K, V> pTree, ITreeRakeProvider<K, V> pProvider) { 
    1415                super(pTree, pProvider); 
    1516                setup(); 
    … …  
    1718 
    1819        /** Constructor for root tree node in creation context. */ 
    19         public TreeRake(Tree<K, V> pTree, ITreeRakeProvider<K, V> pProvider, TreeNode<K, V> pFirstChild) { 
     20        public RSTreeRake(RSTree<K, V> pTree, ITreeRakeProvider<K, V> pProvider, RSTreeNode<K, V> pFirstChild) { 
    2021                super(pTree, pProvider); 
    2122                setup(); 
    … …  
    2425        } 
    2526 
    26         public TreeRake(TreeRake<K, V> pParent, int pOffset, ITreeRakeProvider<K, V> pProvider) { 
     27        public RSTreeRake(RSTreeRake<K, V> pParent, int pOffset, ITreeRakeProvider<K, V> pProvider) { 
    2728                super(pParent, pOffset, pProvider); 
    2829                setup(); 
    … …  
    3031 
    3132        protected void setup() { 
    32                 fChildren = new TreeNode[Math.max(fTree.fProvider.getDefaultRakeCapacity(), getProvider().getSize())]; 
     33                //note : called only from constructor, no lock here. 
     34                fChildren = new RSTreeNode[Math.max(fTree.fProvider.getDefaultRakeCapacity(), getProvider().getSize())]; 
    3335        } 
    3436 
    … …  
    4648         * @see #getLastNode() 
    4749         */ 
    48         public TreeNode<K, V> getNode(int pOffset) { 
    49                 assert (pOffset < getProvider().getSize()); 
    50                 TreeNode<K, V> vResult = fChildren[pOffset]; 
    51                 if (vResult == null) { 
    52                         ITreeNodeProvider<K, V> vNode = getProvider().loadNode(pOffset); 
    53                         vResult = createChildNode(vNode, pOffset); 
    54                         fChildren[pOffset] = vResult; 
    55                 } 
    56                 return vResult; 
    57         } 
    58  
    59         /** 
    60          * Warning : bounds are not checked. 
    61          * @see #getFirstNode() 
    62          * @see #getLastNode() 
    63          */ 
    64         public TreeNode<K, V> getNodeIfLoaded(int pOffset) { 
    65                 assert (pOffset < getProvider().getSize()); 
    66                 return fChildren[pOffset]; 
    67         } 
    68  
    69         public TreeNode<K, V> getFirstNode() { 
     50        public RSTreeNode<K, V> getNode(int pOffset) { 
     51                if (fTree.isThreadSafe()) { 
     52                        synchronized (this) { 
     53                                assert (pOffset < getProvider().getSize()); 
     54                                RSTreeNode<K, V> vResult = fChildren[pOffset]; 
     55                                if (vResult == null) { 
     56                                        ITreeNodeProvider<K, V> vNode = getProvider().loadNode(pOffset); 
     57                                        vResult = createChildNode(vNode, pOffset); 
     58                                        fChildren[pOffset] = vResult; 
     59                                } 
     60                                return vResult; 
     61                        } 
     62                } else { 
     63                        assert (pOffset < getProvider().getSize()); 
     64                        RSTreeNode<K, V> vResult = fChildren[pOffset]; 
     65                        if (vResult == null) { 
     66                                ITreeNodeProvider<K, V> vNode = getProvider().loadNode(pOffset); 
     67                                vResult = createChildNode(vNode, pOffset); 
     68                                fChildren[pOffset] = vResult; 
     69                        } 
     70                        return vResult; 
     71                } 
     72        } 
     73 
     74        public RSTreeNode<K, V> getFirstNode() { 
    7075                int vSize = getProvider().getSize(); 
    7176                return (vSize > 0) ? getNode(0) : null; 
    7277        } 
    7378 
    74         public TreeNode<K, V> getLastNode() { 
     79        public RSTreeNode<K, V> getLastNode() { 
    7580                int vSize = getProvider().getSize(); 
    7681                return (vSize > 0) ? getNode(vSize - 1) : null; 
    7782        } 
    7883 
    79         public TreeRake<K, V> insertNewRake(int pOffset) { 
     84        public RSTreeRake<K, V> insertNewRake(int pOffset) { 
    8085                int vCurrentSize = getProvider().getSize(); 
    8186                assert (pOffset <= vCurrentSize); 
    … …  
    8388                if (vNewRake == null) return null; 
    8489                ensureSize(vCurrentSize + 1); 
    85                 TreeRake vRake = (TreeRake) createChildNode(vNewRake, pOffset); 
     90                RSTreeRake vRake = (RSTreeRake) createChildNode(vNewRake, pOffset); 
    8691                int vCountToMove = vCurrentSize - pOffset - 1; 
    8792                if (vCountToMove > 0) { 
    8893                        //move 
     94                        //note : write access lock is held on tree, no lock here. 
    8995                        System.arraycopy(fChildren, pOffset, fChildren, pOffset + 1, vCountToMove); 
    9096                } 
    … …  
    9399        } 
    94100 
    95         public TreeSlot<K, V> insertNewSlot(int pOffset) { 
     101        public RSTreeSlot<K, V> insertNewSlot(int pOffset) { 
    96102                int vCurrentSize = getProvider().getSize(); 
    97103                assert (pOffset <= getProvider().getSize()); 
    … …  
    99105                if (vNewSlot == null) return null; 
    100106                ensureSize(vCurrentSize + 1); 
    101                 TreeSlot vNode = (TreeSlot) createChildNode(vNewSlot, pOffset); 
     107                RSTreeSlot vNode = (RSTreeSlot) createChildNode(vNewSlot, pOffset); 
    102108                int vCountToMove = vCurrentSize - pOffset - 1; 
    103109                if (vCountToMove > 0) { 
    104110                        //move 
     111                        //note : write access lock is held on tree, no lock here. 
    105112                        System.arraycopy(fChildren, pOffset, fChildren, pOffset + 1, vCountToMove); 
    106113                } 
    … …  
    109116        } 
    110117 
    111         public int adoptEntriesFromRight(TreeNode<K, V> pRightNode, float pTargetFillRate) { 
     118        public int adoptEntriesFromRight(RSTreeNode<K, V> pRightNode, float pTargetFillRate) { 
    112119                int vMoved = super.adoptEntriesFromRight(pRightNode, pTargetFillRate); 
    113120                if (vMoved > 0) { 
    … …  
    115122                        int vNewSize = getProvider().getSize(); 
    116123                        ensureSize(vNewSize); 
    117                         TreeRake<K, V> vRight = (TreeRake) pRightNode; 
    118                         TreeNode<K, V>[] vRightChildren = vRight.fChildren; 
     124                        RSTreeRake<K, V> vRight = (RSTreeRake) pRightNode; 
     125                        //note : write access lock is held on tree, no lock here. 
     126                        RSTreeNode<K, V>[] vRightChildren = vRight.fChildren; 
    119127                        System.arraycopy(vRightChildren, 0, fChildren, vNewSize - vMoved, vMoved); 
    120128                        System.arraycopy(vRightChildren, vMoved, vRightChildren, 0, vRightChildren.length - vMoved); 
    … …  
    126134        } 
    127135 
    128         public int adoptEntriesFromLeft(TreeNode<K, V> pLeftNode, float pTargetFillRate) { 
     136        public int adoptEntriesFromLeft(RSTreeNode<K, V> pLeftNode, float pTargetFillRate) { 
    129137                int vMoved = super.adoptEntriesFromLeft(pLeftNode, pTargetFillRate); 
    130138                if (vMoved > 0) { 
    … …  
    132140                        int vNewSize = getProvider().getSize(); 
    133141                        ensureSize(vNewSize); 
    134                         TreeRake<K, V> vLeft = (TreeRake) pLeftNode; 
    135                         TreeNode<K, V>[] vLeftChildren = vLeft.fChildren; 
     142                        RSTreeRake<K, V> vLeft = (RSTreeRake) pLeftNode; 
     143                        //note : write access lock is held on tree, no lock here. 
     144                        RSTreeNode<K, V>[] vLeftChildren = vLeft.fChildren; 
    136145                        System.arraycopy(fChildren, 0, fChildren, vMoved, vNewSize - vMoved); 
    137146                        System.arraycopy(vLeftChildren, vLeft.getProvider().getSize(), fChildren, 0, vMoved); 
    … …  
    143152        } 
    144153 
    145         public boolean adoptAllEntriesFromRight(TreeNode<K, V> pRightNodeToKill) { 
     154        public boolean adoptAllEntriesFromRight(RSTreeNode<K, V> pRightNodeToKill) { 
    146155                int vOldSize = getProvider().getSize(); 
    147156                if (super.adoptAllEntriesFromRight(pRightNodeToKill)) { 
    … …  
    149158                        int vNewSize = getProvider().getSize(); 
    150159                        ensureSize(vNewSize); 
    151                         TreeRake<K, V> vRight = (TreeRake) pRightNodeToKill; 
    152                         TreeNode<K, V>[] vRightChildren = vRight.fChildren; 
     160                        RSTreeRake<K, V> vRight = (RSTreeRake) pRightNodeToKill; 
     161                        //note : write access lock is held on tree, no lock here. 
     162                        RSTreeNode<K, V>[] vRightChildren = vRight.fChildren; 
    153163                        System.arraycopy(vRightChildren, 0, fChildren, vOldSize, vNewSize - vOldSize); 
    154164                        for (int i = vOldSize; i < vNewSize; i++) { 
    … …  
    160170        } 
    161171 
    162         public boolean adoptAllEntriesFromLeft(TreeNode<K, V> pLeftNodeToKill) { 
     172        public boolean adoptAllEntriesFromLeft(RSTreeNode<K, V> pLeftNodeToKill) { 
    163173                int vMoved = pLeftNodeToKill.getProvider().getSize(); 
    164174                if (super.adoptAllEntriesFromLeft(pLeftNodeToKill)) { 
    … …  
    166176                        int vNewSize = getProvider().getSize(); 
    167177                        ensureSize(vNewSize); 
    168                         TreeRake<K, V> vLeft = (TreeRake) pLeftNodeToKill; 
    169                         TreeNode<K, V>[] vLeftChildren = vLeft.fChildren; 
     178                        RSTreeRake<K, V> vLeft = (RSTreeRake) pLeftNodeToKill; 
     179                        //note : write access lock is held on tree, no lock here. 
     180                        RSTreeNode<K, V>[] vLeftChildren = vLeft.fChildren; 
    170181                        System.arraycopy(fChildren, 0, fChildren, vMoved, vNewSize - vMoved); 
    171182                        System.arraycopy(vLeftChildren, 0, fChildren, 0, vMoved); 
    … …  
    178189        } 
    179190 
    180         public TreeSlot<K, V> findFirstSlot() { 
     191        public RSTreeSlot<K, V> findFirstSlot() { 
    181192                return getNode(0).findFirstSlot(); 
    182193        } 
    183194 
    184         public TreeSlot<K, V> findLastSlot() { 
     195        public RSTreeSlot<K, V> findLastSlot() { 
    185196                return getNode(fProvider.getSize() - 1).findLastSlot(); 
    186197        } 
    187198 
    188         public TreeSlot<K, V> findSlot(Object pKey) { 
     199        public RSTreeSlot<K, V> findSlot(Object pKey) { 
    189200                int vLast = -1; 
    190201                int vLow = 0; 
    … …  
    207218        } 
    208219 
    209         public TreeSlot<K, V> findRightSlot(int pFrom) { 
     220        public RSTreeSlot<K, V> findRightSlot(int pFrom) { 
    210221                if (pFrom < getProvider().getSize() - 1) return getNode(pFrom + 1).findFirstSlot(); 
    211222                return fParent != null ? fParent.findRightSlot(fOffsetInParent) : null; 
    212223        } 
    213224 
    214         public TreeSlot<K, V> findLeftSlot(int pFrom) { 
     225        public RSTreeSlot<K, V> findLeftSlot(int pFrom) { 
    215226                if (pFrom > 0) return getNode(pFrom - 1).findLastSlot(); 
    216227                return fParent != null ? fParent.findLeftSlot(fOffsetInParent) : null; 
    … …  
    218229 
    219230        /** Find the right next node (slot or rake) with the same level. */ 
    220         public TreeNode<K, V> findRightCousin(int pFrom) { 
     231        public RSTreeNode<K, V> findRightCousin(int pFrom) { 
    221232                if (pFrom < getProvider().getSize() - 1) return getNode(pFrom + 1); 
    222233                if (fParent == null) return null; 
    223                 TreeNode<K, V> vParentCousin = fParent.findRightCousin(fOffsetInParent); 
    224                 return vParentCousin != null && vParentCousin.isRake() ? ((TreeRake) vParentCousin).getFirstNode() : null; 
     234                RSTreeNode<K, V> vParentCousin = fParent.findRightCousin(fOffsetInParent); 
     235                return vParentCousin != null && vParentCousin.isRake() ? ((RSTreeRake) vParentCousin).getFirstNode() : null; 
    225236        } 
    226237 
    227238        /** Find the left previous node (slot or rake) with the same level. */ 
    228         public TreeNode<K, V> findLeftCousin(int pFrom) { 
     239        public RSTreeNode<K, V> findLeftCousin(int pFrom) { 
    229240                if (pFrom > 0) return getNode(pFrom - 1); 
    230241                if (fParent == null) return null; 
    231                 TreeNode<K, V> vParentCousin = fParent.findLeftCousin(fOffsetInParent); 
    232                 return vParentCousin != null && vParentCousin.isRake() ? ((TreeRake) vParentCousin).getLastNode() : null; 
    233         } 
    234  
    235         public int getDepthRake() { 
    236                 return 1 + findAnyLoadedEntry().getDepthRake(); 
    237         } 
    238  
    239         protected TreeNode<K, V> findAnyLoadedEntry() { 
    240                 for (TreeNode<K, V> vEntry : fChildren) { 
    241                         if (vEntry != null) return vEntry; 
    242                 } 
    243                 return getNode(0); 
     242                RSTreeNode<K, V> vParentCousin = fParent.findLeftCousin(fOffsetInParent); 
     243                return vParentCousin != null && vParentCousin.isRake() ? ((RSTreeRake) vParentCousin).getLastNode() : null; 
    244244        } 
    245245 
    … …  
    255255        } 
    256256 
    257         public void removeChildNode(TreeNode pEntry) { 
     257        public void removeChildNode(RSTreeNode pEntry) { 
    258258                assert (pEntry.fParent == this); 
    259259                int vOldSize = fProvider.getSize(); 
    … …  
    265265                        } else { 
    266266                                // We are the root, no more entries, we ref the last empty slot as root. 
    267                                 TreeSlot<K, V> vSlot = pEntry.findFirstSlot(); 
     267                                RSTreeSlot<K, V> vSlot = pEntry.findFirstSlot(); 
    268268                                vSlot.setParent(null, 0); 
    269                                 vSlot.clear(); 
     269                                vSlot.clearChildren(); 
    270270                                fTree.setRoot(vSlot); 
    271271                        } 
    … …  
    274274                        int vOffsetEntry = pEntry.getOffsetInParent(); 
    275275                        assert (vOffsetEntry < vOldSize); 
     276                        //note : write access lock is held on tree, no lock here. 
    276277                        for (int i = vOffsetEntry; i < vOldSize - 1; i++) { 
    277                                 TreeNode<K, V> vNext = fChildren[i + 1]; 
     278                                RSTreeNode<K, V> vNext = fChildren[i + 1]; 
    278279                                fChildren[i] = vNext; 
    279280                                vNext.setParent(this, i); 
    … …  
    290291        } 
    291292 
    292         protected TreeNode<K, V> createChildNode(ITreeNodeProvider<K, V> pNode, int pOffset) { 
     293        public int countNodesInMemory() { 
     294                int vCount = 1; 
     295                synchronized (this) { 
     296                        for (int i = 0; i < fChildren.length; i++) { 
     297                                if (fChildren[i] != null) { 
     298                                        vCount += fChildren[i].countNodesInMemory(); 
     299                                } 
     300                        } 
     301                } 
     302                return vCount; 
     303        } 
     304 
     305        public Result accept(IRSTreeNodeVisitor pVisitor, boolean pVisitOnlyInMemoryNodes) { 
     306                IRSTreeNodeVisitor.Result vResult = pVisitor.visitNode(this); 
     307                if (vResult == Result.gotoNext) { 
     308                        if (pVisitOnlyInMemoryNodes) { 
     309                                synchronized (this) { 
     310                                        for (int i = 0; i < fChildren.length; i++) { 
     311                                                if (fChildren[i] != null) { 
     312                                                        if (fChildren[i].accept(pVisitor, pVisitOnlyInMemoryNodes) == Result.stopVisiting) return Result.stopVisiting; 
     313                                                } 
     314                                        } 
     315                                } 
     316                        } else { 
     317                                for (int i = 0, s = fProvider.getSize(); i < s; i++) { 
     318                                        if (getNode(i).accept(pVisitor, pVisitOnlyInMemoryNodes) == Result.stopVisiting) return Result.stopVisiting; 
     319                                        if (fTree.isThreadSafe() && ((RSTreeConcurrent) fTree).fNeedGC) { 
     320                                                ((RSTreeConcurrent) fTree).freeMemory(); 
     321                                        } 
     322                                } 
     323                        } 
     324                } 
     325                return vResult.returnResult(); 
     326        } 
     327 
     328        public void removeChildFromMemory(RSTreeNode<K, V> pNode) { 
     329                synchronized (this) { 
     330                        fChildren[pNode.fOffsetInParent] = null; 
     331                        pNode.setParent(null, 0); 
     332                } 
     333        } 
     334 
     335        protected RSTreeNode<K, V> createChildNode(ITreeNodeProvider<K, V> pNode, int pOffset) { 
    293336                if (pNode.isRake()) { 
    294                         return new TreeRake<K, V>(this, pOffset, (ITreeRakeProvider<K, V>) pNode); 
     337                        return new RSTreeRake<K, V>(this, pOffset, (ITreeRakeProvider<K, V>) pNode); 
    295338                } else { 
    296                         return new TreeSlot<K, V>(this, pOffset, (ITreeSlotProvider<K, V>) pNode); 
     339                        return new RSTreeSlot<K, V>(this, pOffset, (ITreeSlotProvider<K, V>) pNode); 
    297340                } 
    298341        } 
    299342 
    300343        protected void ensureSize(int pTargetSize) { 
     344                //note : write access lock is held on tree, no lock here. 
    301345                if (fChildren.length < pTargetSize) { 
    302                         TreeNode<K, V>[] vNew = new TreeNode[pTargetSize + 10]; 
     346                        RSTreeNode<K, V>[] vNew = new RSTreeNode[pTargetSize + 10]; 
    303347                        System.arraycopy(fChildren, 0, vNew, 0, fChildren.length); 
    304348                        fChildren = vNew; 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/impl/RSTreeSlot.java

    r19678 r19680  
    11package eu.scenari.orient.tree.impl; 
    22 
     3import eu.scenari.orient.tree.impl.IRSTreeNodeVisitor.Result; 
    34import eu.scenari.orient.tree.provider.ITreeSlotProvider; 
    45 
    5 public class TreeSlot<K, V> extends TreeNode<K, V> { 
     6public class RSTreeSlot<K, V> extends RSTreeNode<K, V> { 
    67 
    7         public TreeSlot(Tree<K, V> pTree, ITreeSlotProvider<K, V> pProvider) { 
     8        public RSTreeSlot(RSTree<K, V> pTree, ITreeSlotProvider<K, V> pProvider) { 
    89                super(pTree, pProvider); 
    910        } 
    1011 
    11         public TreeSlot(TreeRake<K, V> pParent, int pOffset, ITreeSlotProvider<K, V> pProvider) { 
     12        public RSTreeSlot(RSTreeRake<K, V> pParent, int pOffset, ITreeSlotProvider<K, V> pProvider) { 
    1213                super(pParent, pOffset, pProvider); 
    1314        } 
    … …  
    6667        } 
    6768 
    68         public TreeSlot<K, V> findFirstSlot() { 
     69        public RSTreeSlot<K, V> findFirstSlot() { 
    6970                return this; 
    7071        } 
    7172 
    72         public TreeSlot<K, V> findLastSlot() { 
     73        public RSTreeSlot<K, V> findLastSlot() { 
    7374                return this; 
    7475        } 
    7576 
    76         public TreeSlot<K, V> findSlot(Object pKey) { 
     77        public RSTreeSlot<K, V> findSlot(Object pKey) { 
    7778                return this; 
    7879        } 
    7980 
    80         public TreeSlot<K, V> findRightSlot() { 
     81        public RSTreeSlot<K, V> findRightSlot() { 
    8182                if (fParent == null) return null; 
    8283                return fParent.findRightSlot(fOffsetInParent); 
    8384        } 
    8485 
    85         public TreeSlot<K, V> findLeftSlot() { 
     86        public RSTreeSlot<K, V> findLeftSlot() { 
    8687                if (fParent == null) return null; 
    8788                return fParent.findLeftSlot(fOffsetInParent); 
    88         } 
    89  
    90         public int getDepthRake() { 
    91                 return 0; 
    9289        } 
    9390 
    … …  
    107104 
    108105        /** Called when this is last slot and setted on tree root. */ 
    109         public void clear() { 
     106        public void clearChildren() { 
    110107                for (int i = getSize() - 1; i >= 0; i--) { 
    111108                        fProvider.remove(i); 
    … …  
    135132        } 
    136133 
     134        public int countNodesInMemory() { 
     135                return 1; 
     136        } 
     137 
     138        public Result accept(IRSTreeNodeVisitor pVisitor, boolean pVisitOnlyInMemoryNodes) { 
     139                return pVisitor.visitNode(this).returnResult(); 
     140        } 
    137141} 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/provider/ITreeNodeProvider.java

    r19672 r19680  
    66        public boolean isRake(); 
    77 
    8         /** Count entries. */ 
     8        /** 
     9         * Count entries in this node. 
     10         *  
     11         * <p>Warning : this method <b>must</b> be aware of {@link ITreeProvider#setConcurrReadAccess(boolean)}  
     12         * parameter.</p> 
     13         **/ 
    914        public int getSize(); 
    1015 
    11         /** */ 
     16        /** 
     17         * Return a key. 
     18         *  
     19         * <p>Warning : this method <b>must</b> be aware of {@link ITreeProvider#setConcurrReadAccess(boolean)}  
     20         * parameter.</p> 
     21         */ 
    1222        public K getKey(int pOffset); 
     23 
     24        /**  
     25         * Fill rate : 0 the node is empty, 1, the node is full. 
     26         *  
     27         */ 
     28        public float getFillRate(); 
    1329 
    1430        /** 
    … …  
    1834         */ 
    1935        public void remove(int pOffset); 
    20  
    21         /**  
    22          * Fill rate : 0 the node is empty, 1, the node is full. 
    23          */ 
    24         public float getFillRate(); 
    2536 
    2637        /** 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/provider/ITreeProvider.java

    r19678 r19680  
    55        public static int SIZE_UNKNOWN = -1; 
    66 
     7        /** 
     8         * This method is called on setup, before any other method. 
     9         * If set to <code>true</code>, all read methods can be called by multiple threads. 
     10         * Implementations <b>must</b> take care of this if they used lazyloading datas. 
     11         */ 
     12        public void setConcurrReadAccess(boolean pMultithreadContext); 
     13 
    714        /**  
    815         * Tree size (number of entries).  
    916         * A provider can not store the current size and then return -1. 
    1017         *  
     18         * <p>Warning : this method <b>must</b> be aware of {@link #setConcurrReadAccess(boolean)} parameter.</p> 
     19         *  
    1120         * @return tree size or {@link #SIZE_UNKNOWN} if size unknown. 
    1221         */ 
    1322        public int getSize(); 
     23 
     24        /**  
     25         * Load root node. 
     26         * Should always return a new and fresh node instance. 
     27         *  
     28         * <p>Warning : this method <b>must</b> be aware of {@link #setConcurrReadAccess(boolean)} parameter.</p> 
     29         **/ 
     30        public ITreeNodeProvider<K, V> loadRoot(); 
    1431 
    1532        /** 
    … …  
    2542         */ 
    2643        public void setSize(int pComputedSize); 
    27  
    28         /** Load root node. */ 
    29         public ITreeNodeProvider<K, V> loadRoot(); 
    3044 
    3145        /** Update root node. */ 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/provider/ITreeRakeProvider.java

    r19672 r19680  
    33public interface ITreeRakeProvider<K, V> extends ITreeNodeProvider<K, V> { 
    44 
     5        /** 
     6         * Load a child node. 
     7         * Should always return a new and fresh node instance. 
     8         *  
     9         * <p>Warning : this method <b>must</b> be aware of {@link ITreeProvider#setConcurrReadAccess(boolean)}  
     10         * parameter.</p> 
     11         */ 
    512        public ITreeNodeProvider<K, V> loadNode(int pOffset); 
    613 

  • trunk/Jav_Orient/src/eu/scenari/orient/tree/provider/ITreeSlotProvider.java

    r19672 r19680  
    55        /** 
    66         * Get a value. 
     7         *  
     8         * <p>Warning : this method <b>must</b> be aware of {@link ITreeProvider#setConcurrReadAccess(boolean)}  
     9         * parameter.</p> 
    710         *  
    811         * @return <code>null</code> for a Set implementation. 

  • trunk/Jav_Orient/test/eu/scenari/orient/tree/TreeBasicTest.java

    r19678 r19680  
    4949 
    5050import eu.scenari.orient.recordstruct.IRecordStruct; 
    51 import eu.scenari.orient.recordstruct.lib.tree.StructTree; 
    52 import eu.scenari.orient.recordstruct.lib.tree.TreeStorageConfig; 
    5351import eu.scenari.orient.recordstruct.lib.tree.ValueTree; 
    54 import eu.scenari.orient.recordstruct.struct.ExtendedStructId; 
    55 import eu.scenari.orient.recordstruct.types.TypesBase; 
    5652import eu.scenari.orient.test.TestDbAbstract; 
    57 import eu.scenari.orient.tree.impl.IBalancingLayout; 
    5853 
    5954public class TreeBasicTest extends TestDbAbstract { 
    6055 
    6156        public static int MAP_SIZE = 2000; 
    62  
    63         public static boolean STORE_SIZE = false; 
    64  
    65         public static final TreeStorageConfig TREECONFIG = new TreeStorageConfig().setKeysStruct(TypesBase.LIST_LONG).setValuesStruct(TypesBase.LIST_LONG).setSizeStored(STORE_SIZE).setBalancingLayout(IBalancingLayout.DEFAULT_BALANCED_INCREMENTAL_INSERT) 
    66                         .setRakeCapacity(32).setSlotCapacity(32); 
    67  
    68         public static final StructTree TREE_LONG_LONG = new StructTree(new ExtendedStructId(1, 1), "trreeLongLong").setTreeConfig(TREECONFIG); 
    6957 
    7058        protected FactorySequentialLong fFactorySeqLong = new FactorySequentialLong(); 
    … …  
    7967                fDatabase = fDbDriver.acquireDatabase(); 
    8068                IRecordStruct<ValueTree<Long, Long>> vRecord = fDatabase.newInstance(); 
    81                 vRecord.setValue((ValueTree) TREE_LONG_LONG.toValue(null, vRecord)); 
     69                vRecord.setValue((ValueTree) TypesTreeTests.TREE_LONG_LONG.toValue(null, vRecord)); 
    8270                vRecord.save(); 
    8371                ORID vId = vRecord.getIdentity(); 
    … …  
    131119 
    132120        protected void checkSize(Map<Long, Long> pTree, int pSize) { 
    133                 if (STORE_SIZE) { 
     121                if (TypesTreeTests.STORE_SIZE) { 
    134122                        Assert.assertEquals(pTree.size(), pSize); 
    135123                } 
Note: See TracChangeset for help on using the changeset viewer.