longtreelist.java

java 数据库 功能强大 效率高 SmallSQL Database is a free DBMS library for the Java(tm) platform. It runs on

/* =============================================================
 * SmallSQL : a free Java DBMS library for the Java(tm) platform
 * =============================================================
 *
 * (C) Copyright 2004-2007, by Volker Berlin.
 *
 * Project Info:  http://www.smallsql.de/
 *
 * This library is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU Lesser General Public License as published by 
 * the Free Software Foundation; either version 2.1 of the License, or 
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, 
 * USA.  
 *
 * [Java is a trademark or registered trademark of Sun Microsystems, Inc. 
 * in the United States and other countries.]
 *
 * ---------------
 * LongTreeList.java
 * ---------------
 * Author: Volker Berlin
 * 
 */
package smallsql.database;

import java.sql.*;

/**
 * This class is used to save the row positions (RowID) list for a not unique index.
 *
 * The values for RowID are long (8 byte). The value differ around the row size. The
 * minimum row size is 30 byte. We calculate a medium row size of 100 bytes.
 *   
 * We used a tree to compress and sort the list. We save the long value in 4 levels
 * a 2 bytes. The first tree levels has a pointer to the next level. The end point 
 * of a level is the value 0. A value of 0 at first in a level means the value 0. 
 * The end point can only occur at second or later position and not on first position. 
 * 
 * 
 * @author Volker Berlin
 *
 */
final class LongTreeList {
	
	
	/*void list(){
		System.out.println("=========== size:"+size);
		LongTreeListEnum listEnum = new LongTreeListEnum();
		listEnum.reset();
		
		long value;
		do{
			value = getNext(listEnum);
			System.out.println(value);
		}while(value >0);
		do{
			value = getPrevious(listEnum);
			System.out.println(value);
		}while(value >0);
	}
	static public void main1(String[] argc) throws Exception{
		LongTreeList list = new LongTreeList();
		list.add( Long.MAX_VALUE/2 );
		list.list();
		list.add( Long.MAX_VALUE );
		list.list();
		list.remove( Long.MAX_VALUE/2 );
		list.list();
		list.add( 12345L );
		list.list();
		list.add( 123L );
		list.list();
		list.add( 12345678L );
		list.list();
		list.add( 12L );
		list.list();
		list.add( 1234L );
		list.list();
		list.add( 123456L );
		list.list();
		list.add( 1234567L );
		list.list();
		list.add( 123456789L );
		list.list();
		list.add( 123456790L );		
		list.list();
		list.add( 1L );
		list.list();
	}

	
	static public void main(String[] argc) throws Exception{
		java.util.Random random = new java.util.Random();
		LongTreeList treeList = new LongTreeList();
		java.util.ArrayList plainList = new java.util.ArrayList(); 
		LongTreeListEnum listEnum = new LongTreeListEnum();
		
		
		for(int i=1; i<1000; i++){
			long value;
			
			value = Math.abs(random.nextLong()) >> 6;
			//System.out.println(value+"  "+treeList.size);
			treeList.add(value);
			plainList.add(new Long(value));
		
			test(treeList, listEnum, plainList);
			
			if( i % 2 == 0){
				int idx = Math.abs(random.nextInt()) % plainList.size();
				value = ((Long)plainList.get( idx )).longValue();
				treeList.remove(value);
				plainList.remove(idx);
				
				test(treeList, listEnum, plainList);				
			}
		}
	}
	
	static void test(LongTreeList treeList, LongTreeListEnum listEnum, java.util.ArrayList plainList){ 
			listEnum.reset();
			int size = plainList.size();
			int count = 0;
			long value2, value = -1;
			do{
				value2 = value;
				value = treeList.getNext(listEnum);	
				if(value <0)break;
				if(value <= value2) throw new RuntimeException("wrong sort order:"+value+" and:"+value2);
				if(!plainList.contains(new Long(value))) throw new RuntimeException("wrong value:"+value);
				count++;
			}while(true);
			if(count != size) throw new RuntimeException("soll count:"+size+"   ist count:"+count);
			
			value = Long.MAX_VALUE;
			do{
				value2 = value;
				value = treeList.getPrevious(listEnum);
				if(value <0)break;
				if(value >= value2) throw new RuntimeException("wrong sort order:"+value+" and:"+value2);
				if(!plainList.contains(new Long(value))) throw new RuntimeException("wrong value:"+value);
				count--;
			}while(true);
			if(count != 0) throw new RuntimeException("Prevous count is wrong:"+count);
	}*/
	

