longtreelist.java

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

		}
	}
	

	/**
	 * Get the next long value from this list.
	 * @return
	 */
	final long getNext(LongTreeListEnum listEnum){
		int shift = (3-listEnum.stack) << 4;
		if(shift >= 64) return -1; //a previous call has return -1
		offset 		= listEnum.offsetStack[listEnum.stack];
		long result = listEnum.resultStack[listEnum.stack];
		boolean firstNode = (offset == 0); // true if it the first entry in a level
		while(true){
			int nextEntry = getUnsignedShort();
			if(nextEntry != 0 || firstNode){
				//there are more entries in this node
				result |= (((long)nextEntry) << shift);
				if(listEnum.stack>=3){
					listEnum.offsetStack[listEnum.stack] = offset;
					return result;
				}
				listEnum.offsetStack[listEnum.stack] = offset+pointerSize;
				offset = getPointer();
				shift -= 16;
				listEnum.stack++;
				listEnum.resultStack[listEnum.stack] = result;
				firstNode = true;
			}else{
				//no more entries in this node
				shift += 16;
				listEnum.stack--;
				if(listEnum.stack<0) return -1; // no more entries
				result = listEnum.resultStack[listEnum.stack];
				offset = listEnum.offsetStack[listEnum.stack];
				firstNode = false;
			}
		}
	}

	
	/**
	 * Get the next long value from this list.
	 * @return
	 */
	final long getPrevious(LongTreeListEnum listEnum){
		int shift = (3-listEnum.stack) << 4;
		if(shift >= 64){ //a previous call of getNext() has return -1
			shift = 48;
			offset = 0;
			listEnum.stack = 0;
			listEnum.offsetStack[0] = 2 + pointerSize;
			loopToEndOfNode(listEnum);
		}else{
			setPreviousOffset(listEnum);
		}
		long result = listEnum.resultStack[listEnum.stack];
		while(true){
			int nextEntry = (offset < 0) ? -1 : getUnsignedShort();
			if(nextEntry >= 0){
				// there are more entries in this node
				result |= (((long)nextEntry) << shift);
				if(listEnum.stack>=3){
					listEnum.offsetStack[listEnum.stack] = offset;
					return result;
				}
				listEnum.offsetStack[listEnum.stack] = offset+pointerSize;
				offset = getPointer();
				shift -= 16;
				listEnum.stack++;
				listEnum.resultStack[listEnum.stack] = result;
				loopToEndOfNode(listEnum);
			}else{
				//no more entries in this node
				shift += 16;
				listEnum.stack--;
				if(listEnum.stack<0) return -1; // no more entries
				result = listEnum.resultStack[listEnum.stack];
				setPreviousOffset(listEnum);
			}
		}
	}
	
	
	/**
	 * Is used from getPrevious(). It set the offset of the previous entry.
	 * If there is no previous entry in this node then set it to -1.
	 * The problem is that "enum" point to the next position to optimize getNext().
	 * We need 2 steps forward to find the previous entry. It can occur that
	 * we are in another node. We need to verify it with the start point of the current node.
	 */
	final private void setPreviousOffset(LongTreeListEnum listEnum){
		int previousOffset = listEnum.offsetStack[listEnum.stack] - 2*(2 + (listEnum.stack>=3 ? 0 : pointerSize));
		if(listEnum.stack == 0){
			offset = previousOffset;
			return;
		}
		offset = listEnum.offsetStack[listEnum.stack-1] - pointerSize;
		int pointer = getPointer();
		if(pointer <= previousOffset){
			offset = previousOffset;
			return;
		}
		offset = -1;
	}
	
	
	/**
	 * Loop to the last entry in this node. Is used from getPrevious().
	 */
	final private void loopToEndOfNode(LongTreeListEnum listEnum){
		int nextEntry;
		int nextOffset1, nextOffset2;
		nextOffset1 = offset;
		offset += 2;
		if(listEnum.stack<3)
			offset += pointerSize;
		do{
			nextOffset2 = nextOffset1;
			nextOffset1 = offset;
			nextEntry = getUnsignedShort();
			if(listEnum.stack<3)
				offset += pointerSize;
		}while(nextEntry != 0);
		offset = nextOffset2;
	}
	
	
	

	/**
	 * Insert a octet entry on the current offset for one of the first 3 levels. 
	 * After it create a new node at the end (simple two 0). 
	 * Then set it the pointer in the new entry to the new node 
	 * @param octet a short value
	 * @return the offset of the new node.
	 */
	final private int insertNode(int octet) throws SQLException{
		int oldOffset = offset;
		
		if(data.length < size + 4 + pointerSize) resize();
		System.arraycopy(data, oldOffset, data, oldOffset + 2+pointerSize, size-oldOffset);
		size += 2+pointerSize;

		writeShort( octet );
		writePointer( size );

		//correct all offset that point behind the new node
		correctPointers( 0, oldOffset, 2+pointerSize, 0 );
		
		data[size++] = (byte)0;
		data[size++] = (byte)0;
		return size-2;
	}
	
		
	/**
	 * Insert the octet of the last level (4 level) on the current offset. 
	 * This level does not include a pointer to a next level.
	 * @param octet a short value
	 */
	final private void insertNodeLastLevel(int octet) throws SQLException{
		int oldOffset = offset;
				
		if(data.length < size + 2) resize();
		System.arraycopy(data, offset, data, offset + 2, size-offset);
		size += 2;
		writeShort( octet );
		
		//correct all offset before this new node that point behind the new node
		correctPointers( 0, oldOffset, 2, 0 );	
	}
	
	
	/**
	 * Remove a octet entry on the current offset for one of the first 3 levels. 
	 * Then set it the pointer in the new entry to the new node 
	 * @param octet a short value
	 */
	final private void removeNode() throws SQLException{
		int oldOffset = offset;
		
		//correct all offset that point behind the old node
		correctPointers( 0, oldOffset, -(2+pointerSize), 0 );

		size -= 2+pointerSize;
		System.arraycopy(data, oldOffset + 2+pointerSize, data, oldOffset, size-oldOffset);

		offset = oldOffset;
	}
	
	
	/**
	 * Remove a octet entry on the current offset for one of the first 3 levels. 
	 * Then set it the pointer in the new entry to the new node 
	 * @param octet a short value
	 */
	final private void removeNodeLastLevel() throws SQLException{
		int oldOffset = offset;
		
		//correct all offset that point behind the old node
		correctPointers( 0, oldOffset, -2, 0 );

		size -= 2;
		System.arraycopy(data, oldOffset + 2, data, oldOffset, size-oldOffset);

		offset = oldOffset;
	}
	
	
	/**
	 * Correct all pointers that point behind a new entry.
	 * @param startOffset the startoffset of the current node
	 * @param oldOffset the offset of the new entry, only pointer that point behind it need to correct.
	 * @param diff the differenz that need added to the pointers
	 * @param level the stack level. There are only 3 levels with pointers.
	 */
	final private void correctPointers(int startOffset, int oldOffset, int diff, int level){
		offset = startOffset;
		boolean firstNode = true;
		while(offset < size){
			if(offset == oldOffset){
				int absDiff = Math.abs(diff);
				if(absDiff == 2) return;
				offset += absDiff;
				firstNode = false;
				continue;
			}
			int value = getUnsignedShort();
			if(value != 0 || firstNode){
				int pointer = getPointer();
				if(pointer > oldOffset){
					offset  -= pointerSize;
					writePointer( pointer + diff );
					if(diff > 0) pointer += diff;
				}				
				if(level < 2){
					startOffset = offset;
					correctPointers( pointer, oldOffset, diff, level+1);
					offset = startOffset;
				}
				firstNode = false;
			}else{
				return;
			}
		}
	}
	
		
	/**
	 * Read a pointer to another node in de index.
	 */
	final private int getPointer(){
		int value = 0;
		for(int i=0; i<pointerSize; i++){
			value <<= 8;
			value += (data[offset++] & 0xFF);
		}
		return value;
	}
	
	
	/**
	 * Write a pointer to another node in the tree list. The size depends from the constant pointerSize.
	 */
	final private void writePointer(int value){
		for(int i=pointerSize-1; i>=0; i--){
			data[offset++] = (byte)(value >> (i*8));
		}
	}

	
	/**
	 * Read a short value from the index.
	 */
	final private int getUnsignedShort(){
		return ((data[ offset++ ] & 0xFF) << 8) | (data[ offset++ ] & 0xFF);
	}
	
	
	/**
	 * Save a short value in the index. The long values are saved in 4 short values-
	 * @param value
	 */
	final private void writeShort(int value){
		data[offset++] = (byte)(value >> 8);
		data[offset++] = (byte)(value);
	}
	
	
	/**
	 * Increment the buffer size for the list.
	 */
	private final void resize() throws SQLException{
		int newsize = data.length << 1;
		if(newsize > 0xFFFFFF){ //see pointerSize
			newsize = 0xFFFFFF;
			if(newsize == data.length) throw Utils.createSQLException("To many equals entry in Index.");
		}
		byte[] temp = new byte[newsize];
		System.arraycopy(data, 0, temp, 0, data.length);
		data = temp;
	}

	final int getSize() {
		return size;
	}
}