IndexNode


1   /* =============================================================
2    * SmallSQL : a free Java DBMS library for the Java(tm) platform
3    * =============================================================
4    *
5    * (C) Copyright 2004-2006, by Volker Berlin.
6    *
7    * Project Info:  http://www.smallsql.de/
8    *
9    * This library is free software; you can redistribute it and/or modify it 
10   * under the terms of the GNU Lesser General Public License as published by 
11   * the Free Software Foundation; either version 2.1 of the License, or 
12   * (at your option) any later version.
13   *
14   * This library is distributed in the hope that it will be useful, but 
15   * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
16   * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 
17   * License for more details.
18   *
19   * You should have received a copy of the GNU Lesser General Public
20   * License along with this library; if not, write to the Free Software
21   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, 
22   * USA.  
23   *
24   * [Java is a trademark or registered trademark of Sun Microsystems, Inc. 
25   * in the United States and other countries.]
26   *
27   * ---------------
28   * IndexNode.java
29   * ---------------
30   * Author: Volker Berlin
31   * 
32   */
33  package smallsql.database;
34  
35  import java.sql.*;
36  
37  /**
38   * @author Volker Berlin
39   */
40  class IndexNode {
41      final private boolean unique;
42      final private char digit; // unsigned short
43      
44      static final private IndexNode[] EMPTY_NODES = new IndexNode[0];
45      /**
46       * Can be a PageIndex to the next page or a byte[] with rest data of the key.
47       */
48      private IndexNode[] nodes = EMPTY_NODES;
49      
50      /** 
51       * On this point of the tree there is no other value. There is only one value.
52       * That's the tree is cut here and the single value is saved. This is very large
53       * benefit if you have large strings and you can difference it with the 
54       * first characters. 
55       */
56      private char[] remainderKey;
57  
58      /**
59       * Can save a Long, LongList with a rowOffset value or a IndexNode of the next root index.
60       */
61      private Object   value;
62  
63      /**
64       * The status array save the status of the digits. The follow table descript all valid combinations.<p><code>
65       * nodes     value         status
66       * ------------------------------------
67       * null      null          NO_ENTRY
68       * IndexNode null          NODE
69       * byte[]    Long/LongList REMAINDER_VALUE
70       * null      Long/LongList FINAL_VALUE
71       * IndexNode Long/LongList FINAL_VALUE + NODE
72       * null      IndexNode     ROOT
73       * byte[]    IndexNode     REMAINDER_VALUE + ROOT
74       * IndexNode IndexNode     NODE + ROOT
75       * 
76       * </code>
77       */
78      
79      /**
80       * Create a new Node in the Index. Do not call this constructor directly 
81       * else use the factory method <code>createIndexNode</code>.
82       * @param unique descript if it is an unique index (primary key) or a multi value index is.
83       * @see #createIndexNode
84       */
85      protected IndexNode(boolean unique, char digit){
86          this.unique = unique;
87          this.digit  = digit;
88      }
89      
90      
91      /**
92       * Create a new Node in the Index. This is a factory method 
93       * that must be overridden from extended classes.
94       * @param unique descript if it is an unique index (primary key) or a multi value index is.
95       */
96      protected IndexNode createIndexNode(boolean unique, char digit){
97          return new IndexNode(unique, digit);
98      }
99  
100     
101     final char getDigit(){
102         return digit;
103     }
104     
105     
106     final boolean getUnique(){
107         return unique;
108     }
109     
110     
111     /**
112      * Returns the current status for the digit.
113      * @param digit The digit must be in the range 0 between 255. 
114      */
115     final boolean isEmpty(){
116         return nodes == EMPTY_NODES && value == null;
117     }
118     
119     
120     final void clear(){
121         nodes = EMPTY_NODES;
122         value = null;
123         remainderKey = null;
124     }
125     
126     
127     final void clearValue(){
128         value = null;
129     }
130     
131     
132     /**
133      * Returns the current value for the digit.
134      * @param digit The digit must be in the range 0 between 255. 
135      */
136     final Object   getValue(){
137         return value;
138     }
139     
140     
141     final IndexNode[] getChildNodes(){
142         return nodes;
143     }
144     
145     
146     /**
147      * Returns the IndexNode for the node position digit.
148      * @param digit The digit must be in the range 0 between 255. 
149      */
150     final IndexNode getChildNode(char digit){
151         int pos = findNodePos(digit);
152         if(pos >=0) return nodes[pos];
153         return null;
154     }
155     
156     
157     final char[] getRemainderValue(){
158         return remainderKey;
159     }
160     
161     
162     /**
163      * Add a node in the middle of a key value.
164      * @param digit The digit must be in the range 0 between 255. 
165      */
166     final IndexNode addNode(char digit) throws SQLException{
167         if(remainderKey != null) moveRemainderValue();
168         int pos = findNodePos( digit );
169         if(pos == -1){
170             IndexNode node = createIndexNode(unique, digit);
171             saveNode( node );
172             return node;
173         }else{
174             return nodes[pos];
175         }
176     }
177     
178     
179     /**
180      * Remove a node.
181      * @param digit The digit must be in the range 0 between 255. 
182      */
183     final void removeNode(char digit){
184         int pos = findNodePos( digit );
185         if(pos != -1){
186             int length = nodes.length-1;
187             IndexNode[] temp = new IndexNode[length];
188             System.arraycopy(nodes, 0, temp, 0, pos);
189             System.arraycopy(nodes, pos+1, temp, pos, length-pos);
190             nodes = temp;
191         }
192     }
193     
194     
195     /**
196      * Add a node on the end of a key value.
197      * @param digit The digit must be in the range 0 between 255. 
198      * @param rowOffset The value that is saved at the end of the tree.
199      */
200     final void addNode(char digit, long rowOffset) throws SQLException{
201         IndexNode node = addNode(digit);
202         if(node.remainderKey != null) node.moveRemainderValue();
203         node.saveValue(rowOffset);
204     }
205     
206     
207     /**
208      * Save the rowOffset on the digit position. This can be used for FINAL_VALUE or REMAINDER_VALUE.
209      * The caller need to verify that there already exist an equals value.
210      * This means that the digit and the remainder is equals.
211      * @param digit The digit must be in the range 0 between 255. 
212      * @param rowOffset The value that is saved in the tree.
213      */
214     final void saveValue(long rowOffset) throws SQLException{
215         if(unique){
216             if(value != null) throw Utils.createSQLException("Duplikate Key");
217             value = new Long  (rowOffset);
218         }else{
219             LongTreeList list = (LongTreeList)value;
220             if(list == null){
221                 value = list = new LongTreeList();
222             }
223             list.add(rowOffset);
224         }
225     }
226     
227 
228     /**
229      * Add a value on a tree node end without roll out the completly tree.
230      * This reduce the size of the tree if there are large enties with a high significance.
231      * for example: 
232      * If you have large strings which are different on the on the first 3 charchters. 
233      * Then you need only a tree size of 3. 
234      * @param digit      The digit must be in the range 0 between 255.
235      * @param rowOffset  The result value. This is the value that is saved in the tree.
236      * @param value      The key value.
237      * @param digitCount The count of digits from value that need to indexing in the tree. 
238      *                   The range is from 1 to 3;  
239      */
240     final void addRemainderKey(long rowOffset, long remainderValue, int charCount) throws SQLException{
241         saveRemainderValue(remainderValue, charCount);
242         value = (unique) ? (Object  )new Long  (rowOffset) : new LongTreeList(rowOffset);
243     }
244     
245     
246     final void addRemainderKey(long rowOffset, char[] remainderValue, int offset) throws SQLException{
247         saveRemainderValue(remainderValue, offset);
248         value = (unique) ? (Object  )new Long  (rowOffset) : new LongTreeList(rowOffset);
249     }
250     
251     
252     /**
253      * Add a new root index on the position of digit at the end of the tree. 
254      * This is needed for multi columns index at the end of the first (not last)
255      * column key value.
256      * @param digit The digit must be in the range 0 between 255. 
257      */
258     final IndexNode addRoot(char digit) throws SQLException{
259         IndexNode node = addNode(digit);
260         if(node.remainderKey != null) node.moveRemainderValue();
261         return node.addRoot();
262     }
263     
264     
265     final IndexNode addRootValue(char[] remainderValue, int offset) throws SQLException{
266         saveRemainderValue(remainderValue, offset);
267         return addRoot();
268     }
269     
270     
271     final IndexNode addRootValue( long remainderValue, int digitCount) throws SQLException{
272         saveRemainderValue(remainderValue, digitCount);
273         return addRoot();
274     }
275     
276     
277     /**
278      * Move a REMAINDER_VALUE node to the next node level.
279      * @param digit
280      * @throws SQLException
281      */
282     private final void moveRemainderValue() throws SQLException{
283         Object   rowOffset = value;
284         char[] puffer = remainderKey;
285         value = null;
286         remainderKey = null;
287         IndexNode newNode = addNode(puffer[0]);
288         if(puffer.length == 1){
289             newNode.value  = rowOffset;
290         }else{
291             newNode.moveRemainderValueSub( rowOffset, puffer);
292         }
293     }
294     
295     
296     private final void moveRemainderValueSub( Object   rowOffset, char[] remainderValue){
297         int length = remainderValue.length-1;
298         this.remainderKey = new char[length];
299         value = rowOffset;
300         System.arraycopy( remainderValue, 1, this.remainderKey, 0, length);
301     }
302     
303 
304     private final void saveRemainderValue(char[] remainderValue, int offset){
305         int length = remainderValue.length-offset;
306         this.remainderKey = new char[length];
307         System.arraycopy( remainderValue, offset, this.remainderKey, 0, length);
308     }
309     
310     
311     private final void saveRemainderValue( long remainderValue, int charCount){
312         this.remainderKey = new char[charCount];
313         for(int i=charCount-1, d=0; i>=0; i--){
314             this.remainderKey[d++] = (char)(remainderValue >> (i<<4));
315         }
316     }
317     
318     /**
319      * Return the root IndexNode for the digit. If does not exists then it create one. 
320      * @param digit
321      */
322     final IndexNode addRoot() throws SQLException{
323         IndexNode root = (IndexNode)value;
324         if(root == null){
325             value = root = createIndexNode(unique, (char)-1);
326         }
327         return root;
328     }
329     
330     
331     private final void saveNode(IndexNode node){
332         int length = nodes.length;
333         IndexNode[] temp = new IndexNode[length+1];
334         if(length == 0){
335             temp[0] = node;
336         }else{
337             int pos = findNodeInsertPos( node.digit, 0, length);
338             System.arraycopy(nodes, 0, temp, 0, pos);
339             System.arraycopy(nodes, pos, temp, pos+1, length-pos);
340             temp[pos] = node;
341         }
342         nodes = temp;
343     }
344     
345     
346     private final int findNodeInsertPos(char digit, int start, int end){
347         if(start == end) return start;
348         int mid = start + (end - start)/2;
349         char nodeDigit = nodes[mid].digit;
350         if(nodeDigit == digit) return mid;
351         if(nodeDigit < digit){
352             return findNodeInsertPos( digit, mid+1, end );
353         }else{
354             if(start == mid) return start;
355             return findNodeInsertPos( digit, start, mid );
356         }
357     }
358     
359 
360     private final int findNodePos(char digit){
361         return findNodePos(digit, 0, nodes.length);
362     }
363     
364 
365     private final int findNodePos(char digit, int start, int end){
366         if(start == nodes.length) return -1;
367         int mid = start + (end - start)/2;
368         char nodeDigit = nodes[mid].digit;
369         if(nodeDigit == digit) return mid;
370         if(nodeDigit < digit){
371             return findNodePos( digit, mid+1, end );
372         }else{
373             if(start == mid) return -1;
374             return findNodePos( digit, start, mid-1 );
375         }
376     }
377     
378     
379     void save(MemoryStream output){
380         output.writeShort(digit);
381         
382         int length = remainderKey == null ? 0 : remainderKey.length;
383         output.writeInt(length);
384         if(length>0) output.writeChars(remainderKey);
385         
386         if(value == null){
387             output.writeByte(0);
388         }else
389         if(value instanceof Long  ){
390             output.writeByte(1);
391             output.writeLong( ((Long  )value).longValue() );
392         }else
393         if(value instanceof LongTreeList){
394             output.writeByte(2);
395             ((LongTreeList)value).save(output);
396         }else
397         if(value instanceof IndexNode){
398             output.writeByte(3);
399             ((IndexNode)value).saveRef(output);
400         }
401         
402         output.writeShort(nodes.length);
403         for(int i=0; i<nodes.length; i++){
404             nodes[i].saveRef( output );
405         }
406 
407     }
408     
409     
410     
411     void saveRef(MemoryStream output){
412         
413     }
414     
415     
416     static IndexNode loadRef( long offset ){
417         throw new Error  ();
418     }
419     
420     
421     void load(MemoryStream input) throws SQLException{
422         int length = input.readInt();
423         remainderKey = (length>0) ? input.readChars(length) : null;
424         
425         int valueType = input.readByte();
426         switch(valueType){
427             case 0:
428                 value = null;
429                 break;
430             case 1:
431                 value = new Long  (input.readLong());
432                 break;
433             case 2:
434                 value = new LongTreeList(input);
435                 break;
436             case 3:
437                 value = IndexNode.loadRef( input.readLong());
438                 break;
439             default: throw Utils.createSQLException("Error in loading Index. Index fils is corrupt. ("+valueType+")");
440         }
441         
442         nodes = new IndexNode[input.readShort()];
443         for(int i=0; i<nodes.length; i++){
444             nodes[i] = loadRef( input.readLong() );
445         }
446     }
447     
448 
449 }
450
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags