Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.0

0.6.0 / src / ak / vector_1.lucb

#==============================================================================================
#
#   vector_1 - Vector<T>: construction, access, searching, appending and removal
#
#   DESCRIPTION:
#       Port of AK/Vector.h (lines 1-614). The struct is support.lucb's Vector[T]: size,
#       capacity and outline buffer, with the inline capacity dropped (DESIGN.md §2.6), so
#       `inline_capacity` is 0 and there is no fast-last-access metadata. Vector<T&> is
#       Vector[T*]. Moves are copies (§3.3 rule 1): a moved-from vector is emptied where the
#       donor empties it, which is why the moving members take the other vector by pointer.
#       A C++ copy of a vector is vector_clone (§3.3 rule 2).
#
#       Predicates are Function1[const T*, bool] (DESIGN.md §2.7): a capture struct on the
#       stack and a function taking its address. Traits<T>::equals is a traits parameter
#       (`vector_contains_slow[T, TT]`); operator== of the elements needs `T: Equatable`.
#
#==============================================================================================

# mark: Construction ============================================================================

## Ported from AK/Vector.h:71 AK::Vector::Vector<T, inline_capacity>.
pub func vector_construct[T](this: Vector[T]*):
    this.m_size = 0
    this.m_capacity = 0
    this.m_outline_buffer = none

## A Vector whose buffer is atomic storage, never scanned for pointers: for vectors of plain
## scalars (DESIGN.md §3.3 rule 5, `Vector[T].create_atomic()`).
pub func vector_create_atomic[T]() -> Vector[T]:
    var vector: Vector[T]
    vector.m_atomic = true
    return vector

## Ported from AK/Vector.h:77 AK::Vector::Vector(std::initializer_list<T>).
pub func vector_construct_opaque[T](this: Vector[T]*, list: const T[]):
    vector_ensure_capacity(this, list.length)
    for item in list:
        vector_unchecked_append_u(this, item)

## Ported from AK/Vector.h:94 AK::Vector::Vector(Vector const&): the copy of `other` with its
## own buffer (DESIGN.md §3.3 rule 2: a C++ copy of a mutable container is a clone).
pub func vector_clone[T](other: const Vector[T]*) -> Vector[T]:
    var vector: Vector[T]
    vector.m_atomic = other.m_atomic
    vector_ensure_capacity(&vector, vector_size(other))
    if vector_size(other) > 0:
        let source = other.m_outline_buffer else trap("VERIFY: Vector without storage")
        _ = typed_transfer_copy(vector_slot(&vector, 0), source, vector_size(other))
    vector.m_size = vector_size(other)
    return vector

## Ported from AK/Vector.h:113 AK::Vector::Vector(ReadonlySpan<T>).
pub func vector_construct_opaque_2[T](this: Vector[T]*, other: const T[]):
    vector_ensure_capacity(this, other.length)
    if other.length > 0:
        _ = typed_transfer_copy(vector_slot(this, 0), other.data, other.length)
    this.m_size = other.length

## Ported from AK/Vector.h:138 AK::Vector::span.
pub func vector_span[T](this: Vector[T]*) -> T[]:
    let data = this.m_outline_buffer else return empty_span[T]()
    return T[](data, this.m_size)

## Ported from AK/Vector.h:139 AK::Vector::span const.
pub func vector_span_const[T](this: const Vector[T]*) -> const T[]:
    let data = this.m_outline_buffer else return empty_span[T]()
    return T[](data, this.m_size)

## Ported from AK/Vector.h:141 AK::Vector::operator Span<T>.
pub func vector_to_span_conditional_contains_reference_raw_ptr_remove_reference_t_type_type_t_type[T](this: Vector[T]*) -> T[]:
    return vector_span(this)

## Ported from AK/Vector.h:142 AK::Vector::operator ReadonlySpan<T>.
pub func vector_to_span_const_conditional_contains_reference_raw_ptr_remove_reference_t_type_type_t_type[T](this: const Vector[T]*) -> const T[]:
    return vector_span_const(this)

# mark: Access ==================================================================================

## Ported from AK/Vector.h:144 AK::Vector::is_empty.
pub func vector_is_empty[T](this: const Vector[T]*) -> bool:
    return vector_size(this) == 0

## Ported from AK/Vector.h:145 AK::Vector::size.
pub func vector_size[T](this: const Vector[T]*) -> usize:
    return this.m_size

## Ported from AK/Vector.h:146 AK::Vector::capacity.
pub func vector_capacity[T](this: const Vector[T]*) -> usize:
    return this.m_capacity

