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

COVERAGE SUMMARY FOR SOURCE FILE [LongTreeList.java]

nameclass, %method, %block, %line, %
LongTreeList.java100% (1/1)67%  (14/21)66%  (700/1058)59%  (144,4/246)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class LongTreeList100% (1/1)67%  (14/21)66%  (700/1058)59%  (144,4/246)
LongTreeList (MemoryStream): void 0%   (0/1)0%   (0/11)0%   (0/4)
getSize (): int 0%   (0/1)0%   (0/3)0%   (0/1)
loopToEndOfNode (LongTreeListEnum): void 0%   (0/1)0%   (0/43)0%   (0/12)
remove (long): void 0%   (0/1)0%   (0/127)0%   (0/47)
removeNode (): void 0%   (0/1)0%   (0/34)0%   (0/6)
removeNodeLastLevel (): void 0%   (0/1)0%   (0/32)0%   (0/6)
save (MemoryStream): void 0%   (0/1)0%   (0/12)0%   (0/3)
getPrevious (LongTreeListEnum): long 100% (1/1)42%  (49/118)44%  (11,8/27)
resize (): void 100% (1/1)71%  (25/35)75%  (6/8)
setPreviousOffset (LongTreeListEnum): void 100% (1/1)92%  (46/50)82%  (9/11)
add (long): void 100% (1/1)94%  (143/152)95%  (37/39)
correctPointers (int, int, int, int): void 100% (1/1)98%  (81/83)95%  (21,8/23)
getNext (LongTreeListEnum): long 100% (1/1)98%  (114/116)99%  (23,8/24)
LongTreeList (): void 100% (1/1)100% (7/7)100% (3/3)
LongTreeList (long): void 100% (1/1)100% (6/6)100% (3/3)
getPointer (): int 100% (1/1)100% (30/30)100% (5/5)
getUnsignedShort (): int 100% (1/1)100% (28/28)100% (1/1)
insertNode (int): int 100% (1/1)100% (76/76)100% (10/10)
insertNodeLastLevel (int): void 100% (1/1)100% (45/45)100% (7/7)
writePointer (int): void 100% (1/1)100% (23/23)100% (3/3)
writeShort (int): void 100% (1/1)100% (27/27)100% (3/3)

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 * LongTreeList.java
29 * ---------------
30 * Author: Volker Berlin
31 * 
32 */
33package smallsql.database;
34 
35import java.sql.*;
36 
37/**
38 * This class is used to save the row posistions (RowID) list for a not unique index.
39 *
40 * Te values for RowID are long (8 byte). The value differ around the row size. The
41 * minimum row size is 30 byte. We calculate a medium row size of 100 bytes.
42 *   
43 * We used a tree to compress and sort the list. We save the long value in 4 levels
44 * a 2 bytes. The first tree levels has a pointer to the next level. The end point 
45 * of a level is the value 0. A value of 0 at first in a level means the value 0. 
46 * The end point can only occur at second or later position and not on first position. 
47 * 
48 * 
49 * @author Volker Berlin
50 *
51 */
52final class LongTreeList {
53        
54        
55        /*void list(){
56                System.out.println("=========== size:"+size);
57                LongTreeListEnum listEnum = new LongTreeListEnum();
58                listEnum.reset();
59                
60                long value;
61                do{
62                        value = getNext(listEnum);
63                        System.out.println(value);
64                }while(value >0);
65                do{
66                        value = getPrevious(listEnum);
67                        System.out.println(value);
68                }while(value >0);
69        }
70        static public void main1(String[] argc) throws Exception{
71                LongTreeList list = new LongTreeList();
72                list.add( Long.MAX_VALUE/2 );
73                list.list();
74                list.add( Long.MAX_VALUE );
75                list.list();
76                list.remove( Long.MAX_VALUE/2 );
77                list.list();
78                list.add( 12345L );
79                list.list();
80                list.add( 123L );
81                list.list();
82                list.add( 12345678L );
83                list.list();
84                list.add( 12L );
85                list.list();
86                list.add( 1234L );
87                list.list();
88                list.add( 123456L );
89                list.list();
90                list.add( 1234567L );
91                list.list();
92                list.add( 123456789L );
93                list.list();
94                list.add( 123456790L );                
95                list.list();
96                list.add( 1L );
97                list.list();
98        }
99 
100        
101        static public void main(String[] argc) throws Exception{
102                java.util.Random random = new java.util.Random();
103                LongTreeList treeList = new LongTreeList();
104                java.util.ArrayList plainList = new java.util.ArrayList(); 
105                LongTreeListEnum listEnum = new LongTreeListEnum();
106                
107                
108                for(int i=1; i<1000; i++){
109                        long value;
110                        
111                        value = Math.abs(random.nextLong()) >> 6;
112                        //System.out.println(value+"  "+treeList.size);
113                        treeList.add(value);
114                        plainList.add(new Long(value));
115                
116                        test(treeList, listEnum, plainList);
117                        
118                        if( i % 2 == 0){
119                                int idx = Math.abs(random.nextInt()) % plainList.size();
120                                value = ((Long)plainList.get( idx )).longValue();
121                                treeList.remove(value);
122                                plainList.remove(idx);
123                                
124                                test(treeList, listEnum, plainList);                                
125                        }
126                }
127        }
128        
129        static void test(LongTreeList treeList, LongTreeListEnum listEnum, java.util.ArrayList plainList){ 
130                        listEnum.reset();
131                        int size = plainList.size();
132                        int count = 0;
133                        long value2, value = -1;
134                        do{
135                                value2 = value;
136                                value = treeList.getNext(listEnum);        
137                                if(value <0)break;
138                                if(value <= value2) throw new RuntimeException("wrong sort order:"+value+" and:"+value2);
139                                if(!plainList.contains(new Long(value))) throw new RuntimeException("wrong value:"+value);
140                                count++;
141                        }while(true);
142                        if(count != size) throw new RuntimeException("soll count:"+size+"   ist count:"+count);
143                        
144                        value = Long.MAX_VALUE;
145                        do{
146                                value2 = value;
147                                value = treeList.getPrevious(listEnum);
148                                if(value <0)break;
149                                if(value >= value2) throw new RuntimeException("wrong sort order:"+value+" and:"+value2);
150                                if(!plainList.contains(new Long(value))) throw new RuntimeException("wrong value:"+value);
151                                count--;
152                        }while(true);
153                        if(count != 0) throw new RuntimeException("Prevous count is wrong:"+count);
154        }*/
155        
156 
157        private byte[] data;
158        private int size;
159        private int offset;
160        static final private int pointerSize = 3; //if change then also in resize()
161        
162        /**
163         * Create a empty LongTreeList.
164         *
165         */
166        LongTreeList(){
167                data = new byte[25];
168        }
169        
170        /**
171         * Create a LongTreeList with a first value.
172         * @param value
173         */
174        LongTreeList(long value) throws SQLException{
175                this();
176                add(value);
177        }
178        
179        /**
180         * Restore a LongTreeList from a MemoryStream.
181         */
182        LongTreeList(MemoryStream input) throws SQLException{
183                int size = input.readInt();
184                data     = input.readBytes(size);
185        }
186        
187        
188        /**
189         * Save this list to a serial stream. This can be used to save it on a harddisk.
190         * @param output
191         */
192        final void save(MemoryStream output){
193                output.writeInt(size);
194                output.writeBytes(data, 0, size);
195        }
196        
197 
198        /**
199         * Add a value to this list.
200         * @param value
201         * @throws SQLException
202         */
203        final void add(long value) throws SQLException{
204                offset = 0;
205                if(size == 0){
206                        writeShort( (int)(value >> 48) );
207                        writePointer ( offset+pointerSize+2 );
208                        writeShort( 0 );
209                        writeShort( (int)(value >> 32) );
210                        writePointer ( offset+pointerSize+2 );
211                        writeShort( 0 );
212                        writeShort( (int)(value >> 16) );
213                        writePointer ( offset+pointerSize+2 );
214                        writeShort( 0 );
215                        writeShort( (int)(value) );
216                        writeShort( 0 );
217                        size = offset;
218                        return;
219                }
220                int shift = 48;
221                boolean firstNode = (size > 2); // if this the first node in this tree level (0 can be the first node and are the end of the level)
222                while(shift>=0){
223                        int octet = (int)(value >> shift) & 0xFFFF;
224                        while(true){
225                                int nextEntry = getUnsignedShort();
226                                if(nextEntry == octet){
227                                        if(shift == 0) return; //value exist allready, this case should not occur
228                                        offset = getPointer();
229                                        firstNode = true;
230                                        break;
231                                }
232                                if((nextEntry == 0 && !firstNode) || nextEntry > octet){
233                                        offset -= 2;
234                                        while(true){
235                                                if(shift != 0){
236                                                        offset = insertNode(octet);                                                
237                                                }else{
238                                                        insertNodeLastLevel(octet);        
239                                                        return;
240                                                }
241                                                shift -= 16;
242                                                octet = (int)(value >> shift) & 0xFFFF;
243                                        }
244                                }
245                                firstNode = false;
246                                if(shift != 0) offset += pointerSize;
247                        }
248                        shift -= 16;
249                }
250        }
251        
252        
253        /**
254         * Remove a value from this list.
255         * @param value
256         * @throws SQLException
257         */
258        final void remove(long value) throws SQLException{
259                if(size == 0) return;
260                int offset1 = 0;
261                int offset2 = 0;
262                int offset3 = 0;
263                offset = 0;
264                int shift = 48;
265                boolean firstNode = true; // if this the first node in this tree level (0 can be the first node and are the end of the level)
266                boolean firstNode1 = true;
267                boolean firstNode2 = true;
268                boolean firstNode3 = true;
269                while(shift>=0){
270                        int octet = (int)(value >> shift) & 0xFFFF;
271                        while(true){
272                                int nextEntry = getUnsignedShort();
273                                if(nextEntry == octet){
274                                        if(shift == 0){
275                                                //value find
276                                                offset -= 2;
277                                                removeNodeLastLevel();
278                                                while(firstNode && getUnsignedShort() == 0){
279                                                        offset -= 2;
280                                                        removeNodeLastLevel(); // the end 0 of a node
281                                                        if(shift >= 3) 
282                                                                break;
283                                                        offset = offset1;
284                                                        offset1 = offset2;
285                                                        offset2 = offset3;
286                                                        firstNode = firstNode1;
287                                                        firstNode1 = firstNode2;
288                                                        firstNode2 = firstNode3;
289                                                        removeNode();
290                                                        shift++;
291                                                }
292                                                return;
293                                        }
294                                        offset3 = offset2;
295                                        offset2 = offset1;
296                                        offset1 = offset -2;
297                                        offset = getPointer();
298                                        firstNode3 = firstNode2;
299                                        firstNode2 = firstNode1;
300                                        firstNode1 = firstNode;
301                                        firstNode = true;
302                                        break;
303                                }
304                                if((nextEntry == 0 && !firstNode) || nextEntry > octet){
305                                        //value is not in the list, this should not occur
306                                        return;
307                                }
308                                firstNode = false;
309                                if(shift != 0) offset += pointerSize;
310                        }
311                        shift -= 16;
312                }
313        }
314        
315 
316        /**
317         * Get the next long value from this list.
318         * @return
319         */
320        final long getNext(LongTreeListEnum listEnum){
321                int shift = (3-listEnum.stack) << 4;
322                if(shift >= 64) return -1; //a previous call has return -1
323                offset                 = listEnum.offsetStack[listEnum.stack];
324                long result = listEnum.resultStack[listEnum.stack];
325                boolean firstNode = (offset == 0); // true if it the first entry in a level
326                while(true){
327                        int nextEntry = getUnsignedShort();
328                        if(nextEntry != 0 || firstNode){
329                                //there are more entries in this node
330                                result |= (((long)nextEntry) << shift);
331                                if(listEnum.stack>=3){
332                                        listEnum.offsetStack[listEnum.stack] = offset;
333                                        return result;
334                                }
335                                listEnum.offsetStack[listEnum.stack] = offset+pointerSize;
336                                offset = getPointer();
337                                shift -= 16;
338                                listEnum.stack++;
339                                listEnum.resultStack[listEnum.stack] = result;
340                                firstNode = true;
341                        }else{
342                                //no more entries in this node
343                                shift += 16;
344                                listEnum.stack--;
345                                if(listEnum.stack<0) return -1; // no more entries
346                                result = listEnum.resultStack[listEnum.stack];
347                                offset = listEnum.offsetStack[listEnum.stack];
348                                firstNode = false;
349                        }
350                }
351        }
352 
353        
354        /**
355         * Get the next long value from this list.
356         * @return
357         */
358        final long getPrevious(LongTreeListEnum listEnum){
359                int shift = (3-listEnum.stack) << 4;
360                if(shift >= 64){ //a previous call of getNext() has return -1
361                        shift = 48;
362                        offset = 0;
363                        listEnum.stack = 0;
364                        listEnum.offsetStack[0] = 2 + pointerSize;
365                        loopToEndOfNode(listEnum);
366                }else{
367                        setPreviousOffset(listEnum);
368                }
369                long result = listEnum.resultStack[listEnum.stack];
370                while(true){
371                        int nextEntry = (offset < 0) ? -1 : getUnsignedShort();
372                        if(nextEntry >= 0){
373                                // there are more entries in this node
374                                result |= (((long)nextEntry) << shift);
375                                if(listEnum.stack>=3){
376                                        listEnum.offsetStack[listEnum.stack] = offset;
377                                        return result;
378                                }
379                                listEnum.offsetStack[listEnum.stack] = offset+pointerSize;
380                                offset = getPointer();
381                                shift -= 16;
382                                listEnum.stack++;
383                                listEnum.resultStack[listEnum.stack] = result;
384                                loopToEndOfNode(listEnum);
385                        }else{
386                                //no more entries in this node
387                                shift += 16;
388                                listEnum.stack--;
389                                if(listEnum.stack<0) return -1; // no more entries
390                                result = listEnum.resultStack[listEnum.stack];
391                                setPreviousOffset(listEnum);
392                        }
393                }
394        }
395        
396        
397        /**
398         * Is used from getPrevious(). It set the offset of the previous entry.
399         * If there is no previous entry in this node then set it to -1.
400         * The problem is that "enum" point to the next postion to optimize getNext().
401         * We need 2 steps forward to find the previous entry. It can occur that
402         * we are in onather node. We need to verify it with the startpoint of the current node.
403         */
404        final private void setPreviousOffset(LongTreeListEnum listEnum){
405                int previousOffset = listEnum.offsetStack[listEnum.stack] - 2*(2 + (listEnum.stack>=3 ? 0 : pointerSize));
406                if(listEnum.stack == 0){
407                        offset = previousOffset;
408                        return;
409                }
410                offset = listEnum.offsetStack[listEnum.stack-1] - pointerSize;
411                int pointer = getPointer();
412                if(pointer <= previousOffset){
413                        offset = previousOffset;
414                        return;
415                }
416                offset = -1;
417        }
418        
419        
420        /**
421         * Loop to the last entry in this node. Is used from getPrevious().
422         */
423        final private void loopToEndOfNode(LongTreeListEnum listEnum){
424                int nextEntry;
425                int nextOffset1, nextOffset2;
426                nextOffset1 = offset;
427                offset += 2;
428                if(listEnum.stack<3)
429                        offset += pointerSize;
430                do{
431                        nextOffset2 = nextOffset1;
432                        nextOffset1 = offset;
433                        nextEntry = getUnsignedShort();
434                        if(listEnum.stack<3)
435                                offset += pointerSize;
436                }while(nextEntry != 0);
437                offset = nextOffset2;
438        }
439        
440        
441        
442 
443        /**
444         * Insert a octet entry on the current offset for one of the first 3 levels. 
445         * After it create a new node at the end (simple two 0). 
446         * Then set it the pointer in the new entry to the new node 
447         * @param octet a short value
448         * @return the offset of the new node.
449         */
450        final private int insertNode(int octet) throws SQLException{
451                int oldOffset = offset;
452                
453                if(data.length < size + 4 + pointerSize) resize();
454                System.arraycopy(data, oldOffset, data, oldOffset + 2+pointerSize, size-oldOffset);
455                size += 2+pointerSize;
456 
457                writeShort( octet );
458                writePointer( size );
459 
460                //correct all offset that point behind the new node
461                correctPointers( 0, oldOffset, 2+pointerSize, 0 );
462                
463                data[size++] = (byte)0;
464                data[size++] = (byte)0;
465                return size-2;
466        }
467        
468                
469        /**
470         * Insert the octet of the last level (4 level) on the current offset. 
471         * This level does not include a pointer to a next level.
472         * @param octet a short value
473         */
474        final private void insertNodeLastLevel(int octet) throws SQLException{
475                int oldOffset = offset;
476                                
477                if(data.length < size + 2) resize();
478                System.arraycopy(data, offset, data, offset + 2, size-offset);
479                size += 2;
480                writeShort( octet );
481                
482                //correct all offset before this new node that point behind the new node
483                correctPointers( 0, oldOffset, 2, 0 );        
484        }
485        
486        
487        /**
488         * Remove a octet entry on the current offset for one of the first 3 levels. 
489         * Then set it the pointer in the new entry to the new node 
490         * @param octet a short value
491         */
492        final private void removeNode() throws SQLException{
493                int oldOffset = offset;
494                
495                //correct all offset that point behind the old node
496                correctPointers( 0, oldOffset, -(2+pointerSize), 0 );
497 
498                size -= 2+pointerSize;
499                System.arraycopy(data, oldOffset + 2+pointerSize, data, oldOffset, size-oldOffset);
500 
501                offset = oldOffset;
502        }
503        
504        
505        /**
506         * Remove a octet entry on the current offset for one of the first 3 levels. 
507         * Then set it the pointer in the new entry to the new node 
508         * @param octet a short value
509         */
510        final private void removeNodeLastLevel() throws SQLException{
511                int oldOffset = offset;
512                
513                //correct all offset that point behind the old node
514                correctPointers( 0, oldOffset, -2, 0 );
515 
516                size -= 2;
517                System.arraycopy(data, oldOffset + 2, data, oldOffset, size-oldOffset);
518 
519                offset = oldOffset;
520        }
521        
522        
523        /**
524         * Correct all pointers that point behind a new entry.
525         * @param startOffset the startoffset of the current node
526         * @param oldOffset the offset of the new entry, only pointer that point behind it need to correct.
527         * @param diff the differenz that need added to the pointers
528         * @param level the stack level. There are only 3 levels with pointers.
529         */
530        final private void correctPointers(int startOffset, int oldOffset, int diff, int level){
531                offset = startOffset;
532                boolean firstNode = true;
533                while(offset < size){
534                        if(offset == oldOffset){
535                                int absDiff = Math.abs(diff);
536                                if(absDiff == 2) return;
537                                offset += absDiff;
538                                firstNode = false;
539                                continue;
540                        }
541                        int value = getUnsignedShort();
542                        if(value != 0 || firstNode){
543                                int pointer = getPointer();
544                                if(pointer > oldOffset){
545                                        offset  -= pointerSize;
546                                        writePointer( pointer + diff );
547                                        if(diff > 0) pointer += diff;
548                                }                                
549                                if(level < 2){
550                                        startOffset = offset;
551                                        correctPointers( pointer, oldOffset, diff, level+1);
552                                        offset = startOffset;
553                                }
554                                firstNode = false;
555                        }else{
556                                return;
557                        }
558                }
559        }
560        
561                
562        /**
563         * Read a pointer to another node in de index.
564         */
565        final private int getPointer(){
566                int value = 0;
567                for(int i=0; i<pointerSize; i++){
568                        value <<= 8;
569                        value += (data[offset++] & 0xFF);
570                }
571                return value;
572        }
573        
574        
575        /**
576         * Write a pointer to another node in the tree list. The size depends from the constant pointerSize.
577         */
578        final private void writePointer(int value){
579                for(int i=pointerSize-1; i>=0; i--){
580                        data[offset++] = (byte)(value >> (i*8));
581                }
582        }
583 
584        
585        /**
586         * Read a short value from the index.
587         */
588        final private int getUnsignedShort(){
589                return ((data[ offset++ ] & 0xFF) << 8) | (data[ offset++ ] & 0xFF);
590        }
591        
592        
593        /**
594         * Save a short value in the index. The long values are saved in 4 short values-
595         * @param value
596         */
597        final private void writeShort(int value){
598                data[offset++] = (byte)(value >> 8);
599                data[offset++] = (byte)(value);
600        }
601        
602        
603        /**
604         * Increment the buffer size for the list.
605         */
606        private final void resize() throws SQLException{
607                int newsize = data.length << 1;
608                if(newsize > 0xFFFFFF){ //see pointerSize
609                        newsize = 0xFFFFFF;
610                        if(newsize == data.length) throw Utils.createSQLException("To many equals entry in Index.");
611                }
612                byte[] temp = new byte[newsize];
613                System.arraycopy(data, 0, temp, 0, data.length);
614                data = temp;
615        }
616 
617        final int getSize() {
618                return size;
619        }
620}

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