2696 - start work on hash 'table' data structure

Very cool that I thought I didn't support type ingredients in arbitrary
positions in container definitions, but I really did. I just didn't have
a test for it, and now I do.

2 files changed, 62 insertions, 4 deletions

diff --git a/059shape_shifting_recipe.cc b/059shape_shifting_recipe.cc
index 9de67a30..55f5f2b8 100644
--- a/059shape_shifting_recipe.cc
+++ b/059shape_shifting_recipe.cc
@@ -335,10 +335,6 @@ void accumulate_type_ingredients(const type_tree* exemplar_type, const type_tree
   }
   if (is_type_ingredient_name(exemplar_type->name)) {
     assert(!refinement_type->name.empty());
-    if (exemplar_type->right) {
-      raise_error << "type_ingredients in non-last position not currently supported\n" << end();
-      return;
-    }
     if (!contains_key(mappings, exemplar_type->name)) {
       trace(9993, "transform") << "adding mapping from " << exemplar_type->name << " to " << to_string(refinement_type) << end();
       put(mappings, exemplar_type->name, new type_tree(*refinement_type));
diff --git a/078table.mu b/078table.mu
new file mode 100644
index 00000000..09613a15
--- /dev/null
+++ b/078table.mu
@@ -0,0 +1,62 @@
+# A table is like an array, except that its keys are not integers but
+# arbitrary types.
+
+scenario table-read-write [
+  run [
+    1:address:shared:table:number:number <- new-table 30
+    put 1:address:shared:table:number:number, 12, 34
+    2:number <- index 1:address:shared:table:number:number, 12
+  ]
+  memory-should-contain [
+    2 <- 34
+  ]
+]
+
+container table:_key:_value [
+  length:number
+  capacity:number
+  data:address:shared:array:table_row:_key:_value
+]
+
+container table_row:_key:_value [
+  occupied?:boolean
+  key:_key
+  value:_value
+]
+
+recipe new-table capacity:number -> result:address:shared:table:_key:_value [
+  local-scope
+  load-ingredients
+  result <- new {(table _key _value): type}
+  tmp:address:number <- get-address *result, capacity:offset
+  *tmp <- copy capacity
+  data:address:address:shared:array:table_row:_key:_value <- get-address *result, data:offset
+  *data <- new {(table_row _key _value): type}, capacity
+]
+
+recipe put table:address:shared:table:_key:_value, key:_key, value:_value -> table:address:shared:table:_key:_value [
+  local-scope
+  load-ingredients
+  hash:number <- hash key
+  capacity:number <- get *table, capacity:offset
+  _, hash <- divide-with-remainder hash, capacity
+  table-data:address:shared:array:table_row:_key:_value <- get *table, data:offset
+  x:address:table_row:_key:_value <- index-address *table-data, hash
+  occupied?:boolean <- get *x, occupied?:offset
+  not-occupied?:boolean <- not occupied?:boolean
+  assert not-occupied?, [can't handle collisions yet]
+  *x <- merge 1/true, key, value
+]
+
+recipe index table:address:shared:table:_key:_value, key:_key -> result:_value [
+  local-scope
+  load-ingredients
+  hash:number <- hash key
+  capacity:number <- get *table, capacity:offset
+  _, hash <- divide-with-remainder hash, capacity
+  table-data:address:shared:array:table_row:_key:_value <- get *table, data:offset
+  x:address:table_row:_key:_value <- index-address *table-data, hash
+  occupied?:boolean <- get *x, occupied?:offset
+  assert occupied?, [can't handle missing elements yet]
+  result <- get *x, value:offset
+]