Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.41.0

0.41.0 / src / support / list.lucb

#==============================================================================================
#
#   list - The compiler's growable collection
#
#   DESCRIPTION:
#       Growth copies the live elements, then releases the previous storage through the
#       allocator captured at creation. An element borrow expires on the next growth.
#
#==============================================================================================

import memory

## A growable array of `T` over a captured allocator.
pub struct List[T]:
    ## The storage; `items[..<count]` are the live elements.
    pub var items: T[]
    ## The number of live elements.
    pub var count: usize
    var allocator: memory.Allocator

    ## An empty list with room for `capacity` elements (at least four).
    pub static func create(capacity: usize) -> List[T]!:
        let room = capacity if capacity > 0 else 4
        return List[T](items = try new T[room] ---, count = 0, allocator = memory.allocator)

    ## Append `item`, growing the storage when it is full.
    pub func push(item: T) -> !:
        if self.count == self.items.length:
            let capacity = self.items.length *? 2 else error(memory.exhausted, "the list capacity overflows")
            let grown = try new T[capacity] --- in self.allocator
            memory.copy(grown, self.items, self.count)
            free(self.items) in self.allocator
            self.items = grown
        self.items[self.count] = item
        self.count += 1

    ## The element at `index`.
    pub func get(index: usize) -> T:
        return self.items[index]

    ## Replace the element at `index` with `item`.
    pub func set(index: usize, item: T):
        self.items[index] = item

    ## The live elements as a span; invalid after the next push.
    pub func span() -> T[]:
        return self.items[..<self.count]

    ## A copy with the same room, in the current allocator, which its growth goes on using:
    ## what is pushed onto one is not in the other.
    pub func copied() -> List[T]!:
        let items = try new T[self.items.length] ---
        memory.copy(items, self.items, self.count)
        return List[T](items = items, count = self.count, allocator = memory.allocator)

    ## Release the storage.
    pub func destroy():
        free(self.items) in self.allocator

test "a list grows and keeps order":
    var backing: u8[4096]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var xs = try List[i64].create(1)
        var i: i64 = 0
        while i < 20:
            try xs.push(i * 3)
            i += 1
        assert(xs.count == 20)
        assert(xs.get(19) == 57)
        var total: i64 = 0
        for x in xs.span():
            total += x
        assert(total == 570)

test "an impossible list capacity is rejected before storage is accessed":
    var values = try List[i64].create(1)
    defer values.destroy()
    let original = values.items
    # Exercise arithmetic at its numeric boundary without allocating or reading
    # a giant buffer. Restore the real descriptor before using or releasing it.
    values.items = i64[](original.data, 9223372036854775808)
    values.count = values.items.length
    var failed = false
    values.push(7) catch failure:
        assert(failure.code == memory.exhausted)
        failed = true
    assert(failed and values.items.length == values.count)
    values.items = original
    values.count = 0
    try values.push(11)
    try values.push(13)
    assert(values.count == 2 and values.get(0) == 11 and values.get(1) == 13)