bplustreelong.cs

R树与B树的混合树

				this.ShrinkFootprint();
			}
		}
		public string FirstKey() 
		{
			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) 
		{
			if (AfterThisKey==null) 
			{
				throw new BplusTreeBadKeyValue("cannot search for null string");
			}
			string result = this.root.FindNextKey(AfterThisKey);
			this.ShrinkFootprint();
			return result;
		}
		public bool ContainsKey(string key) 
		{
			long valueFound;
			return this.ContainsKey(key, out valueFound);
		} 
		public bool ContainsKey(string key, out long valueFound) 
		{
			if (key==null)
			{
				throw new BplusTreeBadKeyValue("cannot search for null string");
			}
			bool result = false;
			valueFound = (long) 0;
			if (this.root!=null) 
			{
				result = this.root.FindMatch(key, out valueFound);
			}
			this.ShrinkFootprint();
			return result;
		}
		public long Get(string key, long defaultValue) 
		{
			long result = defaultValue;
			long valueFound;
			if (this.ContainsKey(key, out valueFound))
			{
				result = valueFound;
			}
			return result;
		}
		public void Set(string key, object map) 
		{
			if (!(map is long)) 
			{
				throw new BplusTreeBadKeyValue("only longs may be used as values in a BplusTreeLong: "+map);
			}
			this[key] = (long) map;
		}
		public object Get(string key, object defaultValue) 
		{
			long valueFound;
			if (this.ContainsKey(key, out valueFound)) 
			{
				return (object) valueFound;
			}
			return defaultValue;
		}
		/// <summary>
		/// Store off any changed buffers, clear the fifo, free invalid buffers
		/// </summary>
		public void Commit() 
		{
			// 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
			ArrayList toFree = new ArrayList();
			foreach (DictionaryEntry d in this.FreeBuffersOnCommit) 
			{
				toFree.Add(d.Key);
			}
			toFree.Sort();
			toFree.Reverse();
			foreach (object thing in toFree) 
			{
				long buffernumber = (long) thing;
				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() 
		{
			// deallocate allocated blocks
			ArrayList toFree = new ArrayList();
			foreach (DictionaryEntry d in this.FreeBuffersOnAbort) 
			{
				toFree.Add(d.Key);
			}
			toFree.Sort();
			toFree.Reverse();
			foreach (object thing in toFree) 
			{
				long buffernumber = (long) thing;
				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() 
		{
			this.FreeBuffersOnCommit.Clear();
			this.FreeBuffersOnAbort.Clear();
			this.IdToTerminalNode.Clear();
			this.TerminalNodeToId.Clear();
		}
		public long allocateBuffer() 
		{
			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) 
		{
			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) 
		{
			//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() 
		{
			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) 
		{
			if (terminalNode==this.root) 
			{
				return; // never record the root node
			}
			if (this.TerminalNodeToId.ContainsKey(terminalNode) )
			{
				return; // don't record it again
			}
			int id = this.TerminalNodeCount;
			this.TerminalNodeCount++;
			this.TerminalNodeToId[terminalNode] = id;
			this.IdToTerminalNode[id] = terminalNode;
		}
		public void ForgetTerminalNode(BplusNode nonterminalNode) 
		{
			if (!this.TerminalNodeToId.ContainsKey(nonterminalNode)) 
			{
				// silently ignore (?)
				return;
			}
			int id = (int) this.TerminalNodeToId[nonterminalNode];
			if (id == this.LowerTerminalNodeCount) 
			{
				this.LowerTerminalNodeCount++;
			}
			this.IdToTerminalNode.Remove(id);
			this.TerminalNodeToId.Remove(nonterminalNode);
		}
		public void ShrinkFootprint() 
		{
			this.InvalidateTerminalNodes(this.FifoLimit);
		}
		public void InvalidateTerminalNodes(int toLimit) 
		{
			while (this.TerminalNodeToId.Count>toLimit) 
			{
				// choose oldest nonterminal and deallocate it
				while (!this.IdToTerminalNode.ContainsKey(this.LowerTerminalNodeCount)) 
				{
					this.LowerTerminalNodeCount++; // since most nodes are terminal this should usually be a short walk
					//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[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() 
		{
			// 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) 
			{
				if (header[index]!=b) 
				{
					throw new BufferFileException("invalid header prefix");
				}
				index++;
			}
			// 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);
			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() 
		{
			// 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);
			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;
			if (this.cultureContext!=null) 
			{
				BufferFile.Store(this.cultureContext.LCID, result, index);
			} 
			else 
			{
				BufferFile.Store(System.Globalization.CultureInfo.InvariantCulture.LCID, result, index);
			}
			index+= BufferFile.INTSTORAGE;
			BufferFile.Store(this.rootSeek, result, index);
			index+= BufferFile.LONGSTORAGE;
			BufferFile.Store(this.freeHeadSeek, result, index);
			return result;
		}
	}
	public class BplusNode 
	{
		public bool isLeaf = true;
		// the maximum number of children to each node.
		int Size;
		// false if the node is no longer active and should not be used.
		//bool isValid = true;
		// true if the materialized node needs to be persisted.
		bool Dirty = true;
		// if non-root reference to the parent node containing this node
		BplusNode parent = null;
		// tree containing this node
		BplusTreeLong owner = null;
		// buffer number of this node
		public long myBufferNumber = BplusTreeLong.NULLBUFFERNUMBER;
		// number of children used by this node
		//int NumberOfValidKids = 0;
		long[] ChildBufferNumbers;
		string[] ChildKeys;
		BplusNode[] MaterializedChildNodes;
		int indexInParent = -1;
		/// <summary>
		/// Create a new BplusNode and install in parent if parent is not null.
		/// </summary>
		/// <param name="owner">tree containing the node</param>
		/// <param name="parent">parent node (if provided)</param>
		/// <param name="indexInParent">location in parent if provided</param>
		public BplusNode(BplusTreeLong owner, BplusNode parent, int indexInParent, bool isLeaf) 
		{
			this.isLeaf = isLeaf;
			this.owner = owner;
			this.parent = parent;
			this.Size = owner.NodeSize;
			//this.isValid = true;
			this.Dirty = true;
			//			this.ChildBufferNumbers = new long[this.Size+1];
			//			this.ChildKeys = new string[this.Size];
			//			this.MaterializedChildNodes = new BplusNode[this.Size+1];
			this.Clear();
			if (parent!=null && indexInParent>=0) 
			{
				if (indexInParent>this.Size) 
				{
					throw new BplusTreeException("parent index too large");
				}
				// key info, etc, set elsewhere
				this.parent.MaterializedChildNodes[indexInParent] = this;
				this.myBufferNumber = this.parent.ChildBufferNumbers[indexInParent];
				this.indexInParent = indexInParent;
			}
		}
		public BplusNode FirstChild() 
		{
			BplusNode result = this.MaterializeNodeAtIndex(0);
			if (result==null) 
			{
				throw new BplusTreeException("no first child");
			}
			return result;
		}
		public long makeRoot() 
		{
			this.parent = null;
			this.indexInParent = -1;
			if (this.myBufferNumber==BplusTreeLong.NULLBUFFERNUMBER) 
			{
				throw new BplusTreeException("no root seek allocated to new root");
			}
			return this.myBufferNumber;
		}
		public void Free() 
		{
			if (this.myBufferNumber!=BplusTreeLong.NULLBUFFERNUMBER) 
			{
				if (this.owner.FreeBuffersOnAbort.ContainsKey(this.myBufferNumber)) 
				{
					// free it now
					this.owner.FreeBuffersOnAbort.Remove(this.myBufferNumber);