Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / hash_map.lucb

#==============================================================================================
#
#   hash_map - HashMap<K, V>: a map over HashTable<Entry, EntryTraits>
#
#   DESCRIPTION:
#       Port of AK/HashMap.h (lines 1-344). The struct is support.lucb's HashMap[K, V, KT],
#       KT the key's traits (DESIGN.md §2.6); its table holds HashMapEntry[K, V] values
#       hashed and compared by the key. ValueTraits are the default ones: PeekType is `V&`,
#       so get() answers `V*?`, and operator== compares values with `==` (`V: Equatable`).
#       Iterating a map is iterating its table: `for entry in hash_map_begin(&map):` yields
#       HashMapEntry[K, V]* in the donor's order. A C++ copy of a map is hash_map_clone.
#       OrderedHashMap is ordered_hash_map.
#
#       Predicates over entries are Function2[const K*, const V*, bool]; lookups by another
#       key type take a HashCompatibleTraits[K, Key] (traits.lucb).
#
#==============================================================================================

# mark: EntryTraits =============================================================================

## Ported from AK/HashMap.h:30 AK::HashMap::EntryTraits::hash: the key's hash.
pub func hash_map_entry_traits_hash[K, V, KT: Traits[K]](entry: const HashMapEntry[K, V]*) -> u32:
    var traits: KT = ---
    return traits.hash_of(&entry.key)

## Ported from AK/HashMap.h:31 AK::HashMap::EntryTraits::equals: the keys' equality.
pub func hash_map_entry_traits_equals[K, V, KT: Traits[K]](a: const HashMapEntry[K, V]*, b: const HashMapEntry[K, V]*) -> bool:
    var traits: KT = ---
    return traits.equals(&a.key, &b.key)

# The predicate of find(key): `KeyTraits::equals(entry.key, key)`. It is a static method of the
# captures because no parameter of a function mentions KT, and a generic function value takes its
# type arguments from the expected function type only (`f[K, V, KT]` does not name an instance).
struct HashMapKeyEquals[K, V, KT: Traits[K]]:
    var key: K

    static func call(context: void*?, entry: const HashMapEntry[K, V]*) -> bool:
        let captures = (const HashMapKeyEquals[K, V, KT]*)(context else trap("HashMap: no captures"))
        var traits: KT = ---
        return traits.equals(&entry.key, &captures.key)

# The predicate of find(Key const&) for a hash-compatible key: `Traits<K>::equals(entry.key, key)`.
struct HashMapCompatibleKeyEquals[K, V, Key, KeyT: HashCompatibleTraits[K, Key]]:
    var key: Key

    static func call(context: void*?, entry: const HashMapEntry[K, V]*) -> bool:
        let captures = (const HashMapCompatibleKeyEquals[K, V, Key, KeyT]*)(context else trap("HashMap: no captures"))
        var traits: KeyT = ---
        return traits.equals(&entry.key, &captures.key)

# The predicate of remove_all_matching and take_all_matching: `predicate(entry.key, entry.value)`,
# with the predicate as the context.
func hash_map_entry_predicate[K, V](context: void*?, entry: const HashMapEntry[K, V]*) -> bool:
    let predicate = (const Function2[const K*, const V*, bool]*)(context else trap("HashMap: no predicate"))
    return function2_call(predicate, &entry.key, &entry.value)

# The captures of ensure()'s initialization callback.
struct HashMapEnsureEntry[K, V]:
    var key: K
    var initialization_callback: Function0[V]

# ensure()'s initialization callback: `[&] -> Entry { return { key, initialization_callback() }; }`.
func hash_map_ensure_entry[K, V](context: void*?) -> HashMapEntry[K, V]:
    let captures = (const HashMapEnsureEntry[K, V]*)(context else trap("HashMap: no captures"))
    return HashMapEntry[K, V](key = captures.key, value = function0_call(&captures.initialization_callback))

# ensure(key)'s default callback: `[] { return V(); }`, the zero value.
func hash_map_default_value[V](context: void*?) -> V:
    _ = context
    var value: V = ---
    memory.set(u8[]((u8*)&value, memory.size_of(V)), 0)
    return value

# mark: Construction and size ===================================================================

## Ported from AK/HashMap.h:43 AK::HashMap::HashMap(std::initializer_list<Entry>).
pub func hash_map_construct[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, list: const HashMapEntry[K, V][]):
    hash_map_try_ensure_capacity(this, list.length) else trap("MUST: HashMap::try_ensure_capacity")
    for entry in list:
        _ = hash_map_set(this, entry.key, entry.value)

