Changeset 19672


Ignore:
Timestamp:
02/07/12 21:22:20 (4 months ago)
Author:
sys
Message:

Tree en cours...

Location:
trunk/Jav_Orient
Files:
25 added
24 edited

Legend:

Unmodified
Added
Removed

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

    r17752 r19672  
    103103 
    104104        /** 
     105         * If {@link #getPredefinedLentgh()} is fixed (positive value), return the full serialized length 
     106         * including struct identifier overhead.  
     107         */ 
     108        public int getFullSerializedLentgh(); 
     109 
     110        /** 
    105111         * Generic method for instanciate struct's value.  
    106112         *  

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

    r17961 r19672  
    3939package eu.scenari.orient.recordstruct; 
    4040 
    41  
    4241public interface IValueSubRecord extends IValueOwner { 
    4342 
    4443        /** 
     44         * Méthode appelée par le subRecord. 
    4545         * Informe le IValueSubRecord que son subRecord est dirty. 
    4646         */ 
    4747        public void onSubRecordDirty(); 
    4848 
     49        /** 
     50         * Méthode appelée par le subRecord pour informer que l'id  
     51         * du subRecord a changé (à la création du record). 
     52         */ 
     53        public void onSubrecordRidChanged(IRecordStruct<IValue<?>> pRecord); 
     54 
     55        /** 
     56         * Mathéode appelé par le record détenant ce IValueSubRecord pour 
     57         * forcer l'enregistrement des subRecords. 
     58         */ 
    4959        public void saveSubRecord(); 
    50  
    51         public void onSubrecordRidChanged(IRecordStruct<IValue<?>> pRecord); 
    5260} 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/impl/IStructWriter.java

    r18481 r19672  
    4141import eu.scenari.orient.recordstruct.IStruct; 
    4242import eu.scenari.orient.recordstruct.IValue; 
    43 import eu.scenari.orient.recordstruct.IValueLazyLoading; 
    4443 
    4544public interface IStructWriter { 
    … …  
    6867         * Push already serialized value. 
    6968         */ 
    70         public void addAsValue(IValueLazyLoading<?> pValue, final byte[] pBuffer, final int pOffset, final int pLength); 
     69        public void addAsValue(IValue<?> pValue, final byte[] pBuffer, final int pOffset, final int pLength); 
    7170 
    7271        /** 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/impl/StructWriter.java

    r19091 r19672  
    4848import eu.scenari.orient.recordstruct.IStruct; 
    4949import eu.scenari.orient.recordstruct.IValue; 
    50 import eu.scenari.orient.recordstruct.IValueLazyLoading; 
    5150import eu.scenari.orient.recordstruct.lib.primitive.ValueNull; 
    5251import eu.scenari.orient.recordstruct.struct.ExtendedStructId; 
    … …  
    109108                ExtendedStructId extendedStructId = pStruct.getExtendedStructId(); 
    110109                if (extendedStructId != null) { 
    111                         int len = extendedStructId.getLength(); 
     110                        int len = extendedStructId.getExtendedIdLength(); 
    112111                        assureSpaceFor(len); 
    113112                        for (int i = 0; i < len; i++) { 
    … …  
    163162         * Push already serialized value. 
    164163         */ 
    165         public void addAsValue(IValueLazyLoading<?> pValue, final byte[] pBuffer, final int pOffset, final int pLength) { 
     164        public void addAsValue(IValue<?> pValue, final byte[] pBuffer, final int pOffset, final int pLength) { 
    166165                startValue(pValue.getStruct(), pLength); 
    167166                write(pBuffer, pOffset, pLength); 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/impl/StructWriterXml.java

    r18986 r19672  
    172172        } 
    173173 
    174         public void addAsValue(IValueLazyLoading<?> pValue, byte[] pBuffer, int pOffset, int pLength) { 
     174        public void addAsValue(IValue<?> pValue, byte[] pBuffer, int pOffset, int pLength) { 
    175175                try { 
    176176                        fValueStarted = false; 
    177                         pValue.unmarshall(); 
     177                        if (pValue instanceof IValueLazyLoading) ((IValueLazyLoading) pValue).unmarshall(); 
    178178                        pValue.writeValue(this); 
    179179                } catch (Exception e) { 

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

    r17887 r19672  
    4242 
    4343import eu.scenari.orient.recordstruct.IStruct; 
     44import eu.scenari.orient.recordstruct.IStructList; 
     45import eu.scenari.orient.recordstruct.IValue.CopyObjective; 
    4446import eu.scenari.orient.recordstruct.IValueOwner; 
    45 import eu.scenari.orient.recordstruct.IValue.CopyObjective; 
    4647import eu.scenari.orient.recordstruct.impl.StructReader; 
    4748import eu.scenari.orient.recordstruct.struct.ConversionException; 
    4849import eu.scenari.orient.recordstruct.struct.StructAbstract; 
    4950 
    50 public class StructList extends StructAbstract<ValueList> { 
     51public class StructList extends StructAbstract<ValueList> implements IStructList<ValueList> { 
    5152 
    5253        public StructList(int pCoreStructId) { 
    … …  
    6162        } 
    6263 
     64        public ValueList newValue(int pDefaultCapacity, IValueOwner pOwner) { 
     65                return new ValueList(pDefaultCapacity, pOwner); 
     66        } 
     67 
    6368        public ValueList readValue(StructReader pReader, int pLen, IValueOwner pOwner) { 
    6469                return new ValueList(pReader, pReader.getPosition(), pLen, pOwner); 

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

    r19336 r19672  
    5050import eu.scenari.orient.recordstruct.IStruct; 
    5151import eu.scenari.orient.recordstruct.IValue; 
     52import eu.scenari.orient.recordstruct.IValueList; 
    5253import eu.scenari.orient.recordstruct.IValueOwner; 
    5354import eu.scenari.orient.recordstruct.IValueVisitor; 
    … …  
    5960import eu.scenari.orient.recordstruct.value.ValueCollectionAbstract; 
    6061 
    61 public class ValueList<E extends IValue<?>> extends ValueCollectionAbstract<List<E>, E> implements List<E> { 
     62public class ValueList<E extends IValue<?>> extends ValueCollectionAbstract<List<E>, E> implements IValueList<E> { 
    6263 
    6364        protected static final boolean[] EMPTY_BOOLARRAY = new boolean[0]; 
    … …  
    7374        } 
    7475 
     76        public ValueList(int pCapacity, IValueOwner pOwner) { 
     77                super(pOwner); 
     78                createUnderlying(pCapacity); 
     79        } 
     80 
    7581        public ValueList(List<?> pValue, IValueOwner pOwner) { 
    7682                super(pOwner); 
    77                 createUnderlying(); 
     83                createUnderlying(pValue.size() + 10); 
    7884                for (Object vItem : pValue) { 
    7985                        fPojo.add((E) StructProvider.findStruct(vItem).toValue(vItem, this)); 
    … …  
    96102                // XXX append or replace ? 
    97103                for (E vValue : vFrom.getUnderlying()) { 
    98                         this.add((E) vValue.copy(this, pObjective)); 
     104                        add((E) vValue.copy(this, pObjective)); 
    99105                } 
    100106                return (RET) this; 
    … …  
    246252        } 
    247253 
    248         public Object[] toArray() { 
    249                 return getUnderlying().toArray(); 
    250         } 
    251  
    252         public <T> T[] toArray(T[] pA) { 
    253                 return getUnderlying().toArray(pA); 
    254         } 
    255  
    256254        @Override 
    257255        public void onPersist(PersistStep pStep, IRecordStruct<?> pRecord, boolean pRemovedValue) { 
    … …  
    323321        } 
    324322 
     323        protected void createUnderlying(int pCapacity) { 
     324                fPojo = new ArrayList<E>(pCapacity); 
     325        } 
     326 
    325327        protected void startRecording() { 
    326328                fRemovedItems = null; 

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

    r19348 r19672  
    118118        } 
    119119 
    120         public Object[] toArray() { 
    121                 return getUnderlying().toArray(); 
    122         } 
    123  
    124         public <T> T[] toArray(T[] pA) { 
    125                 return getUnderlying().toArray(pA); 
    126         } 
    127  
    128120        public <RET extends IValue<Set<E>>> RET copyFrom(IValue<?> pFromValue, CopyObjective pObjective) { 
    129121                ValueSet<E> vFrom = (ValueSet) pFromValue; 

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

    r19337 r19672  
    146146        } 
    147147 
    148         public Object[] toArray() { 
    149                 return getUnderlying().toArray(); 
    150         } 
    151  
    152         public <T> T[] toArray(T[] pA) { 
    153                 return getUnderlying().toArray(pA); 
    154         } 
    155  
    156148        public <RET extends IValue<SortedSet<E>>> RET copyFrom(IValue<?> pFromValue, CopyObjective pObjective) { 
    157149                ValueSortedSet<E> vFrom = (ValueSortedSet) pFromValue; 

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

    r19333 r19672  
    103103        @Override 
    104104        public void onPersist(PersistStep pStep, IRecordStruct<?> pRecord, boolean pRemovedValue) { 
    105                 //getStruct().onTrigger(this, pType, pRecord, pRemovedValue); 
    106105                if (pStep.isAfterSave()) { 
    107106                        unsetDirty(); 
    … …  
    115114                        } 
    116115                } 
    117                 return; 
    118116        } 
    119117 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/struct/ExtendedStructId.java

    r17873 r19672  
    111111        } 
    112112 
    113         public int getLength() { 
     113        public int getExtendedIdLength() { 
    114114                return fLenght; 
    115115        } 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/struct/StructAbstract.java

    r18113 r19672  
    6666        private ExtendedStructId fExtendedStructId; 
    6767 
    68         protected int fPredfinedLength; 
     68        protected int fPredefinedLength; 
    6969 
    7070        /** 
    … …  
    9393 
    9494                public int getExtendedIdLength() { 
    95                         return fPredfinedLength; 
     95                        return fPredefinedLength; 
    9696                } 
    9797 
    … …  
    162162                assert (StructProvider.STRUCT_CORE_INDEX[pCoreStructId] == null); 
    163163                StructProvider.STRUCT_CORE_INDEX[pCoreStructId] = this; 
    164                 fPredfinedLength = pPredefinedLength; 
     164                fPredefinedLength = pPredefinedLength; 
    165165                fExtendedStructId = null; 
    166166                fName = getDefaultStructName(pName); 
    … …  
    168168 
    169169        protected StructAbstract(ExtendedStructId pExtendedId, int pPredefinedLength, String pName) { 
    170                 CoreExtStruct vCoreStruct = lookForCoreStruct(pExtendedId.getLength(), pPredefinedLength); 
     170                CoreExtStruct vCoreStruct = lookForCoreStruct(pExtendedId.getExtendedIdLength(), pPredefinedLength); 
    171171                fMainStructId = vCoreStruct.getCoreStructId(); 
    172                 fPredfinedLength = pPredefinedLength; 
     172                fPredefinedLength = pPredefinedLength; 
    173173                fExtendedStructId = pExtendedId; 
    174174                vCoreStruct.registerExtendedStruct(this); 
    … …  
    189189 
    190190        public int getPredefinedLentgh() { 
    191                 return fPredfinedLength; 
     191                return fPredefinedLength; 
     192        } 
     193 
     194        public int getFullSerializedLentgh() { 
     195                if (fPredefinedLength < 0) return fPredefinedLength; 
     196                int vOverhead = fExtendedStructId != null ? 1 + fExtendedStructId.getExtendedIdLength() : 1; 
     197                return vOverhead + fPredefinedLength; 
    192198        } 
    193199 

  • trunk/Jav_Orient/src/eu/scenari/orient/recordstruct/types/TypesBase.java

    r19581 r19672  
    4242import eu.scenari.orient.recordstruct.lib.base.StructDictionary; 
    4343import eu.scenari.orient.recordstruct.lib.base.StructList; 
     44import eu.scenari.orient.recordstruct.lib.base.StructListLong; 
     45import eu.scenari.orient.recordstruct.lib.base.StructListRID; 
    4446import eu.scenari.orient.recordstruct.lib.base.StructMap; 
    4547import eu.scenari.orient.recordstruct.lib.base.StructRID; 
    … …  
    5658import eu.scenari.orient.recordstruct.lib.bigable.StructBigableString; 
    5759import eu.scenari.orient.recordstruct.lib.link.ValueLinkTiny; 
     60import eu.scenari.orient.recordstruct.lib.tree.StructTreeRake; 
     61import eu.scenari.orient.recordstruct.lib.tree.StructTreeSlotKV; 
    5862import eu.scenari.orient.recordstruct.link.IStructLink; 
    5963import eu.scenari.orient.recordstruct.link.StructLink; 
    … …  
    6973        public static final StructSubRecord SUBRECORD = new StructSubRecord(129); 
    7074 
     75        public static final StructListRID LIST_RID = new StructListRID(130); 
     76 
    7177        public static final IStructLink<ValueLinkTiny> LINK_TINY = new StructLink(131, ValueLinkTiny.class); 
    7278 
    7379        public static final IStructLink<ValueLinkTiny> LINK_TINY_LINKEDSLAVE = new StructLink(132, ValueLinkTiny.class).setLinkedIsSlave(true); 
     80 
     81        //**** Tree struct... 
     82        public static final StructTreeRake TREE_RAKE = new StructTreeRake(157); 
     83 
     84        public static final StructTreeSlotKV TREE_SLOT_KV = new StructTreeSlotKV(158); 
    7485 
    7586        //**** Bigable struct... 
    … …  
    90101        public static final StructBlob BLOB = new StructBlob(170); 
    91102 
    92         //**** List, set , map.... 
     103        //**** List, set , map, dictionary de IValue.... 
    93104 
    94105        public static final StructList LIST = new StructList(180); 
    … …  
    105116 
    106117        public static final StructSortedSet SORTED_SET = new StructSortedSet(186); 
     118 
     119        //**** List de pojo .... 
     120 
     121        public static final StructListLong LIST_LONG = new StructListLong(195); 
     122 
    107123} 

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

    r19333 r19672  
    115115        } 
    116116 
     117        public Object[] toArray() { 
     118                return getUnderlying().toArray(); 
     119        } 
     120 
     121        public <T> T[] toArray(T[] pA) { 
     122                return getUnderlying().toArray(pA); 
     123        } 
     124 
    117125        /** 
    118126         *  

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

    r19310 r19672  
    11package eu.scenari.orient.tree.impl; 
    22 
    3 import eu.scenari.commons.util.lang.ScException; 
     3import eu.scenari.orient.tree.provider.ITreeRakeProvider; 
    44import eu.scenari.orient.tree.provider.ITreeSlotProvider; 
    55 
    66public class BalancedLayout implements IBalancingLayout { 
    77 
    8         /** Accept to absorb entries from sibling if current fill rate is less than <code>fFillingThreshold</code>. */ 
     8        /**  
     9         * Accept to absorb entries from sibling if current fill rate is less than <code>fFillingThreshold</code>. 
     10         * If 0.0, entries are never moved between slots or rakes for finding spaces,  
     11         * but only when new rakes and slots are inserted : useful when keys are mainly incremental values (ID, timestamp, ...). 
     12         **/ 
    913        protected float fFillingThreshold = 0.5f; 
    1014 
    … …  
    1418        /**  
    1519         * Target fillRate on the rightNode when a node is splitted.  
    16          * If Keys are incremental ID or Timestamp, it would better to set 0.1. 
     20         * If keys are incremental values (ID, timestamp, ...), it would better to set 0.1. 
    1721         */ 
    1822        protected float fTargetFillRateForNewRightNode = 0.5f; 
    1923 
    20         protected int fComputedSizeThresholdToOptimize = -1; 
    21  
     24        public BalancedLayout() { 
     25                super(); 
     26        } 
     27 
     28        public BalancedLayout(float pFillingThreshold, float pOptimizeThreshold, float pTargetFillRateForNewRightNode) { 
     29                super(); 
     30                fFillingThreshold = pFillingThreshold; 
     31                fOptimizeThreshold = pOptimizeThreshold; 
     32                fTargetFillRateForNewRightNode = pTargetFillRateForNewRightNode; 
     33        } 
     34 
     35        /** 
     36         * @param pOffset replace position (if>=0) or insert position if negative value. 
     37         */ 
    2238        public <K, V> void addSpaceAndPut(TreeSlot<K, V> pSlot, int pOffset, K pKey, V pValue) { 
    2339                Tree<K, V> vTree = pSlot.fTree; 
    … …  
    2541                ITreeSlotProvider<K, V> vSlotProvider = vSlot.getProvider(); 
    2642                int vCurrentOffset = pOffset; 
    27                 //First step : try to move entries in right slot. 
    2843                if (fFillingThreshold > 0) { 
    29                         TreeSlot<K, V> vRightSlot = vSlot.findNextSlot(); 
     44                        //First step : try to move entries in right slot. 
     45                        TreeSlot<K, V> vRightSlot = vSlot.findRightSlot(); 
    3046                        if (vRightSlot != null && vRightSlot.getProvider().getFillRate() < fFillingThreshold) { 
    3147                                int vMoved = vRightSlot.adoptEntriesFromLeft(vSlot, (vRightSlot.getProvider().getFillRate() + vSlotProvider.getFillRate()) / 2); 
    3248                                if (vMoved > 0) { 
    33                                         //Some entries have been moved. 
     49                                        //Some entries has moved. 
    3450                                        if (vCurrentOffset >= 0) { 
    3551                                                if (vCurrentOffset >= vSlotProvider.getSize()) { 
    … …  
    3955                                                        vSlot = vRightSlot; 
    4056                                                } 
    41                                                 switch (vSlotProvider.replace(vCurrentOffset, pKey, pValue)) { 
    42                                                 case doneNewlyDirty: 
    43                                                         vTree.markDirty(vSlotProvider); 
    44                                                 case done: 
    45                                                         return; 
    46                                                 case failedNodeFull: 
    47                                                         //goto third step. 
    48                                                 } 
     57                                                if (vSlotProvider.replace(vCurrentOffset, pKey, pValue)) return; 
    4958                                        } else { 
    5059                                                if (-vCurrentOffset - 1 > vSlotProvider.getSize()) { 
    5160                                                        //Must insert in the other slot. 
    52                                                         vCurrentOffset = vCurrentOffset - vSlotProvider.getSize(); 
     61                                                        vCurrentOffset = vCurrentOffset + vSlotProvider.getSize(); 
    5362                                                        vSlotProvider = vRightSlot.getProvider(); 
    5463                                                        vSlot = vRightSlot; 
    5564                                                } 
    56                                                 switch (vSlotProvider.insert(-vCurrentOffset - 1, pKey, pValue)) { 
    57                                                 case doneNewlyDirty: 
    58                                                         vTree.markDirty(vSlotProvider); 
    59                                                 case done: 
    60                                                         return; 
    61                                                 case failedNodeFull: 
    62                                                         //goto third step. 
    63                                                 } 
    64                                         } 
    65                                 } 
    66                         } else { 
    67                                 //Second step : try to move entries in previous slot. 
    68                                 TreeSlot<K, V> vLeftSlot = vSlot.findPreviousSlot(); 
     65                                                if (vSlotProvider.insert(-vCurrentOffset - 1, pKey, pValue)) return; 
     66                                        } 
     67                                } 
     68                        } 
     69                        //Second step : try to move entries in left slot if current slot has not change. 
     70                        if (vSlot == pSlot) { 
     71                                TreeSlot<K, V> vLeftSlot = vSlot.findLeftSlot(); 
    6972                                if (vLeftSlot != null && vLeftSlot.getProvider().getFillRate() < fFillingThreshold) { 
    7073                                        ITreeSlotProvider<K, V> vLeftSlotProvider = vLeftSlot.getProvider(); 
    7174                                        int vMoved = vLeftSlot.adoptEntriesFromRight(vSlot, (vLeftSlot.getProvider().getFillRate() + vSlotProvider.getFillRate()) / 2); 
    7275                                        if (vMoved > 0) { 
    73                                                 //Some entries have been moved. 
     76                                                //Some entries has moved. 
    7477                                                if (vCurrentOffset >= 0) { 
    7578                                                        vCurrentOffset -= vMoved; 
    … …  
    8083                                                                vSlot = vLeftSlot; 
    8184                                                        } 
    82                                                         switch (vSlotProvider.replace(vCurrentOffset, pKey, pValue)) { 
    83                                                         case doneNewlyDirty: 
    84                                                                 vTree.markDirty(vSlotProvider); 
    85                                                         case done: 
    86                                                                 return; 
    87                                                         case failedNodeFull: 
    88                                                                 //goto third step. 
    89                                                         } 
     85                                                        if (vSlotProvider.replace(vCurrentOffset, pKey, pValue)) return; 
    9086                                                } else { 
    9187                                                        vCurrentOffset += vMoved; 
    9288                                                        if (vCurrentOffset >= -1) { 
    9389                                                                //Must insert in the other slot. 
    94                                                                 vCurrentOffset = vCurrentOffset + vLeftSlotProvider.getSize(); 
     90                                                                vCurrentOffset = vCurrentOffset - vLeftSlotProvider.getSize(); 
    9591                                                                vSlotProvider = vLeftSlotProvider; 
    9692                                                                vSlot = vLeftSlot; 
    9793                                                        } 
    98                                                         switch (vSlotProvider.insert(-vCurrentOffset - 1, pKey, pValue)) { 
    99                                                         case doneNewlyDirty: 
    100                                                                 vTree.markDirty(vSlotProvider); 
    101                                                         case done: 
    102                                                                 return; 
    103                                                         case failedNodeFull: 
    104                                                                 //goto third step. 
    105                                                         } 
    106                                                 } 
    107                                         } 
    108                                 } 
    109                         } 
    110                 } 
     94                                                        if (vSlotProvider.insert(-vCurrentOffset - 1, pKey, pValue)) return; 
     95                                                } 
     96                                        } 
     97                                } 
     98                        } 
     99                } 
     100 
    111101                //Third step : need to insert new slot. 
    112102                TreeSlot<K, V> vNewSlot; 
    … …  
    119109                        if (vNewSlot == null) { 
    120110                                //parent is full,  
    121                                 vNewSlot = addSpaceAndInsertNewSlot(vSlot.fParent, vSlot.fOffsetInParent + 1); 
    122                         } 
    123                 } 
     111                                vNewSlot = splitRakeAndInsertNewSlot(vSlot.fParent, vSlot.fOffsetInParent + 1); 
     112                        } 
     113                } 
     114 
     115                //Fourth step : balance slot contents 
    124116                vNewSlot.adoptEntriesFromLeft(vSlot, fTargetFillRateForNewRightNode); 
     117 
     118                //Fifth step : replace or insert K, V 
    125119                if (vCurrentOffset >= 0) { 
    126120                        if (vCurrentOffset >= vSlotProvider.getSize()) { 
    … …  
    130124                                vSlot = vNewSlot; 
    131125                        } 
    132                         switch (vSlotProvider.replace(vCurrentOffset, pKey, pValue)) { 
    133                         case doneNewlyDirty: 
    134                                 vTree.markDirty(vSlotProvider); 
    135                         case done: 
    136                                 return; 
    137                         case failedNodeFull: 
    138                                 //try again 
    139                                 vTree.put(pKey, pValue); 
    140                         } 
     126                        if (vSlotProvider.replace(vCurrentOffset, pKey, pValue)) return; 
     127                        //failed, try again, more spaces will be added. 
     128                        vTree.put(pKey, pValue); 
    141129                } else { 
    142130                        if (-vCurrentOffset - 1 > vSlotProvider.getSize()) { 
    143131                                //Must insert in the other slot. 
    144                                 vCurrentOffset = vCurrentOffset - vSlotProvider.getSize(); 
     132                                vCurrentOffset = vCurrentOffset + vSlotProvider.getSize(); 
    145133                                vSlotProvider = vNewSlot.getProvider(); 
    146134                                vSlot = vNewSlot; 
    147135                        } 
    148                         switch (vSlotProvider.insert(-vCurrentOffset - 1, pKey, pValue)) { 
    149                         case doneNewlyDirty: 
    150                                 vTree.markDirty(vSlotProvider); 
    151                         case done: 
    152                                 return; 
    153                         case failedNodeFull: 
    154                                 //try again 
    155                                 vTree.put(pKey, pValue); 
    156                         } 
     136                        if (vSlotProvider.insert(-vCurrentOffset - 1, pKey, pValue)) return; 
     137                        //failed, try again, more spaces will be added. 
     138                        vTree.put(pKey, pValue); 
    157139                } 
    158140        } 
    … …  
    165147        } 
    166148 
    167         public <K, V> void onTreeSizeReduced(Tree<K, V> pTree) { 
    168                 tryToOptimizeDepth(pTree); 
    169         } 
    170  
    171149        public <K, V> void onNewRoot(TreeNode<K, V> pNode) { 
    172                 fComputedSizeThresholdToOptimize = -1; 
     150 
    173151        } 
    174152 
    … …  
    205183        } 
    206184 
    207         protected <K, V> void tryToOptimizeDepth(Tree<K, V> pTree) { 
    208                 if (fComputedSizeThresholdToOptimize == -1) { 
    209                         int vDepth = getDepthRake(pTree); 
    210                         if (vDepth > 0) { 
    211                                 fComputedSizeThresholdToOptimize = (pTree.fProvider.getDefaultRakeCapacity() ^ vDepth) * pTree.fProvider.getDefaultSlotCapacity(); 
    212                                 fComputedSizeThresholdToOptimize *= fOptimizeThreshold; 
    213                         } else { 
    214                                 fComputedSizeThresholdToOptimize = 0; 
    215                         } 
    216                 } 
    217                 if (fComputedSizeThresholdToOptimize > 0 && pTree.fProvider.getSize() < fComputedSizeThresholdToOptimize) { 
    218                         //TODO try to remove one depth... 
    219                         System.out.println("TODO try to remove one depth..."); 
    220                 } 
    221         } 
    222  
    223185        protected <K, V> int getDepthRake(Tree<K, V> pTree) { 
    224186                return pTree.fRoot.getDepthRake(); 
    225187        } 
    226188 
    227         protected <K, V> TreeRake<K, V> addSpaceAndInsertNewRake(TreeRake<K, V> pRake, int pOffset) { 
    228                 //First step : try to move entries in right rake. 
    229  
    230                 //Second step : try to move entries in left rake. 
    231  
    232                 //Third step : need to insert new rake or slot. 
    233                 //return null; 
    234                 throw new ScException("TODO addSpaceAndInsertNewRake"); 
    235         } 
    236  
    237         protected <K, V> TreeSlot<K, V> addSpaceAndInsertNewSlot(TreeRake<K, V> pParent, int pOffset) { 
    238                 //First step : try to move entries in right rake. 
    239  
    240                 //Second step : try to move entries in left rake. 
    241  
    242                 //Third step : need to insert new rake or slot. 
    243                 //return null; 
    244                 throw new ScException("TODO addSpaceAndInsertNewSlot"); 
     189        protected <K, V> TreeRake<K, V> splitRakeAndInsertNewRake(TreeRake<K, V> pRakeToSplit, int pInsertPoint) { 
     190                Tree<K, V> vTree = pRakeToSplit.fTree; 
     191                TreeRake<K, V> vRake = pRakeToSplit; 
     192                ITreeRakeProvider<K, V> vRakeProvider = vRake.getProvider(); 
     193                int vInsertPoint = pInsertPoint; 
     194                if (fFillingThreshold > 0) { 
     195                        //First step : try to move entries in right cousin rake. 
     196                        TreeNode<K, V> vCousin = vRake.findRightCousin(vInsertPoint); 
     197                        if (vCousin != null && vCousin.isRake() && vCousin.getProvider().getFillRate() < fFillingThreshold) { 
     198                                TreeRake<K, V> vRightRake = (TreeRake) vCousin; 
     199                                int vMoved = vRightRake.adoptEntriesFromLeft(vRake, (vRightRake.getProvider().getFillRate() + vRakeProvider.getFillRate()) / 2); 
     200                                if (vMoved > 0) { 
     201                                        //Some entries has moved. 
     202                                        if (vInsertPoint > vRakeProvider.getSize()) { 
     203                                                //Must insert in the other rake. 
     204                                                vInsertPoint = vInsertPoint - vRakeProvider.getSize(); 
     205                                                vRakeProvider = vRightRake.getProvider(); 
     206                                                vRake = vRightRake; 
     207                                        } 
     208                                        TreeRake<K, V> vNewRake = vRake.insertNewRake(vInsertPoint); 
     209                                        if (vNewRake != null) return vNewRake; 
     210                                } 
     211                        } 
     212                        //Second step : try to move entries in left cousin rake if current rake has not change. 
     213                        if (vRake == pRakeToSplit) { 
     214                                vCousin = vRake.findLeftCousin(vInsertPoint); 
     215                                if (vCousin != null && vCousin.isRake() && vCousin.getProvider().getFillRate() < fFillingThreshold) { 
     216                                        TreeRake<K, V> vLeftRake = (TreeRake) vCousin; 
     217                                        ITreeRakeProvider<K, V> vLeftProvider = vLeftRake.getProvider(); 
     218                                        int vMoved = vLeftRake.adoptEntriesFromRight(vRake, (vLeftProvider.getFillRate() + vRakeProvider.getFillRate()) / 2); 
     219                                        if (vMoved > 0) { 
     220                                                //Some entries has moved. 
     221                                                vInsertPoint -= vMoved; 
     222                                                if (vInsertPoint < 0) { 
     223                                                        //Must insert in the other rake. 
     224                                                        vInsertPoint = vInsertPoint + vLeftProvider.getSize(); 
     225                                                        vRakeProvider = vLeftProvider; 
     226                                                        vRake = vLeftRake; 
     227                                                } 
     228                                                TreeRake<K, V> vNewRake = vRake.insertNewRake(vInsertPoint); 
     229                                                if (vNewRake != null) return vNewRake; 
     230                                        } 
     231                                } 
     232                        } 
     233                } 
     234 
     235                //Third step : need to insert new rake in parent context. 
     236                TreeRake<K, V> vNewRake; 
     237                if (vRake.fParent == null) { 
     238                        vTree.createRakeAsRoot(vRake); 
     239                        TreeRake<K, V> vParent = (TreeRake) vTree.fRoot; 
     240                        vNewRake = vParent.insertNewRake(1); 
     241                } else { 
     242                        vNewRake = vRake.fParent.insertNewRake(vRake.fOffsetInParent + 1); 
     243                        if (vNewRake == null) { 
     244                                //parent is full,  
     245                                vNewRake = splitRakeAndInsertNewRake(vRake.fParent, vRake.fOffsetInParent + 1); 
     246                        } 
     247                } 
     248 
     249                //Fourth step : balance rake contents 
     250                vNewRake.adoptEntriesFromLeft(vRake, fTargetFillRateForNewRightNode); 
     251                if (vInsertPoint >= vRakeProvider.getSize()) { 
     252                        //Must replace in the other rake. 
     253                        vInsertPoint = vInsertPoint - vRakeProvider.getSize(); 
     254                        vRakeProvider = vNewRake.getProvider(); 
     255                        vRake = vNewRake; 
     256                } 
     257 
     258                //Fifth step : insert new rake 
     259                return vRake.insertNewRake(vInsertPoint); 
     260        } 
     261 
     262        protected <K, V> TreeSlot<K, V> splitRakeAndInsertNewSlot(TreeRake<K, V> pRakeToSplit, int pInsertPoint) { 
     263                Tree<K, V> vTree = pRakeToSplit.fTree; 
     264                TreeRake<K, V> vRake = pRakeToSplit; 
     265                ITreeRakeProvider<K, V> vRakeProvider = vRake.getProvider(); 
     266                int vInsertPoint = pInsertPoint; 
     267                if (fFillingThreshold > 0) { 
     268                        //First step : try to move entries in right cousin rake. 
     269                        TreeNode<K, V> vCousin = vRake.findRightCousin(vInsertPoint); 
     270                        if (vCousin != null && vCousin.isRake() && vCousin.getProvider().getFillRate() < fFillingThreshold) { 
     271                                TreeRake<K, V> vRightRake = (TreeRake) vCousin; 
     272                                int vMoved = vRightRake.adoptEntriesFromLeft(vRake, (vRightRake.getProvider().getFillRate() + vRakeProvider.getFillRate()) / 2); 
     273                                if (vMoved > 0) { 
     274                                        //Some entries has moved. 
     275                                        if (vInsertPoint > vRakeProvider.getSize()) { 
     276                                                //Must insert in the other rake. 
     277                                                vInsertPoint = vInsertPoint - vRakeProvider.getSize(); 
     278                                                vRakeProvider = vRightRake.getProvider(); 
     279                                                vRake = vRightRake; 
     280                                        } 
     281                                        TreeSlot<K, V> vNewSlot = vRake.insertNewSlot(vInsertPoint); 
     282                                        if (vNewSlot != null) return vNewSlot; 
     283                                } 
     284                        } 
     285                        //Second step : try to move entries in left cousin rake if current rake has not change. 
     286                        if (vRake == pRakeToSplit) { 
     287                                vCousin = vRake.findLeftCousin(vInsertPoint); 
     288                                if (vCousin != null && vCousin.isRake() && vCousin.getProvider().getFillRate() < fFillingThreshold) { 
     289                                        TreeRake<K, V> vLeftRake = (TreeRake) vCousin; 
     290                                        ITreeRakeProvider<K, V> vLeftProvider = vLeftRake.getProvider(); 
     291                                        int vMoved = vLeftRake.adoptEntriesFromRight(vRake, (vLeftProvider.getFillRate() + vRakeProvider.getFillRate()) / 2); 
     292                                        if (vMoved > 0) { 
     293                                                //Some entries has moved. 
     294                                                vInsertPoint -= vMoved; 
     295                                                if (vInsertPoint < 0) { 
     296                                                        //Must insert in the other rake. 
     297                                                        vInsertPoint = vInsertPoint + vLeftProvider.getSize(); 
     298                                                        vRakeProvider = vLeftProvider; 
     299                                                        vRake = vLeftRake; 
     300                                                } 
     301                                                TreeSlot<K, V> vNewSlot = vRake.insertNewSlot(vInsertPoint); 
     302                                                if (vNewSlot != null) return vNewSlot; 
     303                                        } 
     304                                } 
     305                        } 
     306                } 
     307 
     308                //Third step : need to insert new rake in parent context. 
     309                TreeRake<K, V> vNewRake; 
     310                if (vRake.fParent == null) { 
     311                        vTree.createRakeAsRoot(vRake); 
     312                        TreeRake<K, V> vParent = (TreeRake) vTree.fRoot; 
     313                        vNewRake = vParent.insertNewRake(1); 
     314                } else { 
     315                        vNewRake = vRake.fParent.insertNewRake(vRake.fOffsetInParent + 1); 
     316                        if (vNewRake == null) { 
     317                                //parent is full,  
     318                                vNewRake = splitRakeAndInsertNewRake(vRake.fParent, vRake.fOffsetInParent + 1); 
     319                        } 
     320                } 
     321 
     322                //Fourth step : balance rake contents 
     323                vNewRake.adoptEntriesFromLeft(vRake, fTargetFillRateForNewRightNode); 
     324                if (vInsertPoint >= vRakeProvider.getSize()) { 
     325                        //Must replace in the other rake. 
     326                        vInsertPoint = vInsertPoint - vRakeProvider.getSize(); 
     327                        vRakeProvider = vNewRake.getProvider(); 
     328                        vRake = vNewRake; 
     329                } 
     330 
     331                //Fifth step : insert new slot 
     332                return vRake.insertNewSlot(vInsertPoint); 
    245333        } 
    246334} 

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

    r19310 r19672  
    22 
    33public interface IBalancingLayout { 
     4 
     5        public final IBalancingLayout DEFAULT_BALANCED_RANDOM_INSERT = new BalancedLayout(); 
     6 
     7        public final IBalancingLayout DEFAULT_BALANCED_INCREMENTAL_INSERT = new BalancedLayout(0.0f, 0.2f, 0.1f); 
    48 
    59        /** Call on a put if the target slot is full. */ 
    … …  
    913        public <K, V> void onRemovedEntry(TreeNode<K, V> pNode); 
    1014 
    11         /** Call when the tree size is reduced. */ 
    12         public <K, V> void onTreeSizeReduced(Tree<K, V> pTree); 
    13  
    1415        /** Call when the root is changed. */ 
    1516        public <K, V> void onNewRoot(TreeNode<K, V> pNode); 

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

    r19310 r19672  
    4141import java.util.AbstractMap; 
    4242import java.util.AbstractSet; 
    43 import java.util.ArrayList; 
    4443import java.util.Comparator; 
    4544import java.util.ConcurrentModificationException; 
    4645import java.util.Iterator; 
    47 import java.util.List; 
    4846import java.util.Map; 
    4947import java.util.NoSuchElementException; 
    … …  
    5452import eu.scenari.orient.tree.provider.ITreeRakeProvider; 
    5553import eu.scenari.orient.tree.provider.ITreeSlotProvider; 
    56 import eu.scenari.orient.tree.provider.ITreeNodeProvider.UpdateResult; 
    5754 
    5855public class Tree<K, V> extends AbstractMap<K, V> { 
    … …  
    7168 
    7269        protected EntrySet fEntrySet; 
    73  
    74         protected List<ITreeNodeProvider<K, V>> fDirtyNodes = new ArrayList(); 
    7570 
    7671        protected transient int fModCount; 
    … …  
    9287                protected TreeSlot<K, V> fSlot; 
    9388 
    94                 protected int fOffset; 
     89                protected int fOffset = -1; 
    9590 
    9691                protected int fExpectedModCount; 
    … …  
    10398                public boolean hasNext() { 
    10499                        if (fSlot == null) return false; 
    105                         if (fOffset < fSlot.getSize() - 1) return true; 
    106                         fSlot = fSlot.findNextSlot(); 
     100                        if (++fOffset < fSlot.getSize()) return true; 
    107101                        fOffset = 0; 
    108                         return fSlot != null; 
     102                        do { 
     103                                fSlot = fSlot.findRightSlot(); 
     104                                if (fSlot == null) return false; 
     105                                if (fSlot.getSize() > 0) return true; 
     106                        } while (true); 
    109107                } 
    110108 
    … …  
    212210 
    213211        public int size() { 
    214                 return fProvider.getSize(); 
     212                int vSize = fProvider.getSize(); 
     213                if (vSize >= 0) return vSize; 
     214                //Size unknown, we compute size. 
     215                vSize = 0; 
     216                for (TreeSlot<K, V> vSlot = findFirstSlot(); vSlot != null; vSlot = vSlot.findRightSlot()) { 
     217                        vSize += vSlot.getSize(); 
     218                } 
     219                //We keep it in memory 
     220                fProvider.setSize(vSize); 
     221                return vSize; 
    215222        } 
    216223 
    … …  
    233240                int vCurrentOffset = vSlot.indexOf(pKey); 
    234241                V vOldValue = vCurrentOffset >= 0 ? vSlotProvider.getValue(vCurrentOffset) : null; 
    235                 UpdateResult vResult; 
     242                boolean vResult; 
    236243                if (vCurrentOffset >= 0) { 
    237244                        vResult = vSlotProvider.replace(vCurrentOffset, pKey, pValue); 
    … …  
    239246                        vResult = vSlotProvider.insert(-vCurrentOffset - 1, pKey, pValue); 
    240247                } 
    241                 switch (vResult) { 
    242                 case doneNewlyDirty: 
    243                         markDirty(vSlotProvider); 
    244                 case done: 
    245                         if (vCurrentOffset < 0) { 
    246                                 //It was an insertion 
    247                                 fProvider.setSize(fProvider.getSize() + 1); 
    248                         } 
    249                         break; 
    250                 case failedNodeFull: 
     248                if (!vResult) { 
    251249                        // We need spaces 
    252250                        fBalancingLayout.addSpaceAndPut(vSlot, vCurrentOffset, pKey, pValue); 
     251                } 
     252                if (vCurrentOffset < 0) { 
     253                        //It was an insertion 
     254                        fProvider.setSizeByDelta(1); 
    253255                } 
    254256                return vOldValue; 
    … …  
    262264                V vOldValue = vSlotProvider.getValue(vOffset); 
    263265                vSlot.removeEntry(vOffset); 
    264                 fProvider.setSize(fProvider.getSize() - 1); 
    265                 fBalancingLayout.onTreeSizeReduced(this); 
     266                fProvider.setSizeByDelta(-1); 
    266267                return vOldValue; 
    267268        } 
    … …  
    273274        protected TreeSlot<K, V> findSlot(Object pKey) { 
    274275                return fRoot.findSlot(pKey); 
    275         } 
    276  
    277         protected void markDirty(ITreeNodeProvider<K, V> pNode) { 
    278                 fDirtyNodes.add(pNode); 
    279         } 
    280  
    281         protected void deleteFromDirtyNodes(ITreeNodeProvider<K, V> pNode) { 
    282                 for (int i = 0; i < fDirtyNodes.size(); i++) { 
    283                         if (fDirtyNodes.get(0) == pNode) { 
    284                                 fDirtyNodes.remove(i); 
    285                         } 
    286                 } 
    287276        } 
    288277 
    … …  
    291280                if (vRoot == null) { 
    292281                        vRoot = fProvider.createSlotAsRoot(); 
    293                         if (vRoot.isDirty()) markDirty(vRoot); 
    294282                } 
    295283                setRootNode(vRoot); 
    … …  
    298286        protected void createSlotAsRoot() { 
    299287                ITreeNodeProvider<K, V> vRoot = fProvider.createSlotAsRoot(); 
    300                 if (vRoot.isDirty()) markDirty(vRoot); 
    301288                setRootNode(vRoot); 
    302289        } 
    … …  
    304291        protected void createRakeAsRoot(TreeNode<K, V> pChild) { 
    305292                ITreeRakeProvider<K, V> vRoot = fProvider.createRakeAsRoot(pChild.getProvider()); 
    306                 if (vRoot.isDirty()) markDirty(vRoot); 
    307                 setRootNode(vRoot); 
     293                fRoot = new TreeRake<K, V>(this, vRoot, pChild); 
    308294                pChild.setParent((TreeRake) fRoot, 0); 
    309295        } 

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

    r19310 r19672  
    22 
    33import eu.scenari.orient.tree.provider.ITreeNodeProvider; 
    4 import eu.scenari.orient.tree.provider.ITreeNodeProvider.UpdateResult; 
    54 
    65public abstract class TreeNode<K, V> { 
    … …  
    6160 
    6261        public void deleteNode() { 
    63                 // remove from dirty list 
    64                 if (fProvider.isDirty()) { 
    65                         fTree.deleteFromDirtyNodes(fProvider); 
    66                 } 
    6762                // remove form parent 
    6863                if (fParent != null) { 
    … …  
    7772        public int adoptEntriesFromLeft(TreeNode<K, V> pLeftNode, float pTargetFillRate) { 
    7873                ITreeNodeProvider<K, V> vLeftNodeProvider = pLeftNode.getProvider(); 
    79                 boolean vNodeWasDirty = fProvider.isDirty(); 
    80                 boolean vLeftNodeWasDirty = vLeftNodeProvider.isDirty(); 
    8174                int vMoved = fProvider.adoptEntriesFromLeft(vLeftNodeProvider, pTargetFillRate); 
    8275                if (vMoved > 0) { 
    8376                        //Some entries have been moved. 
    84                         if (!vNodeWasDirty) fTree.markDirty(fProvider); 
    85                         if (!vLeftNodeWasDirty) fTree.markDirty(vLeftNodeProvider); 
    8677                        if (fParent != null) fParent.updateKey(fOffsetInParent, getProvider().getKey(0)); 
    8778                } 
    … …  
    9182        public int adoptEntriesFromRight(TreeNode<K, V> pRightNode, float pTargetFillRate) { 
    9283                ITreeNodeProvider<K, V> vRightSlotProvider = pRightNode.getProvider(); 
    93                 boolean vNodeWasDirty = fProvider.isDirty(); 
    94                 boolean vRightNodeWasDirty = vRightSlotProvider.isDirty(); 
    9584                int vOldSize = getProvider().getSize(); 
    9685                int vMoved = fProvider.adoptEntriesFromRight(vRightSlotProvider, pTargetFillRate); 
    9786                if (vMoved > 0) { 
    9887                        //Some entries have been moved. 
    99                         if (!vNodeWasDirty) fTree.markDirty(fProvider); 
    100                         if (!vRightNodeWasDirty) fTree.markDirty(vRightSlotProvider); 
    10188                        TreeRake<K, V> vParent = pRightNode.getParent(); 
    10289                        if (vParent != null) vParent.updateKey(pRightNode.getOffsetInParent(), vRightSlotProvider.getKey(0)); 
    … …  
    10794 
    10895        public boolean adoptAllEntriesFromLeft(TreeNode<K, V> pLeftNodeToKill) { 
    109                 UpdateResult vResult = fProvider.adoptAllEntriesFromLeft(pLeftNodeToKill.getProvider()); 
    110                 switch (vResult) { 
    111                 case doneNewlyDirty: 
    112                         fTree.markDirty(fProvider); 
    113                 case done: 
     96                if (fProvider.adoptAllEntriesFromLeft(pLeftNodeToKill.getProvider())) { 
    11497                        if (fParent != null) fParent.updateKey(fOffsetInParent, getKey(0)); 
    11598                        return true; 
    116                 case failedNodeFull: 
    117                         //cancel 
    11899                } 
    119100                return false; 
    … …  
    121102 
    122103        public boolean adoptAllEntriesFromRight(TreeNode<K, V> pRightNodeToKill) { 
    123                 UpdateResult vResult = fProvider.adoptAllEntriesFromRight(pRightNodeToKill.getProvider()); 
    124                 int vOldSize = getProvider().getSize(); 
    125                 switch (vResult) { 
    126                 case doneNewlyDirty: 
    127                         fTree.markDirty(fProvider); 
    128                 case done: 
     104                if (fProvider.adoptAllEntriesFromRight(pRightNodeToKill.getProvider())) { 
     105                        int vOldSize = getProvider().getSize(); 
    129106                        if (vOldSize == 0 && fParent != null) fParent.updateKey(fOffsetInParent, getKey(0)); 
    130107                        return true; 
    131                 case failedNodeFull: 
    132                         //cancel 
    133108                } 
    134109                return false; 

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

    r19333 r19672  
    33import eu.scenari.commons.util.lang.ScException; 
    44import eu.scenari.orient.tree.provider.ITreeNodeProvider; 
    5 import eu.scenari.orient.tree.provider.ITreeNodeProvider.UpdateResult; 
    65import eu.scenari.orient.tree.provider.ITreeRakeProvider; 
    76import eu.scenari.orient.tree.provider.ITreeSlotProvider; 
    … …  
    1110        protected TreeNode<K, V>[] fChildren; 
    1211 
     12        /** Constructor for root tree node. */ 
    1313        public TreeRake(Tree<K, V> pTree, ITreeRakeProvider<K, V> pProvider) { 
    1414                super(pTree, pProvider); 
    … …  
    1616        } 
    1717 
     18        /** Constructor for root tree node in creation context. */ 
     19        public TreeRake(Tree<K, V> pTree, ITreeRakeProvider<K, V> pProvider, TreeNode<K, V> pFirstChild) { 
     20                super(pTree, pProvider); 
     21                setup(); 
     22                fChildren[0] = pFirstChild; 
     23 
     24        } 
     25 
    1826        public TreeRake(TreeRake<K, V> pParent, int pOffset, ITreeRakeProvider<K, V> pProvider) { 
    1927                super(pParent, pOffset, pProvider); 
    … …  
    2230 
    2331        protected void setup() { 
    24                 fChildren = new TreeNode[fTree.fProvider.getDefaultRakeCapacity()]; 
     32                fChildren = new TreeNode[Math.max(fTree.fProvider.getDefaultRakeCapacity(), getProvider().getSize())]; 
    2533        } 
    2634 
    … …  
    3341        } 
    3442 
     43        /** 
     44         * Warning : bounds are not checked. 
     45         * @see #getFirstNode() 
     46         * @see #getLastNode() 
     47         */ 
    3548        public TreeNode<K, V> getNode(int pOffset) { 
     49                assert (pOffset < getProvider().getSize()); 
    3650                TreeNode<K, V> vResult = fChildren[pOffset]; 
    3751                if (vResult == null) { 
    … …  
    4357        } 
    4458 
     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() { 
     70                int vSize = getProvider().getSize(); 
     71                return (vSize > 0) ? getNode(0) : null; 
     72        } 
     73 
     74        public TreeNode<K, V> getLastNode() { 
     75                int vSize = getProvider().getSize(); 
     76                return (vSize > 0) ? getNode(vSize - 1) : null; 
     77        } 
     78 
    4579        public TreeRake<K, V> insertNewRake(int pOffset) { 
     80                int vCurrentSize = getProvider().getSize(); 
     81                assert (pOffset <= vCurrentSize); 
    4682                ITreeRakeProvider<K, V> vNewRake = getProvider().insertNewRake(pOffset); 
    4783                if (vNewRake == null) return null; 
    48                 if (vNewRake.isDirty()) fTree.markDirty(vNewRake); 
    49                 return (TreeRake) createChildNode(vNewRake, pOffset); 
     84                ensureSize(vCurrentSize + 1); 
     85                TreeRake vRake = (TreeRake) createChildNode(vNewRake, pOffset); 
     86                int vCountToMove = vCurrentSize - pOffset - 1; 
     87                if (vCountToMove > 0) { 
     88                        //move 
     89                        System.arraycopy(fChildren, pOffset, fChildren, pOffset + 1, vCountToMove); 
     90                } 
     91                fChildren[pOffset] = vRake; 
     92                return vRake; 
    5093        } 
    5194 
    5295        public TreeSlot<K, V> insertNewSlot(int pOffset) { 
     96                int vCurrentSize = getProvider().getSize(); 
     97                assert (pOffset <= getProvider().getSize()); 
    5398                ITreeSlotProvider<K, V> vNewSlot = getProvider().insertNewSlot(pOffset); 
    5499                if (vNewSlot == null) return null; 
    55                 if (vNewSlot.isDirty()) fTree.markDirty(vNewSlot); 
    56                 return (TreeSlot) createChildNode(vNewSlot, pOffset); 
    57         } 
    58  
    59         public TreeNode<K, V> getNodeIfLoaded(int pOffset) { 
    60                 return fChildren[pOffset]; 
     100                ensureSize(vCurrentSize + 1); 
     101                TreeSlot vNode = (TreeSlot) createChildNode(vNewSlot, pOffset); 
     102                int vCountToMove = vCurrentSize - pOffset - 1; 
     103                if (vCountToMove > 0) { 
     104                        //move 
     105                        System.arraycopy(fChildren, pOffset, fChildren, pOffset + 1, vCountToMove); 
     106                } 
     107                fChildren[pOffset] = vNode; 
     108                return vNode; 
     109        } 
     110 
     111        public int adoptEntriesFromRight(TreeNode<K, V> pRightNode, float pTargetFillRate) { 
     112                int vMoved = super.adoptEntriesFromRight(pRightNode, pTargetFillRate); 
     113                if (vMoved > 0) { 
     114                        //Move TreeNode children instances. 
     115                        int vNewSize = getProvider().getSize(); 
     116                        ensureSize(vNewSize); 
     117                        TreeRake<K, V> vRight = (TreeRake) pRightNode; 
     118                        TreeNode<K, V>[] vRightChildren = vRight.fChildren; 
     119                        System.arraycopy(vRightChildren, 0, fChildren, vNewSize - vMoved, vMoved); 
     120                        System.arraycopy(vRightChildren, vMoved, vRightChildren, 0, vRightChildren.length - vMoved); 
     121                        for (int i = vNewSize - vMoved; i < vNewSize; i++) { 
     122                                fChildren[i].setParent(this, i); 
     123                        } 
     124                } 
     125                return vMoved; 
     126        } 
     127 
     128        public int adoptEntriesFromLeft(TreeNode<K, V> pLeftNode, float pTargetFillRate) { 
     129                int vMoved = super.adoptEntriesFromLeft(pLeftNode, pTargetFillRate); 
     130                if (vMoved > 0) { 
     131                        //Move TreeNode children instances. 
     132                        int vNewSize = getProvider().getSize(); 
     133                        ensureSize(vNewSize); 
     134                        TreeRake<K, V> vLeft = (TreeRake) pLeftNode; 
     135                        TreeNode<K, V>[] vLeftChildren = vLeft.fChildren; 
     136                        System.arraycopy(fChildren, 0, fChildren, vMoved, vNewSize - vMoved); 
     137                        System.arraycopy(vLeftChildren, vLeft.getProvider().getSize(), fChildren, 0, vMoved); 
     138                        for (int i = 0; i < vMoved; i++) { 
     139                                fChildren[i].setParent(this, i); 
     140                        } 
     141                } 
     142                return vMoved; 
     143        } 
     144 
     145        public boolean adoptAllEntriesFromRight(TreeNode<K, V> pRightNodeToKill) { 
     146                int vOldSize = getProvider().getSize(); 
     147                if (super.adoptAllEntriesFromRight(pRightNodeToKill)) { 
     148                        //Move TreeNode children instances. 
     149                        int vNewSize = getProvider().getSize(); 
     150                        ensureSize(vNewSize); 
     151                        TreeRake<K, V> vRight = (TreeRake) pRightNodeToKill; 
     152                        TreeNode<K, V>[] vRightChildren = vRight.fChildren; 
     153                        System.arraycopy(vRightChildren, 0, fChildren, vOldSize, vNewSize - vOldSize); 
     154                        for (int i = vOldSize; i < vNewSize; i++) { 
     155                                fChildren[i].setParent(this, i); 
     156                        } 
     157                        return true; 
     158                } 
     159                return false; 
     160        } 
     161 
     162        public boolean adoptAllEntriesFromLeft(TreeNode<K, V> pLeftNodeToKill) { 
     163                int vMoved = pLeftNodeToKill.getProvider().getSize(); 
     164                if (super.adoptAllEntriesFromLeft(pLeftNodeToKill)) { 
     165                        //Move TreeNode children instances. 
     166                        int vNewSize = getProvider().getSize(); 
     167                        ensureSize(vNewSize); 
     168                        TreeRake<K, V> vLeft = (TreeRake) pLeftNodeToKill; 
     169                        TreeNode<K, V>[] vLeftChildren = vLeft.fChildren; 
     170                        System.arraycopy(fChildren, 0, fChildren, vMoved, vNewSize - vMoved); 
     171                        System.arraycopy(vLeftChildren, 0, fChildren, 0, vMoved); 
     172                        for (int i = 0; i < vMoved; i++) { 
     173                                fChildren[i].setParent(this, i); 
     174                        } 
     175                        return true; 
     176                } 
     177                return false; 
    61178        } 
    62179 
    … …  
    72189                int vLow = 0; 
    73190                int vHigh = fProvider.getSize() - 1; 
    74                 while (vLow <= vHigh) { 
     191                while (vLow < vHigh) { 
    75192                        int vMid = (vLow + vHigh) >>> 1; 
    76193                        K vMidKey = getKey(vMid); 
    … …  
    88205        } 
    89206 
    90         public TreeSlot<K, V> findNextSlot(int pOffsetInParent) { 
    91                 if (pOffsetInParent < getProvider().getSize() - 1) return getNode(pOffsetInParent + 1).findFirstSlot(); 
    92                 return fParent != null ? fParent.findNextSlot(fOffsetInParent) : null; 
    93         } 
    94  
    95         public TreeSlot<K, V> findPreviousSlot(int pOffsetInParent) { 
    96                 if (pOffsetInParent > 0) return getNode(pOffsetInParent - 1).findLastSlot(); 
    97                 return fParent != null ? fParent.findPreviousSlot(fOffsetInParent) : null; 
     207        public TreeSlot<K, V> findRightSlot(int pFrom) { 
     208                if (pFrom < getProvider().getSize() - 1) return getNode(pFrom + 1).findFirstSlot(); 
     209                return fParent != null ? fParent.findRightSlot(fOffsetInParent) : null; 
     210        } 
     211 
     212        public TreeSlot<K, V> findLeftSlot(int pFrom) { 
     213                if (pFrom > 0) return getNode(pFrom - 1).findLastSlot(); 
     214                return fParent != null ? fParent.findLeftSlot(fOffsetInParent) : null; 
     215        } 
     216 
     217        /** Find the right next node (slot or rake) with the same level. */ 
     218        public TreeNode<K, V> findRightCousin(int pFrom) { 
     219                if (pFrom < getProvider().getSize() - 1) return getNode(pFrom + 1); 
     220                if (fParent == null) return null; 
     221                TreeNode<K, V> vParentCousin = fParent.findRightCousin(fOffsetInParent); 
     222                return vParentCousin != null && vParentCousin.isRake() ? ((TreeRake) vParentCousin).getFirstNode() : null; 
     223        } 
     224 
     225        /** Find the left previous node (slot or rake) with the same level. */ 
     226        public TreeNode<K, V> findLeftCousin(int pFrom) { 
     227                if (pFrom > 0) return getNode(pFrom - 1); 
     228                if (fParent == null) return null; 
     229                TreeNode<K, V> vParentCousin = fParent.findLeftCousin(fOffsetInParent); 
     230                return vParentCousin != null && vParentCousin.isRake() ? ((TreeRake) vParentCousin).getLastNode() : null; 
    98231        } 
    99232 
    … …  
    110243 
    111244        public void updateKey(int pOffset, K pKey) { 
    112                 UpdateResult vResult = getProvider().updateKey(pOffset, pKey); 
    113                 switch (vResult) { 
    114                 case doneNewlyDirty: 
    115                         fTree.markDirty(fProvider); 
    116                 case done: 
    117                         break; 
    118                 case failedNodeFull: 
     245                assert (pOffset < getProvider().getSize()); 
     246                if (!getProvider().updateKey(pOffset, pKey)) { 
    119247                        //TODO failedNodeFull on updateKey 
    120248                        throw new ScException("TODO failedNodeFull on updateKey"); 
    … …  
    144272                } else { 
    145273                        // Remove this entry. 
    146                         if (fProvider.remove(vOffsetEntry)) { 
    147                                 fTree.markDirty(fProvider); 
    148                         } 
     274                        fProvider.remove(vOffsetEntry); 
    149275                        // Update start key. 
    150276                        if (vOffsetEntry == 0 && fParent != null) { 
    … …  
    163289                } 
    164290        } 
     291 
     292        protected void ensureSize(int pTargetSize) { 
     293                if (fChildren.length < pTargetSize) { 
     294                        TreeNode<K, V>[] vNew = new TreeNode[pTargetSize + 10]; 
     295                        System.arraycopy(fChildren, 0, vNew, 0, fChildren.length); 
     296                        fChildren = vNew; 
     297                } 
     298        } 
    165299} 

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

    r19310 r19672  
    7878        } 
    7979 
    80         public TreeSlot<K, V> findNextSlot() { 
     80        public TreeSlot<K, V> findRightSlot() { 
    8181                if (fParent == null) return null; 
    82                 return fParent.findNextSlot(fOffsetInParent); 
     82                return fParent.findRightSlot(fOffsetInParent); 
    8383        } 
    8484 
    85         public TreeSlot<K, V> findPreviousSlot() { 
     85        public TreeSlot<K, V> findLeftSlot() { 
    8686                if (fParent == null) return null; 
    87                 return fParent.findPreviousSlot(fOffsetInParent); 
     87                return fParent.findLeftSlot(fOffsetInParent); 
    8888        } 
    8989 
    … …  
    9393 
    9494        public void removeEntry(int pOffset) { 
     95                assert (pOffset < getProvider().getSize()); 
    9596                if (pOffset == 0 && fProvider.getSize() == 1) { 
    9697                        //cleanup 
    9798                        deleteNode(); 
    9899                } else { 
    99                         if (fProvider.remove(pOffset)) { 
    100                                 fTree.markDirty(fProvider); 
    101                         } 
     100                        fProvider.remove(pOffset); 
    102101                        if (pOffset == 0 && fParent != null) { 
    103102                                fParent.updateKey(fOffsetInParent, getKey(0)); 

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

    r19310 r19672  
    22 
    33public interface ITreeNodeProvider<K, V> { 
    4  
    5         public static enum UpdateResult { 
    6                 done, doneNewlyDirty, failedNodeFull 
    7         } 
    84 
    95        /** Is it a rake or a slot. */ 
    … …  
    2117         * @return <code>true</code> this node is newly dirty. 
    2218         */ 
    23         public boolean remove(int pOffset); 
     19        public void remove(int pOffset); 
    2420 
    2521        /**  
    … …  
    3127         * Move all entries from left node for merging 2 nodes. 
    3228         *  
    33          * @return {@link UpdateResult#failedNodeFull} if all entries can not be moved. 
     29         * @param pLeftNodeToKill Node to merge. pLeftNodeToKill is the same type as this one (rake / slot). 
     30         * @return <code>false</code> if the move has been cancelled because the node has not enough space. 
    3431         */ 
    35         public UpdateResult adoptAllEntriesFromLeft(ITreeNodeProvider<K, V> pLeftNodeToKill); 
     32        public boolean adoptAllEntriesFromLeft(ITreeNodeProvider<K, V> pLeftNodeToKill); 
    3633 
    3734        /** 
    3835         * Move all entries from right node for merging 2 nodes. 
    3936         *  
    40          * @return {@link UpdateResult#failedNodeFull} if all entries can not be moved. 
     37         * @param pRightNodeToKill Node to merge. pLeftNodeToKill is the same type as this one (rake / slot). 
     38         * @return <code>false</code> if the move has been cancelled because the node has not enough space. 
    4139         */ 
    42         public UpdateResult adoptAllEntriesFromRight(ITreeNodeProvider<K, V> pRightNodeToKill); 
     40        public boolean adoptAllEntriesFromRight(ITreeNodeProvider<K, V> pRightNodeToKill); 
    4341 
    4442        /**  
    … …  
    4644         * pLeftNode must always have at least one entry. 
    4745         *  
    48          * @param pLeftNode node from moving entries 
     46         * @param pLeftNode node from moving entries. pLeftNode is the same type as this one (rake / slot) 
    4947         * @param pTargetFillRate target fill rate for this node 
    5048         * @return number of entries moved. 
    … …  
    5654         * pRightNode must always have at least one entry. 
    5755         * 
    58          * @param pRightNode node from moving entries 
     56         * @param pRightNode node from moving entries. pRightNode is the same type as this one (rake / slot) 
    5957         * @param pTargetFillRate target fill rate for this node 
    6058         * @return number of entries moved. 
    … …  
    6260        public int adoptEntriesFromRight(ITreeNodeProvider<K, V> pRightNode, float pTargetFillRate); 
    6361 
    64         /** Delete this node.*/ 
     62        /**  
     63         * This node will not be used any more by the tree, it must be deleted in the storage layer. 
     64         */ 
    6565        public void deleteNode(); 
    6666 
     67        /** Indicate that this node is dirty and will not be garbage collected by the Tree. */ 
    6768        public boolean isDirty(); 
    68  
    69         public void save(); 
    7069} 

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

    r19310 r19672  
    33public interface ITreeProvider<K, V> { 
    44 
    5         /** Tree size (number of entries). */ 
     5        /**  
     6         * Tree size (number of entries).  
     7         * A provider can not store the current size and then return -1. 
     8         *  
     9         * @return tree size or -1 if size unknown. 
     10         */ 
    611        public int getSize(); 
    712 
    8         public void setSize(int pSize); 
     13        /** 
     14         * Add or substract pDelta to the current size. 
     15         */ 
     16        public void setSizeByDelta(int pDelta); 
    917 
     18        /** 
     19         * Set size. 
     20         * Can be called when {@link #getSize()} has returned -1 and the size 
     21         * has been computed by iterating the tree.  
     22         * The size should then be kept in memory for performance. 
     23         */ 
     24        public void setSize(int pComputedSize); 
     25 
     26        /** Load root node. */ 
    1027        public ITreeNodeProvider<K, V> loadRoot(); 
    1128 
     29        /** Update root node. */ 
    1230        public void setRoot(ITreeNodeProvider<K, V> pNewRoot); 
    1331 
     32        /** Create a new rake as a root. */ 
    1433        public ITreeRakeProvider<K, V> createRakeAsRoot(ITreeNodeProvider<K, V> pFirstChild); 
    1534 
     35        /** Create a new slot as a root. */ 
    1636        public ITreeSlotProvider<K, V> createSlotAsRoot(); 
    1737 
    … …  
    2242        public int getDefaultSlotCapacity(); 
    2343 
    24         public boolean isDirty(); 
    25  
    26         public void save(); 
    27  
    2844} 

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

    r19310 r19672  
    2323        public ITreeSlotProvider<K, V> insertNewSlot(int pOffset); 
    2424 
    25         public UpdateResult updateKey(int pOffset, K pKey); 
     25        /** 
     26         * Update the key. 
     27         *  
     28         * @return <code>false</code> if the update has been cancelled because the node has not enough space. 
     29         */ 
     30        public boolean updateKey(int pOffset, K pKey); 
    2631 
    2732} 

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

    r19333 r19672  
    1515         *  
    1616         * @param pValue not used  for a Set implementation. 
     17         * @return <code>false</code> if the insertion has been cancelled because the node has not enough space. 
    1718         */ 
    18         public UpdateResult insert(int pOffset, K pKey, V pValue); 
     19        public boolean insert(int pOffset, K pKey, V pValue); 
    1920 
    2021        /** 
    2122         *  
    2223         * @param pValue not used  for a Set implementation. 
    23          * @return <code>true</code> if succeed. <code>false</code> if slot is full. 
     24         * @return <code>false</code> if the insertion has been cancelled because the node has not enough space. 
    2425         */ 
    25         public UpdateResult replace(int pOffset, K pKey, V pValue); 
     26        public boolean replace(int pOffset, K pKey, V pValue); 
    2627 
    2728} 
Note: See TracChangeset for help on using the changeset viewer.