LongTreeList


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   */
33  package smallsql.database;
34  
35  import 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   */
52  final 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){
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 already, 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 }
621
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags