savier/system_packages/collections/map.rii

import libc { calloc, free }

const MAP_LOAD_FACTOR = 0.9;
const MAP_MIN_SIZE = 8;
global DEFAULT_HASH_FN: HashFn = hash_ptr;
global DEFAULT_KEY_CMP_FN: KeyCmpFn = cmp_ptr;

struct std_map_entry
{
	key, val: void*;
	hash: usize;
}

typedef HashFn   = func(key: void*): usize;
typedef KeyCmpFn = func(key: void*, test: void*): bool;

struct std_map
{
	hash_fn: HashFn;
	key_cmp_fn: KeyCmpFn;
	entries: std_map_entry*;
	size: usize;
	cap: usize;
	mask: usize;
	resize_at: usize;
}


priv func map__ideal_ix(map: std_map*, hash: usize): usize
{
	return hash & map.mask;
}

priv func map__probe_len(map: std_map*, hash: usize, ix: usize): usize
{
	return (ix + map.cap - map__ideal_ix(map, hash)) & map.mask;
}

func std_map_entry_is_empty(entry: std_map_entry*): bool
{
	return entry.hash == 0;
}

func map__entry_clear(m: std_map*, ix: usize)
{
	m.entries[ix].hash = 0;
}

func std_map_clear(m: std_map*)
{
	if (m.size == 0)
	{
		return;
	}

	for (i := 0; i < m.cap; i++)
	{
		map__entry_clear(m, i);
	}

	m.size = 0;
}

func hash_u64(x: ullong): usize
{
	x *= 0xff51afd7ed558ccd;
	x ^= x >> 32;
	return x;
}

func hash_ptr(ptr: void*): usize
{
	return (:usize)(hash_u64((:uintptr)ptr));
}

func cmp_ptr(key: void*, test: void*): bool
{
	return key == test;
}

func std_map_init(m: std_map*, hash_fn: HashFn, key_cmp_fn: KeyCmpFn)
{
	m.hash_fn = hash_fn;
	m.key_cmp_fn = key_cmp_fn;
	std_map_clear(m);
}

func std_map_new(): std_map*
{
	m: std_map* = calloc(1, sizeof(Map));
	std_map_init(m, DEFAULT_HASH_FN, DEFAULT_KEY_CMP_FN);
	return m;
}

func std_map_free(m: std_map*)
{
	free(m.entries);
}

priv func map__grow(m: std_map*, new_cap: usize)
{
	new_cap = std_usize_max(MAP_MIN_SIZE, new_cap);
	#assert(std_is_pow2(new_cap));

	new_m: std_map = {
		hash_fn	   	= m.hash_fn ? m.hash_fn : DEFAULT_HASH_FN,
		key_cmp_fn 	= m.key_cmp_fn ? m.key_cmp_fn : DEFAULT_KEY_CMP_FN,
		entries		= calloc(new_cap, sizeof(std_map_entry)),
		cap			= new_cap,
		mask		= new_cap - 1,
		resize_at	= (:usize)((:double)new_cap * MAP_LOAD_FACTOR)
	};

	for (i: usize = 0; i < m.cap; i++)
	{
		if (!std_map_entry_is_empty(&m.entries[i]))
		{
			map__do_insert(&new_m, m.entries[i].key, m.entries[i].val);
		}
	}

	free(m.entries);

	*m = new_m;
}

func std_map__get_hash(m: std_map *, key: void*): usize
{
	hash := m.hash_fn(key);
	hash |= (hash == 0);		// 0 indicates empty
	return hash;
}

func std_map__find(m: std_map*, key: void*, ix_result: usize*): bool
{
	if (m.size == 0)
	{
		return false;
	}

	#assert(std_is_pow2(m.cap));
	#assert(m.size < m.cap);

	hash := std_map__get_hash(m, key);
	ix := map__ideal_ix(m, hash);
	probe_len: usize = 0;

	while (true)
	{
		if (m.entries[ix].hash == 0)
		{
			return false;
		}
		else if (probe_len > map__probe_len(m, m.entries[ix].hash, ix))
		{
			// Can early out here because an element with a longer probe count than probe_len would have been swapped on insert
			return false;
		}
		else if (m.entries[ix].hash == hash && m.key_cmp_fn(m.entries[ix].key, key))
		{
			*ix_result = ix;
			return true;
		}

		ix = (ix + 1) & m.mask;
		probe_len++;
	}

	return false;
}

func std_map_has_key(m: std_map*, key: void*): bool
{
	ix: usize;
	return std_map__find(m, key, &ix);
}

func std_map_get(m: std_map*, key: void*): void*
{
	ix: usize;
	return std_map__find(m, key, &ix) ? m.entries[ix].val : NULL;
}

func std_map_remove(m: std_map*, key: void*): bool
{
	ix: usize;
	if (!std_map__find(m, key, &ix))
	{
		return false;
	}

	while (true)
	{
		prev_ix := ix;
		ix = (ix + 1) & m.mask;
		if (std_map_entry_is_empty(&m.entries[ix]) || map__probe_len(m, m.entries[ix].hash, ix) == 0)
		{
			std_map__entry_clear(m, prev_ix);
			break;
		}
		else
		{
			m.entries[prev_ix] = m.entries[ix];
		}
	}

	m.size--;
	return true;
}

priv func map__create_entry(m: std_map*, ix: usize, hash: usize, key: void*, val: void*)
{
	m.size++;
	m.entries[ix].key = key;
	m.entries[ix].val = val;
	m.entries[ix].hash = hash;
}

priv func map__do_insert(m: std_map*, key: void*, val: void*)
{
	hash := std_map__get_hash(m, key);
	ix := map__ideal_ix(m, hash);
	probe_len: usize = 0;

	while (true)
	{
		if (std_map_entry_is_empty(&m.entries[ix]))
		{
			map__create_entry(m, ix, hash, key, val);
			return;
		}
		else if (m.key_cmp_fn(m.entries[ix].key, key))
		{
			m.entries[ix].val = val;
			m.entries[ix].hash = hash;
			return;
		}

		occupant_probe_len := map__probe_len(m, m.entries[ix].hash, ix);

		// If occupant is closer to its ideal slot, insert the new item here and continue looking for a slot for the evicted item
		if (occupant_probe_len < probe_len)
		{
			tmp: std_map_entry = m.entries[ix];
			m.entries[ix].key = key;
			m.entries[ix].val = val;
			m.entries[ix].hash = hash;
			key = tmp.key;
			val = tmp.val;
			hash = tmp.hash;

			probe_len = occupant_probe_len;
		}

		ix = (ix + 1) & m.mask;
		probe_len++;
	}
}

func std_map_put(m: std_map*, key: void*, val: void*)
{
	if (m.resize_at <= m.size)
	{
		map__grow(m, 2 * m.cap);
	}

	map__do_insert(m, key, val);
}