From 230933348c7305e1d9efb193c0ca963847cde804 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Tue, 7 Feb 2023 09:14:42 -0600 Subject: [PATCH] documented core.map --- core/container/map.onyx | 99 ++++++++++++++++++++++++++++++++++++----- 1 file changed, 89 insertions(+), 10 deletions(-) diff --git a/core/container/map.onyx b/core/container/map.onyx index daeb19b6..3d2bd202 100644 --- a/core/container/map.onyx +++ b/core/container/map.onyx @@ -3,6 +3,11 @@ package core.map use core {array, hash, memory, math, conv, Optional} use core.intrinsics.onyx { __initialize } +// +// Map is a generic hash-map implementation that uses chaining. +// Values can be of any type. Keys must of a type that supports +// the core.hash.to_u32, and the '==' operator. +// @conv.Custom_Format.{ #solidify format_map {K=Key_Type, V=Value_Type} } Map :: struct (Key_Type: type_expr, Value_Type: type_expr) where ValidKey(Key_Type) { allocator : Allocator; @@ -46,14 +51,25 @@ Map :: struct (Key_Type: type_expr, Value_Type: type_expr) where ValidKey(Key_Ty } -#match __make_overload macro (x: ^Map($K, $V), allocator := context.allocator) => #this_package.make(K, V); +// +// Allows for creation of a Map using make(). +// +// m := make(Map(str, i32)); +// +#overload +__make_overload :: macro (x: ^Map($K, $V), allocator := context.allocator) => + #this_package.make(K, V); -make :: ($Key: type_expr, $Value: type_expr, default := Value.{}) -> Map(Key, Value) { +// +// Creates and initializes a new map using the types provided. +make :: macro ($Key: type_expr, $Value: type_expr, default := Value.{}) -> Map(Key, Value) { map : Map(Key, Value); - init(^map, default = default); + #this_package.init(^map, default = default); return map; } +// +// Initializes a map. init :: (use map: ^Map($K, $V), default := V.{}) { __initialize(map); @@ -66,13 +82,20 @@ init :: (use map: ^Map($K, $V), default := V.{}) { array.init(^entries, allocator=allocator); } +// +// Allows for deletion of a Map using delete(^map). #match builtin.delete core.map.free +// +// Destroys a map and frees all memory. free :: (use map: ^Map) { if hashes.data != null do memory.free_slice(^hashes, allocator=allocator); if entries.data != null do array.free(^entries); } +// +// Sets the value at the specified key, or creates a new entry +// if the key was not already present. put :: (use map: ^Map, key: map.Key_Type, value: map.Value_Type) { lr := lookup(map, key); @@ -87,11 +110,20 @@ put :: (use map: ^Map, key: map.Key_Type, value: map.Value_Type) { if full(map) do grow(map); } +// +// Returns true if the map contains the key. has :: (use map: ^Map, key: map.Key_Type) -> bool { lr := lookup(map, key); return lr.entry_index >= 0; } +// +// Returns the value at the specified key, or map.default_value if +// the key is not present. +// +// This is subject to change with the addition of Optional to the +// standard library. +// get :: (use map: ^Map, key: map.Key_Type) -> map.Value_Type { lr := lookup(map, key); if lr.entry_index >= 0 do return entries[lr.entry_index].value; @@ -99,6 +131,9 @@ get :: (use map: ^Map, key: map.Key_Type) -> map.Value_Type { return default_value; } +// +// Returns a pointer to the value at the specified key, or null if +// the key is not present. get_ptr :: (use map: ^Map, key: map.Key_Type) -> ^map.Value_Type { lr := lookup(map, key); if lr.entry_index >= 0 do return ^entries[lr.entry_index].value; @@ -106,6 +141,10 @@ get_ptr :: (use map: ^Map, key: map.Key_Type) -> ^map.Value_Type { return null; } +// +// Returns an Optional of the value at the specified key. The Optional +// has a value if the key is present, otherwise the optional does not +// have a value. get_opt :: (use map: ^Map, key: map.Key_Type) -> Optional(map.Value_Type) { lr := lookup(map, key); if lr.entry_index >= 0 do return Optional.make(entries[lr.entry_index].value); @@ -113,6 +152,8 @@ get_opt :: (use map: ^Map, key: map.Key_Type) -> Optional(map.Value_Type) { return .{}; } +// +// Removes an entry from the map. delete :: (use map: ^Map, key: map.Key_Type) { lr := lookup(map, key); if lr.entry_index < 0 do return; @@ -132,6 +173,18 @@ delete :: (use map: ^Map, key: map.Key_Type) { else do hashes[last.hash_index] = lr.entry_index; } +// +// Helper macro that finds a value by the key, and if it exists, +// runs the code, providing an `it` variable that is a pointer +// to the value. +// +// m: Map(str, i32); +// m->update("test") { +// *it += 10; +// } +// or: +// m->update("test", #(*it += 10)); +// update :: macro (map: ^Map, key: map.Key_Type, body: Code) { lookup_ :: lookup lr := lookup_(map, key); @@ -142,15 +195,23 @@ update :: macro (map: ^Map, key: map.Key_Type, body: Code) { } } +// +// Removes all entries from the hash map. Does NOT +// modify memory, so be wary of dangling pointers! clear :: (use map: ^Map) { for i: 0 .. hashes.count do hashes.data[i] = -1; entries.count = 0; } +// +// Returns if the map does not contain any elements. empty :: (use map: ^Map) -> bool { return entries.count == 0; } +// +// Helper procedure to nicely format a Map when printing. +// Rarely ever called directly, instead used by conv.format_any. format_map :: (output: ^conv.Format_Output, format: ^conv.Format, x: ^Map($K, $V)) { if format.pretty_printing { output->write("{\n"); @@ -169,12 +230,14 @@ format_map :: (output: ^conv.Format_Output, format: ^conv.Format, x: ^Map($K, $V } } -#local -MapLiteralValue :: struct (K: type_expr, V: type_expr) { - key: K; - value: V; -} - +// +// Quickly create a Map with some entries. +// +// Map.literal(str, i32, .[ +// .{ "test", 123 }, +// .{ "foo", 456 }, +// ]); +// literal :: ($Key: type_expr, $Value: type_expr, values: [] MapLiteralValue(Key, Value)) => { m := core.map.make(Key, Value); for ^ values { @@ -184,6 +247,15 @@ literal :: ($Key: type_expr, $Value: type_expr, values: [] MapLiteralValue(Key, return m; } +#local +MapLiteralValue :: struct (K: type_expr, V: type_expr) { + key: K; + value: V; +} + +// +// Produces an iterator that yields all values of the map, +// in an unspecified order, as Map is unordered. as_iter :: (m: ^Map) => core.iter.generator( ^.{ m = m, i = 0 }, @@ -198,12 +270,19 @@ as_iter :: (m: ^Map) => }); +// +// Helper operator overloads for accessing values, accessing +// values by pointer, and setting values. #operator [] macro (map: Map($K, $V), key: K) -> V { return #this_package.get(^map, key); } #operator ^[] macro (map: Map($K, $V), key: K) -> ^V { return #this_package.get_ptr(^map, key); } #operator []= macro (map: Map($K, $V), key: K, value: V) { #this_package.put(^map, key, value); } // // Private symbols +// +// These are used for the implementation of Map, +// but do not need to be used by any other part +// of the code. // #local { @@ -236,7 +315,7 @@ as_iter :: (m: ^Map) => return lr; } - full :: (use map: ^Map) => entries.count >= ~~(0.75f * ~~hashes.count); + full :: (use map: ^Map) => entries.count >= (hashes.count * 3) / 4; grow :: (use map: ^Map) { new_size := math.max(hashes.count << 1, 8); -- 2.25.1