## Ported from AK/Vector.h:148 AK::Vector::data.
pub func vector_data[T](this: Vector[T]*) -> T*?:
    return this.m_outline_buffer

## Ported from AK/Vector.h:155 AK::Vector::data const.
pub func vector_data_const[T](this: const Vector[T]*) -> const T*?:
    return this.m_outline_buffer

## Ported from AK/Vector.h:162 AK::Vector::at const.
pub func vector_at_const[T](this: const Vector[T]*, i: usize) -> const T*:
    assert(i < this.m_size)
    let data = this.m_outline_buffer else trap("VERIFY: Vector without storage")
    return data + i

## Ported from AK/Vector.h:171 AK::Vector::at.
pub func vector_at[T](this: Vector[T]*, i: usize) -> T*:
    assert(i < this.m_size)
    let data = this.m_outline_buffer else trap("VERIFY: Vector without storage")
    return data + i

## Ported from AK/Vector.h:180 AK::Vector::operator[] const.
pub func vector_at_const_2[T](this: const Vector[T]*, i: usize) -> const T*:
    return vector_at_const(this, i)

## Ported from AK/Vector.h:181 AK::Vector::operator[].
pub func vector_at_2[T](this: Vector[T]*, i: usize) -> T*:
    return vector_at(this, i)

## Ported from AK/Vector.h:183 AK::Vector::get.
pub func vector_get[T](this: Vector[T]*, i: usize) -> T*?:
    if i >= vector_size(this):
        return none
    return vector_at(this, i)

## Ported from AK/Vector.h:190 AK::Vector::get const.
pub func vector_get_const[T](this: const Vector[T]*, i: usize) -> const T*?:
    if i >= vector_size(this):
        return none
    return vector_at_const(this, i)

## Ported from AK/Vector.h:197 AK::Vector::first const.
pub func vector_first_const[T](this: const Vector[T]*) -> const T*:
    return vector_at_const(this, 0)

## Ported from AK/Vector.h:198 AK::Vector::first.
pub func vector_first[T](this: Vector[T]*) -> T*:
    return vector_at(this, 0)

## Ported from AK/Vector.h:200 AK::Vector::last const.
pub func vector_last_const[T](this: const Vector[T]*) -> const T*:
    return vector_at_const(this, this.m_size - 1)

## Ported from AK/Vector.h:212 AK::Vector::last.
pub func vector_last[T](this: Vector[T]*) -> T*:
    return vector_at(this, this.m_size - 1)

## Ported from AK/Vector.h:225 AK::Vector::unsafe_last const (fast-last-access vectors: the
## last element without a bounds check).
pub func vector_unsafe_last_const[T](this: const Vector[T]*) -> const T*:
    let data = this.m_outline_buffer else trap("VERIFY: Vector without storage")
    return data + (this.m_size - 1)

## Ported from AK/Vector.h:230 AK::Vector::unsafe_last.
pub func vector_unsafe_last[T](this: Vector[T]*) -> T*:
    let data = this.m_outline_buffer else trap("VERIFY: Vector without storage")
    return data + (this.m_size - 1)

## Ported from AK/Vector.h:237 AK::Vector::first_matching.
pub func vector_first_matching[T](this: Vector[T]*, predicate: Function1[const T*, bool]) -> T*?:
    for i in 0..<vector_size(this):
        if function1_call(&predicate, vector_at(this, i)):
            return vector_at(this, i)
    return none

## Ported from AK/Vector.h:249 AK::Vector::first_matching const.
pub func vector_first_matching_const[T](this: const Vector[T]*, predicate: Function1[const T*, bool]) -> const T*?:
    for i in 0..<vector_size(this):
        if function1_call(&predicate, vector_at_const(this, i)):
            return vector_at_const(this, i)
    return none

## Ported from AK/Vector.h:261 AK::Vector::last_matching.
pub func vector_last_matching[T](this: const Vector[T]*, predicate: Function1[const T*, bool]) -> const T*?:
    var i = (isize)vector_size(this) - 1
    while i >= 0:
        if function1_call(&predicate, vector_at_const(this, (usize)i)):
            return vector_at_const(this, (usize)i)
        i -= 1
    return none

## Ported from AK/Vector.h:273 AK::Vector::operator==.
pub func vector_eq[T: luce.Equatable](this: const Vector[T]*, other: const Vector[T]*) -> bool:
    if this.m_size != vector_size(other):
        return false
    let a = this.m_outline_buffer else return true
    let b = other.m_outline_buffer else return true
    return typed_transfer_compare(a, b, vector_size(this))

