bplustreelong.java

R树与B树的混合树

			theroot.Free();
		}
	}
	public long get(String key)
		throws Exception
	{
		//long valueFound;
		boolean test = this.ContainsKey(key);
		if (!test) 
		{
			throw new BplusTreeKeyMissing("no such key found: "+key);
		}
		return this.LastValueFound;
	}
	public void set(String key, long value)
		throws Exception
	{
		if (!BplusNode.KeyOK(key, this)) 
		{
			String data = "null";
			if (key!=null) 
			{
				data = "key "+key+" length "+key.length();
			}
			throw new BplusTreeBadKeyValue("null or too large key cannot be inserted into tree: "+data);
		}
		boolean rootinit = false;
		if (this.root==null) 
		{
			// allocate root
			this.root = new BplusNode(this, null, -1, true);
			rootinit = true;
			//this.rootSeek = root.DumpToFreshBuffer();
		}
		// insert into root...
		//root.Insert(key, value, out splitString, out splitNode);
		root.Insert(key, value);
		String splitString = root.splitString;
		BplusNode splitNode = root.splitNode;
		// clear split info
		root.splitString = null;
		root.splitNode = null;
		if (splitNode!=null) 
		{
			// split of root: make a new root.
			rootinit = true;
			BplusNode oldRoot = this.root;
			this.root = BplusNode.BinaryRoot(oldRoot, splitString, splitNode, this);
		}
		if (rootinit) 
		{
			this.rootSeek = root.DumpToFreshBuffer();
		}
		// check size in memory
		this.ShrinkFootprint();
	}
		
	public String FirstKey() 
		throws Exception
	{
		String result = null;
		if (this.root!=null) 
		{
			// empty String is smallest possible tree
			if (this.ContainsKey("")) 
			{
				result = "";
			} 
			else 
			{
				return this.root.FindNextKey("");
			}
			this.ShrinkFootprint();
		}
		return result;
	}
	public String NextKey(String AfterThisKey) 
		throws Exception
	{
		if (AfterThisKey==null) 
		{
			throw new BplusTreeBadKeyValue("cannot search for null String");
		}
		String result = this.root.FindNextKey(AfterThisKey);
		this.ShrinkFootprint();
		return result;
	}
	//		public boolean containsKey(String key) 
	//		{
	//			long valueFound;
	//			return this.containsKey(key, out valueFound);
	//		} 
	public boolean ContainsKey(String key) 
		throws Exception
	{
		if (key==null)
		{
			throw new BplusTreeBadKeyValue("cannot search for null String");
		}
		boolean result = false;
		//valueFound = (long) 0;
		if (this.root!=null) 
		{
			result = this.root.FindMatch(key);
			this.LastValueFound = this.root.LastValueFound;
		}
		this.ShrinkFootprint();
		return result;
	}
	//		public long Get(String key, long defaultValue) 
	//		{
	//			long result = defaultValue;
	//			long valueFound;
	//			if (this.containsKey(key))
	//			{
	//				result = this.LastValueFound;
	//			}
	//			return result;
	//		}
	public void Set(String key, Object map) 
		throws Exception
	{
		//if (!(map is long)) 
		if (map.getClass()!=Long.class)
		{
			throw new BplusTreeBadKeyValue("only longs may be used as values in a BplusTreeLong: "+map);
		}
		//this[key] = ((Long) map).longValue();
		this.set(key, ((Long) map).longValue());
	}
	public Object Get(String key, Object defaultValue) 
		throws Exception
	{
		long valueFound;
		if (this.ContainsKey(key)) 
		{
			return new Long(this.LastValueFound);
		}
		return defaultValue;
	}
	/// <summary>
	/// Store off any changed buffers, clear the fifo, free invalid buffers
	/// </summary>
	public void Commit() 
		throws Exception
	{
		// store all modifications
		if (this.root!=null) 
		{
			this.rootSeek = this.root.Invalidate(false);
		}
		//this.fromfile.Flush();
		// commit the new root
		this.setHeader();
		//this.fromfile.Flush();
		// at this point the changes are committed, but some space is unreachable.
		// now free all unfreed buffers no longer in use
		//this.FreeBuffersOnCommit.Sort();
		//this.FreeBuffersOnCommit.Reverse();
		//foreach (Object thing in this.FreeBuffersOnCommit) 
		//for (int i=0; i<this.FreeBuffersOnCommit.size(); i++)
		for (Enumeration e=this.FreeBuffersOnCommit.keys(); e.hasMoreElements(); )
		{
			Long thing = (Long) e.nextElement();
			long buffernumber = thing.longValue();
			this.deallocateBuffer(buffernumber);
		}
		// store the free list head
		this.setHeader();
		//this.fromfile.Flush();
		this.ResetBookkeeping();
	}
	/// <summary>
	/// Forget all changes since last commit
	/// </summary>
	public void Abort() 
		throws Exception
	{
		// deallocate allocated blocks
		//this.FreeBuffersOnAbort.Sort();
		//this.FreeBuffersOnAbort.Reverse();
		//foreach (Object thing in this.FreeBuffersOnAbort) 
		//for (int i=0; i<this.FreeBuffersOnAbort.size(); i++)
		for (Enumeration e=this.FreeBuffersOnAbort.keys(); e.hasMoreElements(); )
		{
			Long thing = (Long) e.nextElement();
			long buffernumber = thing.longValue();
			this.deallocateBuffer(buffernumber);
		}
		long freehead = this.freeHeadSeek;
		// reread the header (except for freelist head)
		this.readHeader();
		// restore the root
		if (this.rootSeek==NULLBUFFERNUMBER) 
		{
			this.root = null; // nothing was committed
		} 
		else 
		{
			this.root.LoadFromBuffer(this.rootSeek);
		}
		this.ResetBookkeeping();
		this.freeHeadSeek = freehead;
		this.setHeader(); // store new freelist head
		//this.fromfile.Flush();
	}
	void ResetBookkeeping() 
		throws Exception
	{
		this.FreeBuffersOnCommit.clear();
		this.FreeBuffersOnAbort.clear();
		this.IdToTerminalNode.clear();
		this.TerminalNodeToId.clear();
	}
	public long allocateBuffer() 
		throws Exception
	{
		long allocated = -1;
		if (this.freeHeadSeek==NULLBUFFERNUMBER) 
		{
			// should be written immediately after allocation
			allocated = this.buffers.nextBufferNumber();
			//System.Diagnostics.Debug.WriteLine("<br> allocating fresh buffer "+allocated);
			return allocated;
		}
		// get the free head data
		allocated = this.freeHeadSeek;
		this.freeHeadSeek = this.parseFreeBuffer(allocated);
		//System.Diagnostics.Debug.WriteLine("<br> recycling free buffer "+allocated);
		return allocated;
	}
	long parseFreeBuffer(long buffernumber) 
		throws Exception
	{
		int freesize = 1+BufferFile.LONGSTORAGE;
		byte[] buffer = new byte[freesize];
		this.buffers.getBuffer(buffernumber, buffer, 0, freesize);
		if (buffer[0]!=FREE) 
		{
			throw new BplusTreeException("free buffer not marked free");
		}
		long result = BufferFile.RetrieveLong(buffer, 1);
		return result;
	}
	public void deallocateBuffer(long buffernumber) 
		throws Exception
	{
		//System.Diagnostics.Debug.WriteLine("<br> deallocating "+buffernumber);
		int freesize = 1+BufferFile.LONGSTORAGE;
		byte[] buffer = new byte[freesize];
		// it better not already be marked free
		this.buffers.getBuffer(buffernumber, buffer, 0, 1);
		if (buffer[0]==FREE) 
		{
			throw new BplusTreeException("attempt to re-free free buffer not allowed");
		}
		buffer[0] = FREE;
		BufferFile.Store(this.freeHeadSeek, buffer, 1);
		this.buffers.setBuffer(buffernumber, buffer, 0, freesize);
		this.freeHeadSeek = buffernumber;
	}
	void setHeader() 
		throws Exception
	{
		byte[] header = this.makeHeader();
		this.fromfile.seek(this.seekStart);//, System.IO.SeekOrigin.Begin);
		this.fromfile.write(header, 0, header.length);
	}
	public void RecordTerminalNode(BplusNode terminalNode) 
		throws Exception
	{
		if (terminalNode==this.root) 
		{
			return; // never record the root node
		}
		if (this.TerminalNodeToId.containsKey(terminalNode) )
		{
			return; // don't record it again
		}
		Integer id = new Integer(this.TerminalNodeCount);
		this.TerminalNodeCount++;
		//this.TerminalNodeToId[terminalNode] = id;
		this.TerminalNodeToId.put(terminalNode, id);
		//this.IdToTerminalNode[id] = terminalNode;
		this.IdToTerminalNode.put(id, terminalNode);
	}
	public void ForgetTerminalNode(BplusNode nonterminalNode) 
		throws Exception
	{
		if (!this.TerminalNodeToId.containsKey(nonterminalNode)) 
		{
			// silently ignore (?)
			return;
		}
		Integer id = (Integer) this.TerminalNodeToId.get(nonterminalNode);
		if (id.intValue() == this.LowerTerminalNodeCount) 
		{
			this.LowerTerminalNodeCount++;
		}
		this.IdToTerminalNode.remove(id);
		this.TerminalNodeToId.remove(nonterminalNode);
	}
	public void ShrinkFootprint() 
		throws Exception
	{
		this.InvalidateTerminalNodes(this.FifoLimit);
	}
	public void InvalidateTerminalNodes(int toLimit) 
		throws Exception
	{
		while (this.TerminalNodeToId.size()>toLimit) 
		{
			// choose oldest nonterminal and deallocate it
			Integer id = new Integer(this.LowerTerminalNodeCount);
			while (!this.IdToTerminalNode.containsKey(id)) 
			{
				this.LowerTerminalNodeCount++; // since most nodes are terminal this should usually be a short walk
				id = new Integer(this.LowerTerminalNodeCount);
				//System.Diagnostics.Debug.WriteLine("<BR>WALKING "+this.LowerTerminalNodeCount);
				//System.Console.WriteLine("<BR>WALKING "+this.LowerTerminalNodeCount);
				if (this.LowerTerminalNodeCount>this.TerminalNodeCount) 
				{
					throw new BplusTreeException("internal error counting nodes, lower limit went too large");
				}
			}
			//System.Console.WriteLine("<br> done walking");
			//int id = this.LowerTerminalNodeCount;
			BplusNode victim = (BplusNode) this.IdToTerminalNode.get(id);
			//System.Diagnostics.Debug.WriteLine("\r\n<br>selecting "+victim.myBufferNumber+" for deallocation from fifo");
			this.IdToTerminalNode.remove(id);
			this.TerminalNodeToId.remove(victim);
			if (victim.myBufferNumber!=NULLBUFFERNUMBER) 
			{
				victim.Invalidate(true);
			}
		}
	}
	void readHeader() 
		throws Exception
	{
		// prefix | version | node size | key size | culture id | buffer number of root | buffer number of free list head
		byte[] header = new byte[this.headersize];
		this.fromfile.seek(this.seekStart); //, System.IO.SeekOrigin.Begin);
		this.fromfile.read(header, 0, this.headersize);
		int index = 0;
		// check prefix
		//foreach (byte b in HEADERPREFIX) 
		for (index=0; index<HEADERPREFIX.length; index++)
		{
			if (header[index]!=HEADERPREFIX[index]) 
			{
				throw new BplusTreeException("invalid header prefix");
			}
			index++;
		}
		index = HEADERPREFIX.length;
		// skip version (for now)
		index++;
		this.NodeSize = BufferFile.Retrieve(header, index);
		index+= BufferFile.INTSTORAGE;
		this.KeyLength = BufferFile.Retrieve(header, index);
		index+= BufferFile.INTSTORAGE;
		int CultureId = BufferFile.Retrieve(header, index);
		//this.cultureContext = new System.Globalization.CultureInfo(CultureId);
		if (CultureId!=INVARIANTCULTUREID) 
		{
			throw new BplusTreeException("BplusJ only supports the invariant culture");
		}
		index+= BufferFile.INTSTORAGE;
		this.rootSeek = BufferFile.RetrieveLong(header, index);
		index+= BufferFile.LONGSTORAGE;
		this.freeHeadSeek = BufferFile.RetrieveLong(header, index);
		this.SanityCheck();
		//this.header = header;
	}
	public byte[] makeHeader() 
		throws Exception
	{
		// prefix | version | node size | key size | culture id | buffer number of root | buffer number of free list head
		byte[] result = new byte[this.headersize];
		//HEADERPREFIX.CopyTo(result, 0);
		for (int i=0; i<HEADERPREFIX.length; i++) 
		{
			result[i] = HEADERPREFIX[i];
		}
		result[HEADERPREFIX.length] = VERSION;
		int index = HEADERPREFIX.length+1;
		BufferFile.Store(this.NodeSize, result, index);
		index+= BufferFile.INTSTORAGE;
		BufferFile.Store(this.KeyLength, result, index);
		index+= BufferFile.INTSTORAGE;
		BufferFile.Store(INVARIANTCULTUREID, result, index);
		index+= BufferFile.INTSTORAGE;
		BufferFile.Store(this.rootSeek, result, index);