bplustest.cs

R树与B树的混合树

using System;
using System.Diagnostics;
using System.Collections;

namespace testing
{

	/// <summary>
	/// Serializable class for testing serializable tree.
	/// </summary>
	[Serializable]
	public class SerializableThing
	{
		public int i, j, k;
		public SerializableThing(int i, int j, int k) 
		{
			this.i = i;
			this.j = j;
			this.k = k;
		}
		public override bool Equals(object obj)
		{
			if (! (obj is SerializableThing)) 
			{
				return false;
			}
			SerializableThing other = (SerializableThing) obj;
			return (other.i == this.i) && (other.j == this.j) && (other.k == this.k);
		}
		public override int GetHashCode()
		{
			return this.i^(this.j<<8)^(this.k<<16);
		}

	}

	/// <summary>
	/// tests main entry point for bplusdotnet.  Throws exception on failure.
	/// </summary>
	public class bplusTest
	{
		static string tempdirectory = @"c:\tmp"; // set to a directory to test storing to/from files
		static Hashtable allinserts = new Hashtable();
		static Hashtable lastcommittedinserts = new Hashtable();
		static bool full = true;
		static int keylength = 20;
		static int prefixlength = 6;
		static int nodesize = 6;
		static int buffersize = 100;
		static int bucketsizelimit = 100; // sanity check
		static bool DoAllTests = true;
		public static void Main() 
		{
			if (DoAllTests) 
			{
				byteStringTest();
				intTests();
				longTests();
				shortTests();
				//BplusDotNet.BufferFile nullbf = new BplusDotNet.BufferFile(null, 90);
				testBufferFile();
				LinkedFileTest();
				BplusTreeLongTest();
				//bplustreetest();
				Test();
				xTest();
				hTest();
				sTest();
			}
			CompatTest();
		}
		static string keyMaker(int i, int j, int k) 
		{
			int selector = (i+j+k)%3;
			string result = ""+i+"."+j+"."+k;
			if (selector==0) 
			{
				result = ""+k+"."+(j%5)+"."+i;
			} 
			else if (selector==1) 
			{
				result = ""+k+"."+j+"."+i;
			}
			return result;
		}
		static string xkeyMaker(int i, int j, int k) 
		{
			string result = keyMaker(i,j,k);
			result = result+result+result;
			result = result + keyMaker(k,i,j);
			return result;
		}
		static string ValueMaker(int i, int j, int k)
		{
			if ( ((i+j+k)%5) == 3 )
			{
				return "";
			}
			System.Text.StringBuilder sb = new System.Text.StringBuilder();
			sb.Append("value");
			for (int x=0; x<i+k*5; x++) 
			{
				sb.Append(j);
				sb.Append(k);
			}
			return sb.ToString();
		}

