diff options
author | Kartik K. Agaram <vc@akkartik.com> | 2016-06-13 16:25:45 -0700 |
---|---|---|
committer | Kartik K. Agaram <vc@akkartik.com> | 2016-06-13 16:25:45 -0700 |
commit | 5e15a74f06e19e75954547cadc8bc73f9034727e (patch) | |
tree | 865531ced05be722a67dd874338c791eb4da9622 /069table.mu | |
parent | 29cc15d6b3559221e1147f1a822e10dcb22678e6 (diff) | |
download | mu-5e15a74f06e19e75954547cadc8bc73f9034727e.tar.gz |
3055
Diffstat (limited to '069table.mu')
-rw-r--r-- | 069table.mu | 87 |
1 files changed, 87 insertions, 0 deletions
diff --git a/069table.mu b/069table.mu new file mode 100644 index 00000000..4c98cf91 --- /dev/null +++ b/069table.mu @@ -0,0 +1,87 @@ +# A table is like an array, except that its keys are not integers but +# arbitrary types. + +scenario table-read-write [ + run [ + local-scope + tab:address:table:number:number <- new-table 30 + put-index tab, 12, 34 + 1:number/raw <- index tab, 12 + ] + memory-should-contain [ + 1 <- 34 + ] +] + +scenario table-read-write-non-integer [ + run [ + local-scope + key:address:array:character <- new [abc def] + {tab: (address table (address array character) number)} <- new-table 30 + put-index tab, key, 34 + 1:number/raw <- index tab, key + ] + memory-should-contain [ + 1 <- 34 + ] +] + +container table:_key:_value [ + length:number + capacity:number + data:address:array:table_row:_key:_value +] + +container table_row:_key:_value [ + occupied?:boolean + key:_key + value:_value +] + +def new-table capacity:number -> result:address:table:_key:_value [ + local-scope + load-ingredients + result <- new {(table _key _value): type} + data:address:array:table_row:_key:_value <- new {(table_row _key _value): type}, capacity + *result <- merge 0/length, capacity, data +] + +def put-index table:address:table:_key:_value, key:_key, value:_value -> table:address:table:_key:_value [ + local-scope + load-ingredients + hash:number <- hash key + hash <- abs hash + capacity:number <- get *table, capacity:offset + _, hash <- divide-with-remainder hash, capacity + hash <- abs hash # in case hash overflows into a negative integer + table-data:address:array:table_row:_key:_value <- get *table, data:offset + x:table_row:_key:_value <- index *table-data, hash + occupied?:boolean <- get x, occupied?:offset + not-occupied?:boolean <- not occupied?:boolean + assert not-occupied?, [can't handle collisions yet] + new-row:table_row:_key:_value <- merge 1/true, key, value + *table-data <- put-index *table-data, hash, new-row +] + +def abs n:number -> result:number [ + local-scope + load-ingredients + positive?:boolean <- greater-or-equal n, 0 + return-if positive?, n + result <- multiply n, -1 +] + +def index table:address:table:_key:_value, key:_key -> result:_value [ + local-scope + load-ingredients + hash:number <- hash key + hash <- abs hash + capacity:number <- get *table, capacity:offset + _, hash <- divide-with-remainder hash, capacity + hash <- abs hash # in case hash overflows into a negative integer + table-data:address:array:table_row:_key:_value <- get *table, data:offset + x:table_row:_key:_value <- index *table-data, hash + occupied?:boolean <- get x, occupied?:offset + assert occupied?, [can't handle missing elements yet] + result <- get x, value:offset +] |