Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / hash_table_2.lucb

#==============================================================================================
#
#   hash_table_2 - HashTable<T>: removal, rehashing and the Robin Hood bucket machinery
#
#   DESCRIPTION:
#       Port of AK/HashTable.h (lines 512-940); see hash_table_1.
#
#==============================================================================================

# mark: Removal and bulk access =================================================================

## Ported from AK/HashTable.h:512 AK::HashTable::remove(Iterator&). This invalidates the
## iterator.
pub func hash_table_remove_opaque[T, TT: Traits[T]](this: HashTable[T, TT]*, iterator: HashTableIterator[T]*):
    let bucket = iterator.m_bucket else trap("VERIFY: removing the end of a HashTable")
    hash_table_delete_bucket(this, bucket)
    iterator.m_bucket = none

## Ported from AK/HashTable.h:518 AK::HashTable::remove_all_matching.
pub func hash_table_remove_all_matching[T, TT: Traits[T]](this: HashTable[T, TT]*, predicate: Function1[const T*, bool]) -> bool:
    var has_removed_anything = false
    var i: usize = 0
    while i < hash_table_capacity(this):
        let bucket = hash_table_bucket_at(this, i)
        if bucket.state == (u8)BucketState.free_ or not function1_call(&predicate, &bucket.storage):
            i += 1
            continue

        hash_table_delete_bucket(this, bucket)
        has_removed_anything = true

        # If a bucket was shifted up, reevaluate this bucket index
        if bucket.state == (u8)BucketState.free_:
            i += 1
    return has_removed_anything

## Ported from AK/HashTable.h:537 AK::HashTable::take_all_matching.
pub func hash_table_take_all_matching[T, TT: Traits[T]](this: HashTable[T, TT]*, predicate: Function1[const T*, bool]) -> Vector[T]:
    var values: Vector[T]
    var i: usize = 0
    while i < hash_table_capacity(this):
        let bucket = hash_table_bucket_at(this, i)
        if bucket.state == (u8)BucketState.free_ or not function1_call(&predicate, &bucket.storage):
            i += 1
            continue

        vector_append_t(&values, bucket.storage)
        hash_table_delete_bucket(this, bucket)

        # If a bucket was shifted up, reevaluate this bucket index
        if bucket.state == (u8)BucketState.free_:
            i += 1
    return values

## Ported from AK/HashTable.h:555 AK::HashTable::take_last (ordered tables only).
pub func hash_table_take_last[T, TT: Traits[T]](this: HashTable[T, TT]*) -> T:
    assert(this.m_ordered)
    assert(not hash_table_is_empty(this))
    let tail = this.m_tail else trap("VERIFY: empty OrderedHashTable")
    let element = tail.storage
    hash_table_delete_bucket(this, tail)
    return element

## Ported from AK/HashTable.h:564 AK::HashTable::take_first (ordered tables only).
pub func hash_table_take_first[T, TT: Traits[T]](this: HashTable[T, TT]*) -> T:
    assert(this.m_ordered)
    assert(not hash_table_is_empty(this))
    let head = this.m_head else trap("VERIFY: empty OrderedHashTable")
    let element = head.storage
    hash_table_delete_bucket(this, head)
    return element

## Ported from AK/HashTable.h:573 AK::HashTable::values.
pub func hash_table_values[T, TT: Traits[T]](this: const HashTable[T, TT]*) -> Vector[T]:
    var list: Vector[T]
    vector_ensure_capacity(&list, hash_table_size(this))
    for value in hash_table_begin_const(this):
        vector_unchecked_append_u(&list, *value)
    return list

# mark: Buckets =================================================================================

## Ported from AK/HashTable.h:583 AK::HashTable::should_grow.
pub func hash_table_should_grow[T, TT: Traits[T]](this: const HashTable[T, TT]*) -> bool:
    return ((this.m_size + 1) * 100) >= (hash_table_capacity(this) * hash_table_grow_at_load_factor_percent)

## Ported from AK/HashTable.h:584 AK::HashTable::size_in_bytes.
pub func hash_table_size_in_bytes[T, TT: Traits[T]](capacity: usize) -> usize:
    return memory.size_of(HashTableBucket[T]) * capacity

# The bucket at `index` of the bucket array.
func hash_table_bucket_at[T, TT: Traits[T]](this: const HashTable[T, TT]*, index: usize) -> HashTableBucket[T]*:
    let buckets = this.m_buckets else trap("VERIFY: HashTable without buckets")
    return buckets + index

## Ported from AK/HashTable.h:586 AK::HashTable::relocate_bucket. An unordered table's links are
## always none, so exchanging them is the donor's `if constexpr (IsOrdered)` branch or nothing.
pub func hash_table_relocate_bucket[T, TT: Traits[T]](dst: HashTableBucket[T]*, src: HashTableBucket[T]*):
    dst.state = src.state
    dst.hash = src.hash
    dst.previous = exchange(&src.previous, none)
    dst.next = exchange(&src.next, none)
    dst.storage = src.storage