## Ported from AK/HashMap.h:309 AK::HashMap::clone: a map with its own table holding the same
## entries (also what a C++ copy of a map is, DESIGN.md §3.3 rule 2).
pub func hash_map_clone[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*) -> HashMap[K, V, KT]!:
    var hash_map_clone_: HashMap[K, V, KT]
    hash_map_clone_.m_table.m_ordered = this.m_table.m_ordered
    try hash_map_try_ensure_capacity(&hash_map_clone_, hash_map_size(this))
    for entry in hash_map_begin_const(this):
        _ = hash_map_set(&hash_map_clone_, entry.key, entry.value)
    return hash_map_clone_

## Ported from AK/HashMap.h:52 AK::HashMap::is_empty.
pub func hash_map_is_empty[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*) -> bool:
    return hash_table_is_empty(&this.m_table)

## Ported from AK/HashMap.h:56 AK::HashMap::size.
pub func hash_map_size[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*) -> usize:
    return hash_table_size(&this.m_table)

## Ported from AK/HashMap.h:57 AK::HashMap::capacity.
pub func hash_map_capacity[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*) -> usize:
    return hash_table_capacity(&this.m_table)

## Ported from AK/HashMap.h:58 AK::HashMap::clear.
pub func hash_map_clear[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*):
    hash_table_clear(&this.m_table)

## Ported from AK/HashMap.h:59 AK::HashMap::clear_with_capacity.
pub func hash_map_clear_with_capacity[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*):
    hash_table_clear_with_capacity(&this.m_table)

# mark: Setting =================================================================================

## Ported from AK/HashMap.h:61 AK::HashMap::set(K const&, V const&).
pub func hash_map_set[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K, value: V, existing_entry_behavior: HashSetExistingEntryBehavior = HashSetExistingEntryBehavior.replace) -> HashSetResult:
    return hash_table_set(&this.m_table, HashMapEntry[K, V](key = key, value = value), existing_entry_behavior)

## Ported from AK/HashMap.h:62 AK::HashMap::set(K const&, V&&).
pub func hash_map_set_2[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K, value: V, existing_entry_behavior: HashSetExistingEntryBehavior = HashSetExistingEntryBehavior.replace) -> HashSetResult:
    return hash_map_set(this, key, value, existing_entry_behavior)

## Ported from AK/HashMap.h:63 AK::HashMap::set(K&&, V&&).
pub func hash_map_set_3[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K, value: V, existing_entry_behavior: HashSetExistingEntryBehavior = HashSetExistingEntryBehavior.replace) -> HashSetResult:
    return hash_map_set(this, key, value, existing_entry_behavior)

## Ported from AK/HashMap.h:64 AK::HashMap::try_set(K const&, V const&).
pub func hash_map_try_set[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K, value: V, existing_entry_behavior: HashSetExistingEntryBehavior = HashSetExistingEntryBehavior.replace) -> HashSetResult!:
    return try hash_table_try_set(&this.m_table, HashMapEntry[K, V](key = key, value = value), existing_entry_behavior)

## Ported from AK/HashMap.h:65 AK::HashMap::try_set(K const&, V&&).
pub func hash_map_try_set_2[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K, value: V, existing_entry_behavior: HashSetExistingEntryBehavior = HashSetExistingEntryBehavior.replace) -> HashSetResult!:
    return try hash_map_try_set(this, key, value, existing_entry_behavior)

## Ported from AK/HashMap.h:66 AK::HashMap::try_set(K&&, V&&).
pub func hash_map_try_set_3[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K, value: V, existing_entry_behavior: HashSetExistingEntryBehavior = HashSetExistingEntryBehavior.replace) -> HashSetResult!:
    return try hash_map_try_set(this, key, value, existing_entry_behavior)

## Ported from AK/HashMap.h:68 AK::HashMap::update.
pub func hash_map_update[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, other: const HashMap[K, V, KT]*):
    for entry in hash_map_begin_const(other):
        _ = hash_map_set(this, entry.key, entry.value)

# mark: Removal =================================================================================

## Ported from AK/HashMap.h:74 AK::HashMap::remove.
pub func hash_map_remove_k[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K) -> bool:
    var it = hash_map_find_k(this, key)
    if it.m_bucket != none:
        hash_table_remove_opaque(&this.m_table, &it)
        return true
    return false

