dymokomi/luce-browser-foundation
Source of release 0.6.1
0.6.1 / src / ak / tests_hash_table.lucb
#==============================================================================================
#
# tests_hash_table - HashTable and OrderedHashTable (tests_hash_map has the maps)
#
# DESCRIPTION:
# Ports of Tests/AK/TestHashTable.cpp and TestHashMap.cpp. ByteString and String keys
# (region r02) are `str` keys with TestStrTraits (AK's string_hash of the bytes); the
# NonnullOwnPtr and non-trivial-type cases use plain pointers and structs (values are
# plain data here). Iteration orders are pinned against the donor's HashTable and
# HashMap (a C++ program over the reference build's AK, run while porting).
#
#==============================================================================================
# Traits<ByteString> for the `str` keys of these tests: string_hash of the bytes.
struct TestStrTraits: Traits[str]:
var empty_: u8
func hash_of(key: const str*) -> u32: return test_str_hash(*key)
func equals(a: const str*, b: const str*) -> bool: return *a == *b
func test_str_hash(key: str) -> u32:
return string_hash(key.bytes.data, key.length)
# CaseInsensitiveASCIIStringTraits for `str` keys.
struct TestCaseInsensitiveStrTraits: Traits[str]:
var empty_: u8
func hash_of(key: const str*) -> u32: return test_case_insensitive_str_hash(*key)
func equals(a: const str*, b: const str*) -> bool: return test_str_equals_ignoring_case(*a, *b)
func test_case_insensitive_str_hash(key: str) -> u32:
return case_insensitive_string_hash(key.bytes.data, key.length)
func test_str_equals_ignoring_case(a: str, b: str) -> bool:
if a.length != b.length:
return false
for i in 0..<a.length:
var x = a.bytes[i]
var y = b.bytes[i]
if x >= 'A' and x <= 'Z':
x += 0x20
if y >= 'A' and y <= 'Z':
y += 0x20
if x != y:
return false
return true
# StringCollisionTraits: every string hashes to 0.
struct TestCollisionStrTraits: Traits[str]:
var empty_: u8
func hash_of(key: const str*) -> u32: return test_zero_hash(*key)
func equals(a: const str*, b: const str*) -> bool: return *a == *b
func test_zero_hash(key: str) -> u32:
_ = key
return 0
# ByteString::number(i) for the tests' keys: the decimal text of `i` in a table of spellings.
let test_number_texts: str[16] = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15"]
func test_int_greater_than_two(context: void*?, value: const i32*) -> bool:
_ = context
return *value > 2
func test_int_bool(context: void*?, value: const i32*) -> bool:
_ = value
return context != none
type IntTable = HashTable[i32, I32Traits]
type OrderedIntTable = OrderedHashTable[i32, I32Traits]
# mark: TestHashTable ===========================================================================
test "hash_table: construct":
var table: IntTable
assert(hash_table_is_empty(&table))
assert(hash_table_size(&table) == 0)
test "hash_table: basic_move and move_is_not_swap":
var foo: IntTable
_ = hash_table_set(&foo, 1)
assert(hash_table_size(&foo) == 1)
var bar = foo
foo = IntTable()
assert(hash_table_size(&bar) == 1)
assert(hash_table_size(&foo) == 0)
var baz: IntTable
_ = hash_table_set(&baz, 2)
foo = baz
baz = IntTable()
assert(hash_table_contains_t(&foo, 2))
assert(not hash_table_contains_t(&baz, 1))
assert(hash_table_size(&baz) == 0)
test "hash_table: populate, range_loop and table_remove":
var strings: HashTable[str, TestStrTraits]
assert(hash_table_set(&strings, "One") == HashSetResult.inserted_new_entry)
assert(hash_table_set(&strings, "Two") == HashSetResult.inserted_new_entry)
assert(hash_table_set(&strings, "Three") == HashSetResult.inserted_new_entry)
assert(not hash_table_is_empty(&strings))
assert(hash_table_size(&strings) == 3)
var loop_counter = 0
for it in hash_table_begin(&strings):
assert(it.length != 0)
loop_counter += 1
assert(loop_counter == 3)
assert(hash_table_remove_t(&strings, "One"))
assert(hash_table_size(&strings) == 2)
let one = hash_table_find_t(&strings, "One")
assert(hash_table_iterator_eq(&one, hash_table_end(&strings)))
assert(hash_table_remove_t(&strings, "Three"))
assert(hash_table_size(&strings) == 1)
assert(hash_table_find_t(&strings, "Three").m_bucket == none)
assert(hash_table_find_t(&strings, "Two").m_bucket != none)
test "hash_table: range_loop_reverse":
let strings: str[3] = ["One", "Two", "Three"]
var table: OrderedHashTable[str, TestStrTraits]
for s in strings:
assert(ordered_hash_table_set(&table, s) == HashSetResult.inserted_new_entry)
var loop_counter = 0
var index = 2
for it in ordered_hash_table_in_reverse(&table):
assert(*it == strings[index])
loop_counter += 1
index -= 1
assert(loop_counter == 3)
test "hash_table: remove_all_matching and take_all_matching":
var ints: IntTable
for i: i32 in 1..=4:
_ = hash_table_set(&ints, i)
assert(hash_table_size(&ints) == 4)
assert(hash_table_remove_all_matching(&ints, Function1[const i32*, bool](call = test_int_greater_than_two, context = none)))
assert(not hash_table_remove_all_matching(&ints, Function1[const i32*, bool](call = test_int_bool, context = none)))
assert(hash_table_size(&ints) == 2)
assert(hash_table_contains_t(&ints, 1))
assert(hash_table_contains_t(&ints, 2))
var yes: u8 = 1
assert(hash_table_remove_all_matching(&ints, Function1[const i32*, bool](call = test_int_bool, context = &yes)))
assert(hash_table_is_empty(&ints))
assert(not hash_table_remove_all_matching(&ints, Function1[const i32*, bool](call = test_int_bool, context = &yes)))
for i: i32 in 1..=4:
_ = hash_table_set(&ints, i)
let first_values = hash_table_take_all_matching(&ints, Function1[const i32*, bool](call = test_int_greater_than_two, context = none))
assert(vector_size(&first_values) == 2)
assert(vector_contains_slow[i32, I32Traits](&first_values, 3))
assert(vector_contains_slow[i32, I32Traits](&first_values, 4))
let none_taken = hash_table_take_all_matching(&ints, Function1[const i32*, bool](call = test_int_bool, context = none))
assert(vector_is_empty(&none_taken))
assert(hash_table_size(&ints) == 2)
let second_values = hash_table_take_all_matching(&ints, Function1[const i32*, bool](call = test_int_bool, context = &yes))
assert(vector_size(&second_values) == 2)
assert(vector_contains_slow[i32, I32Traits](&second_values, 1))
assert(hash_table_is_empty(&ints))
test "hash_table: case_insensitive":
var casetable: HashTable[str, TestCaseInsensitiveStrTraits]
assert(hash_table_set(&casetable, "nickserv") == HashSetResult.inserted_new_entry)
assert(hash_table_set(&casetable, "NickServ") == HashSetResult.replaced_existing_entry)
assert(hash_table_size(&casetable) == 1)
test "hash_table: many_ints":
with memory.heap:
var ints: IntTable
for i: i32 in 0..<999:
assert(hash_table_set(&ints, i) == HashSetResult.inserted_new_entry)
assert(hash_table_size(&ints) == 999)
for i: i32 in 0..<999:
assert(hash_table_remove_t(&ints, i))
assert(hash_table_is_empty(&ints))
test "hash_table: many_collisions and space_reuse":
with memory.heap:
var strings: HashTable[str, TestCollisionStrTraits]
for text in test_number_texts:
assert(hash_table_set(&strings, text) == HashSetResult.inserted_new_entry)
assert(hash_table_set(&strings, "foo") == HashSetResult.inserted_new_entry)
assert(hash_table_size(&strings) == 17)
for text in test_number_texts:
assert(hash_table_remove_t(&strings, text))
assert(hash_table_find_t(&strings, "foo").m_bucket != none)
var reuse: HashTable[str, TestCollisionStrTraits]
assert(hash_table_set(&reuse, "0") == HashSetResult.inserted_new_entry)
for i in 1..<5usize:
assert(hash_table_set(&reuse, test_number_texts[i]) == HashSetResult.inserted_new_entry)
assert(hash_table_remove_t(&reuse, test_number_texts[i - 1]))
let capacity = hash_table_capacity(&reuse)
for i in 5..<16usize:
assert(hash_table_set(&reuse, test_number_texts[i]) == HashSetResult.inserted_new_entry)
assert(hash_table_remove_t(&reuse, test_number_texts[i - 1]))
assert(hash_table_capacity(&reuse) == capacity)
test "hash_table: basic_remove and basic_contains":
var table: IntTable
_ = hash_table_set(&table, 1)
_ = hash_table_set(&table, 2)
_ = hash_table_set(&table, 3)
assert(hash_table_contains_t(&table, 1))
assert(hash_table_contains_t(&table, 3))
assert(not hash_table_contains_t(&table, 4))
assert(hash_table_remove_t(&table, 3))
assert(not hash_table_remove_t(&table, 3))
assert(not hash_table_contains_t(&table, 3))
assert(hash_table_size(&table) == 2)
assert(hash_table_remove_t(&table, 1))
assert(not hash_table_remove_t(&table, 1))
assert(hash_table_size(&table) == 1)
assert(hash_table_remove_t(&table, 2))
assert(not hash_table_remove_t(&table, 2))
assert(hash_table_size(&table) == 0)
test "hash_table: capacity_leak":
with memory.heap:
var table: IntTable
for i: i32 in 0..<10000:
_ = hash_table_set(&table, i)
_ = hash_table_remove_t(&table, i)
assert(hash_table_capacity(&table) < 100)
test "hash_table: floats and doubles":
var floats: HashTable[f32, F32Traits]
_ = hash_table_set(&floats, 0.0)
_ = hash_table_set(&floats, 1.0)
_ = hash_table_set(&floats, 2.0)
assert(hash_table_size(&floats) == 3)
assert(hash_table_contains_t(&floats, 0.0))
assert(hash_table_contains_t(&floats, 2.0))
var doubles: HashTable[f64, F64Traits]
_ = hash_table_set(&doubles, 0.0)
_ = hash_table_set(&doubles, 1.0)
_ = hash_table_set(&doubles, 2.0)
assert(hash_table_size(&doubles) == 3)
assert(hash_table_contains_t(&doubles, 1.0))
test "hash_table: reinsertion and clear_with_capacity":
var map: OrderedHashTable[str, TestStrTraits]
_ = ordered_hash_table_set(&map, "ytidb::LAST_RESULT_ENTRY_KEY")
_ = ordered_hash_table_set(&map, "__sak")
_ = ordered_hash_table_remove_t(&map, "__sak")
_ = ordered_hash_table_set(&map, "__sak")
assert(ordered_hash_table_size(&map) == 2)
var ints: IntTable
hash_table_clear_with_capacity(&ints)
_ = hash_table_set(&ints, 0)
_ = hash_table_set(&ints, 1)
assert(hash_table_size(&ints) == 2)
hash_table_clear_with_capacity(&ints)
assert(hash_table_size(&ints) == 0)
assert(not hash_table_contains_t(&ints, 1))
test "hash_table: iterator_removal":
var map: IntTable
_ = hash_table_set(&map, 0)
_ = hash_table_set(&map, 1)
var it = hash_table_begin(&map)
hash_table_remove_opaque(&map, &it)
assert(hash_table_iterator_eq(&it, hash_table_end(&map)))
assert(hash_table_size(&map) == 1)
func test_expect_ordered(table: OrderedIntTable*, values: const i32[]):
var index: usize = 0
var it = ordered_hash_table_begin(table)
while hash_table_iterator_ne(&it, ordered_hash_table_end(table)):
assert(*hash_table_iterator_deref(&it) == values[index])
assert(ordered_hash_table_contains_t(table, values[index]))
hash_table_iterator_inc(&it)
index += 1
assert(index == values.length)
index = ordered_hash_table_size(table)
var rit = ordered_hash_table_rbegin(table)
while reverse_ordered_hash_table_iterator_ne(&rit, ordered_hash_table_rend(table)):
index -= 1
assert(*reverse_ordered_hash_table_iterator_deref(&rit) == values[index])
reverse_ordered_hash_table_iterator_inc(&rit)
assert(index == 0)
test "hash_table: ordered_insertion_and_deletion":
var table: OrderedIntTable
for i: i32 in 0..<4:
assert(ordered_hash_table_set(&table, i) == HashSetResult.inserted_new_entry)
assert(ordered_hash_table_size(&table) == 4)
let all: i32[4] = [0, 1, 2, 3]
test_expect_ordered(&table, all)
assert(ordered_hash_table_remove_t(&table, 0))
assert(ordered_hash_table_remove_t(&table, 2))
assert(not ordered_hash_table_remove_t(&table, 4))
assert(ordered_hash_table_size(&table) == 2)
let rest: i32[2] = [1, 3]
test_expect_ordered(&table, rest)
test "hash_table: ordered_deletion_and_reinsertion":
var table: OrderedIntTable
_ = ordered_hash_table_set(&table, 1)
_ = ordered_hash_table_set(&table, 3)
_ = ordered_hash_table_remove_t(&table, 1)
assert(ordered_hash_table_size(&table) == 1)
# By adding 1 again but this time in a different position, we
# test whether the bucket's neighbors are reset properly.
_ = ordered_hash_table_set(&table, 1)
assert(ordered_hash_table_size(&table) == 2)
let expected: i32[2] = [3, 1]
test_expect_ordered(&table, expected)
test "hash_table: ordered take_last, iterator_removal, remove_from_head":
var table: OrderedIntTable
_ = ordered_hash_table_set(&table, 1)
_ = ordered_hash_table_set(&table, 2)
_ = ordered_hash_table_set(&table, 3)
assert(ordered_hash_table_take_last(&table) == 3)
assert(ordered_hash_table_take_last(&table) == 2)
assert(ordered_hash_table_take_first(&table) == 1)
assert(ordered_hash_table_is_empty(&table))
_ = ordered_hash_table_set(&table, 0)
_ = ordered_hash_table_set(&table, 1)
var it = ordered_hash_table_begin(&table)
ordered_hash_table_remove_opaque(&table, &it)
assert(hash_table_iterator_eq(&it, ordered_hash_table_end(&table)))
assert(ordered_hash_table_size(&table) == 1)
var map: OrderedIntTable
for i: i32 in 1..=6:
_ = ordered_hash_table_set(&map, i)
assert(ordered_hash_table_size(&map) == 6)
for i in 0..<6:
_ = i
var head = ordered_hash_table_begin(&map)
ordered_hash_table_remove_opaque(&map, &head)
assert(ordered_hash_table_size(&map) == 0)
test "hash_table: ordered_infinite_loop_clang_regression":
var map: OrderedHashTable[str, TestStrTraits]
let keys: str[7] = ["", "1", "_cb", "2", "3", "_cb_svref", "_cb_svref_expires"]
for key in keys:
_ = ordered_hash_table_set(&map, key)
_ = ordered_hash_table_remove_t(&map, "_cb_svref")
_ = ordered_hash_table_remove_t(&map, "_cb_svref_expires")
_ = ordered_hash_table_set(&map, "_cb_svref")
var iterations: usize = 0
let size = ordered_hash_table_size(&map)
for it in ordered_hash_table_begin(&map):
_ = it
iterations += 1
assert(iterations <= size)
assert(iterations == 6)
test "hash_table: values":
var table: OrderedIntTable
_ = ordered_hash_table_set(&table, 10)
_ = ordered_hash_table_set(&table, 30)
_ = ordered_hash_table_set(&table, 20)
let values = ordered_hash_table_values(&table)
assert(vector_size(&values) == ordered_hash_table_size(&table))
assert(*vector_at_const(&values, 0) == 10)
assert(*vector_at_const(&values, 1) == 30)
assert(*vector_at_const(&values, 2) == 20)
test "hash_table: iteration order matches the donor":
with memory.heap:
var t: IntTable
for i: i32 in 0..<40:
_ = hash_table_set(&t, i * 7 - 50)
var i: i32 = 0
while i < 40:
_ = hash_table_remove_t(&t, i * 7 - 50)
i += 3
let expected: i32[26] = [-43, 6, -15, 153, 195, 132, 167, 41, 48, 216, 146, 104, 188, 111, -22, 20, 209, 69, 83, 90, 27, -36, 174, 62, 125, -1]
var index: usize = 0
for value in hash_table_begin(&t):
assert(*value == expected[index])
index += 1
assert(index == 26)
assert(hash_table_capacity(&t) == 64)
var big: HashTable[u64, U64Traits]
for k: u64 in 0..<30:
_ = hash_table_set(&big, k << 32)
let expected_big: u64[30] = [0, 5, 11, 2, 22, 20, 23, 6, 25, 12, 24, 26, 21, 13, 7, 8, 1, 4, 15, 28, 16, 17, 9, 27, 14, 19, 29, 10, 3, 18]
index = 0
for value in hash_table_begin(&big):
assert(*value >> 32 == expected_big[index])
index += 1
assert(index == 30)
test "hash_table: clone":
var table: IntTable
_ = hash_table_set(&table, 5)
_ = hash_table_set(&table, 6)
var copy = hash_table_clone(&table)
_ = hash_table_set(©, 7)
assert(hash_table_size(&table) == 2)
assert(hash_table_size(©) == 3)
assert(not hash_table_contains_t(&table, 7))