Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / intrusive_list.lucb

#==============================================================================================
#
#   intrusive_list - IntrusiveList<&T::member>: a list threaded through nodes inside its values
#
#   DESCRIPTION:
#       Port of AK/IntrusiveList.h (lines 1-453) and AK/IntrusiveDetails.h. The donor's list
#       type carries a pointer-to-member template argument naming the IntrusiveListNode field
#       of T; luce-base has no such argument, so it is `member`, the field's offset
#       (`offsetof(HeapBlock, m_list_node)`), passed to the members that take a T and look at
#       its node (append, prepend, insert_before, remove, contains, next, prev) and recorded in
#       the list's storage by the first insertion, from where the members that only hold nodes
#       (first, last, take_first, begin, ...) take it. node_to_value is container_of: the
#       node's address minus the offset (DESIGN.md §2.6).
#
#       Container is always a raw pointer here (T*?; RefPtr and OwnPtr are pointers,
#       DESIGN.md §2.6), so `IsRaw` holds and the self reference is never set. first(), last()
#       and take_*() answer `T*?`.
#
#==============================================================================================

# mark: IntrusiveList ===========================================================================

# The node of `n` (`n.*member`).
func intrusive_list_node_of[T, TContainer](n: const T*, member: usize) -> IntrusiveListNode[T, TContainer]*:
    return (IntrusiveListNode[T, TContainer]*)((u8*)n + member)

## Ported from AK/IntrusiveList.h:191 AK::Detail::IntrusiveList::clear.
pub func intrusive_list_clear[T, TContainer](this: IntrusiveList[T, TContainer]*):
    while let first = this.m_storage.m_first:
        intrusive_list_node_remove(first)

## Ported from AK/IntrusiveList.h:198 AK::Detail::IntrusiveList::is_empty.
pub func intrusive_list_is_empty[T, TContainer](this: const IntrusiveList[T, TContainer]*) -> bool:
    return this.m_storage.m_first == none

## Ported from AK/IntrusiveList.h:204 AK::Detail::IntrusiveList::size_slow.
pub func intrusive_list_size_slow[T, TContainer](this: const IntrusiveList[T, TContainer]*) -> usize:
    var size: usize = 0
    for it in intrusive_list_begin_const(this):
        _ = it
        size += 1
    return size

## Ported from AK/IntrusiveList.h:215 AK::Detail::IntrusiveList::append.
pub func intrusive_list_append[T, TContainer](this: IntrusiveList[T, TContainer]*, n: T*, member: usize):
    intrusive_list_remove(this, n, member)

    this.m_storage.m_member = member
    let nnode = intrusive_list_node_of[T, TContainer](n, member)
    nnode.m_storage = &this.m_storage
    nnode.m_prev = this.m_storage.m_last
    nnode.m_next = none

    if let last = this.m_storage.m_last:
        last.m_next = nnode
    this.m_storage.m_last = nnode
    if this.m_storage.m_first == none:
        this.m_storage.m_first = nnode

## Ported from AK/IntrusiveList.h:234 AK::Detail::IntrusiveList::prepend.
pub func intrusive_list_prepend[T, TContainer](this: IntrusiveList[T, TContainer]*, n: T*, member: usize):
    intrusive_list_remove(this, n, member)

    this.m_storage.m_member = member
    let nnode = intrusive_list_node_of[T, TContainer](n, member)
    nnode.m_storage = &this.m_storage
    nnode.m_prev = none
    nnode.m_next = this.m_storage.m_first

    if let first = this.m_storage.m_first:
        first.m_prev = nnode
    this.m_storage.m_first = nnode
    if this.m_storage.m_last == none:
        this.m_storage.m_last = nnode

## Ported from AK/IntrusiveList.h:253 AK::Detail::IntrusiveList::insert_before.
pub func intrusive_list_insert_before[T, TContainer](this: IntrusiveList[T, TContainer]*, bn: T*, n: T*, member: usize):
    intrusive_list_remove(this, n, member)

    this.m_storage.m_member = member
    let new_node = intrusive_list_node_of[T, TContainer](n, member)
    let before_node = intrusive_list_node_of[T, TContainer](bn, member)
    new_node.m_storage = &this.m_storage
    new_node.m_next = before_node
    new_node.m_prev = before_node.m_prev
    if let prev = before_node.m_prev:
        prev.m_next = new_node
    before_node.m_prev = new_node

    if this.m_storage.m_first == (IntrusiveListNode[T, TContainer]*?)before_node:
        this.m_storage.m_first = new_node

## Ported from AK/IntrusiveList.h:275 AK::Detail::IntrusiveList::remove.
pub func intrusive_list_remove[T, TContainer](this: IntrusiveList[T, TContainer]*, n: T*, member: usize):
    _ = this
    let nnode = intrusive_list_node_of[T, TContainer](n, member)
    if nnode.m_storage != none:
        intrusive_list_node_remove(nnode)

