From fd8481a0417f49ebc047600e7217eeed31a54fe0 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Sat, 29 May 2021 15:36:35 -0500 Subject: [PATCH] added set package --- core/container/map.onyx | 17 +----- core/container/set.onyx | 113 ++++++++++++++++++++++++++++++++++++++ core/hash.onyx | 12 ++++ core/std.onyx | 2 + tests/aoc-2020/day17.onyx | 2 +- tests/aoc-2020/day24.onyx | 2 +- tests/sets | 6 ++ tests/sets.onyx | 21 +++++++ 8 files changed, 159 insertions(+), 16 deletions(-) create mode 100644 core/container/set.onyx create mode 100644 core/hash.onyx create mode 100644 tests/sets create mode 100644 tests/sets.onyx diff --git a/core/container/map.onyx b/core/container/map.onyx index 385062f7..60adda30 100644 --- a/core/container/map.onyx +++ b/core/container/map.onyx @@ -1,7 +1,7 @@ package core.map #private_file array :: package core.array -#private_file string :: package core.string +#private_file hash :: package core.hash use package core.intrinsics.onyx { __zero_value } Map :: struct (K: type_expr, V: type_expr) { @@ -108,17 +108,6 @@ empty :: (use map: ^Map($K, $V)) -> bool { return entries.count == 0; } -hash_function :: proc { - (key: rawptr) -> u32 { return 0xcbf29ce7 ^ cast(u32) key; }, - (key: i32) -> u32 { return 0xcbf29ce7 ^ cast(u32) key; }, - (key: i64) -> u32 { return cast(u32) (cast(u64) 0xcbf29ce7 ^ cast(u64) key); }, - (key: str) -> u32 { - hash: u32 = 5381; - for ch: key do hash += (hash << 5) + ~~ch; - return hash; - }, -} - // // Private symbols // @@ -134,9 +123,9 @@ MapLookupResult :: struct { lookup :: (use map: ^Map($K, $V), key: K) -> MapLookupResult { lr := MapLookupResult.{}; - hash: u32 = hash_function(key); // You cannot use this type for the key, unless you add an overload. + hash_value: u32 = hash.to_u32(key); // You cannot use this type for the key, unless you add an overload. - lr.hash_index = hash % hashes.count; + lr.hash_index = hash_value % hashes.count; lr.entry_index = hashes[lr.hash_index]; while lr.entry_index >= 0 { diff --git a/core/container/set.onyx b/core/container/set.onyx new file mode 100644 index 00000000..ceb87d65 --- /dev/null +++ b/core/container/set.onyx @@ -0,0 +1,113 @@ +package core.set + +#private_file array :: package core.array +#private_file hash :: package core.hash +use package core.intrinsics.onyx { __zero_value } + +Set :: struct (T: type_expr) { + hashes : [..] i32; + entries : [..] Entry(T); + + default_value: T; + + Entry :: struct (T: type_expr) { + next : i32; + value : T; + } +} + +make :: ($T: type_expr, default := __zero_value(T), hash_count: i32 = 16) -> Set(T) { + set : Set(T); + init(^set, default=default, hash_count=hash_count); + return set; +} + +init :: (use set: ^Set($T), default := __zero_value(T), hash_count: i32 = 16) { + array.init(^hashes, hash_count); + hashes.count = hash_count; + array.fill(^hashes, -1); + + array.init(^entries, 4); + + default_value = default; +} + +free :: (use set: ^Set($T)) { + array.free(^hashes); + array.free(^entries); +} + +insert :: (use set: ^Set($T), value: T) { + lr := lookup(set, value); + + if lr.entry_index >= 0 do return; + + array.push(^entries, .{ + value = value, + hashes[lr.hash_index], + }); + + hashes[lr.hash_index] = entries.count - 1; +} + +has :: (use set: ^Set($T), value: T) -> bool { + lr := lookup(set, value); + return lr.entry_index >= 0; +} + +remove :: (use set: ^Set($T), value: T) { + lr := lookup(set, value); + 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(set, entries[lr.entry_index].value); + if last.entry_prev >= 0 do entries[last.entry_prev].next = lr.entry_index; + else do hashes[last.hash_index] = lr.entry_index; +} + +clear :: (use set: ^Set($T)) { + array.fill(^hashes, -1); + array.clear(^entries); +} + +empty :: (use set: ^Set($T)) -> bool { + return entries.count == 0; +} + +// +// Private symbols +// + +#private_file +SetLookupResult :: struct { + hash_index : i32 = -1; + entry_index : i32 = -1; + entry_prev : i32 = -1; +} + +#private_file +lookup :: (use set: ^Set($T), value: T) -> SetLookupResult { + lr := SetLookupResult.{}; + + hash_value: u32 = hash.to_u32(value); // You cannot have a set of this type without defining a to_u32 hash. + + lr.hash_index = hash_value % hashes.count; + lr.entry_index = hashes[lr.hash_index]; + + while lr.entry_index >= 0 { + if entries[lr.entry_index].value == value do return lr; + + lr.entry_prev = lr.entry_index; + lr.entry_index = entries[lr.entry_index].next; + } + + return lr; +} diff --git a/core/hash.onyx b/core/hash.onyx new file mode 100644 index 00000000..bf3b5028 --- /dev/null +++ b/core/hash.onyx @@ -0,0 +1,12 @@ +package core.hash + +to_u32 :: proc { + (key: rawptr) -> u32 { return 0xcbf29ce7 ^ cast(u32) key; }, + (key: i32) -> u32 { return 0xcbf29ce7 ^ cast(u32) key; }, + (key: i64) -> u32 { return cast(u32) (cast(u64) 0xcbf29ce7 ^ cast(u64) key); }, + (key: str) -> u32 { + hash: u32 = 5381; + for ch: key do hash += (hash << 5) + ~~ch; + return hash; + }, +} diff --git a/core/std.onyx b/core/std.onyx index 1e861a6a..15d5a7be 100644 --- a/core/std.onyx +++ b/core/std.onyx @@ -8,10 +8,12 @@ package core #load "./container/map" #load "./container/list" #load "./container/iter" +#load "./container/set" #load "./conv" #load "./math" #load "./random" +#load "./hash" #load "./string" #load "./string/builder" diff --git a/tests/aoc-2020/day17.onyx b/tests/aoc-2020/day17.onyx index 22cf20b6..cfef3b25 100644 --- a/tests/aoc-2020/day17.onyx +++ b/tests/aoc-2020/day17.onyx @@ -12,7 +12,7 @@ CubeState :: struct { next := false; } -#add_overload map.hash_function, (c: CubePos) -> u32 { +#add_overload hash.to_u32, (c: CubePos) -> u32 { return 17 * c.x + 13 * c.y + 11 * c.z + 19 * c.w; } diff --git a/tests/aoc-2020/day24.onyx b/tests/aoc-2020/day24.onyx index ee1458de..a2182c57 100644 --- a/tests/aoc-2020/day24.onyx +++ b/tests/aoc-2020/day24.onyx @@ -7,7 +7,7 @@ Vec2 :: struct { y: i32 = 0; } -#add_overload map.hash_function, (v: Vec2) -> u32 { +#add_overload hash.to_u32, (v: Vec2) -> u32 { return v.x * 11 + v.y * 17; } diff --git a/tests/sets b/tests/sets new file mode 100644 index 00000000..49ba581e --- /dev/null +++ b/tests/sets @@ -0,0 +1,6 @@ +5 +6 +true +-------------- +6 +false diff --git a/tests/sets.onyx b/tests/sets.onyx new file mode 100644 index 00000000..a1b42452 --- /dev/null +++ b/tests/sets.onyx @@ -0,0 +1,21 @@ +#load "core/std" + +use package core + +main :: (args: [] cstr) { + + S := set.make(i32); + + set.insert(^S, 5); + set.insert(^S, 5); + set.insert(^S, 6); + for entry: S.entries do println(entry.value); + + println(set.has(^S, 5)); + + println("--------------"); + set.remove(^S, 5); + for entry: S.entries do println(entry.value); + println(set.has(^S, 5)); + +} \ No newline at end of file -- 2.25.1