Skip to content

Commit

Permalink
Showing 5 changed files with 426 additions and 0 deletions.
95 changes: 95 additions & 0 deletions packages/collections/list.pony
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
194 changes: 194 additions & 0 deletions packages/collections/map.pony
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.

Copy link
@malthe

malthe Jun 8, 2016

Contributor

Why do we need to assign _MapDeleted to the old array here?

This comment has been minimized.

Copy link
@jemc

jemc Jun 8, 2016

Member

Because we need to be able to match on it later in search

This comment has been minimized.

Copy link
@malthe

malthe Jun 8, 2016

Contributor

But _old here refers to the old array which is no longer referred to anywhere. It'll be gc'ed shortly after and won't be used in any search method.

This comment has been minimized.

Copy link
@jemc

jemc Jun 8, 2016

Member

Ah, I see what's going on here. We have to extract the entry from the _old array, in a consume style to preserve any uniqueness guarantees it may have (iso or trn). But we can only consume a local reference, so we need to use destructive-read instead. In essence, we can assign _MapDeleted to "pop" the element out and get an ephemeral reference to retain uniqueness properties of the original in the array.

This comment has been minimized.

Copy link
@malthe

malthe Jun 8, 2016

Contributor

Gotcha. Thanks for explaining. There's got to be a way for the compiler to accept a destructive read without actually writing anything to the soon-to-be-gc'ed old array.


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)
24 changes: 24 additions & 0 deletions packages/collections/range.pony
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
28 changes: 28 additions & 0 deletions packages/collections/reverse.pony
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
85 changes: 85 additions & 0 deletions packages/time/time.pony
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

0 comments on commit 80e2ec1

Please sign in to comment.