Luce packages
LuceLuce BaseLuciaOS

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)