		public static void hTest() 
		{
			string watchKey = ""; //"4.3.04.3.04.3.03.0.4";
			Console.WriteLine("TESTING HBPLUSTREE");
			System.IO.Stream treefile=null, blockfile=null;
			BplusDotNet.hBplusTree bpt = getHTree(null, ref treefile, ref blockfile);
			Hashtable allmaps = new Hashtable();
			for (int i=0; i<10; i++) 
			{
				Console.WriteLine("Pass "+i+" of 10");
				bpt.SetFootPrintLimit(16-i);
				for (int j=0; j<30; j++) 
				{
					Hashtable record = new Hashtable();
					for (int k=0; k<30; k++) 
					{
						string thiskey = xkeyMaker(i,j,k);
						string thisvalue = ValueMaker(j,k,i);
						if (thiskey.Equals(watchKey)) 
						{
							Debug.WriteLine("<br> NOW SETTING "+watchKey);
						}
						record[thiskey] = thisvalue;
						bpt[thiskey] = thisvalue;
						if (thiskey.Equals(watchKey)) 
						{
							Debug.WriteLine("<br> AFTER SETTING "+bpt.toHtml());
						}
					}
					if ((j%3)==1) 
					{
						bpt.Recover(false);
					}
					if ( ((i+j)%2) == 1 ) 
					{
						bpt.Commit();
						bpt.Abort();  // should have no effect
						bpt.Commit();  // ditto
						if ( (i+j)%5 < 2) 
						{
							//Debug.WriteLine(bpt.toHtml());
							foreach (DictionaryEntry d in record) 
							{
								string thiskey = (string) d.Key;
								bpt.RemoveKey(thiskey);
								if (thiskey.Equals(watchKey)) 
								{
									Debug.WriteLine("<br> NOW REMOVING "+watchKey);
								}
								if (allmaps.ContainsKey(thiskey)) 
								{
									allmaps.Remove(thiskey);
								}
							}
							//Debug.WriteLine(bpt.toHtml());
							bpt.Commit();
							//return;
						} 
						else 
						{
							foreach (DictionaryEntry d in record) 
							{
								allmaps[d.Key] = d.Value;
							}
						}
					} 
					else 
					{
						bpt.Abort();
					}
					if ((j%4)==2) 
					{
						bpt = getHTree(bpt, ref treefile, ref blockfile);
					}
					// now check the structure
					//ArrayList allkeys = new ArrayList();
					foreach (DictionaryEntry d in allmaps) 
					{
						string thiskey = (string)d.Key;
						string thisvalue = (string)d.Value;
						if (thiskey.Equals(watchKey)) 
						{
							Debug.WriteLine(" retrieving "+thiskey);
						}
						string treemap = bpt[thiskey];
						if (!treemap.Equals(thisvalue)) 
						{
							throw new ApplicationException("key "+thiskey+" maps to "+treemap+" but should map to "+thisvalue);
						}
						//allkeys.Add(thiskey);
					}
					string currentkey = bpt.FirstKey();
					Hashtable visited = new Hashtable();
					//allkeys.Sort();
					while (currentkey!=null) 
					{
						if (visited.ContainsKey(currentkey)) 
						{
							throw new ApplicationException("key visited twice in traversal "+currentkey);
						}
						visited[currentkey] = currentkey;
						if (!allmaps.ContainsKey(currentkey)) 
						{
							throw new ApplicationException("key found in tree but not in hash table "+currentkey);
						}
						currentkey = bpt.NextKey(currentkey);
					}
				}
			}
		}
		public static void xTest() 
		{
			Console.WriteLine("TESTING XBPLUSTREE");
			System.IO.Stream treefile=null, blockfile=null;
			BplusDotNet.xBplusTree bpt = getXTree(null, ref treefile, ref blockfile);
			Hashtable allmaps = new Hashtable();
			for (int i=0; i<10; i++) 
			{
				Console.WriteLine("Pass "+i+" of 10");
				bpt.SetFootPrintLimit(16-i);
				for (int j=0; j<30; j++) 
				{
					Hashtable record = new Hashtable();
					for (int k=0; k<30; k++) 
					{
						string thiskey = xkeyMaker(i,j,k);
						string thisvalue = ValueMaker(j,k,i);
						record[thiskey] = thisvalue;
						bpt[thiskey] = thisvalue;
					}
					if ((j%3)==1) 
					{
						bpt.Recover(false);
					}
					if ( ((i+j)%2) == 1 ) 
					{
						bpt.Commit();
						bpt.Abort();  // should have no effect
						bpt.Commit();  // ditto
						if ( (i+j)%5 < 2) 
						{
							//Debug.WriteLine(bpt.toHtml());
							foreach (DictionaryEntry d in record) 
							{
								string thiskey = (string) d.Key;
								bpt.RemoveKey(thiskey);
								if (allmaps.ContainsKey(thiskey)) 
								{
									allmaps.Remove(thiskey);
								}
							}
							//Debug.WriteLine(bpt.toHtml());
							bpt.Commit();
							//return;
						} 
						else 
						{
							foreach (DictionaryEntry d in record) 
							{
								allmaps[d.Key] = d.Value;
							}
						}
					} 
					else 
					{
						bpt.Abort();
					}
					if ((j%4)==2) 
					{
						bpt = getXTree(bpt, ref treefile, ref blockfile);
					}
					// now check the structure
					ArrayList allkeys = new ArrayList();
					foreach (DictionaryEntry d in allmaps) 
					{
						string thiskey = (string)d.Key;
						string thisvalue = (string)d.Value;
						string treemap = bpt[thiskey];
						if (!treemap.Equals(thisvalue)) 
						{
							throw new ApplicationException("key "+thiskey+" maps to "+treemap+" but should map to "+thisvalue);
						}
						allkeys.Add(thiskey);
					}
					string currentkey = bpt.FirstKey();
					allkeys.Sort();
					foreach (object thing in allkeys) 
					{
						//Debug.WriteLine("currentkey = "+currentkey);
						string recordedkey = (string) thing;
						if (currentkey==null) 
						{
							throw new ApplicationException("end of keys found when expecting "+recordedkey);
						}
						if (!currentkey.Equals(recordedkey)) 
						{
							Debug.WriteLine(bpt.toHtml());
							throw new ApplicationException("key "+currentkey+" found where expecting "+recordedkey);
						}
						currentkey = bpt.NextKey(currentkey);
					}
					if (currentkey!=null) 
					{
						throw new ApplicationException("found "+currentkey+" when expecting end of keys");
					}
				}
			}
		}