## Ported from AK/HashMap.h:85 AK::HashMap::remove(Key const&) for a hash-compatible key.
pub func hash_map_remove_t_key[K, V, KT: Traits[K], Key, KeyT: HashCompatibleTraits[K, Key]](this: HashMap[K, V, KT]*, key: Key) -> bool:
    var it = hash_map_find_t_key[K, V, KT, Key, KeyT](this, key)
    if it.m_bucket != none:
        hash_table_remove_opaque(&this.m_table, &it)
        return true
    return false

## Ported from AK/HashMap.h:96 AK::HashMap::remove_all_matching.
pub func hash_map_remove_all_matching[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, predicate: Function2[const K*, const V*, bool]) -> bool:
    var captured = predicate
    let call: func(void*?, const HashMapEntry[K, V]*) -> bool = hash_map_entry_predicate
    return hash_table_remove_all_matching(&this.m_table, Function1[const HashMapEntry[K, V]*, bool](call = call, context = &captured))

## Ported from AK/HashMap.h:104 AK::HashMap::take_all_matching.
pub func hash_map_take_all_matching[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, predicate: Function2[const K*, const V*, bool]) -> Vector[HashMapEntry[K, V]]:
    var captured = predicate
    let call: func(void*?, const HashMapEntry[K, V]*) -> bool = hash_map_entry_predicate
    return hash_table_take_all_matching(&this.m_table, Function1[const HashMapEntry[K, V]*, bool](call = call, context = &captured))

# mark: Iteration and lookup ====================================================================

## Ported from AK/HashMap.h:116 AK::HashMap::begin.
pub func hash_map_begin[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*) -> HashTableIterator[HashMapEntry[K, V]]:
    return hash_table_begin(&this.m_table)

## Ported from AK/HashMap.h:117 AK::HashMap::end.
pub func hash_map_end[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*) -> HashTableIterator[HashMapEntry[K, V]]:
    return hash_table_end(&this.m_table)

## Ported from AK/HashMap.h:118 AK::HashMap::find.
pub func hash_map_find_k[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K) -> HashTableIterator[HashMapEntry[K, V]]:
    if hash_table_is_empty(&this.m_table):
        return hash_table_end(&this.m_table)
    var traits: KT = ---
    var captures = HashMapKeyEquals[K, V, KT](key = key)
    let call: func(void*?, const HashMapEntry[K, V]*) -> bool = HashMapKeyEquals[K, V, KT].call
    return hash_table_find_u32_tt_unary_predicate(&this.m_table, traits.hash_of(&key), Function1[const HashMapEntry[K, V]*, bool](call = call, context = &captures))

## Ported from AK/HashMap.h:125 AK::HashMap::find(hash, predicate).
pub func hash_map_find_u32_tt_unary_predicate[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, hash_: u32, predicate: Function1[const HashMapEntry[K, V]*, bool]) -> HashTableIterator[HashMapEntry[K, V]]:
    return hash_table_find_u32_tt_unary_predicate(&this.m_table, hash_, predicate)

## Ported from AK/HashMap.h:130 AK::HashMap::begin const.
pub func hash_map_begin_const[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*) -> HashTableIterator[HashMapEntry[K, V]]:
    return hash_table_begin_const(&this.m_table)

## Ported from AK/HashMap.h:131 AK::HashMap::end const.
pub func hash_map_end_const[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*) -> HashTableIterator[HashMapEntry[K, V]]:
    return hash_table_end_const(&this.m_table)

## Ported from AK/HashMap.h:132 AK::HashMap::find const.
pub func hash_map_find_k_const[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*, key: K) -> HashTableIterator[HashMapEntry[K, V]]:
    return hash_map_find_k((HashMap[K, V, KT]*)this, key)

## Ported from AK/HashMap.h:139 AK::HashMap::find(hash, predicate) const.
pub func hash_map_find_u32_tt_unary_predicate_const[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*, hash_: u32, predicate: Function1[const HashMapEntry[K, V]*, bool]) -> HashTableIterator[HashMapEntry[K, V]]:
    return hash_table_find_u32_tt_unary_predicate_const(&this.m_table, hash_, predicate)

