dymokomi/luce-browser-foundation
Source of release 0.6.0
0.6.0 / src / gc / containers.lucb
#==============================================================================================
#
# containers - the collector's own vectors, hash maps and intrusive lists
#
# DESCRIPTION:
# Addition to LibGC (DESIGN.md §3.2-§3.3). LibGC keeps its bookkeeping (the block caches,
# the root set, the possible-pointer set, the mark stack, the lists of allocators, roots,
# root vectors and weak blocks) in AK's Vector, HashMap, HashTable and IntrusiveList, which
# allocate with malloc. In the port AK's containers allocate from the current allocator,
# and that is the collected heap itself (§3.3): the collector's own data must never live in
# the heap it collects. These are the same shapes over the C heap (`memory.heap`), with
# AK's behaviour where the collector depends on it (IntrusiveList::append unlinks the node
# from the list it was in; Vector::unstable_take moves the last element into the hole).
#
#==============================================================================================
# mark: GcVector ================================================================================
## A growable array on the C heap: the shape of AK::Vector<T> the collector uses for its own
## data (block caches, the mark stack, post-GC tasks).
pub struct GcVector[T]:
pub var m_data: T*?
pub var m_size: usize
pub var m_capacity: usize
## Vector::size.
pub func gc_vector_size[T](this: const GcVector[T]*) -> usize:
return this.m_size
## Vector::is_empty.
pub func gc_vector_is_empty[T](this: const GcVector[T]*) -> bool:
return this.m_size == 0
## Vector::at: the element at `index` (checked).
pub func gc_vector_at[T](this: const GcVector[T]*, index: usize) -> T:
assert(index < this.m_size)
let data = this.m_data else trap("GcVector: no storage")
return data[index]
## Vector::ensure_capacity: room for `capacity` elements without another allocation.
pub func gc_vector_ensure_capacity[T](this: GcVector[T]*, capacity: usize):
if capacity <= this.m_capacity:
return
var new_capacity = this.m_capacity * 2 if this.m_capacity > 0 else 8
if new_capacity < capacity:
new_capacity = capacity
let fresh = (new T[new_capacity] --- in memory.heap) else trap("out of memory")
if let old = this.m_data:
memory.copy(fresh, T[](old, this.m_size), this.m_size)
free(T[](old, this.m_capacity)) in memory.heap
this.m_data = fresh.data
this.m_capacity = new_capacity
## Vector::append.
pub func gc_vector_append[T](this: GcVector[T]*, value: T):
gc_vector_ensure_capacity(this, this.m_size + 1)
let data = this.m_data else trap("GcVector: no storage")
data[this.m_size] = value
this.m_size += 1
## Vector::insert: `value` before the element at `index`.
pub func gc_vector_insert[T](this: GcVector[T]*, index: usize, value: T):
assert(index <= this.m_size)
gc_vector_ensure_capacity(this, this.m_size + 1)
let data = this.m_data else trap("GcVector: no storage")
var i = this.m_size
while i > index:
data[i] = data[i - 1]
i -= 1
data[index] = value
this.m_size += 1
## Vector::remove: drop the element at `index`, keeping the order of the rest.
pub func gc_vector_remove[T](this: GcVector[T]*, index: usize):
assert(index < this.m_size)
let data = this.m_data else trap("GcVector: no storage")
for i in index + 1..<this.m_size:
data[i - 1] = data[i]
this.m_size -= 1
## Vector::take_last.
pub func gc_vector_take_last[T](this: GcVector[T]*) -> T:
assert(this.m_size > 0)
let data = this.m_data else trap("GcVector: no storage")
this.m_size -= 1
return data[this.m_size]
## Vector::unstable_take: the element at `index`, the last element moved into its place.
pub func gc_vector_unstable_take[T](this: GcVector[T]*, index: usize) -> T:
assert(index < this.m_size)
let data = this.m_data else trap("GcVector: no storage")
let value = data[index]
data[index] = data[this.m_size - 1]
this.m_size -= 1
return value
## Vector::clear: no elements and no storage.
pub func gc_vector_clear[T](this: GcVector[T]*):
if let old = this.m_data:
free(T[](old, this.m_capacity)) in memory.heap
this.m_data = none
this.m_size = 0
this.m_capacity = 0
## The elements as a span (valid until the next append).
pub func gc_vector_span[T](this: const GcVector[T]*) -> T[]:
let data = this.m_data else return T[]((T*)8, 0)
return T[](data, this.m_size)
# mark: GcHashMap ===============================================================================
## A hash map from nonzero addresses to `V` on the C heap (open addressing, linear probing,
## backward-shift removal): the shape of AK's HashMap<Cell*, HeapRoot>, HashMap<FlatPtr, HeapRoot> and
## HashTable<HeapBlock*> in the collector. Iteration order is the slot order; nothing in LibGC
## depends on the order of these tables.
pub struct GcHashMap[V]:
pub var m_keys: usize*?
pub var m_values: V*?
pub var m_size: usize
pub var m_capacity: usize
## HashMap::size.
pub func gc_hash_map_size[V](this: const GcHashMap[V]*) -> usize:
return this.m_size
## The slot `key` hashes to, where its probe starts.
func gc_hash_map_home[V](this: const GcHashMap[V]*, key: usize) -> usize:
return (usize)(((u64)key >> 4) *% 0x9E3779B97F4A7C15 >> 17) & (this.m_capacity - 1)
## The slot of `key` (probing from its hash), holding the key or empty (0).
func gc_hash_map_slot[V](this: const GcHashMap[V]*, key: usize) -> usize:
let keys = this.m_keys else trap("GcHashMap: no storage")
let mask = this.m_capacity - 1
var index = gc_hash_map_home(this, key)
while keys[index] != 0 and keys[index] != key:
index = (index + 1) & mask
return index
## HashMap::ensure_capacity: room for `capacity` keys below the load factor.
pub func gc_hash_map_ensure_capacity[V](this: GcHashMap[V]*, capacity: usize):
if (capacity + 1) * 4 <= this.m_capacity * 3:
return
var new_capacity = this.m_capacity * 2 if this.m_capacity > 0 else 16
while (capacity + 1) * 4 > new_capacity * 3:
new_capacity *= 2
let old_keys = this.m_keys
let old_values = this.m_values
let old_capacity = this.m_capacity
let keys = (new usize[new_capacity] in memory.heap) else trap("out of memory")
let values = (new V[new_capacity] --- in memory.heap) else trap("out of memory")
this.m_keys = keys.data
this.m_values = values.data
this.m_capacity = new_capacity
if let ok = old_keys:
let ov = old_values else trap("GcHashMap: no values")
for i in 0..<old_capacity:
if ok[i] != 0:
let slot = gc_hash_map_slot(this, ok[i])
keys[slot] = ok[i]
values[slot] = ov[i]
free(usize[](ok, old_capacity)) in memory.heap
free(V[](ov, old_capacity)) in memory.heap
## HashMap::set: `key` maps to `value` (replacing an existing value).
pub func gc_hash_map_set[V](this: GcHashMap[V]*, key: usize, value: V):
assert(key != 0)
gc_hash_map_ensure_capacity(this, this.m_size + 1)
let keys = this.m_keys else trap("GcHashMap: no storage")
let values = this.m_values else trap("GcHashMap: no values")
let slot = gc_hash_map_slot(this, key)
if keys[slot] == 0:
keys[slot] = key
this.m_size += 1
values[slot] = value
## HashMap::get: the value of `key`, or none.
pub func gc_hash_map_get[V](this: const GcHashMap[V]*, key: usize) -> V*?:
if this.m_size == 0 or key == 0:
return none
let keys = this.m_keys else return none
let values = this.m_values else return none
let slot = gc_hash_map_slot(this, key)
if keys[slot] == 0:
return none
return &values[slot]
## HashMap::remove: `key` and its value leave the map; answers whether it was there. The keys
## after it in its probe run move back into the hole when their probe starts at or before it,
## so every key stays reachable from its home slot without tombstones.
pub func gc_hash_map_remove[V](this: GcHashMap[V]*, key: usize) -> bool:
if this.m_size == 0 or key == 0:
return false
let keys = this.m_keys else return false
let values = this.m_values else return false
var hole = gc_hash_map_slot(this, key)
if keys[hole] == 0:
return false
let mask = this.m_capacity - 1
var index = (hole + 1) & mask
while keys[index] != 0:
let home = gc_hash_map_home(this, keys[index])
if ((index -% home) & mask) >= ((index -% hole) & mask):
keys[hole] = keys[index]
values[hole] = values[index]
hole = index
index = (index + 1) & mask
keys[hole] = 0
this.m_size -= 1
return true
## HashMap::contains.
pub func gc_hash_map_contains[V](this: const GcHashMap[V]*, key: usize) -> bool:
return gc_hash_map_get(this, key) != none
## HashMap::clear: no keys and no storage.
pub func gc_hash_map_clear[V](this: GcHashMap[V]*):
if let keys = this.m_keys:
free(usize[](keys, this.m_capacity)) in memory.heap
if let values = this.m_values:
free(V[](values, this.m_capacity)) in memory.heap
this.m_keys = none
this.m_values = none
this.m_size = 0
this.m_capacity = 0
## `for key in gc_hash_map_keys(&map)`: HashMap::keys() as a loop.
pub func gc_hash_map_keys[V](this: const GcHashMap[V]*) -> GcHashMapKeys[V]:
return GcHashMapKeys[V](map = this)
## The keys of a GcHashMap, in slot order.
pub struct GcHashMapKeys[V]: luce.Iterable[usize, GcHashMapKeyIterator[V]]:
pub var map: const GcHashMap[V]*
func iterator() -> GcHashMapKeyIterator[V]:
return GcHashMapKeyIterator[V](map = self.map, index = 0)
## The iterator of GcHashMapKeys.
pub struct GcHashMapKeyIterator[V]: luce.Iterator[usize]:
pub var map: const GcHashMap[V]*
pub var index: usize
func next() -> usize?:
let keys = self.map.m_keys else return none
while self.index < self.map.m_capacity:
let key = keys[self.index]
self.index += 1
if key != 0:
return key
return none
# mark: Intrusive lists =========================================================================
## AK::IntrusiveListNode: the links a listed object embeds, and the list it is on.
pub struct ListNode:
pub var m_list: List*?
pub var m_next: ListNode*?
pub var m_prev: ListNode*?
## AK::IntrusiveList: a doubly linked list of embedded ListNodes. The owner of a node is found
## from the node by the offset of the node in it (`container_of`).
pub struct List:
pub var m_first: ListNode*?
pub var m_last: ListNode*?
## IntrusiveList::is_empty.
pub func list_is_empty(this: const List*) -> bool:
return this.m_first == none
## IntrusiveListNode::is_in_list.
pub func list_node_is_in_list(this: const ListNode*) -> bool:
return this.m_list != none
## IntrusiveListNode::remove: unlink the node from the list it is on, if any.
pub func list_node_remove(this: ListNode*):
let list = this.m_list else return
if let prev = this.m_prev:
prev.m_next = this.m_next
else:
list.m_first = this.m_next
if let next = this.m_next:
next.m_prev = this.m_prev
else:
list.m_last = this.m_prev
this.m_list = none
this.m_next = none
this.m_prev = none
## IntrusiveList::append: `node` last, unlinked first from the list it was on (as AK does).
pub func list_append(this: List*, node: ListNode*):
list_node_remove(node)
node.m_list = this
node.m_prev = this.m_last
node.m_next = none
if let last = this.m_last:
last.m_next = node
else:
this.m_first = node
this.m_last = node
## IntrusiveList::remove.
pub func list_remove(this: List*, node: ListNode*):
assert(node.m_list == this)
list_node_remove(node)
## IntrusiveList::contains.
pub func list_contains(this: const List*, node: const ListNode*) -> bool:
return node.m_list == (List*)this
## IntrusiveList::first.
pub func list_first(this: const List*) -> ListNode*?:
return this.m_first
## IntrusiveList::last.
pub func list_last(this: const List*) -> ListNode*?:
return this.m_last
## `for node in list_nodes(&list)`: the nodes first to last (the list must not change meanwhile).
pub func list_nodes(this: const List*) -> ListNodes:
return ListNodes(list = this)
## The nodes of a List.
pub struct ListNodes: luce.Iterable[ListNode*, ListNodeIterator]:
pub var list: const List*
func iterator() -> ListNodeIterator:
return ListNodeIterator(next_node = self.list.m_first)
## The iterator of ListNodes.
pub struct ListNodeIterator: luce.Iterator[ListNode*]:
pub var next_node: ListNode*?
func next() -> ListNode*?:
let node = self.next_node else return none
self.next_node = node.m_next
return node