Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.0

0.6.0 / src / ak / vector_2.lucb

#==============================================================================================
#
#   vector_2 - Vector<T>: taking, fallible growth, resizing, iteration and storage
#
#   DESCRIPTION:
#       Port of AK/Vector.h (lines 615-1141); see vector_1. ErrorOr<void> is `!`: the only
#       failures are ENOMEM from the allocator and EINVAL from an out-of-range insert
#       (ak_error_throw, DESIGN.md ยง2.10).
#
#==============================================================================================

# mark: Taking elements =========================================================================

## Ported from AK/Vector.h:615 AK::Vector::take_last.
pub func vector_take_last[T](this: Vector[T]*) -> T:
    assert(not vector_is_empty(this))
    let value = *vector_raw_last(this)
    this.m_size -= 1
    return value

## Ported from AK/Vector.h:645 AK::Vector::unsafe_take_last.
pub func vector_unsafe_take_last[T](this: Vector[T]*) -> T:
    let value = *vector_raw_last(this)
    this.m_size -= 1
    vector_update_metadata(this)  # We have *some* space, we just removed something that was there.
    return value

## Ported from AK/Vector.h:660 AK::Vector::take_first.
pub func vector_take_first[T](this: Vector[T]*) -> T:
    assert(not vector_is_empty(this))
    let value = *vector_raw_first(this)
    vector_remove(this, 0)
    return value

## Ported from AK/Vector.h:671 AK::Vector::take.
pub func vector_take[T](this: Vector[T]*, index: usize) -> T:
    let value = *vector_raw_at(this, index)
    vector_remove(this, index)
    return value

## Ported from AK/Vector.h:681 AK::Vector::unstable_take.
pub func vector_unstable_take[T](this: Vector[T]*, index: usize) -> T:
    assert(index < this.m_size)
    swap_5(vector_raw_at(this, index), vector_raw_at(this, this.m_size - 1))
    return vector_take_last(this)

# mark: Fallible insertion ======================================================================

## Ported from AK/Vector.h:689 AK::Vector::try_insert.
pub func vector_try_insert[T](this: Vector[T]*, index: usize, value: T) -> !:
    if index > vector_size(this):
        try ak_error_throw(ak_error_from_errno(einval))
    if index == vector_size(this):
        return try vector_try_append_t(this, value)
    try vector_try_grow_capacity(this, vector_size(this) + 1)
    this.m_size += 1
    typed_transfer_move(vector_slot(this, index + 1), vector_slot(this, index), this.m_size - index - 1)
    *vector_slot(this, index) = value
    vector_update_metadata(this)  # We have *some* space, try_grow_capacity above ensured nonzero.

## Ported from AK/Vector.h:715 AK::Vector::try_insert_before_matching.
pub func vector_try_insert_before_matching[T](this: Vector[T]*, value: T, predicate: Function1[const T*, bool], first_index: usize = 0, inserted_index: usize*? = none) -> !:
    var i = first_index
    while i < vector_size(this):
        if function1_call(&predicate, vector_at(this, i)):
            try vector_try_insert(this, i, value)
            if let index_out = inserted_index:
                *index_out = i
            return
        i += 1
    try vector_try_append_t(this, value)
    if let index_out = inserted_index:
        *index_out = vector_size(this) - 1

## Ported from AK/Vector.h:732 AK::Vector::try_extend(Vector&&): `other` is emptied.
pub func vector_try_extend[T](this: Vector[T]*, other: Vector[T]*) -> !:
    if vector_is_empty(this) and vector_capacity(this) <= vector_capacity(other):
        vector_move_assign(this, other)
        return
    let other_size = vector_size(other)
    var tmp: Vector[T]
    vector_move_assign(&tmp, other)
    try vector_try_grow_capacity(this, vector_size(this) + other_size)
    if let source = tmp.m_outline_buffer:
        typed_transfer_move(vector_slot(this, this.m_size), source, other_size)
    this.m_size += other_size
    vector_update_metadata(this)  # We have *some* space, try_grow_capacity above ensured nonzero.