## Ported from AK/HashMap.h:145 AK::HashMap::find(Key const&) for a hash-compatible key.
pub func hash_map_find_t_key[K, V, KT: Traits[K], Key, KeyT: HashCompatibleTraits[K, Key]](this: HashMap[K, V, KT]*, key: Key) -> HashTableIterator[HashMapEntry[K, V]]:
    if hash_table_is_empty(&this.m_table):
        return hash_table_end(&this.m_table)
    var traits: KeyT = ---
    var captures = HashMapCompatibleKeyEquals[K, V, Key, KeyT](key = key)
    let call: func(void*?, const HashMapEntry[K, V]*) -> bool = HashMapCompatibleKeyEquals[K, V, Key, KeyT].call
    return hash_table_find_u32_tt_unary_predicate(&this.m_table, traits.hash_of(&key), Function1[const HashMapEntry[K, V]*, bool](call = call, context = &captures))

## Ported from AK/HashMap.h:153 AK::HashMap::find(Key const&) const for a hash-compatible key.
pub func hash_map_find_t_key_const[K, V, KT: Traits[K], Key, KeyT: HashCompatibleTraits[K, Key]](this: const HashMap[K, V, KT]*, key: Key) -> HashTableIterator[HashMapEntry[K, V]]:
    return hash_map_find_t_key[K, V, KT, Key, KeyT]((HashMap[K, V, KT]*)this, key)

## Ported from AK/HashMap.h:159 AK::HashMap::try_ensure_capacity.
pub func hash_map_try_ensure_capacity[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, capacity: usize) -> !:
    return try hash_table_try_ensure_capacity(&this.m_table, capacity)

## Ported from AK/HashMap.h:161 AK::HashMap::ensure_capacity.
pub func hash_map_ensure_capacity[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, capacity: usize):
    hash_table_ensure_capacity(&this.m_table, capacity)

## Ported from AK/HashMap.h:163 AK::HashMap::get const: the value for `key`, if any.
pub func hash_map_get_k_const[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*, key: K) -> const V*?:
    var it = hash_map_find_k_const(this, key)
    let bucket = it.m_bucket else return none
    return &bucket.storage.value

## Ported from AK/HashMap.h:181 AK::HashMap::get: the value for `key`, if any.
pub func hash_map_get_k[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K) -> V*?:
    var it = hash_map_find_k(this, key)
    let bucket = it.m_bucket else return none
    return &bucket.storage.value

## Ported from AK/HashMap.h:190 AK::HashMap::get(Key const&) const for a hash-compatible key.
pub func hash_map_get_t_key_const[K, V, KT: Traits[K], Key, KeyT: HashCompatibleTraits[K, Key]](this: const HashMap[K, V, KT]*, key: Key) -> const V*?:
    var it = hash_map_find_t_key_const[K, V, KT, Key, KeyT](this, key)
    let bucket = it.m_bucket else return none
    return &bucket.storage.value

## Ported from AK/HashMap.h:210 AK::HashMap::get(Key const&) for a hash-compatible key.
pub func hash_map_get_t_key[K, V, KT: Traits[K], Key, KeyT: HashCompatibleTraits[K, Key]](this: HashMap[K, V, KT]*, key: Key) -> V*?:
    var it = hash_map_find_t_key[K, V, KT, Key, KeyT](this, key)
    let bucket = it.m_bucket else return none
    return &bucket.storage.value

## Ported from AK/HashMap.h:220 AK::HashMap::contains.
pub func hash_map_contains_k[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*, key: K) -> bool:
    let it = hash_map_find_k_const(this, key)
    return it.m_bucket != none

## Ported from AK/HashMap.h:226 AK::HashMap::contains(Key const&) for a hash-compatible key.
pub func hash_map_contains_t_key[K, V, KT: Traits[K], Key, KeyT: HashCompatibleTraits[K, Key]](this: const HashMap[K, V, KT]*, value: Key) -> bool:
    let it = hash_map_find_t_key_const[K, V, KT, Key, KeyT](this, value)
    return it.m_bucket != none

## Ported from AK/HashMap.h:231 AK::HashMap::remove(IteratorType).
pub func hash_map_remove_opaque[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, it: HashTableIterator[HashMapEntry[K, V]]):
    var iterator = it
    hash_table_remove_opaque(&this.m_table, &iterator)

# mark: Taking and ensuring =====================================================================

## Ported from AK/HashMap.h:236 AK::HashMap::take.
pub func hash_map_take_k[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K) -> V?:
    var it = hash_map_find_k(this, key)
    if let bucket = it.m_bucket:
        let value = bucket.storage.value
        hash_table_remove_opaque(&this.m_table, &it)
        return value
    return none