## Ported from AK/HashTable.h:597 AK::HashTable::swap_buckets.
pub func hash_table_swap_buckets[T, TT: Traits[T]](a: HashTableBucket[T]*, b: HashTableBucket[T]*):
    swap_5(&a.state, &b.state)
    swap_5(&a.hash, &b.hash)
    swap_5(&a.previous, &b.previous)
    swap_5(&a.next, &b.next)
    swap_5(&a.storage, &b.storage)

## Ported from AK/HashTable.h:609 AK::HashTable::end_bucket.
pub func hash_table_end_bucket[T, TT: Traits[T]](this: HashTable[T, TT]*) -> HashTableBucket[T]*?:
    if this.m_ordered:
        return this.m_tail
    let buckets = this.m_buckets else return none
    return buckets + hash_table_capacity(this)

## Ported from AK/HashTable.h:615 AK::HashTable::end_bucket const.
pub func hash_table_end_bucket_const[T, TT: Traits[T]](this: const HashTable[T, TT]*) -> HashTableBucket[T]*?:
    return hash_table_end_bucket((HashTable[T, TT]*)this)

## Ported from AK/HashTable.h:623 AK::HashTable::try_rehash.
pub func hash_table_try_rehash[T, TT: Traits[T]](this: HashTable[T, TT]*, new_capacity: usize) -> !:
    let at_least = hash_table_capacity(this) + 1
    let capacity = exp2_usize(ceil_log2_usize(new_capacity if new_capacity > at_least else at_least))
    assert(capacity >= hash_table_size(this))

    let old_buckets = this.m_buckets
    var old_iter = hash_table_begin(this)

    let new_buckets = kcalloc(1, hash_table_size_in_bytes[T, TT](capacity)) else return try ak_error_throw(ak_error_from_errno(enomem))

    this.m_buckets = (HashTableBucket[T]*)new_buckets
    this.m_mask = capacity - 1

    if this.m_ordered:
        this.m_head = none
        this.m_tail = none

    let buckets = old_buckets else return

    this.m_size = 0
    while let value = hash_table_iterator_next(&old_iter):
        _ = hash_table_write_value(this, *value, HashSetExistingEntryBehavior.keep)

    kfree(buckets)

## Ported from AK/HashTable.h:653 AK::HashTable::rehash.
pub func hash_table_rehash[T, TT: Traits[T]](this: HashTable[T, TT]*, new_capacity: usize):
    hash_table_try_rehash(this, new_capacity) else trap("MUST: HashTable::rehash")

## Ported from AK/HashTable.h:659 AK::HashTable::lookup_with_hash.
pub func hash_table_lookup_with_hash[T, TT: Traits[T]](this: const HashTable[T, TT]*, hash_: u32, predicate: Function1[const T*, bool]) -> HashTableBucket[T]*?:
    if hash_table_is_empty(this):
        return none

    var bucket_index = (usize)hash_ & this.m_mask
    while true:
        let bucket = hash_table_bucket_at(this, bucket_index)
        if bucket.state == (u8)BucketState.free_:
            return none
        if bucket.hash == hash_ and function1_call(&predicate, &bucket.storage):
            return bucket
        bucket_index = (bucket_index + 1) & this.m_mask

## Ported from AK/HashTable.h:675 AK::HashTable::used_bucket_probe_length.
pub func hash_table_used_bucket_probe_length[T, TT: Traits[T]](this: const HashTable[T, TT]*, bucket: const HashTableBucket[T]*) -> usize:
    assert(bucket.state != (u8)BucketState.free_)

    if bucket.state == (u8)BucketState.calculate_length:
        var traits: TT = ---
        let ideal_bucket_index = (usize)traits.hash_of(&bucket.storage) & this.m_mask

        let buckets = this.m_buckets else trap("VERIFY: HashTable without buckets")
        assert(bucket >= buckets)
        let actual_bucket_index = (usize)(bucket - buckets)

        if actual_bucket_index < ideal_bucket_index:
            return hash_table_capacity(this) + actual_bucket_index - ideal_bucket_index
        return actual_bucket_index - ideal_bucket_index

    return (usize)bucket.state - 1

## Ported from AK/HashTable.h:693 AK::HashTable::bucket_state_for_probe_length: the state byte of
## a used bucket (a probe length + 1, or CalculateLength).
pub func hash_table_bucket_state_for_probe_length[T, TT: Traits[T]](this: HashTable[T, TT]*, probe_length: usize) -> BucketState:
    _ = this
    if probe_length > 253:
        return BucketState.calculate_length
    return (BucketState)(u8)(probe_length + 1)