## Ported from AK/Vector.h:747 AK::Vector::try_extend(Vector const&).
pub func vector_try_extend_2[T](this: Vector[T]*, other: const Vector[T]*) -> !:
    try vector_try_grow_capacity(this, vector_size(this) + vector_size(other))
    if let source = other.m_outline_buffer:
        _ = typed_transfer_copy(vector_slot(this, this.m_size), source, vector_size(other))
    this.m_size += other.m_size
    vector_update_metadata(this)  # We have *some* space, try_grow_capacity above ensured nonzero.

## Ported from AK/Vector.h:756 AK::Vector::try_append(T&&).
pub func vector_try_append_t[T](this: Vector[T]*, value: T) -> !:
    try vector_try_grow_capacity(this, vector_size(this) + 1)
    *vector_slot(this, this.m_size) = value
    this.m_size += 1
    vector_update_metadata(this)  # We have *some* space, try_grow_capacity above ensured nonzero.

## Ported from AK/Vector.h:768 AK::Vector::try_append(T const&).
pub func vector_try_append_t_2[T](this: Vector[T]*, value: T) -> !:
    return try vector_try_append_t(this, value)

## Ported from AK/Vector.h:774 AK::Vector::try_append(StorageType const*, size_t).
pub func vector_try_append_opaque[T](this: Vector[T]*, values: const T*?, count: usize) -> !:
    if count == 0:
        return
    let source = values else trap("VERIFY: try_append from null")
    try vector_try_grow_capacity(this, vector_size(this) + count)
    _ = typed_transfer_copy(vector_slot(this, this.m_size), source, count)
    this.m_size += count
    vector_update_metadata(this)  # We have *some* space, try_grow_capacity above ensured nonzero.

## Ported from AK/Vector.h:797 AK::Vector::try_prepend.
pub func vector_try_prepend_u[T](this: Vector[T]*, value: T) -> !:
    return try vector_try_insert(this, 0, value)

## Ported from AK/Vector.h:803 AK::Vector::try_prepend(Vector&&): `other` is emptied.
pub func vector_try_prepend_vector[T](this: Vector[T]*, other: Vector[T]*) -> !:
    if vector_is_empty(other):
        return

    if vector_is_empty(this):
        vector_move_assign(this, other)
        return

    let other_size = vector_size(other)
    try vector_try_grow_capacity(this, vector_size(this) + other_size)

    typed_transfer_move(vector_slot(this, other_size), vector_slot(this, 0), this.m_size)

    var tmp: Vector[T]
    vector_move_assign(&tmp, other)
    if let source = tmp.m_outline_buffer:
        typed_transfer_move(vector_slot(this, 0), source, vector_size(&tmp))
    this.m_size += other_size
    vector_update_metadata(this)  # We have *some* space, try_grow_capacity above ensured nonzero.

## Ported from AK/Vector.h:828 AK::Vector::try_prepend(StorageType const*, size_t).
pub func vector_try_prepend_opaque[T](this: Vector[T]*, values: const T*?, count: usize) -> !:
    if count == 0:
        return
    let source = values else trap("VERIFY: try_prepend from null")
    try vector_try_grow_capacity(this, vector_size(this) + count)
    typed_transfer_move(vector_slot(this, count), vector_slot(this, 0), this.m_size)
    _ = typed_transfer_copy(vector_slot(this, 0), source, count)
    this.m_size += count
    vector_update_metadata(this)  # We have *some* space, try_grow_capacity above ensured nonzero.

# mark: Capacity and resizing ===================================================================

## Ported from AK/Vector.h:840 AK::Vector::try_grow_capacity.
pub func vector_try_grow_capacity[T](this: Vector[T]*, needed_capacity: usize) -> !:
    if this.m_capacity >= needed_capacity:
        return
    return try vector_try_ensure_capacity(this, vector_padded_capacity[T](needed_capacity))

## Ported from AK/Vector.h:847 AK::Vector::try_ensure_capacity.
pub func vector_try_ensure_capacity[T](this: Vector[T]*, needed_capacity: usize) -> !:
    if this.m_capacity >= needed_capacity:
        return
    let new_capacity = kmalloc_good_size(needed_capacity * memory.size_of(T)) // memory.size_of(T)
    var allocation: void*?
    if this.m_atomic:
        let size = mul_usize(make_checked(new_capacity), make_checked(memory.size_of(T)))
        allocation = kmalloc_atomic(checked_value(&size))
    else:
        allocation = kmalloc_array(make_checked(new_capacity), make_checked(memory.size_of(T)))
    let new_buffer = (T*)(allocation else return try ak_error_throw(ak_error_from_errno(enomem)))

    if let old_buffer = this.m_outline_buffer:
        _ = typed_transfer_copy(new_buffer, old_buffer, this.m_size)
        kfree(old_buffer)
    this.m_outline_buffer = new_buffer
    this.m_capacity = new_capacity
    vector_update_metadata(this)  # We have *some* space, we just allocated it.

