dymokomi/luce-base
Source of release 0.42.0
0.42.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)