silk.collections.list.

When to use#

Use List when the number of elements is known only at runtime, or the sequence must grow. Use a fixed array [T; N] when the length is part of the type. Use silk.collections.bytes.Bytes for a block of bytes that does not grow.

Details#

List.make does not allocate. The first growth allocates space for four elements, and each later growth doubles the capacity. Use List.reserve or List.reserveExact to allocate before a sequence of appends. Growth copies the elements into new storage before it releases the old storage. Thus a failed List.append or List.reserve leaves the list unchanged.

List.remove, List.clear, and List.truncate drop the elements that they remove and keep the capacity. Dropping a list drops each element and then releases the storage.

List.sort is stable and works for elements that are not Copy. It allocates temporary storage. List.binarySearch needs a sorted list and returns the lowest index of equal elements.

Gotchas#

List.get, List.set, and List.remove trap if the index is not less than the length. List.insert traps if the index is more than the length. List.get copies the element, so it needs T: Copy. Use List.asSlice to borrow an element that is not Copy.

Examples#

Grow and change a list#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.collections.list { List }

pub effect fn main() -> i32
  ! OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut values = List<i32>.make()
  run List<i32>.append(&mut values, 10) |> Effect.provideMut<Allocator>(&mut allocator)
  run List<i32>.append(&mut values, 30) |> Effect.provideMut<Allocator>(&mut allocator)
  run List<i32>.insert(&mut values, 1, 20) |> Effect.provideMut<Allocator>(&mut allocator)
  List<i32>.set(&mut values, 2, 22)
  let removed = List<i32>.remove(&mut values, 0)

  // The list is now [20, 22].
  if removed != 10 || List<i32>.get(&values, 0) + List<i32>.get(&values, 1) != 42 {
    return 1
  }
  return 0
}

Sort values and find the first equal value#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.core.option { Option }
import silk.num.usize
import silk.collections.list { List }

pub effect fn main() -> i32
  ! OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut values = List<i32>.make()
  run List<i32>.append(&mut values, 36) |> Effect.provideMut<Allocator>(&mut allocator)
  run List<i32>.append(&mut values, 3) |> Effect.provideMut<Allocator>(&mut allocator)
  run List<i32>.append(&mut values, 3) |> Effect.provideMut<Allocator>(&mut allocator)
  run List<i32>.sort(&mut values) |> Effect.provideMut<Allocator>(&mut allocator)

  // The list is now [3, 3, 36]. The search returns the first 3.
  let found = List<i32>.binarySearch(&values, 3) |> Option<usize>.unwrapOr(usize.MAX)
  if found != usize.ZERO || List<i32>.get(&values, 2) != 36 {
    return 1
  }
  return 0
}

Import as List with import silk.collections.list { List }.

Public declarations: 1.

List#

pub struct List<T>

A growable list that owns its elements in one contiguous allocation.

Details#

The length is the number of elements in the list. The capacity is the number of elements that fit before the next growth. Dropping a list drops each element and then releases the storage. A list is affine. Copy it element by element if a second list is necessary.

List.make does not allocate. The first growth allocates space for four elements, and each later growth doubles the capacity. Use List.makeWithCapacity to create a list with its storage in one call, or List.reserve and List.reserveExact to allocate before a sequence of appends. Growth copies the elements into new storage before it releases the old storage, so a failed List.append or List.reserve leaves the list unchanged. List.remove, List.clear, and List.truncate drop the elements that they remove and keep the capacity, so a list cleared in a loop reuses its storage. List.clearAndFree also releases the storage, and List.shrinkToFit releases only the capacity beyond the length.

List.sort is stable, works for elements that are not Copy, and allocates temporary storage. List.binarySearch needs a sorted list and returns the lowest index of equal elements.

Gotchas#

List.get, List.set, and List.remove trap if the index is not less than the length. List.insert traps if the index is more than the length. List.get copies the element, so it needs T: Copy. Use List.asSlice to borrow an element that is not Copy.

Implementation List<T>#

impl<T> List<T>

Associated function make#

pub fn make() -> List<T>

Returns an empty list. This function does not allocate.

Details#

The capacity is 0. The first List.append, List.insert, or List.reserve allocates.

Associated function makeWithCapacity#

