KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > daffodilwoods > daffodildb > server > datasystem > indexsystem > FixedBTreeCluster


1 package com.daffodilwoods.daffodildb.server.datasystem.indexsystem;
2
3 import com.daffodilwoods.daffodildb.server.datasystem.btree.*;
4 import com.daffodilwoods.daffodildb.server.datasystem.persistentsystem.*;
5 import com.daffodilwoods.daffodildb.utils.*;
6 import com.daffodilwoods.daffodildb.utils.byteconverter.*;
7 import com.daffodilwoods.database.resource.*;
8 import com.daffodilwoods.database.utility.P;
9 import com.daffodilwoods.daffodildb.server.datasystem.persistentsystem.versioninfo.VersionHandler;
10
11
12
13 /**
14  * FixedBtreeCluster stores and fetches bytes of elements of btree and stores other required information
15  * as next node address, previous node address, parent node address, whether particular node is leaf
16  * node or not etc.
17  * <p>Title: FixedBTreeCluster
18  */
19
20 public class FixedBTreeCluster extends Cluster {
21
22
23     public FixedBTreeCluster(ClusterCharacteristics cc,DatabaseProperties databaseProperties0,VersionHandler versionHandler0) throws DException{
24         super(cc,databaseProperties0,versionHandler0);
25     }
26
27     /**
28      * sets header of cluster when any new Btree Cluster is made. header of BtreeCluster is made of
29        Position Information
30      * 0 : Insertable Address
31      * 8 : actual Record count
32      * 16: active Record count
33      * 24: previous node address
34      * 32: updatable memory
35      * 40: PARENTNODEADDRESS
36      * 48: LEVEL_NODE
37      * 50: IS_LEAFNODE
38      * 51: Is_DummyNode
39      *
40      * @throws DException
41      */
42     public void setHeader()throws DException{
43         updateBytes(0,CCzufDpowfsufs.getBytes(versionHandler.BTREECLUSTER_STARTPOINTER));
44         updateByte(versionHandler.IS_LEAFNODE,versionHandler.TRUE);
45         updateBytes(versionHandler.PARENTNODEADDRESS,CCzufDpowfsufs.getBytes((int)0));
46         updateBytes(versionHandler.LEVEL_NODE,CCzufDpowfsufs.getBytes((short)0));
47     }
48
49   public boolean isLeafCluster(){
50         return clusterBytes[versionHandler.IS_LEAFNODE] == versionHandler.TRUE;
51     }
52
53     /**
54      * Inserts bytes at position, Updates next insertable address and total element count in cluster , it stores
55      * elemnt start address in last of cluster if element has to insert in middle then shifts all elements
56      * start address in cluster.
57      * @param position position at which element has to insert
58      * @param bytes bytes of element key, value and child address
59      * @throws DException if elemnt can not be inserted in this cluster(node)
60      */
61    public void insert(int position,byte[] bytes) throws DException{
62             short insertableAddress = CCzufDpowfsufs.getShortValue(clusterBytes,0);
63             int length = bytes.length;
64             if(freeSpace() < length){
65                 throw StaticExceptions.SPLIT_NODE_EXCEPTION;
66             }
67             updateBytes(insertableAddress,bytes);
68             int keyPointerInCluster = databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (activeRecordCount+1) * versionHandler.LENGTH;
69             if(position == activeRecordCount)
70                 updateBytes(keyPointerInCluster,CCzufDpowfsufs.getBytes(insertableAddress));
71             else
72                 shiftBytes(keyPointerInCluster+versionHandler.LENGTH,position,insertableAddress);
73             activeRecordCount++;
74             actualRecordCount++;
75             updateClusterInformation((short)(insertableAddress + length));
76     }
77
78
79     /**
80      * deletes element at given position for it removes this element start pointer from the last of cluster
81      * where elements start address are stored and
82      * if position is last record then updates the InsertableAddress and also decreases active
83      * record count by 1 , if total number of active records in cluster are less than half of total actual
84      * records in cluster then optimizes space in this cluster by calling deleteRange.
85      * @param position at which element has to delete
86      */
87   public void delete(int position) throws DException{
88               int pointerOfRecordToBeDeleted =databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - ((position + 1) * versionHandler.LENGTH);
89               short insertableAddress = CCzufDpowfsufs.getShortValue(clusterBytes,0);
90               short deletedRecordPointer = CCzufDpowfsufs.getShortValue(clusterBytes,pointerOfRecordToBeDeleted);
91               short sizeOfRecord = CCzufDpowfsufs.getShortValue(clusterBytes,deletedRecordPointer);
92               if(deletedRecordPointer + sizeOfRecord == insertableAddress){ //this check is applied as the record may be present in the cluster as the last record but in pointers it may be any other record(as record inserted in between thru change of pointers only)
93 short newInsertableaddress = (short) (insertableAddress - sizeOfRecord);
94                 updateBytes(0, CCzufDpowfsufs.getBytes(newInsertableaddress));
95               }
96
97                if(position + 1 != activeRecordCount){
98                  int startPointer = databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (activeRecordCount * versionHandler.LENGTH);
99                  int size = pointerOfRecordToBeDeleted - startPointer;
100                  byte[] bytes = new byte[size];
101                  System.arraycopy(clusterBytes, startPointer, bytes, 0, bytes.length);
102                  updateBytes(startPointer + versionHandler.LENGTH, bytes);
103                }
104
105             activeRecordCount--;
106             updateBytes(2*versionHandler.LENGTH,CCzufDpowfsufs.getBytes(activeRecordCount));
107             if(activeRecordCount < actualRecordCount/2 || activeRecordCount == 1){
108               deleteRange(0,activeRecordCount-1);
109             }
110     }
111
112     /**
113      * returns BufferRange corresponding to bytes of element at given position for it first calucaltes
114      * element start address in cluster and its size
115      * @param position at which record has to retrieve
116      * @return BufferRange corresponding to bytes of element at given position
117      */
118   public BufferRange getRowBuffer(int position)throws DException {
119         int pointer = databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (position+1) * versionHandler.LENGTH;
120         short startPointer = CCzufDpowfsufs.getShortValue(clusterBytes,pointer);
121         short lengthOfRow = (short)(CCzufDpowfsufs.getShortValue(clusterBytes,startPointer) - versionHandler.LENGTH);
122
123         byte[] recordBytes = new byte[lengthOfRow];
124           System.arraycopy(clusterBytes, startPointer + versionHandler.LENGTH, recordBytes, 0,
125                            lengthOfRow);
126         BufferRange buffer = new BufferRange(recordBytes,0,lengthOfRow);
127         return buffer;
128     }
129
130     /**
131      * shifts bytes from position to endPointer and writes insertable address at position
132      * @param endPointer from where elements start address would start in cluster
133      * @param position at which new element has to insert
134      * @param insertableAddress insertable address of new element in cluster
135      */
136
137     private void shiftBytes(int endPointer, int position,short insertableAddress)throws DException{
138             int writePointer = databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (position+1) * versionHandler.LENGTH;
139             byte[] shiftBytes = new byte[ writePointer - endPointer + versionHandler.LENGTH];
140             System.arraycopy(clusterBytes,endPointer,shiftBytes,0,shiftBytes.length);
141             updateBytes(writePointer,CCzufDpowfsufs.getBytes(insertableAddress) );
142             updateBytes(endPointer - versionHandler.LENGTH, shiftBytes);
143     }
144
145   public short getLevel(){
146         return CCzufDpowfsufs.getShortValue(clusterBytes,versionHandler.LEVEL_NODE);
147     }
148
149     public void setLevel(short level)throws DException{
150         updateBytes(versionHandler.LEVEL_NODE,CCzufDpowfsufs.getBytes(level));
151     }
152
153     /**
154      * Reinitializes cluster bytes by inserting elements from startposition to endPosition.It makes new
155      * byte array , retrives element values from cluster bytes and inserts in new byte array, then set
156      * cluster bytes by this array and updates cluster insertable address, actual record count and active
157      * record count
158      *
159      * @param startPosition from where element has to insert
160      * @param endPosition till where element has to insert
161      */
162    public void deleteRange(int startPosition,int endPosition)throws DException{
163          byte[] bytes = new byte[databaseProperties.CLUSTERSIZE];
164          short dataPointer = versionHandler.BTREECLUSTER_STARTPOINTER;
165          int startPositionPointer = databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - versionHandler.LENGTH;
166          int pointer = databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (startPosition+1) * versionHandler.LENGTH;
167          short startPointer ,lengthOfRow;
168          for(int i = startPosition; i <= endPosition ; i++){
169              startPointer = CCzufDpowfsufs.getShortValue(clusterBytes,pointer);
170               lengthOfRow = CCzufDpowfsufs.getShortValue(clusterBytes,startPointer);
171              System.arraycopy(clusterBytes, startPointer, bytes, dataPointer,lengthOfRow);
172              System.arraycopy(CCzufDpowfsufs.getBytes(dataPointer),0,bytes,startPositionPointer,versionHandler.LENGTH);
173              dataPointer += lengthOfRow;
174              startPositionPointer -= versionHandler.LENGTH;
175              pointer -= versionHandler.LENGTH;
176          }
177          short count = (short)(endPosition - startPosition + 1);
178          initializeBytes(bytes,count,dataPointer);
179          actualRecordCount = activeRecordCount = count ;
180          setBytes(bytes);
181          setDirty(true);
182     }
183
184     /**
185      * Initializes cluster header Bytes
186      * @param bytes in which cluster header information has to update
187      * @param count total number of elements in node
188      * @param insertableAddress insertable address in cluster
189      */
190     private void initializeBytes(byte [] bytes,short count,short insertableAddress){
191         byte[] bb = CCzufDpowfsufs.getBytes(count);
192         System.arraycopy(CCzufDpowfsufs.getBytes(insertableAddress),0,bytes,0,versionHandler.LENGTH);
193         System.arraycopy(bb,0,bytes,versionHandler.LENGTH,versionHandler.LENGTH);
194         System.arraycopy(bb,0,bytes,2 * versionHandler.LENGTH,versionHandler.LENGTH);
195         System.arraycopy(clusterBytes,databaseProperties.NEXTCLUSTERADDRESS,bytes,databaseProperties.NEXTCLUSTERADDRESS,versionHandler.NEWADDRESSLENGTH);
196         System.arraycopy(clusterBytes,versionHandler.PREVIOUSCLUSTERADDRESS,bytes,versionHandler.PREVIOUSCLUSTERADDRESS,versionHandler.NEWADDRESSLENGTH);
197         System.arraycopy(clusterBytes,versionHandler.PARENTNODEADDRESS,bytes,versionHandler.PARENTNODEADDRESS,7);
198     }
199
200     /**
201      * Inserts elements from start position to endPosition in given byte Array
202      * @param bytes in which elements has to be inserted
203      * @param startPosition from which element has to insert
204      * @param endPosition up to which element has to insert
205      */
206  public void insertRange(byte[]bytes,int startPosition,int endPosition)throws DException{
207             short dataPointer = (short)(versionHandler.BTREECLUSTER_STARTPOINTER + 3 * versionHandler.LENGTH);
208             int startPositionPointer = databaseProperties.CLUSTERSIZE - 2*versionHandler.LENGTH - versionHandler.NEWADDRESSLENGTH ;
209             int pointer = databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (startPosition+1) * versionHandler.LENGTH;
210              short startPointer ,lengthOfRow;
211             for (int i = startPosition; i <= endPosition; i++) {
212                  startPointer = CCzufDpowfsufs.getShortValue(bytes,pointer);
213                 lengthOfRow = CCzufDpowfsufs.getShortValue(bytes,startPointer);
214                 System.arraycopy(bytes,startPointer,clusterBytes,dataPointer,lengthOfRow);
215                 System.arraycopy(CCzufDpowfsufs.getBytes(dataPointer),0,clusterBytes,startPositionPointer,versionHandler.LENGTH);
216                 dataPointer += lengthOfRow;
217                 startPositionPointer -= versionHandler.LENGTH;
218                 pointer -= versionHandler.LENGTH;
219             }
220
221             short count = (short)(endPosition - startPosition + 1);
222             actualRecordCount += count;
223             activeRecordCount += count;
224             updateClusterInformation(dataPointer);
225             setDirty(true);
226     }
227
228     /**
229      * returns cluster characteristics of parent node of current node, if there is no parent node then
230      * returns null
231      *
232      * @return cluster characteristics of parent node of current node
233      */
234
235
236    public ClusterCharacteristics getParentKey()throws DException{
237             int add = CCzufDpowfsufs.getIntValue(clusterBytes,versionHandler.PARENTNODEADDRESS);
238             if(add == 0)
239                 return null;
240             return new ClusterCharacteristics(add,true);
241     }
242
243     /**
244      * sets leaf node byte in cluster which tells whether particular cluster is leaf or not
245      * @param flag true if leaf node else false
246      */
247   public void setLeafNode(boolean flag)throws DException{
248             updateByte(versionHandler.IS_LEAFNODE, flag ? versionHandler.TRUE : versionHandler.FALSE);
249     }
250
251     /**
252      * sets given clustercharacteristics as parent node of currentNode
253      * @param cc parent clusterCharacteristics of current Node
254      */
255     public void setParentNode(ClusterCharacteristics cc) throws DException {
256         updateBytes(versionHandler.PARENTNODEADDRESS,CCzufDpowfsufs.getBytes(cc.getStartAddress()));
257     }
258
259     /**
260      * Updates child address of element at given position.calculates where child address of this elemnt
261      * has to write
262      * @param position position of element whose child address has to change
263      * @param key address of child
264      */
265     public void updateChild(int position,Object JavaDoc key) throws DException{
266         int add = ((ClusterCharacteristics)key).getStartAddress();
267         byte[] bytes = CCzufDpowfsufs.getBytes(add);
268         int pointer = databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (position+1)*versionHandler.LENGTH;
269         short startPointer = CCzufDpowfsufs.getShortValue(clusterBytes,pointer);
270         short lengthOfRow = CCzufDpowfsufs.getShortValue(clusterBytes,startPointer);
271         startPointer = (short)(startPointer + lengthOfRow - versionHandler.NEWADDRESSLENGTH);
272         updateBytes(startPointer,bytes);
273     }
274
275
276     public String JavaDoc toString(){
277         return "FixedBtreeCluster " + super.toString();
278     }
279
280     public DatabaseProperties getDatabaseProperties() {
281         return databaseProperties;
282     }
283
284     /**
285      * updates record in case of fixedBtreeCluster just by overwriting the new bytes over
286      * old record bytes
287      * @param bytes newBytes
288      */
289
290     public void updateFixed(int position, byte[] bytes) throws DException{
291       int startPointer =databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (position+1) * versionHandler.LENGTH;
292       updateBytes(CCzufDpowfsufs.getShortValue(clusterBytes,startPointer),bytes);
293     }
294
295     /**
296      * updates bytes in case of VariableBTreeCluster in case the new bytes are equal or less then old bytes
297      * else throws RECORD_CANNOT_UPDATED
298      * @param position
299      * @param newBytes
300      * @throws DException
301      */
302
303     public void updateVariable1(int position, byte[] newBytes) throws DException {
304       int freeSpace = getRange();
305       short startPointer = getStartPointerOfRecord((short)(position+1));
306       short sizeOfRecord = CCzufDpowfsufs.getShortValue(clusterBytes,startPointer);
307       short insertableAddress = CCzufDpowfsufs.getShortValue(clusterBytes,0);
308       boolean flag = startPointer + sizeOfRecord == insertableAddress;
309       int oldRecordSize =(int)(CCzufDpowfsufs.getShortValue(clusterBytes,startPointer));
310       if(newBytes.length <= freeSpace + oldRecordSize) {
311         short changeInStartPositions = (short) (newBytes.length - oldRecordSize);
312         byte[] bytes = null;
313         if (changeInStartPositions != 0)
314           bytes = getClusterBytes( (short) (position + 2));
315         short currentPointer = (short) (startPointer);
316         updateBytes(currentPointer, newBytes);
317         currentPointer += newBytes.length;
318
319         updateClusterInformation(currentPointer);
320         if (!flag) {
321           if (changeInStartPositions != 0) {
322             updateBytes(currentPointer, bytes);
323             short s = (short) (position+1);
324             short recordSizePointer = (short) (databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - s * versionHandler.LENGTH - versionHandler.LENGTH);
325             for (short len = (short) getColumnPositions().length; s < len; s++) {
326               updateColumnPositions(s,((short)(getStartPointerOfRecord((short)(s + 1)) + changeInStartPositions)));
327               updateBytes(recordSizePointer,CCzufDpowfsufs.getBytes(getColumnPositions()[s]));
328               recordSizePointer -= versionHandler.LENGTH;
329             }
330           }
331         }
332       }
333       else
334         throw RECORD_CANNOT_UPDATED;
335     }
336
337
338
339
340     public void updateVariable(int position, byte[] newBytes) throws DException {
341          short startPointer = getStartPointerOfRecord((short)(position+1));
342          short oldRecordSize = CCzufDpowfsufs.getShortValue(clusterBytes,startPointer);
343          short insertableAddress = CCzufDpowfsufs.getShortValue(clusterBytes,0);
344          boolean flag = startPointer + oldRecordSize == insertableAddress;
345          if(newBytes.length <= getRange() + oldRecordSize) {
346            short changeInStartPositions = (short) (newBytes.length - oldRecordSize);
347            byte[] bytes = null;
348            if(!flag)
349              bytes = getClusterBytes( (short) (startPointer + oldRecordSize));
350            short currentPointer = startPointer;
351            updateBytes(currentPointer, newBytes);
352            currentPointer += newBytes.length;
353
354          if(flag)
355            updateClusterInformation(currentPointer);
356          else{
357              if (changeInStartPositions != 0) {
358                updateBytes(currentPointer, bytes);
359                updateClusterInformation((short)(currentPointer+bytes.length));
360                short recordSizePointer = (short) (databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - versionHandler.LENGTH);
361                for (int i = 0; i < activeRecordCount; i++) { //check for position in cluster
362 short recordPointer = CCzufDpowfsufs.getShortValue(clusterBytes,recordSizePointer);
363                  if( recordPointer > startPointer)
364                    updateBytes(recordSizePointer,CCzufDpowfsufs.getBytes((short)(recordPointer + changeInStartPositions)));
365                  recordSizePointer -= versionHandler.LENGTH;
366                }
367              }
368          }
369          }
370          else
371            throw RECORD_CANNOT_UPDATED;
372
373     }
374
375
376     /** returns byte[] starting from recordNumber to lastRecord in the cluster
377      * for the purpose of shifting it to the new position in case oldRecordsize is
378      * not equal to the new record size
379      */
380
381      private byte[] getClusterBytes(short startPointerOfNextRecord) throws DException {
382            short len = (short)(CCzufDpowfsufs.getShortValue(clusterBytes,0) - startPointerOfNextRecord);
383            byte[] bytes = new byte[len];
384              System.arraycopy(clusterBytes,startPointerOfNextRecord,bytes,0,len);
385            return bytes;
386          }
387
388      /**
389       * returns free space in the cluster left for updation
390       */
391
392     public int getRange() throws DException {
393       return databaseProperties.CLUSTERSIZE -
394           CCzufDpowfsufs.getShortValue(getBytes(), 0) - versionHandler.LENGTH * activeRecordCount - versionHandler.NEWADDRESSLENGTH;
395     }
396
397      short getStartPointerOfRecord(short recordNumber) throws DException{
398          return CCzufDpowfsufs.getShortValue(clusterBytes,databaseProperties.CLUSTERSIZE - versionHandler.NEWADDRESSLENGTH - (recordNumber) * versionHandler.LENGTH);
399
400        }
401        public void reInitializeActiveRecordCount(){
402          activeRecordCount =0;
403        }
404        public void reInitializeActualRecordCount(){
405          actualRecordCount =0;
406        }
407   }
408
Popular Tags