Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-browser-foundation

Source of release 0.6.1

0.6.1 / src / ak / queue.lucb

#==============================================================================================
#
#   queue - Queue<T>: a FIFO of fixed-size segments
#
#   DESCRIPTION:
#       Port of AK/Queue.h (lines 1-116). The segments are Vectors of at most `segment_size`
#       (the default 1000) values, kept in an IntrusiveList through QueueSegment.node; a
#       segment is freed where the donor deletes it (managed memory, DESIGN.md ยง3.3).
#       for_each's callback is a Function1[const T*, unit].
#
#==============================================================================================

let queue_segment_size: usize = 1000

# offsetof(QueueSegment<T>, node): the IntrusiveList's `member` (intrusive_list.lucb).
func queue_segment_member[T]() -> usize:
    return memory.offset_of(QueueSegment[T], node)

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

## Ported from AK/Queue.h:27 AK::Queue::is_empty.
pub func queue_is_empty[T](this: const Queue[T]*) -> bool:
    return this.m_size == 0

## Ported from AK/Queue.h:30 AK::Queue::enqueue.
pub func queue_enqueue[T](this: Queue[T]*, value: T):
    if intrusive_list_is_empty(&this.m_segments) or vector_size(&(intrusive_list_last(&this.m_segments) else trap("unreachable")).data) >= queue_segment_size:
        let segment = new QueueSegment[T] else trap("out of memory")
        intrusive_list_append(&this.m_segments, segment, queue_segment_member[T]())
    let last = intrusive_list_last(&this.m_segments) else trap("unreachable")
    vector_append_t(&last.data, value)
    this.m_size += 1

## Ported from AK/Queue.h:40 AK::Queue::try_dequeue.
pub func queue_try_dequeue[T](this: Queue[T]*) -> T!:
    if queue_is_empty(this):
        try ak_error_throw(ak_error_from_errno(enoent))
    return queue_dequeue(this)

## Ported from AK/Queue.h:48 AK::Queue::dequeue.
pub func queue_dequeue[T](this: Queue[T]*) -> T:
    assert(not queue_is_empty(this))
    let first = intrusive_list_first(&this.m_segments) else trap("unreachable")
    let value = *vector_at(&first.data, this.m_index_into_first)
    this.m_index_into_first += 1
    if this.m_index_into_first == queue_segment_size:
        let taken = intrusive_list_take_first(&this.m_segments) else trap("unreachable")
        free(taken)
        this.m_index_into_first = 0
    this.m_size -= 1
    if this.m_size == 0 and not intrusive_list_is_empty(&this.m_segments):
        # This is not necessary for correctness but avoids faulting in
        # all the pages for the underlying Vector in the case where
        # the caller repeatedly enqueues and then dequeues a single item.
        this.m_index_into_first = 0
        let last = intrusive_list_last(&this.m_segments) else trap("unreachable")
        vector_clear_with_capacity(&last.data)
    return value

## Ported from AK/Queue.h:68 AK::Queue::head.
pub func queue_head[T](this: Queue[T]*) -> T*:
    assert(not queue_is_empty(this))
    let first = intrusive_list_first(&this.m_segments) else trap("unreachable")
    return vector_at(&first.data, this.m_index_into_first)

## Ported from AK/Queue.h:75 AK::Queue::tail.
pub func queue_tail[T](this: Queue[T]*) -> T*:
    assert(not queue_is_empty(this))
    let last = intrusive_list_last(&this.m_segments) else trap("unreachable")
    return vector_last(&last.data)

## Ported from AK/Queue.h:82 AK::Queue::for_each.
pub func queue_for_each[T](this: const Queue[T]*, callback: Function1[const T*, unit]):
    var first = true
    for segment in intrusive_list_begin_const(&this.m_segments):
        let start = this.m_index_into_first if first else 0
        first = false
        for i in start..<vector_size(&segment.data):
            function1_call(&callback, vector_at_const(&segment.data, i))

## Ported from AK/Queue.h:93 AK::Queue::clear.
pub func queue_clear[T](this: Queue[T]*):
    while let segment = intrusive_list_take_first(&this.m_segments):
        free(segment)
    this.m_index_into_first = 0
    this.m_size = 0