EMMA Coverage Report (generated Wed Jun 28 19:54:35 CEST 2006)
[all classes][smallsql.database]

COVERAGE SUMMARY FOR SOURCE FILE [IndexNode.java]

nameclass, %method, %block, %line, %
IndexNode.java100% (1/1)79%  (26/33)68%  (462/677)68%  (103,4/153)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class IndexNode100% (1/1)79%  (26/33)68%  (462/677)68%  (103,4/153)
clearValue (): void 0%   (0/1)0%   (0/4)0%   (0/2)
getDigit (): char 0%   (0/1)0%   (0/3)0%   (0/1)
load (MemoryStream): void 0%   (0/1)0%   (0/70)0%   (0/17)
loadRef (MemoryStream): IndexNode 0%   (0/1)0%   (0/4)0%   (0/1)
removeNode (char): void 0%   (0/1)0%   (0/38)0%   (0/8)
save (MemoryStream): void 0%   (0/1)0%   (0/90)0%   (0/19)
saveRef (MemoryStream): void 0%   (0/1)0%   (0/1)0%   (0/1)
saveValue (long): void 100% (1/1)91%  (30/33)94%  (7,5/8)
findNodeInsertPos (char, int, int): int 100% (1/1)96%  (44/46)99%  (7,9/8)
<static initializer> 100% (1/1)100% (4/4)100% (2/2)
IndexNode (boolean, char): void 100% (1/1)100% (12/12)100% (5/5)
addNode (char): IndexNode 100% (1/1)100% (29/29)100% (7/7)
addNode (char, long): void 100% (1/1)100% (13/13)100% (4/4)
addRemainderKey (long, char [], int): void 100% (1/1)100% (19/19)100% (3/3)
addRemainderKey (long, long, int): void 100% (1/1)100% (19/19)100% (3/3)
addRoot (): IndexNode 100% (1/1)100% (18/18)100% (4/4)
addRoot (char): IndexNode 100% (1/1)100% (12/12)100% (3/3)
addRootValue (char [], int): IndexNode 100% (1/1)100% (7/7)100% (2/2)
addRootValue (long, int): IndexNode 100% (1/1)100% (7/7)100% (2/2)
clear (): void 100% (1/1)100% (10/10)100% (4/4)
findNodePos (char): int 100% (1/1)100% (8/8)100% (1/1)
findNodePos (char, int, int): int 100% (1/1)100% (50/50)100% (8/8)
getChildNode (char): IndexNode 100% (1/1)100% (13/13)100% (3/3)
getChildNodes (): IndexNode [] 100% (1/1)100% (3/3)100% (1/1)
getRemainderValue (): char [] 100% (1/1)100% (3/3)100% (1/1)
getUnique (): boolean 100% (1/1)100% (3/3)100% (1/1)
getValue (): Object 100% (1/1)100% (3/3)100% (1/1)
isEmpty (): boolean 100% (1/1)100% (11/11)100% (1/1)
moveRemainderValue (): void 100% (1/1)100% (31/31)100% (9/9)
moveRemainderValueSub (Object, char []): void 100% (1/1)100% (20/20)100% (5/5)
saveNode (IndexNode): void 100% (1/1)100% (49/49)100% (10/10)
saveRemainderValue (char [], int): void 100% (1/1)100% (17/17)100% (4/4)
saveRemainderValue (long, int): void 100% (1/1)100% (27/27)100% (4/4)

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 */
33package smallsql.database;
34 
35import java.sql.*;
36 
37/**
38 * @author Volker Berlin
39 */
40class 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.
81         * @param unique descript if it is a unique index (primary key) or a multi value index is.
82         */
83        IndexNode(boolean unique, char digit){
84                this.unique = unique;
85                this.digit  = digit;
86        }
87 
88        
89        final char getDigit(){
90                return digit;
91        }
92        
93        
94        final boolean getUnique(){
95                return unique;
96        }
97        
98        
99        /**
100         * Returns the current status for the digit.
101         * @param digit The digit must be in the range 0 between 255. 
102         */
103        final boolean isEmpty(){
104                return nodes == EMPTY_NODES && value == null;
105        }
106        
107        
108        final void clear(){
109                nodes = EMPTY_NODES;
110                value = null;
111                remainderKey = null;
112        }
113        
114        
115        final void clearValue(){
116                value = null;
117        }
118        
119        
120        /**
121         * Returns the current value for the digit.
122         * @param digit The digit must be in the range 0 between 255. 
123         */
124        final Object getValue(){
125                return value;
126        }
127        
128        
129        final IndexNode[] getChildNodes(){
130                return nodes;
131        }
132        
133        
134        /**
135         * Returns the IndexNode for the node position digit.
136         * @param digit The digit must be in the range 0 between 255. 
137         */
138        final IndexNode getChildNode(char digit){
139                int pos = findNodePos(digit);
140                if(pos >=0) return nodes[pos];
141                return null;
142        }
143        
144        
145        final char[] getRemainderValue(){
146                return remainderKey;
147        }
148        
149        
150        /**
151         * Add a node in the middle of a key value.
152         * @param digit The digit must be in the range 0 between 255. 
153         */
154        final IndexNode addNode(char digit) throws SQLException{
155                if(remainderKey != null) moveRemainderValue();
156                int pos = findNodePos( digit );
157                if(pos == -1){
158                        IndexNode node = new IndexNode(unique, digit);
159                        saveNode( node );
160                        return node;
161                }else{
162                        return nodes[pos];
163                }
164        }
165        
166        
167        /**
168         * Remove a node.
169         * @param digit The digit must be in the range 0 between 255. 
170         */
171        final void removeNode(char digit){
172                int pos = findNodePos( digit );
173                if(pos != -1){
174                        int length = nodes.length-1;
175                        IndexNode[] temp = new IndexNode[length];
176                        System.arraycopy(nodes, 0, temp, 0, pos);
177                        System.arraycopy(nodes, pos+1, temp, pos, length-pos);
178                        nodes = temp;
179                }
180        }
181        
182        
183        /**
184         * Add a node on the end of a key value.
185         * @param digit The digit must be in the range 0 between 255. 
186         * @param rowOffset The value that is saved at the end of the tree.
187         */
188        final void addNode(char digit, long rowOffset) throws SQLException{
189                IndexNode node = addNode(digit);
190                if(node.remainderKey != null) node.moveRemainderValue();
191                node.saveValue(rowOffset);
192        }
193        
194        
195        /**
196         * Save the rowOffset on the digit position. This can be used for FINAL_VALUE or REMAINDER_VALUE.
197         * The caller need to verify that there allready exist an equals value.
198         * This means that the digit and the remainder is equals.
199         * @param digit The digit must be in the range 0 between 255. 
200         * @param rowOffset The value that is saved in the tree.
201         */
202        final void saveValue(long rowOffset) throws SQLException{
203                if(unique){
204                        if(value != null) throw Utils.createSQLException("Duplikate Key");
205                        value = new Long(rowOffset);
206                }else{
207                        LongTreeList list = (LongTreeList)value;
208                        if(list == null){
209                                value = list = new LongTreeList();
210                        }
211                        list.add(rowOffset);
212                }
213        }
214        
215 
216        /**
217         * Add a value on a tree node end without roll out the completly tree.
218         * This reduce the size of the tree if there are large enties with a high significance.
219         * for example: 
220         * If you have large strings which are different on the on the first 3 charchters. 
221         * Then you need only a tree size of 3. 
222         * @param digit          The digit must be in the range 0 between 255.
223         * @param rowOffset  The result value. This is the value that is saved in the tree.
224         * @param value          The key value.
225         * @param digitCount The count of digits from value that need to indexing in the tree. 
226         *                                          The range is from 1 to 3;  
227         */
228        final void addRemainderKey(long rowOffset, long remainderValue, int charCount) throws SQLException{
229                saveRemainderValue(remainderValue, charCount);
230                value = (unique) ? (Object)new Long(rowOffset) : new LongTreeList(rowOffset);
231        }
232        
233        
234        final void addRemainderKey(long rowOffset, char[] remainderValue, int offset) throws SQLException{
235                saveRemainderValue(remainderValue, offset);
236                value = (unique) ? (Object)new Long(rowOffset) : new LongTreeList(rowOffset);
237        }
238        
239        
240        /**
241         * Add a new root index on the position of digit at the end of the tree. 
242         * This is needed for multi columns index at the end of the first (not last)
243         * column key value.
244         * @param digit The digit must be in the range 0 between 255. 
245         */
246        final IndexNode addRoot(char digit) throws SQLException{
247                IndexNode node = addNode(digit);
248                if(node.remainderKey != null) node.moveRemainderValue();
249                return node.addRoot();
250        }
251        
252        
253        final IndexNode addRootValue(char[] remainderValue, int offset) throws SQLException{
254                saveRemainderValue(remainderValue, offset);
255                return addRoot();
256        }
257        
258        
259        final IndexNode addRootValue( long remainderValue, int digitCount) throws SQLException{
260                saveRemainderValue(remainderValue, digitCount);
261                return addRoot();
262        }
263        
264        
265        /**
266         * Move a REMAINDER_VALUE node to the next node level.
267         * @param digit
268         * @throws SQLException
269         */
270        private final void moveRemainderValue() throws SQLException{
271                Object rowOffset = value;
272                char[] puffer = remainderKey;
273                value = null;
274                remainderKey = null;
275                IndexNode newNode = addNode(puffer[0]);
276                if(puffer.length == 1){
277                        newNode.value  = rowOffset;
278                }else{
279                        newNode.moveRemainderValueSub( rowOffset, puffer);
280                }
281        }
282        
283        
284        private final void moveRemainderValueSub( Object rowOffset, char[] remainderValue){
285                int length = remainderValue.length-1;
286                this.remainderKey = new char[length];
287                value = rowOffset;
288                System.arraycopy( remainderValue, 1, this.remainderKey, 0, length);
289        }
290        
291 
292        private final void saveRemainderValue(char[] remainderValue, int offset){
293                int length = remainderValue.length-offset;
294                this.remainderKey = new char[length];
295                System.arraycopy( remainderValue, offset, this.remainderKey, 0, length);
296        }
297        
298        
299        private final void saveRemainderValue( long remainderValue, int charCount){
300                this.remainderKey = new char[charCount];
301                for(int i=charCount-1, d=0; i>=0; i--){
302                        this.remainderKey[d++] = (char)(remainderValue >> (i<<4));
303                }
304        }
305        
306        /**
307         * Return the root IndexNode for the digit. If does not exists then it create one. 
308         * @param digit
309         */
310        final IndexNode addRoot() throws SQLException{
311                IndexNode root = (IndexNode)value;
312                if(root == null){
313                        value = root = new IndexNode(unique, (char)-1);
314                }
315                return root;
316        }
317        
318        
319        private final void saveNode(IndexNode node){
320                int length = nodes.length;
321                IndexNode[] temp = new IndexNode[length+1];
322                if(length == 0){
323                        temp[0] = node;
324                }else{
325                        int pos = findNodeInsertPos( node.digit, 0, length);
326                        System.arraycopy(nodes, 0, temp, 0, pos);
327                        System.arraycopy(nodes, pos, temp, pos+1, length-pos);
328                        temp[pos] = node;
329                }
330                nodes = temp;
331        }
332        
333        
334        private final int findNodeInsertPos(char digit, int start, int end){
335                if(start == end) return start;
336                int mid = start + (end - start)/2;
337                char nodeDigit = nodes[mid].digit;
338                if(nodeDigit == digit) return mid;
339                if(nodeDigit < digit){
340                        return findNodeInsertPos( digit, mid+1, end );
341                }else{
342                        if(start == mid) return start;
343                        return findNodeInsertPos( digit, start, mid );
344                }
345        }
346        
347 
348        private final int findNodePos(char digit){
349                return findNodePos(digit, 0, nodes.length);
350        }
351        
352 
353        private final int findNodePos(char digit, int start, int end){
354                if(start == nodes.length) return -1;
355                int mid = start + (end - start)/2;
356                char nodeDigit = nodes[mid].digit;
357                if(nodeDigit == digit) return mid;
358                if(nodeDigit < digit){
359                        return findNodePos( digit, mid+1, end );
360                }else{
361                        if(start == mid) return -1;
362                        return findNodePos( digit, start, mid-1 );
363                }
364        }
365        
366        void save(MemoryStream output){
367                output.writeShort(digit);
368                output.writeShort(nodes.length);
369                for(int i=0; i<nodes.length; i++){
370                        output.writeShort( nodes[i].digit );
371                }
372                
373                int length = remainderKey == null ? 0 : remainderKey.length;
374                output.writeInt(length);
375                if(length>0) output.writeChars(remainderKey);
376                
377                if(value == null){
378                        output.writeByte(0);
379                }else
380                if(value instanceof Long){
381                        output.writeByte(1);
382                        output.writeLong( ((Long)value).longValue() );
383                }else
384                if(value instanceof LongTreeList){
385                        output.writeByte(2);
386                        ((LongTreeList)value).save(output);
387                }else
388                if(value instanceof IndexNode){
389                        output.writeByte(3);
390                        ((IndexNode)value).saveRef(output);
391                }
392        }
393        
394        
395        
396        void saveRef(MemoryStream output){
397                
398        }
399        
400        static IndexNode loadRef(MemoryStream input){
401                throw new Error();
402        }
403        
404        void load(MemoryStream input) throws SQLException{
405                /*digit = (char)*/input.readShort();
406                nodes = new IndexNode[input.readShort()];
407                for(int i=0; i<nodes.length; i++){
408                        //output.writeShort( nodes[i].digit );
409                }
410                
411                int length = input.readInt();
412                remainderKey = (length>0) ? input.readChars(length) : null;
413                
414                int valueType = input.readByte();
415                switch(valueType){
416                        case 0:
417                                value = null;
418                                break;
419                        case 1:
420                                value = new Long(input.readLong());
421                                break;
422                        case 2:
423                                value = new LongTreeList(input);
424                                break;
425                        case 3:
426                                value = IndexNode.loadRef(input);
427                                break;
428                        default: throw Utils.createSQLException("Error in loading Index. Index fils is corrupt. ("+valueType+")");
429                }
430        }
431        
432 
433}

[all classes][smallsql.database]
EMMA 2.1.5320 (stable) (C) Vladimir Roubtsov