1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
/* andrew reese's Exponential Array datatype */
use bits, mem.Arena, mem.arena_alloc
const XAR_INIT_SZ = 8
const XAR_MAX_DOUBLE = 20
struct Xar(T) {
n u32,
chunk [XAR_MAX_DOUBLE]^T
}
#[inline]
func xar_chnk_slot(xar ^Xar(T), idx u32) (u32, u32) {
let chnk = 31 - bits.clz((idx / XAR_INIT_SZ) + 1)
let slot = idx - ((XAR_INIT_SZ << chnk) - XAR_INIT_SZ)
return (chnk, slot)
}
func xar_get(xar ^Xar(T), idx u32) ^T {
let chnk, slot = xar_chnk_slot(xar, idx)
return xar->chunk[chnk] + (slot * sizeof(T))
}
func xar_put(xar ^Xar(T), idx u32, a ^Arena) {
let chnk, slot = xar_chnk_slot(xar, idx)
if (!xar->chunk[chnk]) {
xar->chunk[chnk] := arena_alloc(a, sizeof(T) * (XAR_INIT_SZ << chnk)), alignof(T))
}
return xar->chunk[chnk] + (slot * sizeof(T))
}
proc xar_push(xar ^Xar(T), v T, a ^Arena) {
xar_put(xar, xar.n, a)^ = v
xar.n := xar.n + 1
}
|