## Ported from AK/Vector.h:872 AK::Vector::try_resize: new elements are zero.
pub func vector_try_resize[T](this: Vector[T]*, new_size: usize, keep_capacity: bool = false) -> !:
    if new_size <= vector_size(this):
        vector_shrink(this, new_size, keep_capacity)
        return

    try vector_try_ensure_capacity(this, new_size)

    # For trivial types, we can just zero the new memory. (Every luce-base value is one.)
    let old_size = vector_size(this)
    let bytes = (new_size - old_size) * memory.size_of(T)
    memory.set(u8[]((u8*)vector_slot(this, old_size), bytes), 0)
    this.m_size = new_size
    vector_update_metadata(this)  # We have *some* space, try_ensure_capacity above ensured nonzero.

## Ported from AK/Vector.h:895 AK::Vector::try_resize_with_default_value.
pub func vector_try_resize_with_default_value[T](this: Vector[T]*, new_size: usize, default_value: T, keep_capacity: bool) -> !:
    if new_size <= vector_size(this):
        vector_shrink(this, new_size, keep_capacity)
        return

    try vector_try_ensure_capacity(this, new_size)

    for i in vector_size(this)..<new_size:
        *vector_slot(this, i) = default_value
    this.m_size = new_size
    vector_update_metadata(this)  # We have *some* space, try_ensure_capacity above ensured nonzero.

## Ported from AK/Vector.h:912 AK::Vector::try_resize_and_keep_capacity.
pub func vector_try_resize_and_keep_capacity[T](this: Vector[T]*, new_size: usize) -> !:
    return try vector_try_resize(this, new_size, true)

## Ported from AK/Vector.h:918 AK::Vector::grow_capacity.
pub func vector_grow_capacity[T](this: Vector[T]*, needed_capacity: usize):
    vector_try_grow_capacity(this, needed_capacity) else trap("MUST: Vector::grow_capacity")

## Ported from AK/Vector.h:923 AK::Vector::ensure_capacity.
pub func vector_ensure_capacity[T](this: Vector[T]*, needed_capacity: usize):
    vector_try_ensure_capacity(this, needed_capacity) else trap("MUST: Vector::ensure_capacity")

## Ported from AK/Vector.h:928 AK::Vector::shrink.
pub func vector_shrink[T](this: Vector[T]*, new_size: usize, keep_capacity: bool = false):
    assert(new_size <= vector_size(this))
    if new_size == vector_size(this):
        return

    if new_size == 0:
        if keep_capacity:
            vector_clear_with_capacity(this)
        else:
            vector_clear(this)
        return

    this.m_size = new_size
    vector_update_metadata(this)  # We have *some* space, as new_size can't be zero here.

## Ported from AK/Vector.h:950 AK::Vector::unsafe_shrink.
pub func vector_unsafe_shrink[T](this: Vector[T]*, new_size: usize):
    this.m_size = new_size
    vector_update_metadata(this)  # We have at least an allocation, as we are not freeing anything.

## Ported from AK/Vector.h:961 AK::Vector::resize.
pub func vector_resize[T](this: Vector[T]*, new_size: usize, keep_capacity: bool = false):
    vector_try_resize(this, new_size, keep_capacity) else trap("MUST: Vector::resize")

## Ported from AK/Vector.h:967 AK::Vector::resize_and_keep_capacity.
pub func vector_resize_and_keep_capacity[T](this: Vector[T]*, new_size: usize):
    vector_try_resize_and_keep_capacity(this, new_size) else trap("MUST: Vector::resize_and_keep_capacity")