## Ported from AK/Vector.h:281 AK::Vector::contains_slow.
pub func vector_contains_slow[T, TT: Traits[T]](this: const Vector[T]*, value: T) -> bool:
    var traits: TT = ---
    for i in 0..<vector_size(this):
        if traits.equals(vector_at_const(this, i), &value):
            return true
    return false

## Ported from AK/Vector.h:291 AK::Vector::contains (predicate).
pub func vector_contains[T](this: const Vector[T]*, predicate: Function1[const T*, bool]) -> bool:
    let it = vector_find_if_const(this, predicate)
    return not simple_iterator_is_end(&it)

## Ported from AK/Vector.h:297 AK::Vector::contains_in_range.
pub func vector_contains_in_range[T, TT: Traits[T]](this: const Vector[T]*, value: T, start: usize, end: usize) -> bool:
    assert(start <= end)
    assert(end < vector_size(this))
    var traits: TT = ---
    for i in start..=end:
        if traits.equals(vector_at_const(this, i), &value):
            return true
    return false

# mark: Insertion and appending =================================================================

## Ported from AK/Vector.h:309 AK::Vector::insert.
pub func vector_insert[T](this: Vector[T]*, index: usize, value: T):
    vector_try_insert(this, index, value) else trap("MUST: Vector::insert")

## Ported from AK/Vector.h:316 AK::Vector::insert_before_matching.
pub func vector_insert_before_matching[T](this: Vector[T]*, value: T, predicate: Function1[const T*, bool], first_index: usize = 0, inserted_index: usize*? = none):
    vector_try_insert_before_matching(this, value, predicate, first_index, inserted_index) else trap("MUST: Vector::insert_before_matching")

## Ported from AK/Vector.h:322 AK::Vector::extend(Vector&&): `other` is emptied.
pub func vector_extend[T](this: Vector[T]*, other: Vector[T]*):
    vector_try_extend(this, other) else trap("MUST: Vector::extend")

## Ported from AK/Vector.h:327 AK::Vector::extend(Vector const&).
pub func vector_extend_2[T](this: Vector[T]*, other: const Vector[T]*):
    vector_try_extend_2(this, other) else trap("MUST: Vector::extend")

## Ported from AK/Vector.h:332 AK::Vector::append(T&&).
pub func vector_append_t[T](this: Vector[T]*, value: T):
    vector_try_append_t(this, value) else trap("MUST: Vector::append")

## Ported from AK/Vector.h:340 AK::Vector::append(T const&).
pub func vector_append_t_2[T](this: Vector[T]*, value: T):
    vector_try_append_t_2(this, value) else trap("MUST: Vector::append")

## Ported from AK/Vector.h:346 AK::Vector::append(StorageType const*, size_t).
pub func vector_append_opaque[T](this: Vector[T]*, values: const T*?, count: usize):
    vector_try_append_opaque(this, values, count) else trap("MUST: Vector::append")

## Ported from AK/Vector.h:352 AK::Vector::unchecked_append.
pub func vector_unchecked_append_u[T](this: Vector[T]*, value: T):
    assert(this.m_size < vector_capacity(this))
    this.m_size += 1

    let last_slot = vector_slot(this, this.m_size - 1)
    *last_slot = value

## Ported from AK/Vector.h:376 AK::Vector::unchecked_append(StorageType const*, size_t).
pub func vector_unchecked_append_opaque[T](this: Vector[T]*, values: const T*?, count: usize):
    if count == 0:
        return
    assert((vector_size(this) + count) <= vector_capacity(this))
    let source = values else trap("VERIFY: unchecked_append from null")
    _ = typed_transfer_copy(vector_slot(this, this.m_size), source, count)
    this.m_size += count
    vector_update_metadata(this)  # We have *some* space, since we're appending.

## Ported from AK/Vector.h:415 AK::Vector::prepend.
pub func vector_prepend_u[T](this: Vector[T]*, value: T):
    vector_try_insert(this, 0, value) else trap("MUST: Vector::prepend")

## Ported from AK/Vector.h:421 AK::Vector::prepend(Vector&&): `other` is emptied.
pub func vector_prepend_vector[T](this: Vector[T]*, other: Vector[T]*):
    vector_try_prepend_vector(this, other) else trap("MUST: Vector::prepend")

