dymokomi/luce-browser-foundation
Source of release 0.6.1
0.6.1 / src / ak / tests_hash_map.lucb
#==============================================================================================
#
# tests_hash_map - HashMap and OrderedHashMap
#
# DESCRIPTION:
# Port of Tests/AK/TestHashMap.cpp; the key traits and helpers are tests_hash_table's.
#
#==============================================================================================
# mark: TestHashMap =============================================================================
type IntIntMap = HashMap[i32, i32, I32Traits]
func test_map_key_one_or_value_two(context: void*?, key: const i32*, value: const str*) -> bool:
_ = context
return *key == 1 or *value == "Two"
func test_map_bool(context: void*?, key: const i32*, value: const str*) -> bool:
_ = key
_ = value
return context != none
test "hash_map: construct, populate and range_loop":
var empty: IntIntMap
assert(hash_map_is_empty(&empty))
assert(hash_map_size(&empty) == 0)
var number_to_string: HashMap[i32, str, I32Traits]
let list: HashMapEntry[i32, str][3] = [HashMapEntry[i32, str](key = 1, value = "One"), HashMapEntry[i32, str](key = 2, value = "Two"), HashMapEntry[i32, str](key = 3, value = "Three")]
hash_map_construct(&number_to_string, list)
assert(not hash_map_is_empty(&number_to_string))
assert(hash_map_size(&number_to_string) == 3)
var loop_counter = 0
for it in hash_map_begin(&number_to_string):
assert(it.value.length != 0)
loop_counter += 1
assert(loop_counter == 3)
test "hash_map: map_remove":
var number_to_string: HashMap[i32, str, I32Traits]
assert(hash_map_set(&number_to_string, 1, "One") == HashSetResult.inserted_new_entry)
assert(hash_map_set(&number_to_string, 2, "Two") == HashSetResult.inserted_new_entry)
assert(hash_map_set(&number_to_string, 3, "Three") == HashSetResult.inserted_new_entry)
assert(hash_map_remove_k(&number_to_string, 1))
assert(hash_map_size(&number_to_string) == 2)
assert(hash_map_find_k(&number_to_string, 1).m_bucket == none)
assert(hash_map_remove_k(&number_to_string, 3))
assert(hash_map_size(&number_to_string) == 1)
assert(hash_map_find_k(&number_to_string, 2).m_bucket != none)
test "hash_map: a removed entry's bucket keeps none of its bytes":
# Addition: the storage of a freed bucket is cleared (hash_table_delete_bucket), so the
# conservative scan of managed memory cannot keep what a removed value pointed to alive.
var map: HashMap[u64, u64, U64Traits]
for key: u64 in 1..=6:
hash_map_set(&map, key, 0xdeadbeef00 + key)
assert(hash_map_remove_k(&map, 3))
assert(hash_map_remove_k(&map, 5))
let buckets = map.m_table.m_buckets else trap("no buckets")
var found_removed = false
for i in 0..=map.m_table.m_mask:
let bucket = &buckets[i]
if bucket.storage.key == 3 or bucket.storage.value == 0xdeadbeef03 or bucket.storage.value == 0xdeadbeef05:
found_removed = true
assert(not found_removed)
assert(*(hash_map_get_k(&map, 4) else trap("key 4 is missing")) == 0xdeadbeef04)
test "hash_map: remove_all_matching and take_all_matching":
var map: HashMap[i32, str, I32Traits]
_ = hash_map_set(&map, 1, "One")
_ = hash_map_set(&map, 2, "Two")
_ = hash_map_set(&map, 3, "Three")
_ = hash_map_set(&map, 4, "Four")
assert(hash_map_remove_all_matching(&map, Function2[const i32*, const str*, bool](call = test_map_key_one_or_value_two, context = none)))
assert(hash_map_size(&map) == 2)
assert(not hash_map_remove_all_matching(&map, Function2[const i32*, const str*, bool](call = test_map_bool, context = none)))
assert(hash_map_contains_k(&map, 3))
assert(hash_map_contains_k(&map, 4))
var yes: u8 = 1
assert(hash_map_remove_all_matching(&map, Function2[const i32*, const str*, bool](call = test_map_bool, context = &yes)))
assert(hash_map_is_empty(&map))
_ = hash_map_set(&map, 1, "One")
_ = hash_map_set(&map, 2, "Two")
_ = hash_map_set(&map, 3, "Three")
_ = hash_map_set(&map, 4, "Four")
let first_entries = hash_map_take_all_matching(&map, Function2[const i32*, const str*, bool](call = test_map_key_one_or_value_two, context = none))
assert(vector_size(&first_entries) == 2)
let low = 1usize if vector_at_const(&first_entries, 0).key > vector_at_const(&first_entries, 1).key else 0
assert(vector_at_const(&first_entries, low).key == 1)
assert(vector_at_const(&first_entries, low).value == "One")
assert(vector_at_const(&first_entries, 1 - low).key == 2)
assert(vector_at_const(&first_entries, 1 - low).value == "Two")
assert(hash_map_size(&map) == 2)
let second_entries = hash_map_take_all_matching(&map, Function2[const i32*, const str*, bool](call = test_map_bool, context = &yes))
assert(vector_size(&second_entries) == 2)
assert(hash_map_is_empty(&map))
test "hash_map: case_insensitive":
var casemap: HashMap[str, i32, TestCaseInsensitiveStrTraits]
assert(hash_map_set(&casemap, "nickserv", 3) == HashSetResult.inserted_new_entry)
assert(hash_map_set(&casemap, "NickServ", 3) == HashSetResult.replaced_existing_entry)
assert(hash_map_size(&casemap) == 1)
struct TestMapObject:
var string: str
test "hash_map: hashmap_of_pointers_get":
var objects: HashMap[i32, TestMapObject*, I32Traits]
let one = new TestMapObject(string = "One") else trap("out of memory")
let two = new TestMapObject(string = "Two") else trap("out of memory")
let three = new TestMapObject(string = "Three") else trap("out of memory")
_ = hash_map_set(&objects, 1, one)
_ = hash_map_set(&objects, 2, two)
_ = hash_map_set(&objects, 3, three)
let x = hash_map_get_k(&objects, 2) else trap("missing")
assert((*x).string == "Two")
# Do it again to make sure that peeking into the map above didn't
# remove the value from the map.
let y = hash_map_get_k(&objects, 2) else trap("missing")
assert((*y).string == "Two")
assert(hash_map_size(&objects) == 3)
test "hash_map: basic_remove and basic_contains":
var map: IntIntMap
_ = hash_map_set(&map, 1, 10)
_ = hash_map_set(&map, 2, 20)
_ = hash_map_set(&map, 3, 30)
assert(hash_map_contains_k(&map, 1))
assert(not hash_map_contains_k(&map, 4))
assert(hash_map_remove_k(&map, 3))
assert(not hash_map_remove_k(&map, 3))
assert(not hash_map_contains_k(&map, 3))
assert(hash_map_size(&map) == 2)
assert(hash_map_remove_k(&map, 1))
assert(hash_map_remove_k(&map, 2))
assert(not hash_map_remove_k(&map, 2))
assert(hash_map_size(&map) == 0)
test "hash_map: in_place_rehashing_ordered_loop_bug":
var map: OrderedHashMap[str, str, TestStrTraits]
_ = ordered_hash_map_set(&map, "yt.innertube::nextId", "")
_ = ordered_hash_map_set(&map, "yt.innertube::requests", "")
_ = ordered_hash_map_remove_k(&map, "yt.innertube::nextId")
_ = ordered_hash_map_set(&map, "yt.innertube::nextId", "")
let keys = ordered_hash_map_keys(&map)
assert(vector_size(&keys) == 2)
assert(*vector_at_const(&keys, 0) == "yt.innertube::requests")
assert(ordered_hash_map_take_first(&map) == "")
assert(ordered_hash_map_size(&map) == 1)
test "hash_map: take":
var map: HashMap[str, i32, TestStrTraits]
assert(hash_map_take_k(&map, "foo") == none)
_ = hash_map_set(&map, "foo", 1)
_ = hash_map_set(&map, "bar", 2)
_ = hash_map_set(&map, "baz", 3)
assert(hash_map_take_k(&map, "foo") == 1)
assert(hash_map_take_k(&map, "foo") == none)
assert(hash_map_take_k(&map, "bar") == 2)
assert(hash_map_take_k(&map, "bar") == none)
assert(hash_map_take_k(&map, "baz") == 3)
assert(hash_map_take_k(&map, "baz") == none)
test "hash_map: clone, move and update":
var orig: IntIntMap
_ = hash_map_set(&orig, 1, 10)
_ = hash_map_set(&orig, 2, 20)
_ = hash_map_set(&orig, 3, 30)
let second = hash_map_clone(&orig) else trap("clone failed")
assert(hash_map_size(&orig) == 3)
assert(*(hash_map_get_k_const(&orig, 2) else trap("missing")) == 20)
assert(hash_map_size(&second) == 3)
assert(*(hash_map_get_k_const(&second, 2) else trap("missing")) == 20)
var first: IntIntMap
var other: IntIntMap
_ = hash_map_set(&first, 1, 10)
_ = hash_map_set(&first, 2, 20)
_ = hash_map_set(&other, 1, 9)
_ = hash_map_set(&other, 3, 30)
_ = hash_map_set(&other, 4, 40)
hash_map_update(&first, &other)
assert(hash_map_size(&first) == 4)
assert(hash_map_size(&other) == 3)
assert(*(hash_map_get_k(&first, 1) else trap("missing")) == 9)
assert(*(hash_map_get_k(&first, 2) else trap("missing")) == 20)
assert(*(hash_map_get_k(&first, 3) else trap("missing")) == 30)
assert(*(hash_map_get_k(&first, 4) else trap("missing")) == 40)
hash_map_update(&other, &first)
assert(hash_map_size(&other) == 4)
test "hash_map: compare":
var first: IntIntMap
var second: IntIntMap
assert(hash_map_eq(&first, &second))
_ = hash_map_set(&first, 1, 10)
_ = hash_map_set(&second, 1, 10)
assert(hash_map_eq(&first, &second))
_ = hash_map_set(&first, 2, 20)
assert(hash_map_ne(&second, &first))
struct TestSentinel:
var magic: u64
let test_sentinel_magic: u64 = 0xC0FFEECAFEBABE
struct TestEnsureCaptures:
var map: HashMap[i32, TestSentinel, I32Traits]*
var visited: usize
func test_ensure_callback(context: void*?) -> TestSentinel:
let captures = (TestEnsureCaptures*)(context else trap("no captures"))
for it in hash_map_begin(captures.map):
assert(it.value.magic == test_sentinel_magic)
captures.visited += 1
return TestSentinel(magic = test_sentinel_magic)
test "hash_map: ensure_callback_sees_consistent_table":
# HashMap::ensure() must run the initialization callback while the tentative
# target bucket is invisible to iterators.
var map: HashMap[i32, TestSentinel, I32Traits]
for i: i32 in 0..<100:
_ = hash_map_set(&map, i, TestSentinel(magic = test_sentinel_magic))
var captures = TestEnsureCaptures(map = &map, visited = 0)
let value = hash_map_ensure_t_callback(&map, 9999, Function0[TestSentinel](call = test_ensure_callback, context = &captures))
assert(value.magic == test_sentinel_magic)
assert(captures.visited == 100)
assert(hash_map_size(&map) == 101)
let zero = hash_map_ensure(&map, 12345)
assert(zero.magic == 0)
assert(hash_map_size(&map) == 102)
test "hash_map: iteration order matches the donor":
var m: HashMap[u32, u32, U32Traits]
for i: u32 in 0..<25:
_ = hash_map_set(&m, i * 1000003, i)
_ = hash_map_remove_k(&m, 5 * 1000003)
_ = hash_map_remove_k(&m, 17 * 1000003)
let expected: u32[23] = [0, 9, 11, 16, 12, 7, 19, 23, 4, 13, 24, 22, 1, 21, 18, 8, 20, 6, 10, 15, 2, 14, 3]
var index: usize = 0
for entry in hash_map_begin(&m):
assert(entry.value == expected[index])
index += 1
assert(index == 23)