## Ported from AK/Vector.h:973 AK::Vector::resize_with_default_value_and_keep_capacity.
pub func vector_resize_with_default_value_and_keep_capacity[T](this: Vector[T]*, new_size: usize, default_value: T):
    vector_try_resize_with_default_value(this, new_size, default_value, true) else trap("MUST: Vector::resize_with_default_value")

## Ported from AK/Vector.h:979 AK::Vector::resize_with_default_value.
pub func vector_resize_with_default_value[T](this: Vector[T]*, new_size: usize, default_value: T, keep_capacity: bool = false):
    vector_try_resize_with_default_value(this, new_size, default_value, keep_capacity) else trap("MUST: Vector::resize_with_default_value")

## Ported from AK/Vector.h:985 AK::Vector::fill.
pub func vector_fill[T](this: Vector[T]*, value: T):
    for i in 0..<vector_size(this):
        *vector_at(this, i) = value

## Ported from AK/Vector.h:991 AK::Vector::shrink_to_fit.
pub func vector_shrink_to_fit[T](this: Vector[T]*):
    if vector_size(this) == vector_capacity(this):
        return
    var new_vector: Vector[T]
    new_vector.m_atomic = this.m_atomic
    vector_ensure_capacity(&new_vector, vector_size(this))
    for element in vector_span(this):
        vector_unchecked_append_u(&new_vector, element)
    vector_move_assign(this, &new_vector)

# mark: Iteration and searching =================================================================

## Ported from AK/Vector.h:1008 AK::Vector::begin const.
pub func vector_begin_const[T](this: const Vector[T]*) -> SimpleIterator[Vector[T], T]:
    return simple_iterator_begin[Vector[T], T]((Vector[T]*)this)

## Ported from AK/Vector.h:1009 AK::Vector::begin.
pub func vector_begin[T](this: Vector[T]*) -> SimpleIterator[Vector[T], T]:
    return simple_iterator_begin[Vector[T], T](this)

## Ported from AK/Vector.h:1010 AK::Vector::rbegin.
pub func vector_rbegin[T](this: Vector[T]*) -> SimpleReverseIterator[Vector[T], T]:
    return simple_reverse_iterator_rbegin[T, Vector[T]](this)

## Ported from AK/Vector.h:1011 AK::Vector::rbegin const.
pub func vector_rbegin_const[T](this: const Vector[T]*) -> SimpleReverseIterator[Vector[T], T]:
    return simple_reverse_iterator_rbegin[T, Vector[T]]((Vector[T]*)this)

## Ported from AK/Vector.h:1013 AK::Vector::end const.
pub func vector_end_const[T](this: const Vector[T]*) -> SimpleIterator[Vector[T], T]:
    return simple_iterator_end[T, Vector[T]]((Vector[T]*)this)

## Ported from AK/Vector.h:1014 AK::Vector::end.
pub func vector_end[T](this: Vector[T]*) -> SimpleIterator[Vector[T], T]:
    return simple_iterator_end[T, Vector[T]](this)

## Ported from AK/Vector.h:1015 AK::Vector::rend.
pub func vector_rend[T](this: Vector[T]*) -> SimpleReverseIterator[Vector[T], T]:
    return simple_reverse_iterator_rend[Vector[T], T](this)

## Ported from AK/Vector.h:1016 AK::Vector::rend const.
pub func vector_rend_const[T](this: const Vector[T]*) -> SimpleReverseIterator[Vector[T], T]:
    return simple_reverse_iterator_rend[Vector[T], T]((Vector[T]*)this)

## Ported from AK/Vector.h:1018 AK::Vector::in_reverse.
pub func vector_in_reverse[T](this: Vector[T]*) -> ReverseWrapper[Vector[T]]:
    return reverse_wrapper_in_reverse(this)

## Ported from AK/Vector.h:1023 AK::Vector::in_reverse const.
pub func vector_in_reverse_const[T](this: const Vector[T]*) -> ReverseWrapper[Vector[T]]:
    return reverse_wrapper_in_reverse((Vector[T]*)this)

## Ported from AK/Vector.h:1029 AK::Vector::find_if const.
pub func vector_find_if_const[T](this: const Vector[T]*, finder: Function1[const T*, bool]) -> SimpleIterator[Vector[T], T]:
    return find_if(vector_begin_const(this), vector_end_const(this), finder)