## Ported from AK/Vector.h:426 AK::Vector::prepend(StorageType const*, size_t).
pub func vector_prepend_opaque[T](this: Vector[T]*, values: const T*?, count: usize):
    vector_try_prepend_opaque(this, values, count) else trap("MUST: Vector::prepend")

## Ported from AK/Vector.h:432 AK::Vector::operator=(Vector&&): `this` takes `other`'s
## buffer and `other` is emptied.
pub func vector_move_assign[T](this: Vector[T]*, other: Vector[T]*):
    if this != other:
        vector_clear(this)
        this.m_size = other.m_size
        this.m_capacity = other.m_capacity
        this.m_outline_buffer = other.m_outline_buffer
        this.m_atomic = other.m_atomic
        other.m_outline_buffer = none
        other.m_size = 0
        vector_reset_capacity(other)

# mark: Clearing and removal ====================================================================

## Ported from AK/Vector.h:480 AK::Vector::clear.
pub func vector_clear[T](this: Vector[T]*):
    vector_clear_with_capacity(this)
    if let buffer = this.m_outline_buffer:
        kfree(buffer)
        this.m_outline_buffer = none
    vector_reset_capacity(this)

## Ported from AK/Vector.h:490 AK::Vector::clear_with_capacity.
pub func vector_clear_with_capacity[T](this: Vector[T]*):
    this.m_size = 0
    if this.m_capacity != 0:
        vector_update_metadata(this)

## Ported from AK/Vector.h:501 AK::Vector::remove.
pub func vector_remove[T](this: Vector[T]*, index: usize):
    assert(index < this.m_size)

    _ = typed_transfer_copy(vector_slot(this, index), vector_slot(this, index + 1), this.m_size - index - 1)

    this.m_size -= 1
    vector_update_metadata(this)  # We have *some* space, we just removed something that was there.

## Ported from AK/Vector.h:519 AK::Vector::remove(size_t, size_t).
pub func vector_remove_usize[T](this: Vector[T]*, index: usize, count: usize):
    if count == 0:
        return
    assert(index + count > index)
    assert(index + count <= this.m_size)

    _ = typed_transfer_copy(vector_slot(this, index), vector_slot(this, index + count), this.m_size - index - count)

    this.m_size -= count
    vector_update_metadata(this)  # We have *some* space, we just removed something that was there.

## Ported from AK/Vector.h:543 AK::Vector::remove_all(It, EndIt, ToIndex): removes the indices
## an iterator pair yields, *in ascending order*. The pair is a span of indices here (the
## donor's `to_index` maps an iterator to its index; with indices it is the identity).
pub func vector_remove_all_t_it[T](this: Vector[T]*, indices: const usize[]):
    var it: usize = 0
    let end = indices.length
    if not (it != end):
        return
    var write_index = indices[it]
    assert(write_index < this.m_size)
    it += 1
    var next_remove_index = indices[it] if it != end else this.m_size
    for read_index in (write_index + 1)..<this.m_size:
        if read_index == next_remove_index:
            it += 1
            next_remove_index = indices[it] if it != end else this.m_size
        else:
            *vector_slot(this, write_index) = *vector_slot(this, read_index)
            write_index += 1

    assert(not (it != end))
    this.m_size = write_index
    vector_update_metadata(this)  # We have *some* space, we just removed something that was there.

## Ported from AK/Vector.h:574 AK::Vector::remove_all(Is, ToIndex): the indices held by a
## container (a Vector of indices, ascending).
pub func vector_remove_all_t_is[T](this: Vector[T]*, indices: const Vector[usize]*):
    vector_remove_all_t_it(this, vector_span_const(indices))

## Ported from AK/Vector.h:580 AK::Vector::remove_first_matching.
pub func vector_remove_first_matching[T](this: Vector[T]*, predicate: Function1[const T*, bool]) -> bool:
    for i in 0..<vector_size(this):
        if function1_call(&predicate, vector_at(this, i)):
            vector_remove(this, i)
            return true
    return false

## Ported from AK/Vector.h:592 AK::Vector::remove_all_matching.
pub func vector_remove_all_matching[T](this: Vector[T]*, predicate: Function1[const T*, bool]) -> bool:
    var write_index: usize = 0
    for read_index in 0..<this.m_size:
        if function1_call(&predicate, vector_at(this, read_index)):
            continue
        if read_index != write_index:
            typed_transfer_move(vector_slot(this, write_index), vector_slot(this, read_index), 1)
        write_index += 1

    if write_index == this.m_size:
        return false

    this.m_size = write_index
    vector_update_metadata(this)
    return true