pub effect fn makeWithCapacity(capacity: usize) -> List<T> ! OutOfMemoryError ? &mut Allocator

Returns an empty list with storage for exactly capacity elements.

When to use#

Use makeWithCapacity when the number of elements is known or can be estimated before the appends, so that the list allocates once instead of growing step by step.

Details#

The length is 0 and the capacity is capacity. Appends up to that capacity do not allocate. A capacity of 0 does not allocate and gives the same list as List.make.

Errors#

• OutOfMemoryError if the size of capacity elements overflows, or the Allocator cannot supply the storage.

Examples#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.collections.list { List }

pub effect fn main() -> i32
  ! OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut values = run List<u32>.makeWithCapacity(16) |> Effect.provideMut<Allocator>(&mut allocator)
  run List<u32>.append(&mut values, 7) |> Effect.provideMut<Allocator>(&mut allocator)
  if List<u32>.length(&values) != 1 || List<u32>.capacity(&values) != 16 {
    return 1
  }
  return 0
}

Method length#

pub fn length(self: &Self) -> usize

Returns the number of elements in the list.

Method capacity#

pub fn capacity(self: &Self) -> usize

Returns the number of elements that fit in the current storage before the next growth.

Method asSlice#

pub fn asSlice(self: &Self) -> &[T]

Returns a shared borrow of all elements as a slice, in list order.

When to use#

Use asSlice to read elements that are not Copy, or to give the elements to a function that takes &[T].

Gotchas#

The slice borrows the list. The compiler rejects a change to the list, such as an append, while the slice is live.

Method asMutSlice#

pub fn asMutSlice(self: &mut Self) -> &mut [T]

Returns an exclusive borrow of all elements as a slice, in list order.

When to use#

Use asMutSlice to change elements in place, such as in a loop over all elements.

Gotchas#

The slice cannot change the length. The compiler rejects other uses of the list while the slice is live.

Method append#

pub effect<'env> fn append<'env>(self: &mut Self, value: T) -> () ! OutOfMemoryError ? &mut Allocator

Adds value at the end of the list.

Details#

The list takes ownership of value. If the list is full, it grows: the first growth allocates space for four elements, and each later growth doubles the capacity.

Errors#

• OutOfMemoryError if the Allocator cannot supply the new storage. The list does not change.

Method insert#

pub effect<'env> fn insert<'env>(self: &mut Self, index: usize, value: T) -> ()
  ! OutOfMemoryError
  ? &mut Allocator

Inserts value at position index and moves the elements from index onward one position to the right.

Details#

index equal to List.length appends the value. The move of the later elements takes time in proportion to their number. T does not need to be Copy.

Errors#

• OutOfMemoryError if the Allocator cannot supply the new storage. The list does not change.

Gotchas#

If index is more than List.length, the program traps.

Method get#

pub fn get<T: Copy>(self: &Self, index: usize) -> T

Returns a copy of the element at position index.

When to use#

Use get when T is Copy. Use List.asSlice to borrow an element that is not Copy.

Gotchas#

If index is not less than List.length, the program traps.

Method pop#

pub fn pop(self: &mut Self) -> Option<T>

Removes the last element and returns it. Returns None if the list is empty.

Details#

The caller owns the returned element. The capacity does not change.

Method remove#

pub fn remove(self: &mut Self, index: usize) -> T

Removes the element at position index, returns it, and moves the later elements one position to the left.

Details#

The caller owns the returned element. The capacity does not change. Use List.pop to remove the last element without a move of other elements.

Gotchas#

If index is not less than List.length, the program traps.

Method clear#

pub fn clear(self: &mut Self) -> ()

Drops all elements and sets the length to 0. The capacity does not change.

When to use#

Use clear to reuse a list, such as a buffer filled again on each pass of a loop: later appends up to the old capacity do not allocate. Use List.clearAndFree to also release the storage.

Method clearAndFree#

pub fn clearAndFree(self: &mut Self) -> ()

Drops all elements and releases the storage. The length and the capacity become 0.

When to use#

Use clearAndFree when the list stays alive but its storage is no longer needed, such as a large buffer that is kept for rare later use. Use List.clear to keep the storage for reuse.

Details#

This function does not allocate and does not need an Allocator. The next append allocates again, as on a list from List.make.

Method truncate#

pub fn truncate(self: &mut Self, length: usize) -> ()