	private byte[] data;
	private int size;
	private int offset;
	static final private int pointerSize = 3; //if change then also in resize()
	
	/**
	 * Create a empty LongTreeList.
	 *
	 */
	LongTreeList(){
		data = new byte[25];
	}
	
	/**
	 * Create a LongTreeList with a first value.
	 * @param value
	 */
	LongTreeList(long value) throws SQLException{
		this();
		add(value);
	}
	
	/**
	 * Restore a LongTreeList from a MemoryStream.
	 */
	LongTreeList(StoreImpl input){
		int readSize = input.readInt();
		data     = input.readBytes(readSize);
	}
	
	
	/**
	 * Save this list to a serial stream. This can be used to save it on a hard disk.
	 * @param output
	 */
	final void save(StoreImpl output){
		output.writeInt(size);
		output.writeBytes(data, 0, size);
	}
	

	/**
	 * Add a value to this list.
	 * @param value
	 * @throws SQLException
	 */
	final void add(long value) throws SQLException{
		offset = 0;
		if(size == 0){
			writeShort( (int)(value >> 48) );
			writePointer ( offset+pointerSize+2 );
			writeShort( 0 );
			writeShort( (int)(value >> 32) );
			writePointer ( offset+pointerSize+2 );
			writeShort( 0 );
			writeShort( (int)(value >> 16) );
			writePointer ( offset+pointerSize+2 );
			writeShort( 0 );
			writeShort( (int)(value) );
			writeShort( 0 );
			size = offset;
			return;
		}
		int shift = 48;
		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)
		while(shift>=0){
			int octet = (int)(value >> shift) & 0xFFFF;
			while(true){
				int nextEntry = getUnsignedShort();
				if(nextEntry == octet){
					if(shift == 0) return; //value exist already, this case should not occur
					offset = getPointer();
					firstNode = true;
					break;
				}
				if((nextEntry == 0 && !firstNode) || nextEntry > octet){
					offset -= 2;
					while(true){
						if(shift != 0){
							offset = insertNode(octet);						
						}else{
							insertNodeLastLevel(octet);	
							return;
						}
						shift -= 16;
						octet = (int)(value >> shift) & 0xFFFF;
					}
				}
				firstNode = false;
				if(shift != 0) offset += pointerSize;
			}
			shift -= 16;
		}
	}
	
	
	/**
	 * Remove a value from this list.
	 * @param value
	 * @throws SQLException
	 */
	final void remove(long value) throws SQLException{
		if(size == 0) return;
		int offset1 = 0;
		int offset2 = 0;
		int offset3 = 0;
		offset = 0;
		int shift = 48;
		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)
		boolean firstNode1 = true;
		boolean firstNode2 = true;
		boolean firstNode3 = true;
		while(shift>=0){
			int octet = (int)(value >> shift) & 0xFFFF;
			while(true){
				int nextEntry = getUnsignedShort();
				if(nextEntry == octet){
					if(shift == 0){
						//value find
						offset -= 2;
						removeNodeLastLevel();
						while(firstNode && getUnsignedShort() == 0){
							offset -= 2;
							removeNodeLastLevel(); // the end 0 of a node
							if(shift >= 3) 
								break;
							offset = offset1;
							offset1 = offset2;
							offset2 = offset3;
							firstNode = firstNode1;
							firstNode1 = firstNode2;
							firstNode2 = firstNode3;
							removeNode();
							shift++;
						}
						return;
					}
					offset3 = offset2;
					offset2 = offset1;
					offset1 = offset -2;
					offset = getPointer();
					firstNode3 = firstNode2;
					firstNode2 = firstNode1;
					firstNode1 = firstNode;
					firstNode = true;
					break;
				}
				if((nextEntry == 0 && !firstNode) || nextEntry > octet){
					//value is not in the list, this should not occur
					return;
				}
				firstNode = false;
				if(shift != 0) offset += pointerSize;
			}
			shift -= 16;