## Ported from AK/Vector.h:1035 AK::Vector::find_if.
pub func vector_find_if[T](this: Vector[T]*, finder: Function1[const T*, bool]) -> SimpleIterator[Vector[T], T]:
    return find_if(vector_begin(this), vector_end(this), finder)

## Ported from AK/Vector.h:1040 AK::Vector::find const.
pub func vector_find_const[T: luce.Equatable](this: const Vector[T]*, value: T) -> SimpleIterator[Vector[T], T]:
    return find(vector_begin_const(this), vector_end_const(this), value)

## Ported from AK/Vector.h:1045 AK::Vector::find.
pub func vector_find[T: luce.Equatable](this: Vector[T]*, value: T) -> SimpleIterator[Vector[T], T]:
    return find(vector_begin(this), vector_end(this), value)

## Ported from AK/Vector.h:1050 AK::Vector::find_first_index.
pub func vector_find_first_index[T: luce.Equatable](this: const Vector[T]*, value: T) -> usize?:
    let index = find_index(vector_begin_const(this), vector_end_const(this), value)
    if index < vector_size(this):
        return index
    return none

## Ported from AK/Vector.h:1060 AK::Vector::find_first_index_if.
pub func vector_find_first_index_if[T](this: const Vector[T]*, finder: Function1[const T*, bool]) -> usize?:
    let maybe_result = find_if(vector_begin_const(this), vector_end_const(this), finder)
    let end = vector_end_const(this)
    if simple_iterator_eq(&maybe_result, end):
        return none
    return simple_iterator_index(&maybe_result)

## Ported from AK/Vector.h:1068 AK::Vector::reverse.
pub func vector_reverse[T](this: Vector[T]*):
    for i in 0..<(vector_size(this) // 2):
        swap_5(vector_at(this, i), vector_at(this, vector_size(this) - i - 1))

# mark: Storage =================================================================================

## Ported from AK/Vector.h:1075 AK::Vector::reset_capacity.
pub func vector_reset_capacity[T](this: Vector[T]*):
    this.m_capacity = 0

## Ported from AK/Vector.h:1080 AK::Vector::padded_capacity.
pub func vector_padded_capacity[T](capacity: usize) -> usize:
    return 4 + capacity + capacity // 4

## Ported from AK/Vector.h:1085 AK::Vector::slot.
pub func vector_slot[T](this: Vector[T]*, i: usize) -> T*:
    let data = this.m_outline_buffer else trap("VERIFY: Vector without storage")
    return data + i

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

## Ported from AK/Vector.h:1088 AK::Vector::inline_buffer: the inline capacity is always 0
## here (static_assert(inline_capacity > 0) in the donor).
pub func vector_inline_buffer[T](this: Vector[T]*) -> T*:
    _ = this
    trap("VERIFY: Vector has no inline buffer (inline capacity is dropped)")

## Ported from AK/Vector.h:1093 AK::Vector::inline_buffer const.
pub func vector_inline_buffer_const[T](this: const Vector[T]*) -> const T*:
    _ = this
    trap("VERIFY: Vector has no inline buffer (inline capacity is dropped)")

## Ported from AK/Vector.h:1099 AK::Vector::raw_last.
pub func vector_raw_last[T](this: Vector[T]*) -> T*:
    return vector_raw_at(this, vector_size(this) - 1)

## Ported from AK/Vector.h:1100 AK::Vector::raw_first.
pub func vector_raw_first[T](this: Vector[T]*) -> T*:
    return vector_raw_at(this, 0)

## Ported from AK/Vector.h:1101 AK::Vector::raw_at.
pub func vector_raw_at[T](this: Vector[T]*, index: usize) -> T*:
    return vector_slot(this, index)

## Ported from AK/Vector.h:1104 AK::Vector::update_metadata: only fast-last-access vectors
## keep metadata, and the port has none.
# NOTE: Do *not* call unguarded if m_capacity can be zero.
pub func vector_update_metadata[T](this: Vector[T]*):
    _ = this

## Ported from AK/Vector.h:1114 AK::Vector::storage_size.
pub func vector_storage_size[T]() -> usize:
    return 0

## Ported from AK/Vector.h:1122 AK::Vector::storage_alignment.
pub func vector_storage_alignment[T]() -> usize:
    return 1