From 1c3b1c7aaeb7701ed60683c50329ef89f3ece306 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Mon, 14 Dec 2020 10:44:46 -0600 Subject: [PATCH] deprecated all mapping structures in favor of new 'Map(K, V)' in map.onyx --- core/i32map.onyx | 2 + core/map.onyx | 130 +++++++++++++++++++++++++++++++++++++++++++++ core/ptrmap.onyx | 2 + core/std/js.onyx | 1 + core/std/wasi.onyx | 1 + core/strmap.onyx | 2 + 6 files changed, 138 insertions(+) create mode 100644 core/map.onyx diff --git a/core/i32map.onyx b/core/i32map.onyx index 41b7b064..5f34a037 100644 --- a/core/i32map.onyx +++ b/core/i32map.onyx @@ -1,5 +1,7 @@ package core.i32map +// THIS PACKAGE IS DEPRECATED IN FAVOR OF USING 'Map(i32, ...)' from map.onyx. + use package core.array as array I32Map :: struct ($T) { diff --git a/core/map.onyx b/core/map.onyx new file mode 100644 index 00000000..d1f2e533 --- /dev/null +++ b/core/map.onyx @@ -0,0 +1,130 @@ +package core.map + +use package core.array as array +use package core.string as string + +Map :: struct ($K, $V) { + hashes : [..] i32; + entries : [..] MapEntry(K, V); +} + +MapEntry :: struct ($K, $T) { + next : i32; + key : K; + value : T; +} + +init :: proc (use map: ^Map($K, $V), hash_count: i32 = 16) { + array.init(^hashes, hash_count); + array.init(^entries, 4); + + for i: 0 .. hash_count do array.push(^hashes, -1); +} + +free :: proc (use map: ^Map($K, $V)) { + array.free(^hashes); + array.free(^entries); +} + +put :: proc (use map: ^Map($K, $V), key: K, value: V) { + lr := lookup(map, key); + + if lr.entry_index >= 0 { + entries[lr.entry_index].value = value; + return; + } + + entry : MapEntry(K, V); + entry.key = key; + entry.value = value; + entry.next = hashes[lr.hash_index]; + + array.push(^entries, entry); + + hashes[lr.hash_index] = entries.count - 1; +} + +has :: proc (use map: ^Map($K, $V), key: K) -> bool { + lr := lookup(map, key); + return lr.entry_index >= 0; +} + +get :: proc (use map: ^Map($K, $V), key: K, default := cast(V) 0) -> V { + lr := lookup(map, key); + if lr.entry_index >= 0 do return entries[lr.entry_index].value; + + return default; +} + +delete :: proc (use map: ^Map($K, $V), key: K) { + lr := lookup(map, key); + if lr.entry_index < 0 do return; + + if lr.entry_prev < 0 do hashes[lr.hash_index] = entries[lr.entry_index].next; + else do entries[lr.entry_prev].next = entries[lr.entry_index].next; + + if lr.entry_index == entries.count - 1 { + array.pop(^entries); + return; + } + + array.fast_delete(^entries, lr.entry_index); + last := lookup(map, entries[lr.entry_index].key); + if last.entry_prev >= 0 do entries[last.entry_prev].next = lr.entry_index; + else do hashes[last.hash_index] = lr.entry_index; +} + +clear :: proc (use map: ^Map($K, $V)) { + for i: 0 .. hashes.count do hashes.data[i] = -1; + entries.count = 0; +} + +hash_function :: proc { + proc (key: rawptr) -> u32 { return 0xcbf29ce7 ^ cast(u32) key; }, + proc (key: i32) -> u32 { return 0xcbf29ce7 ^ cast(u32) key; }, + proc (key: i64) -> u32 { return cast(u32) (cast(u64) 0xcbf29ce7 ^ cast(u64) key); }, + + proc (key: str) -> u32 { + hash: u32 = 5381; + for ch: key do hash += (hash << 5) + ~~ch; + return hash; + }, +} + +cmp_function :: proc { + proc (a: rawptr, b: rawptr) -> bool { return a == b; }, + proc (a: i32, b: i32) -> bool { return a == b; }, + proc (a: i64, b: i64) -> bool { return a == b; }, + + string.equal, +} + +// +// Private symbols +// + +#private_file +MapLookupResult :: struct { + hash_index : i32 = -1; + entry_index : i32 = -1; + entry_prev : i32 = -1; +} + +#private_file +lookup :: proc (use map: ^Map($K, $V), key: K) -> MapLookupResult { + lr := MapLookupResult.{}; + + hash := hash_function(key); + + lr.hash_index = hash % hashes.count; + lr.entry_index = hashes[lr.hash_index]; + + while lr.entry_index >= 0 { + if cmp_function(entries[lr.entry_index].key, key) do return lr; + + lr.entry_prev = lr.entry_index; + lr.entry_index = entries[lr.entry_index].next; + } + + return lr; +} diff --git a/core/ptrmap.onyx b/core/ptrmap.onyx index 17683682..65681e1b 100644 --- a/core/ptrmap.onyx +++ b/core/ptrmap.onyx @@ -1,5 +1,7 @@ package core.ptrmap +// THIS PACKAGE IS DEPRECATED IN FAVOR OF USING 'Map(rawptr, ...)' from map.onyx. + use package core.array as array PtrMap :: struct { diff --git a/core/std/js.onyx b/core/std/js.onyx index 72453ddc..e0dacf62 100644 --- a/core/std/js.onyx +++ b/core/std/js.onyx @@ -6,6 +6,7 @@ package core #include_file "core/array" #include_file "core/i32map" #include_file "core/intrinsics" +#include_file "core/map" #include_file "core/math" #include_file "core/memory" #include_file "core/ptrmap" diff --git a/core/std/wasi.onyx b/core/std/wasi.onyx index c6669203..e73b581e 100644 --- a/core/std/wasi.onyx +++ b/core/std/wasi.onyx @@ -7,6 +7,7 @@ package core #include_file "core/file" #include_file "core/i32map" #include_file "core/intrinsics" +#include_file "core/map" #include_file "core/math" #include_file "core/memory" #include_file "core/ptrmap" diff --git a/core/strmap.onyx b/core/strmap.onyx index f248f052..faf12512 100644 --- a/core/strmap.onyx +++ b/core/strmap.onyx @@ -1,5 +1,7 @@ package core.strmap +// THIS PACKAGE IS DEPRECATED IN FAVOR OF USING 'Map(str, ...)' from map.onyx. + use package core.array as array use package core.string as string use package core { print } -- 2.25.1