StringSet.v3

// Copyright 2020 Ben L. Titzer. All rights reserved.
// See LICENSE for details of Apache 2.0 license.

// A utility to check if a set of strings contains any duplicate equivalent
// strings, for up to {max} strings. Do not add more than {max} strings; gets
// O(n) slow and fills up completely at {4*max}.
class StringSet(max: int) {
	private def mask_shift = StringSetUtil.computeMaskAndShift(max);
	private def hashes = Array<int>.new(mask_shift.0 + 1);
	private def strings = Array<string>.new(mask_shift.0 + 1);

	// Add a string to this set. Return {true} if an equivalent
	// string has already been added.
	def add(str: string) -> bool {
		var hashcode = Strings.hash(str);
		var index = search(str, hashcode);
		if (index < 0) return true;
		hashes[index] = hashcode;
		strings[index] = str;
		return false;
	}
	// Return {true} if an equivalent string has already been added.
	// Does not modify this set.
	def has(str: string) -> bool {
		return search(str, Strings.hash(str)) < 0;
	}
	// Searches the internal storage for the given string. Returns {-1}
	// if found. Otherwise returns the index of the proper empty slot
	// for it to be inserted.
	private def search(str: string, hashcode: int) -> int {
		var t = mask_shift, mask = t.0, shift = t.1;
		var upper = hashcode >>> shift;
		var index = hashcode;
		while (upper != 0) {  // mix in upper bits of hashcode into index
			index ^= upper;
			upper = upper >>> shift;
		}
		index = index & mask;
		var last = (index - 1) & mask;
		// Linear search starting from hash index, wrapping around.
		for (i = index; i != last; i = (i + 1) & mask) {
			var es = strings[i];
			if (es == null) return i;
			var eh = hashes[i];
			if (eh == hashcode && Strings.equal(str, es)) return -1;
		}
		// Only happens if this set completely fills up, i.e.
		// the caller lied about {max}.
		return -1;
	}
}
// Exposed for testing.
component StringSetUtil {
	def computeMaskAndShift(max: int) -> (int, u5) {
		var i = 1, shift = 0;
		while (i < max) {
			i = i << 1;
			shift++;
		}
		return (4 * i - 1, u5.!(2 + shift));  // 4x sparsity
	}
}