## Ported from AK/IntrusiveList.h:283 AK::Detail::IntrusiveList::contains.
pub func intrusive_list_contains[T, TContainer](this: const IntrusiveList[T, TContainer]*, n: const T*, member: usize) -> bool:
    let nnode = intrusive_list_node_of[T, TContainer](n, member)
    return nnode.m_storage == (const IntrusiveListStorage[T, TContainer]*?)&this.m_storage

## Ported from AK/IntrusiveList.h:290 AK::Detail::IntrusiveList::first.
pub func intrusive_list_first[T, TContainer](this: const IntrusiveList[T, TContainer]*) -> T*?:
    let first = this.m_storage.m_first else return none
    return intrusive_list_node_to_value(first, this.m_storage.m_member)

## Ported from AK/IntrusiveList.h:316 AK::Detail::IntrusiveList::last.
pub func intrusive_list_last[T, TContainer](this: const IntrusiveList[T, TContainer]*) -> T*?:
    let last = this.m_storage.m_last else return none
    return intrusive_list_node_to_value(last, this.m_storage.m_member)

## Ported from AK/IntrusiveList.h:296 AK::Detail::IntrusiveList::take_first.
pub func intrusive_list_take_first[T, TContainer](this: IntrusiveList[T, TContainer]*) -> T*?:
    if let ptr = intrusive_list_first(this):
        intrusive_list_remove(this, ptr, this.m_storage.m_member)
        return ptr
    return none

## Ported from AK/IntrusiveList.h:306 AK::Detail::IntrusiveList::take_last.
pub func intrusive_list_take_last[T, TContainer](this: IntrusiveList[T, TContainer]*) -> T*?:
    if let ptr = intrusive_list_last(this):
        intrusive_list_remove(this, ptr, this.m_storage.m_member)
        return ptr
    return none

## Ported from AK/IntrusiveList.h:354 AK::Detail::IntrusiveList::begin.
pub func intrusive_list_begin[T, TContainer](this: IntrusiveList[T, TContainer]*) -> IntrusiveListIterator[T, TContainer]:
    return intrusive_list_begin_const(this)

## Ported from AK/IntrusiveList.h:91 AK::Detail::IntrusiveList::end.
pub func intrusive_list_end[T, TContainer](this: IntrusiveList[T, TContainer]*) -> IntrusiveListIterator[T, TContainer]:
    return IntrusiveListIterator[T, TContainer](m_value = none, m_member = this.m_storage.m_member)

## Ported from AK/IntrusiveList.h:360 AK::Detail::IntrusiveList::rbegin.
pub func intrusive_list_rbegin[T, TContainer](this: IntrusiveList[T, TContainer]*) -> IntrusiveListReverseIterator[T, TContainer]:
    return IntrusiveListReverseIterator[T, TContainer](m_value = intrusive_list_last(this), m_member = this.m_storage.m_member)

## Ported from AK/IntrusiveList.h:117 AK::Detail::IntrusiveList::rend.
pub func intrusive_list_rend[T, TContainer](this: IntrusiveList[T, TContainer]*) -> IntrusiveListReverseIterator[T, TContainer]:
    return IntrusiveListReverseIterator[T, TContainer](m_value = none, m_member = this.m_storage.m_member)

## Ported from AK/IntrusiveList.h:366 AK::Detail::IntrusiveList::begin const.
pub func intrusive_list_begin_const[T, TContainer](this: const IntrusiveList[T, TContainer]*) -> IntrusiveListIterator[T, TContainer]:
    return IntrusiveListIterator[T, TContainer](m_value = intrusive_list_first(this), m_member = this.m_storage.m_member)

## Ported from AK/IntrusiveList.h:141 AK::Detail::IntrusiveList::end const.
pub func intrusive_list_end_const[T, TContainer](this: const IntrusiveList[T, TContainer]*) -> IntrusiveListIterator[T, TContainer]:
    return IntrusiveListIterator[T, TContainer](m_value = none, m_member = this.m_storage.m_member)

## Ported from AK/IntrusiveList.h:338 AK::Detail::IntrusiveList::next.
pub func intrusive_list_next[T, TContainer](current: T*, member: usize) -> T*?:
    let nextnode = intrusive_list_node_of[T, TContainer](current, member).m_next else return none
    return intrusive_list_node_to_value(nextnode, member)

## Ported from AK/IntrusiveList.h:346 AK::Detail::IntrusiveList::prev.
pub func intrusive_list_prev[T, TContainer](current: T*, member: usize) -> T*?:
    let prevnode = intrusive_list_node_of[T, TContainer](current, member).m_prev else return none
    return intrusive_list_node_to_value(prevnode, member)

## Ported from AK/IntrusiveList.h:322 AK::Detail::IntrusiveList::next (const).
pub func intrusive_list_next_2[T, TContainer](current: const T*, member: usize) -> const T*?:
    return intrusive_list_next[T, TContainer]((T*)current, member)