Drops the elements from position length to the end. The capacity does not change.

Details#

If length is more than or equal to the current length, this function does nothing.

Method set#

pub fn set(self: &mut Self, index: usize, value: T) -> ()

Replaces the element at position index with value and drops the old element.

Gotchas#

If index is not less than List.length, the program traps.

Method reserve#

pub effect fn reserve(self: &mut Self, additional: usize) -> ()
  ! OutOfMemoryError
  ? &mut Allocator

Makes sure that at least additional more elements fit without another allocation.

When to use#

Use reserve before a loop of appends when the number of new elements is known. Use List.reserveExact when the final length is known and extra capacity is not wanted.

Details#

If the capacity is already sufficient, this function does nothing. Otherwise, it grows the capacity by doubling until the elements fit. The length does not change.

Errors#

• OutOfMemoryError if length + additional overflows usize, or the Allocator cannot supply the new storage. The list does not change.

Method reserveExact#

pub effect fn reserveExact(self: &mut Self, additional: usize) -> ()
  ! OutOfMemoryError
  ? &mut Allocator

Makes sure that at least additional more elements fit, with no extra capacity.

When to use#

Use reserveExact when the final length is known, such as before a copy of a slice. Use List.reserve when more appends can follow.

Details#

If the capacity is already sufficient, this function does nothing and does not shrink the storage. Otherwise, it allocates storage for exactly length + additional elements. The length does not change.

Errors#

• OutOfMemoryError if length + additional overflows usize, or the Allocator cannot supply the new storage. The list does not change.

Method shrinkToFit#

pub effect fn shrinkToFit(self: &mut Self) -> () ! OutOfMemoryError ? &mut Allocator

Releases the capacity beyond the length.

When to use#

Use shrinkToFit on a list that is complete and kept for a long time, so that the spare room left by doubling growth does not stay allocated.

Details#

If the capacity equals the length, this function does nothing. If the list is empty, it releases the storage, and the capacity becomes 0. Otherwise, it moves the elements into storage for exactly the length. The length does not change.

Errors#

• OutOfMemoryError if the Allocator cannot supply the new storage. The list does not change. An empty list never fails.

Method sort#

pub effect fn sort<T: Order>(self: &mut Self) -> () ! OutOfMemoryError ? &mut Allocator

Sorts the elements in place, in ascending order of the Order conformance of T.

Details#

The sort is stable: equal elements keep their order. The result is deterministic. The sort works for elements that are not Copy. It allocates temporary storage from the active Allocator.

Errors#

• OutOfMemoryError if the Allocator cannot supply the temporary storage. The list does not change.

Method binarySearch#

pub fn binarySearch<T: Order>(self: &Self, target: T) -> Option<usize>

Returns the position of an element equal to target in a sorted list, or None if no element is equal.

Details#

If more than one element is equal to target, the result is the lowest position. The search takes time in proportion to the logarithm of the length. This function consumes target and does not change the list.

Gotchas#

The list must be sorted in ascending order by the same Order conformance, for example by List.sort. For a list that is not sorted, the result has no meaning.

Implementation Drop for List<T>#

impl<T> Drop for List<T>

Operation drop#

fn drop(self: &mut List<T>) -> ()

Implementation List<T>#

impl<T> List<T>

Method appendBytes#

pub effect fn appendBytes(self: &mut List<u8>, values: &[u8]) -> ()
  ! OutOfMemoryError
  ? &mut Allocator

Adds a copy of each byte of values at the end of the list, in order.

When to use#

Use appendBytes to add many bytes at once. It copies the bytes in one operation, which is faster than one List.append for each byte. List.appendSlice does the same for any Copy element type.

Errors#

• OutOfMemoryError if the Allocator cannot supply the new storage. The list does not change.

Method appendSlice#

pub effect fn appendSlice<T: Copy>(self: &mut Self, values: &[T]) -> ()
  ! OutOfMemoryError
  ? &mut Allocator

Adds a copy of each element of values at the end of the list, in order.

When to use#

Use appendSlice to add many elements at once. It grows the list once and copies the elements in one operation, which is faster than one List.append for each element.

Errors#

• OutOfMemoryError if the Allocator cannot supply the new storage. The list does not change.

Examples#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.collections.list { List }