		public static void sTest() 
		{
			Console.WriteLine("TESTING SERIALIZEDTREE");
			System.IO.Stream treefile=null, blockfile=null;
			BplusDotNet.SerializedTree bpt = getsTree(null, ref treefile, ref blockfile);
			Hashtable allmaps = new Hashtable();
			for (int i=0; i<10; i++) 
			{
				Console.WriteLine("Pass "+i+" of 10");
				bpt.SetFootPrintLimit(16-i);
				for (int j=0; j<30; j++) 
				{
					Hashtable record = new Hashtable();
					for (int k=0; k<30; k++) 
					{
						string thiskey = keyMaker(i,j,k);
						SerializableThing thisvalue = new SerializableThing(j,k,i);
						record[thiskey] = thisvalue;
						bpt[thiskey] = thisvalue;
					}
					if ((j%3)==1) 
					{
						bpt.Recover(false);
					}
					if ( ((i+j)%2) == 1 ) 
					{
						bpt.Commit();
						bpt.Abort();  // should have no effect
						bpt.Commit();  // ditto
						if ( (i+j)%5 < 2) 
						{
							//Debug.WriteLine(bpt.toHtml());
							foreach (DictionaryEntry d in record) 
							{
								string thiskey = (string) d.Key;
								bpt.RemoveKey(thiskey);
								if (allmaps.ContainsKey(thiskey)) 
								{
									allmaps.Remove(thiskey);
								}
							}
							//Debug.WriteLine(bpt.toHtml());
							bpt.Commit();
							//return;
						} 
						else 
						{
							foreach (DictionaryEntry d in record) 
							{
								allmaps[d.Key] = d.Value;
							}
						}
					} 
					else 
					{
						bpt.Abort();
					}
					if ((j%4)==2) 
					{
						bpt = getsTree(bpt, ref treefile, ref blockfile);
					}
					// now check the structure
					ArrayList allkeys = new ArrayList();
					foreach (DictionaryEntry d in allmaps) 
					{
						string thiskey = (string)d.Key;
						SerializableThing thisvalue = (SerializableThing)d.Value;
						SerializableThing treemap = (SerializableThing)bpt[thiskey];
						if (!treemap.Equals(thisvalue)) 
						{
							throw new ApplicationException("key "+thiskey+" maps to "+treemap+" but should map to "+thisvalue);
						}
						allkeys.Add(thiskey);
					}
					string currentkey = bpt.FirstKey();
					allkeys.Sort();
					foreach (object thing in allkeys) 
					{
						string recordedkey = (string) thing;
						if (currentkey==null) 
						{
							throw new ApplicationException("end of keys found when expecting "+recordedkey);
						}
						if (!currentkey.Equals(recordedkey)) 
						{
							//Debug.WriteLine(bpt.toHtml());
							throw new ApplicationException("key "+currentkey+" found where expecting "+recordedkey);
						}
						currentkey = bpt.NextKey(currentkey);
					}
					if (currentkey!=null) 
					{
						throw new ApplicationException("found "+currentkey+" when expecting end of keys");
					}
				}
			}
		}
		public static void Test()