## Ported from AK/HashMap.h:247 AK::HashMap::take(Key const&) for a hash-compatible key.
pub func hash_map_take_t_key[K, V, KT: Traits[K], Key, KeyT: HashCompatibleTraits[K, Key]](this: HashMap[K, V, KT]*, key: Key) -> V?:
    var it = hash_map_find_t_key[K, V, KT, Key, KeyT](this, key)
    if let bucket = it.m_bucket:
        let value = bucket.storage.value
        hash_table_remove_opaque(&this.m_table, &it)
        return value
    return none

## Ported from AK/HashMap.h:261 AK::HashMap::take_first (ordered maps only).
pub func hash_map_take_first[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*) -> V:
    assert(this.m_table.m_ordered)
    assert(not hash_map_is_empty(this))
    let first = this.m_table.m_head else trap("VERIFY: empty OrderedHashMap")
    return hash_map_take_k(this, first.storage.key) else trap("VERIFY: OrderedHashMap::take_first")

## Ported from AK/HashMap.h:269 AK::HashMap::ensure(key, initialization_callback).
pub func hash_map_ensure_t_callback[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K, initialization_callback: Function0[V], existing_entry_behavior: HashSetExistingEntryBehavior = HashSetExistingEntryBehavior.keep) -> V*:
    var traits: KT = ---
    var equals_captures = HashMapKeyEquals[K, V, KT](key = key)
    let equals: func(void*?, const HashMapEntry[K, V]*) -> bool = HashMapKeyEquals[K, V, KT].call
    var entry_captures = HashMapEnsureEntry[K, V](key = key, initialization_callback = initialization_callback)
    let make_entry: func(void*?) -> HashMapEntry[K, V] = hash_map_ensure_entry
    let entry = hash_table_ensure_u32(&this.m_table, traits.hash_of(&key), Function1[const HashMapEntry[K, V]*, bool](call = equals, context = &equals_captures), Function0[HashMapEntry[K, V]](call = make_entry, context = &entry_captures), existing_entry_behavior)
    return &entry.value

## Ported from AK/HashMap.h:274 AK::HashMap::ensure(key): inserts V() (the zero value) when the
## key is absent.
pub func hash_map_ensure[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K) -> V*:
    let make_value: func(void*?) -> V = hash_map_default_value
    return hash_map_ensure_t_callback(this, key, Function0[V](call = make_value, context = none))

## Ported from AK/HashMap.h:280 AK::HashMap::try_ensure. A fallible callback (FallibleFunction)
## is a Function0 whose function fails: call it with `try` before passing its value here.
pub func hash_map_try_ensure[K, V, KT: Traits[K]](this: HashMap[K, V, KT]*, key: K, initialization_callback: Function0[V]) -> V!:
    let it = hash_map_find_k(this, key)
    if let bucket = it.m_bucket:
        return bucket.storage.value
    let result = try hash_map_try_set(this, key, function0_call(&initialization_callback))
    assert(result == HashSetResult.inserted_new_entry)
    let found = hash_map_find_k(this, key)
    let bucket = found.m_bucket else trap("VERIFY: HashMap::try_ensure")
    return bucket.storage.value

## Ported from AK/HashMap.h:295 AK::HashMap::keys.
pub func hash_map_keys[K, V, KT: Traits[K]](this: const HashMap[K, V, KT]*) -> Vector[K]:
    var list: Vector[K]
    vector_ensure_capacity(&list, hash_map_size(this))
    for entry in hash_map_begin_const(this):
        vector_unchecked_append_u(&list, entry.key)
    return list

# mark: Comparison ==============================================================================

## Ported from AK/HashMap.h:318 AK::HashMap::operator==.
pub func hash_map_eq[K, V: luce.Equatable, KT: Traits[K]](this: const HashMap[K, V, KT]*, other: const HashMap[K, V, KT]*) -> bool:
    if hash_map_size(this) != hash_map_size(other):
        return false
    if hash_map_is_empty(this):
        return true
    for entry in hash_map_begin_const(this):
        let it = hash_map_find_k_const(other, entry.key)
        let bucket = it.m_bucket else return false
        if not (entry.value == bucket.storage.value):
            return false
    return true

## Ported from AK/HashMap.h:336 AK::HashMap::operator!=.
pub func hash_map_ne[K, V: luce.Equatable, KT: Traits[K]](this: const HashMap[K, V, KT]*, other: const HashMap[K, V, KT]*) -> bool:
    return not hash_map_eq(this, other)