pub effect fn main() -> i32
  ! OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut values = List<u16>.make()
  let more: [u16; 2] = [8, 9]
  run List<u16>.appendSlice(&mut values, &more) |> Effect.provideMut<Allocator>(&mut allocator)
  if List<u16>.length(&values) != 2 || List<u16>.get(&values, 1) != 9 {
    return 1
  }
  return 0
}

Method appendRepeated#

pub effect fn appendRepeated<T: Copy>(self: &mut Self, value: T, count: usize) -> ()
  ! OutOfMemoryError
  ? &mut Allocator

Adds count copies of value at the end of the list.

Details#

The list grows at most once, and the copies are written in one tight loop with no call or capacity check for each element. For u8 the loop compiles to a memset. A count of 0 does nothing and does not allocate.

Errors#

• OutOfMemoryError if length + count overflows usize, or the Allocator cannot supply the new storage. The list does not change.

Examples#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.collections.list { List }

pub effect fn main() -> i32
  ! OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut levels = List<u16>.make()
  run List<u16>.appendRepeated(&mut levels, 65535, 4) |> Effect.provideMut<Allocator>(&mut allocator)
  if List<u16>.length(&levels) != 4 || List<u16>.get(&levels, 3) != 65535 {
    return 1
  }
  return 0
}

Method insertSlice#

pub effect fn insertSlice<T: Copy>(self: &mut Self, index: usize, values: &[T]) -> ()
  ! OutOfMemoryError
  ? &mut Allocator

Inserts a copy of each element of values at position index, in order, and moves the elements from index onward values.length positions to the right.

When to use#

Use insertSlice to insert many elements at once. It grows the list at most once and moves the later elements with one overlapping copy, where one List.insert for each element moves them once per element.

Errors#

• OutOfMemoryError if the Allocator cannot supply the new storage. The list does not change.

Gotchas#

If index is more than List.length, the program traps.

Examples#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.collections.list { List }

pub effect fn main() -> i32
  ! OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut values = List<u16>.make()
  let ends: [u16; 2] = [1, 4]
  let middle: [u16; 2] = [2, 3]
  run List<u16>.appendSlice(&mut values, &ends) |> Effect.provideMut<Allocator>(&mut allocator)
  run List<u16>.insertSlice(&mut values, 1, &middle) |> Effect.provideMut<Allocator>(&mut allocator)
  if List<u16>.length(&values) != 4 || List<u16>.get(&values, 2) != 3 || List<u16>.get(&values, 3) != 4 {
    return 1
  }
  return 0
}

Method insertRepeated#

pub effect fn insertRepeated<T: Copy>(self: &mut Self, index: usize, value: T, count: usize) -> ()
  ! OutOfMemoryError
  ? &mut Allocator

Inserts count copies of value at position index and moves the elements from index onward count positions to the right.

Details#

The list grows at most once, the later elements move with one overlapping copy, and the copies are written in one tight loop. A count of 0 does nothing and does not allocate.

Errors#

• OutOfMemoryError if length + count overflows usize, or the Allocator cannot supply the new storage. The list does not change.

Gotchas#

If index is more than List.length, the program traps.

Examples#

import silk.mem.allocator { Allocator, OutOfMemoryError }
import silk.core.effect { Effect }
import silk.collections.list { List }

pub effect fn main() -> i32
  ! OutOfMemoryError {
  let mut allocator = Allocator.systemAllocatorProvider()
  let mut values = List<u16>.make()
  let ends: [u16; 2] = [1, 9]
  run List<u16>.appendSlice(&mut values, &ends) |> Effect.provideMut<Allocator>(&mut allocator)
  run List<u16>.insertRepeated(&mut values, 1, 5, 3) |> Effect.provideMut<Allocator>(&mut allocator)
  if List<u16>.length(&values) != 5 || List<u16>.get(&values, 3) != 5 || List<u16>.get(&values, 4) != 9 {
    return 1
  }
  return 0
}

Category: Collections.

Profiles: aarch64-apple-darwin, aarch64-unknown-linux-gnu, aarch64-unknown-linux-gnu-no-libc, x86_64-unknown-linux-gnu, x86_64-unknown-linux-gnu-no-libc, wasm32-unknown-unknown, wasm32-wasip1, wasm32-wasip2.