-
-
Notifications
You must be signed in to change notification settings - Fork 419
Commit
- release-0.45.2
- 0.58.11
- 0.58.10
- 0.58.9
- 0.58.8
- 0.58.7
- 0.58.6
- 0.58.5
- 0.58.4
- 0.58.3
- 0.58.2
- 0.58.1
- 0.58.0
- 0.57.1
- 0.57.0
- 0.56.2
- 0.56.1
- 0.56.0
- 0.55.1
- 0.55.0
- 0.54.1
- 0.54.0
- 0.53.0
- 0.52.5
- 0.52.4
- 0.52.3
- 0.52.2
- 0.52.1
- 0.52.0
- 0.51.4
- 0.51.3
- 0.51.2
- 0.51.1
- 0.51.0
- 0.50.0
- 0.49.1
- 0.49.0
- 0.48.0
- 0.47.0
- 0.46.0
- 0.45.2
- 0.45.1
- 0.45.0
- 0.44.0
- 0.43.2
- 0.43.1
- 0.43.0
- 0.42.0
- 0.41.2
- 0.41.1
- 0.41.0
- 0.40.0
- 0.39.1
- 0.39.0
- 0.38.3
- 0.38.2
- 0.38.1
- 0.38.0
- 0.37.0
- 0.36.0
- 0.35.1
- 0.35.0
- 0.34.1
- 0.34.0
- 0.33.2
- 0.33.1
- 0.33.0
- 0.32.0
- 0.31.0
- 0.30.0
- 0.29.0
- 0.28.1
- 0.28.0
- 0.27.0
- 0.26.0
- 0.25.0
- 0.24.4
- 0.24.3
- 0.24.2
- 0.24.1
- 0.24.0
- 0.23.0
- 0.22.6
- 0.22.5
- 0.22.4
- 0.22.3
- 0.22.2
- 0.22.1
- 0.22.0
- 0.21.3
- 0.21.2
- 0.21.1
- 0.21.0
- 0.20.0
- 0.19.3
- 0.19.2
- 0.19.1
- 0.19.0
- 0.18.1
- 0.18.0
- 0.17.0
- 0.16.1
- 0.16.0
- 0.15.0
- 0.14.0
- 0.13.2
- 0.13.1
- 0.13.0
- 0.12.3
- 0.12.2
- 0.12.1
- 0.12.0
- 0.11.4
- 0.11.3
- 0.11.2
- 0.11.1
- 0.11.0
- 0.10.0
- 0.9.0
- 0.8.0
- 0.7.0
- 0.6.0
- 0.5.1
- 0.5.0
- 0.4.0
- 0.3.3
- 0.3.2
- 0.3.1
- 0.3.0
- 0.2.1
- 0.2.0
- 0.1.7
- 0.1.6
- 0.1.5
- 0.1.4
- 0.1.3
- 0.1.2
- 0.1.1
- 0.1.0
There are no files selected for viewing
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,95 @@ | ||
class ListNode[A] | ||
""" | ||
A node in a list. | ||
""" | ||
var _item: (A | None) | ||
var _next: (ListNode[A] | None) | ||
|
||
new create(item': A, next': (ListNode[A] | None)) => | ||
_item = consume item' | ||
_next = next' | ||
|
||
fun box item(): this->A ? => | ||
match _item | ||
| var some: this->A! => | ||
consume some | ||
else | ||
error | ||
end | ||
|
||
fun ref pop(): this->A^ ? => | ||
match _item = None | ||
| var some: this->A => | ||
consume some | ||
else | ||
error | ||
end | ||
|
||
fun box next(): (this->ListNode[A] | None) => _next | ||
|
||
class List[A] | ||
""" | ||
A singly linked list. | ||
""" | ||
var _head: (ListNode[A] | None) | ||
|
||
new create() => | ||
""" | ||
Creates an empty list. | ||
""" | ||
_head = None | ||
|
||
fun ref push(a: A): List[A]^ => | ||
""" | ||
Pushes a value to the head of the list. | ||
""" | ||
_head = ListNode[A](consume a, _head) | ||
this | ||
|
||
fun ref pop(): A^ ? => | ||
""" | ||
Pops a value from the head of the list. | ||
""" | ||
match _head | ||
| var head: ListNode[A] => | ||
_head = head.next() | ||
head.pop() | ||
else | ||
error | ||
end | ||
|
||
fun box values(): ListValues[A, this->ListNode[A]]^ => | ||
""" | ||
Return an iterator on the values in the list. | ||
""" | ||
ListValues[A, this->ListNode[A]](_head) | ||
|
||
class ListValues[A, N: ListNode[A] box] is Iterator[N->A] | ||
""" | ||
Iterate over the values in a list. | ||
""" | ||
var _next: (N | None) | ||
|
||
new create(head: (N | None)) => | ||
""" | ||
Keep the next list node to be examined. | ||
""" | ||
_next = head | ||
|
||
fun box has_next(): Bool => | ||
""" | ||
If we have a list node, we have more values. | ||
""" | ||
_next isnt None | ||
|
||
fun ref next(): N->A ? => | ||
""" | ||
Get the value of the list node and replace it with the next one. | ||
""" | ||
match _next | ||
| let next': N => | ||
_next = next'.next() | ||
next'.item() | ||
else | ||
error | ||
end |
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,194 @@ | ||
interface Hashable | ||
fun box hash(): U64 | ||
|
||
primitive _MapEmpty is Comparable[_MapEmpty] | ||
primitive _MapDeleted is Comparable[_MapDeleted] | ||
|
||
class Map[Key: (Hashable box & Comparable[Key] box), Value] | ||
var _size: U64 = 0 | ||
var _array: Array[((Key, Value) | _MapEmpty | _MapDeleted)] = | ||
Array[((Key, Value) | _MapEmpty | _MapDeleted)].prealloc(8) | ||
|
||
new create() => | ||
for i in Range(0, 8) do | ||
_array.append(_MapEmpty) | ||
end | ||
|
||
fun box size(): U64 => _size | ||
|
||
fun box space(): U64 => _array.space() | ||
|
||
fun box apply(key: Key): this->Value ? => | ||
var (index, found) = _search(key) | ||
|
||
if found then | ||
match _array(index) | ||
| (let k: Key, let v: this->Value!) => | ||
return consume v | ||
end | ||
end | ||
error | ||
|
||
fun ref update(key: Key, value: Value): (Value^ | None) => | ||
try | ||
let (index, found) = _search(key) | ||
let prev = _array(index) = (key, consume value) | ||
|
||
match consume prev | ||
| (let k: Key, let v: Value) => | ||
return consume v | ||
else | ||
_size = _size + 1 | ||
|
||
if (_size * 2) > _array.size() then | ||
_resize() | ||
end | ||
end | ||
end | ||
None | ||
|
||
fun ref remove(key: Key): (Value^ | None) => | ||
try | ||
let (index, found) = _search(key) | ||
|
||
if found then | ||
let prev = _array(index) = _MapDeleted | ||
_size = _size - 1 | ||
|
||
match consume prev | ||
| (let k: Key, let v: Value) => | ||
return consume v | ||
end | ||
end | ||
end | ||
None | ||
|
||
fun box index(idx: U64 = -1): (U64, Key, this->Value) ? => | ||
for i in Range(idx + 1, _array.size()) do | ||
let entry = _array(i) | ||
|
||
match entry | ||
| (let k: Key!, let v: this->Value!) => | ||
return (i, consume k, consume v) | ||
end | ||
end | ||
error | ||
|
||
fun box _search(key: Key): (U64, Bool) => | ||
var idx_del = _array.size() | ||
let mask = idx_del - 1 | ||
let h = key.hash() | ||
var idx = h and mask | ||
|
||
try | ||
for i in Range(0, _array.size()) do | ||
let entry = _array(idx) | ||
|
||
match entry | ||
| (let k: Key, let v: this->Value!) => | ||
if k == key then | ||
return (idx, true) | ||
end | ||
| _MapEmpty => | ||
if idx_del <= mask then | ||
return (idx_del, false) | ||
else | ||
return (idx, false) | ||
end | ||
| _MapDeleted => | ||
if idx_del > mask then | ||
idx_del = i | ||
end | ||
end | ||
|
||
idx = (h + ((i + (i * i)) / 2)) and mask | ||
end | ||
end | ||
|
||
(idx_del, false) | ||
|
||
fun ref _resize() => | ||
let _old = _array | ||
let old_len = _old.size() | ||
let new_len = old_len * 4 | ||
|
||
_array = Array[((Key, Value) | _MapEmpty | _MapDeleted)].prealloc(new_len) | ||
_size = 0 | ||
|
||
for i in Range(0, new_len) do | ||
_array.append(_MapEmpty) | ||
end | ||
|
||
try | ||
for i in Range(0, old_len) do | ||
let entry = _old(i) = _MapDeleted | ||
This comment has been minimized.
Sorry, something went wrong.
This comment has been minimized.
Sorry, something went wrong.
This comment has been minimized.
Sorry, something went wrong.
malthe
Contributor
|
||
|
||
match consume entry | ||
| (let k: Key, let v: Value) => | ||
this(k) = consume v | ||
end | ||
end | ||
end | ||
|
||
fun box keys(): MapKeys[Key, Value, this->Map[Key, Value]]^ => | ||
MapKeys[Key, Value, this->Map[Key, Value]](this) | ||
|
||
fun box values(): MapValues[Key, Value, this->Map[Key, Value]]^ => | ||
MapValues[Key, Value, this->Map[Key, Value]](this) | ||
|
||
fun box pairs(): MapPairs[Key, Value, this->Map[Key, Value]]^ => | ||
MapPairs[Key, Value, this->Map[Key, Value]](this) | ||
|
||
class MapKeys[ | ||
Key: (Hashable box & Comparable[Key] box), | ||
Value, | ||
M: Map[Key, Value] box] is Iterator[Key] | ||
|
||
var _map: M | ||
var _i: U64 | ||
|
||
new create(map: M) => | ||
_map = map | ||
_i = if _map.size() > 0 then U64(0) else U64(-1) end | ||
|
||
fun box has_next(): Bool => _i < _map.space() | ||
|
||
fun ref next(): Key ? => | ||
(_i, var k: Key, var v: M->Value!) = _map.index(_i) | ||
k | ||
|
||
class MapValues[ | ||
Key: (Hashable box & Comparable[Key] box), | ||
Value, | ||
M: Map[Key, Value] box] is Iterator[M->Value] | ||
|
||
var _map: M | ||
var _i: U64 | ||
|
||
new create(map: M) => | ||
_map = map | ||
_i = if _map.size() > 0 then U64(0) else U64(-1) end | ||
|
||
fun box has_next(): Bool => _i < _map.space() | ||
|
||
fun ref next(): M->Value ? => | ||
(_i, var k: Key, var v: M->Value!) = _map.index(_i) | ||
consume v | ||
|
||
class MapPairs[ | ||
Key: (Hashable box & Comparable[Key] box), | ||
Value, | ||
M: Map[Key, Value] box] is Iterator[(Key, M->Value)] | ||
|
||
var _map: M | ||
var _i: U64 | ||
|
||
new create(map: M) => | ||
_map = map | ||
_i = if _map.size() > 0 then U64(0) else U64(-1) end | ||
|
||
fun box has_next(): Bool => _i < _map.space() | ||
|
||
fun ref next(): (Key, M->Value) ? => | ||
(_i, var k: Key, var v: M->Value!) = _map.index(_i) | ||
(k, consume v) |
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,24 @@ | ||
// Produces [min, max) | ||
class Range[A: (Real[A] box & Number) = U64] is Iterator[A] | ||
let _min: A | ||
let _max: A | ||
let _inc: A | ||
var _idx: A | ||
|
||
new create(min: A, max: A) => | ||
_min = min | ||
_max = max | ||
_inc = 1 | ||
_idx = min | ||
|
||
new step(min: A, max: A, inc: A) => | ||
_min = min | ||
_max = max | ||
_inc = inc | ||
_idx = min | ||
|
||
fun box has_next(): Bool => _idx < _max | ||
|
||
fun ref next(): A => if _idx < _max then _idx = _idx + _inc else _idx end | ||
|
||
fun ref rewind() => _idx = _min |
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,28 @@ | ||
// Produces (max, min] | ||
class Reverse[A: (Real[A] box & Number) = U64] is Iterator[A] | ||
let _min: A | ||
let _max: A | ||
let _dec: A | ||
var _idx: A | ||
|
||
new create(max: A, min: A) => | ||
_min = min | ||
_max = max | ||
_dec = 1 | ||
_idx = max | ||
|
||
new step(max: A, min: A, dec: A) => | ||
_min = min | ||
_max = max | ||
_dec = dec | ||
_idx = max | ||
|
||
fun box has_next(): Bool => _idx >= (_min + _dec) | ||
|
||
fun ref next(): A => | ||
if _idx >= (_min + _dec) then | ||
_idx = _idx - _dec | ||
end | ||
_idx | ||
|
||
fun ref rewind() => _idx = _max |
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,85 @@ | ||
use "lib:rt" where linux | ||
|
||
primitive Time | ||
""" | ||
A collection of ways to fetch the current time. | ||
""" | ||
|
||
fun tag seconds(): I64 => | ||
""" | ||
The wall-clock adjusted system time. | ||
""" | ||
@time[I64](U64(0)) | ||
|
||
fun tag now(): (I64, I64) => | ||
""" | ||
The wall-clock adjusted system time with nanoseconds. | ||
""" | ||
if Platform.osx() then | ||
var ts: (I64, I64) = (0, 0) | ||
@gettimeofday[I32](&ts, U64(0)) | ||
(ts._1, ts._2 * 1000) | ||
elseif Platform.linux() then | ||
var ts: (I64, I64) = (0, 0) | ||
@clock_gettime[I32](U64(0), &ts) | ||
ts | ||
elseif Platform.windows() then | ||
var ft: (U32, U32) = (0, 0) | ||
@GetSystemTimeAsFileTime[None](&ft) | ||
var qft = ft._1.u64() or (ft._2.u64() << 32) | ||
var epoch = qft.i64() - 116444736000000000 | ||
var sec = epoch / 10000000 | ||
var nsec = (epoch - (sec * 10000000)) * 100 | ||
(sec, nsec) | ||
else | ||
(I64(0), I64(0)) | ||
end | ||
|
||
fun tag nanos(): U64 => | ||
""" | ||
Monotonic unadjusted nanoseconds. | ||
""" | ||
if Platform.osx() then | ||
@mach_absolute_time[U64]() | ||
elseif Platform.linux() then | ||
var ts: (U64, U64) = (0, 0) | ||
@clock_gettime[I32](U64(1), &ts) | ||
(ts._1 * 1000000000) + ts._2 | ||
elseif Platform.windows() then | ||
var pf: (U32, U32) = (0, 0) | ||
var pc: (U32, U32) = (0, 0) | ||
@QueryPerformanceFrequency[U32](&pf) | ||
@QueryPerformanceCounter[U32](&pc) | ||
var qpf = pf._1.u64() or (pf._2.u64() << 32) | ||
var qpc = pc._1.u64() or (pc._2.u64() << 32) | ||
(qpc * 1000000000) / qpf | ||
else | ||
U64(0) | ||
end | ||
|
||
fun tag cycles(): U64 => | ||
""" | ||
Processor cycle count. Don't use this for performance timing, as it does | ||
not control for out-of-order execution. | ||
""" | ||
@llvm.readcyclecounter[U64]() | ||
|
||
fun tag perf_begin(): U64 => | ||
""" | ||
Get a cycle count for beginning a performance testing block. This will | ||
will prevent instructions from before this call leaking into the block and | ||
instructions after this call being executed earlier. | ||
""" | ||
@internal.x86.cpuid[(I32, I32, I32, I32)](I32(0)) | ||
@llvm.x86.rdtsc[U64]() | ||
|
||
fun tag perf_end(): U64 => | ||
""" | ||
Get a cycle count for ending a performance testing block. This will | ||
will prevent instructions from after this call leaking into the block and | ||
instructions before this call being executed later. | ||
""" | ||
var aux: I32 = 0 | ||
var ts = @internal.x86.rdtscp[U64](&aux) | ||
@internal.x86.cpuid[(I32, I32, I32, I32)](I32(0)) | ||
ts |
Why do we need to assign
_MapDeleted
to the old array here?