Skip to content
← Back

src/ir/program/row_displacement.ghul

1
namespace IR.Program is
2
use Collections.LIST
3
use Collections.MAP
4
use Collections.SET
5
6
/// Packs sparse rows into one table so that each row's entries keep
7
/// their columns relative to the row's offset and no two rows claim
8
/// the same slot. Reading `offset(row) + column` then finds exactly the
9
/// entry `row` has at `column`.
10
///
11
/// Rows are placed largest first, each at the lowest offset where all
12
/// of its columns are free.
13
class ROW_DISPLACEMENT[T] is
14
_rows: LIST[(key: T, columns: LIST[int])]
15
_offsets: MAP[T, int]
16
_size: int
17
18
init() is
19
_rows = LIST[(key: T, columns: LIST[int])]()
20
_offsets = MAP[T, int]()
21
si
22
23
/// Adds a row that has entries at `columns`, each zero or more.
24
add(key: T, columns: Collections.Iterable[int]) is
25
_rows.add((key, LIST[int](columns)))
26
si
27
28
/// Places every row added; call after the last one.
29
pack() is
30
_offsets.clear()
31
_size = 0
32
33
let order = LIST[(key: T, columns: LIST[int])](_rows)
34
35
order.sort((a, b) => b.columns.count - a.columns.count)
36
37
let used = SET[int]()
38
39
for row in order do
40
let offset mut = 0
41
42
while !_fits(row.columns, offset, used) do
43
offset = offset + 1
44
od
45
46
for column in row.columns do
47
used.add(offset + column)
48
49
if offset + column + 1 > _size then
50
_size = offset + column + 1
51
fi
52
od
53
54
_offsets[row.key] = offset
55
od
56
si
57
58
_fits(columns: LIST[int], offset: int, used: SET[int]) -> bool is
59
for column in columns do
60
if used.contains(offset + column) then
61
return false
62
fi
63
od
64
65
return true
66
si
67
68
/// Where the row for `key` starts.
69
offset(key: T) -> int => _offsets[key]
70
71
/// One past the highest slot any row uses.
72
size: int => _size
73
si
74
si