+
+ /// <summary>
+ /// This is a wrapper around StreamReader which is seekable backwards
+ /// within a window of around 2048 chars.
+ /// </summary>
+ public class SeekableStreamReader
+ {
+ public SeekableStreamReader (StreamReader reader)
+ {
+ this.reader = reader;
+ this.buffer = new char [AverageReadLength * 3];
+
+ // Let the StreamWriter autodetect the encoder
+ reader.Peek ();
+ }
+
+ public SeekableStreamReader (Stream stream, Encoding encoding)
+ : this (new StreamReader (stream, encoding, true))
+ { }
+
+ StreamReader reader;
+
+ private const int AverageReadLength = 1024;
+
+ char[] buffer;
+ int buffer_start; // in chars
+ int char_count; // count buffer[] valid characters
+ int pos; // index into buffer[]
+
+ /// <remarks>
+ /// This value corresponds to the current position in a stream of characters.
+ /// The StreamReader hides its manipulation of the underlying byte stream and all
+ /// character set/decoding issues. Thus, we cannot use this position to guess at
+ /// the corresponding position in the underlying byte stream even though there is
+ /// a correlation between them.
+ /// </remarks>
+ public int Position {
+ get { return buffer_start + pos; }
+
+ set {
+ if (value < buffer_start || value > buffer_start + char_count)
+ throw new InternalErrorException ("can't seek that far back: " + (pos - value));
+ pos = value - buffer_start;
+ }
+ }
+
+ private bool ReadBuffer ()
+ {
+ int slack = buffer.Length - char_count;
+ if (slack <= AverageReadLength / 2) {
+ // shift the buffer to make room for AverageReadLength number of characters
+ int shift = AverageReadLength - slack;
+ Array.Copy (buffer, shift, buffer, 0, char_count - shift);
+ pos -= shift;
+ char_count -= shift;
+ buffer_start += shift;
+ slack += shift; // slack == AverageReadLength
+ }
+
+ int chars_read = reader.Read (buffer, char_count, slack);
+ char_count += chars_read;
+
+ return pos < char_count;
+ }
+
+ public int Peek ()
+ {
+ if ((pos >= char_count) && !ReadBuffer ())
+ return -1;
+
+ return buffer [pos];
+ }
+
+ public int Read ()
+ {
+ if ((pos >= char_count) && !ReadBuffer ())
+ return -1;
+
+ return buffer [pos++];
+ }
+ }
+
+ public class DoubleHash {
+ const int DEFAULT_INITIAL_BUCKETS = 100;
+
+ public DoubleHash () : this (DEFAULT_INITIAL_BUCKETS) {}
+
+ public DoubleHash (int size)
+ {
+ count = size;
+ buckets = new Entry [size];
+ }
+
+ int count;
+ Entry [] buckets;
+ int size = 0;
+
+ class Entry {
+ public object key1;
+ public object key2;
+ public int hash;
+ public object value;
+ public Entry next;
+
+ public Entry (object key1, object key2, int hash, object value, Entry next)
+ {
+ this.key1 = key1;
+ this.key2 = key2;
+ this.hash = hash;
+ this.next = next;
+ this.value = value;
+ }
+ }
+
+ public bool Lookup (object a, object b, out object res)
+ {
+ int h = (a.GetHashCode () ^ b.GetHashCode ()) & 0x7FFFFFFF;
+
+ for (Entry e = buckets [h % count]; e != null; e = e.next) {
+ if (e.hash == h && e.key1.Equals (a) && e.key2.Equals (b)) {
+ res = e.value;
+ return true;
+ }
+ }
+ res = null;
+ return false;
+ }
+
+ public void Insert (object a, object b, object value)
+ {
+ // Is it an existing one?
+
+ int h = (a.GetHashCode () ^ b.GetHashCode ()) & 0x7FFFFFFF;
+
+ for (Entry e = buckets [h % count]; e != null; e = e.next) {
+ if (e.hash == h && e.key1.Equals (a) && e.key2.Equals (b))
+ e.value = value;
+ }
+
+ int bucket = h % count;
+ buckets [bucket] = new Entry (a, b, h, value, buckets [bucket]);
+
+ // Grow whenever we double in size
+ if (size++ == count) {
+ count <<= 1;
+ count ++;
+
+ Entry [] newBuckets = new Entry [count];
+ foreach (Entry root in buckets) {
+ Entry e = root;
+ while (e != null) {
+ int newLoc = e.hash % count;
+ Entry n = e.next;
+ e.next = newBuckets [newLoc];
+ newBuckets [newLoc] = e;
+ e = n;
+ }
+ }
+
+ buckets = newBuckets;
+ }
+ }
+ }