## Ported from AK/IntrusiveList.h:330 AK::Detail::IntrusiveList::prev (const).
pub func intrusive_list_prev_2[T, TContainer](current: const T*, member: usize) -> const T*?:
    return intrusive_list_prev[T, TContainer]((T*)current, member)

## Ported from AK/IntrusiveList.h:372 AK::Detail::IntrusiveList::node_to_value: the T holding
## `node` at offset `member` (container_of).
# Note: `node` is a reference that resides in some part of the actual value (of type T), the
#       placement (i.e. offset) of which is described by the pointer-to-data-member parameter
#       named `member`.
#       This function effectively takes in the address of the data member, and returns the address
#       of the value (of type T) holding that member.
pub func intrusive_list_node_to_value[T, TContainer](node: IntrusiveListNode[T, TContainer]*, member: usize) -> T*:
    return (T*)((u8*)node - member)

# mark: Iterators ===============================================================================

## Ported from AK/IntrusiveList.h:76 AK::Detail::IntrusiveList::Iterator::operator*.
pub func intrusive_list_iterator_deref[T, TContainer](this: IntrusiveListIterator[T, TContainer]*) -> T*:
    return this.m_value else trap("VERIFY: dereferencing the end of an IntrusiveList")

## Ported from AK/IntrusiveList.h:78 AK::Detail::IntrusiveList::Iterator::operator==.
pub func intrusive_list_iterator_eq[T, TContainer](this: const IntrusiveListIterator[T, TContainer]*, other: IntrusiveListIterator[T, TContainer]) -> bool:
    return other.m_value == this.m_value

## Ported from AK/IntrusiveList.h:79 AK::Detail::IntrusiveList::Iterator::operator++.
pub func intrusive_list_iterator_inc[T, TContainer](this: IntrusiveListIterator[T, TContainer]*) -> IntrusiveListIterator[T, TContainer]*:
    let value = this.m_value else trap("VERIFY: incrementing the end of an IntrusiveList")
    this.m_value = intrusive_list_next[T, TContainer](value, this.m_member)
    return this

## Ported from AK/IntrusiveList.h:176 AK::Detail::IntrusiveList::Iterator::erase: removes the
## value the iterator is at and moves it to the next one.
pub func intrusive_list_iterator_erase[T, TContainer](this: IntrusiveListIterator[T, TContainer]*) -> IntrusiveListIterator[T, TContainer]*:
    let old = this.m_value else trap("VERIFY: erasing the end of an IntrusiveList")
    this.m_value = intrusive_list_next[T, TContainer](old, this.m_member)
    intrusive_list_node_remove(intrusive_list_node_of[T, TContainer](old, this.m_member))
    return this

## The value the iterator is at, and the iterator moved past it; none at the end (the `for`
## protocol). The next value is read before the body runs, so the body may remove the value.
pub func intrusive_list_iterator_next[T, TContainer](this: IntrusiveListIterator[T, TContainer]*) -> T*?:
    let value = this.m_value else return none
    this.m_value = intrusive_list_next[T, TContainer](value, this.m_member)
    return value

## Ported from AK/IntrusiveList.h:106 AK::Detail::IntrusiveList::ReverseIterator::operator++.
pub func intrusive_list_reverse_iterator_inc[T, TContainer](this: IntrusiveListReverseIterator[T, TContainer]*) -> IntrusiveListReverseIterator[T, TContainer]*:
    let value = this.m_value else trap("VERIFY: incrementing the end of an IntrusiveList")
    this.m_value = intrusive_list_prev[T, TContainer](value, this.m_member)
    return this

## The value the reverse iterator is at, and the iterator moved past it (the `for` protocol).
pub func intrusive_list_reverse_iterator_next[T, TContainer](this: IntrusiveListReverseIterator[T, TContainer]*) -> T*?:
    let value = this.m_value else return none
    this.m_value = intrusive_list_prev[T, TContainer](value, this.m_member)
    return value

# mark: IntrusiveListNode =======================================================================

## Ported from AK/IntrusiveList.h:397 AK::Detail::IntrusiveListNode::remove.
pub func intrusive_list_node_remove[T, TContainer](this: IntrusiveListNode[T, TContainer]*):
    let storage = this.m_storage else trap("VERIFY: removing an IntrusiveListNode that is in no list")
    let self_node: IntrusiveListNode[T, TContainer]*? = this
    if storage.m_first == self_node:
        storage.m_first = this.m_next
    if storage.m_last == self_node:
        storage.m_last = this.m_prev
    if let prev = this.m_prev:
        prev.m_next = this.m_next
    if let next = this.m_next:
        next.m_prev = this.m_prev
    this.m_prev = none
    this.m_next = none
    this.m_storage = none

## Ported from AK/IntrusiveList.h:416 AK::Detail::IntrusiveListNode::is_in_list.
pub func intrusive_list_node_is_in_list[T, TContainer](this: const IntrusiveListNode[T, TContainer]*) -> bool:
    return this.m_storage != none