From 56b249c9a911dfc78f102fa3f88767501b3a6d6a Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Mon, 14 Dec 2020 12:31:41 -0600 Subject: [PATCH] removed old map data structures, in favor of generic map --- core/i32map.onyx | 113 -------------------------------------- core/map.onyx | 2 +- core/ptrmap.onyx | 113 -------------------------------------- core/std/js.onyx | 3 - core/std/wasi.onyx | 3 - core/strmap.onyx | 133 --------------------------------------------- tests/i32map.onyx | 24 ++++---- 7 files changed, 13 insertions(+), 378 deletions(-) delete mode 100644 core/i32map.onyx delete mode 100644 core/ptrmap.onyx delete mode 100644 core/strmap.onyx diff --git a/core/i32map.onyx b/core/i32map.onyx deleted file mode 100644 index 5f34a037..00000000 --- a/core/i32map.onyx +++ /dev/null @@ -1,113 +0,0 @@ -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) { - hashes : [..] i32; - entries : [..] I32MapEntry(T); -} - -I32MapEntry :: struct ($T) { - key : i32; - next : i32; - value : T; -} - -init :: proc (use imap: ^I32Map($T), 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 imap: ^I32Map($T)) { - array.free(^hashes); - array.free(^entries); -} - -put :: proc (use imap: ^I32Map($T), key: i32, value: T) { - lr := lookup(imap, key); - - if lr.entry_index >= 0 { - entries[lr.entry_index].value = value; - return; - } - - entry : I32MapEntry(T); - 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 imap: ^I32Map($T), key: i32) -> bool { - lr := lookup(imap, key); - return lr.entry_index >= 0; -} - -get :: proc (use imap: ^I32Map($T), key: i32, default := cast(T) 0) -> T { - lr := lookup(imap, key); - if lr.entry_index >= 0 do return entries[lr.entry_index].value; - - return default; -} - -delete :: proc (use imap: ^I32Map($T), key: i32) { - lr := lookup(imap, 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(imap, 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 imap: ^I32Map($T)) { - for i: 0 .. hashes.count do hashes.data[i] = -1; - entries.count = 0; -} - - - -// -// Private symbols -// - -#private_file -I32MapLookupResult :: struct { - hash_index : i32 = -1; - entry_index : i32 = -1; - entry_prev : i32 = -1; -} - -#private_file -lookup :: proc (use imap: ^I32Map($T), key: i32) -> I32MapLookupResult { - lr := I32MapLookupResult.{}; - - hash := cast(u32) 0xcbf29ce7 ^ cast(u32) key; - - lr.hash_index = hash % hashes.count; - lr.entry_index = hashes[lr.hash_index]; - - while lr.entry_index >= 0 { - if 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/map.onyx b/core/map.onyx index de7264b5..997c0aff 100644 --- a/core/map.onyx +++ b/core/map.onyx @@ -114,7 +114,7 @@ MapLookupResult :: struct { lookup :: proc (use map: ^Map($K, $V), key: K) -> MapLookupResult { lr := MapLookupResult.{}; - hash := hash_function(key); // You cannot use this type for the key, unless you add an overload. + hash: u32 = hash_function(key); // You cannot use this type for the key, unless you add an overload. lr.hash_index = hash % hashes.count; lr.entry_index = hashes[lr.hash_index]; diff --git a/core/ptrmap.onyx b/core/ptrmap.onyx deleted file mode 100644 index 65681e1b..00000000 --- a/core/ptrmap.onyx +++ /dev/null @@ -1,113 +0,0 @@ -package core.ptrmap - -// THIS PACKAGE IS DEPRECATED IN FAVOR OF USING 'Map(rawptr, ...)' from map.onyx. - -use package core.array as array - -PtrMap :: struct { - hashes : [..] i32; - entries : [..] PtrMapEntry; -} - -PtrMapEntry :: struct { - key : rawptr; - value : rawptr; - - next : i32; -} - -init :: proc (use pmap: ^PtrMap, 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 pmap: ^PtrMap) { - array.free(^hashes); - array.free(^entries); -} - -put :: proc (use pmap: ^PtrMap, key: rawptr, value: rawptr) { - lr := lookup(pmap, key); - - if lr.entry_index >= 0 { - entries[lr.entry_index].value = value; - return; - } - - array.push(^entries, PtrMapEntry.{ - key = key, - value = value, - next = hashes[lr.hash_index], - }); - - hashes[lr.hash_index] = entries.count - 1; -} - -has :: proc (use pmap: ^PtrMap, key: rawptr) -> bool { - lr := lookup(pmap, key); - return lr.entry_index >= 0; -} - -get :: proc (use pmap: ^PtrMap, key: rawptr) -> rawptr { - lr := lookup(pmap, key); - if lr.entry_index >= 0 do return entries[lr.entry_index].value; - - return null; -} - -delete :: proc (use pmap: ^PtrMap, key: rawptr) { - lr := lookup(pmap, 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(pmap, 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 pmap: ^PtrMap) { - for i: 0 .. hashes.count do hashes.data[i] = -1; - entries.count = 0; -} - - - -// -// Private symbols -// - -#private_file -PtrMapLookupResult :: struct { - hash_index : i32 = -1; - entry_index : i32 = -1; - entry_prev : i32 = -1; -} - -#private_file -lookup :: proc (use pmap: ^PtrMap, key: rawptr) -> PtrMapLookupResult { - lr := PtrMapLookupResult.{}; - - hash := cast(u32) 0xcbf29ce7 ^ cast(u32) key; - - lr.hash_index = hash % hashes.count; - lr.entry_index = hashes[lr.hash_index]; - - while lr.entry_index >= 0 { - if 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/std/js.onyx b/core/std/js.onyx index e0dacf62..5efe76ba 100644 --- a/core/std/js.onyx +++ b/core/std/js.onyx @@ -4,17 +4,14 @@ package core #include_file "core/alloc" #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" #include_file "core/random" #include_file "core/stdio" #include_file "core/string" #include_file "core/string/reader" -#include_file "core/strmap" #include_file "core/sys/js" diff --git a/core/std/wasi.onyx b/core/std/wasi.onyx index e73b581e..28c50274 100644 --- a/core/std/wasi.onyx +++ b/core/std/wasi.onyx @@ -5,17 +5,14 @@ package core #include_file "core/alloc" #include_file "core/array" #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" #include_file "core/random" #include_file "core/stdio" #include_file "core/string" #include_file "core/string/reader" -#include_file "core/strmap" #include_file "core/wasi" #include_file "core/sys/wasi" diff --git a/core/strmap.onyx b/core/strmap.onyx deleted file mode 100644 index faf12512..00000000 --- a/core/strmap.onyx +++ /dev/null @@ -1,133 +0,0 @@ -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 } - -StrMap :: struct ($T) { - hashes : [..] i32; - entries : [..] StrMapEntry(T); - - key_store : [..] u8; -} - -StrMapEntry :: struct ($T) { - next : i32; - key : str; - value : T; -} - -init :: proc (use smap: ^StrMap($T), hash_count: i32 = 16) { - array.init(^hashes, hash_count); - array.init(^entries, 4); - array.init(^key_store, 16); - - for i: 0 .. hash_count do array.push(^hashes, -1); -} - -free :: proc (use smap: ^StrMap($T)) { - array.free(^hashes); - array.free(^entries); - array.free(^key_store); -} - -put :: proc (use smap: ^StrMap($T), key: str, value: T, copy_key := false) { - lr := lookup(smap, key); - - if lr.entry_index >= 0 { - entries[lr.entry_index].value = value; - return; - } - - // FIX: This is broken at the moment, because the array could relocated - // and that would break all entries key member. - // - // new_key := key; - // if copy_key { - // new_key.data = ^key_store[key_store.count]; - // new_key.count = key.count; - // array.ensure_capacity(^key_store, key_store.count + key.count); - // key_store.count += key.count; - - // string.copy(key, new_key); - // } - - entry : StrMapEntry(T); - 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 smap: ^StrMap($T), key: str) -> bool { - lr := lookup(smap, key); - return lr.entry_index >= 0; -} - -get :: proc (use smap: ^StrMap($T), key: str, default := cast(T) 0) -> T { - lr := lookup(smap, key); - if lr.entry_index >= 0 do return entries[lr.entry_index].value; - - return default; -} - -delete :: proc (use smap: ^StrMap($T), key: str) { - lr := lookup(smap, 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(smap, 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 smap: ^StrMap($T)) { - for i: 0 .. hashes.count do hashes.data[i] = -1; - entries.count = 0; -} - - - -// -// Private symbols -// - -#private_file -StrMapLookupResult :: struct { - hash_index : i32 = -1; - entry_index : i32 = -1; - entry_prev : i32 = -1; -} - -#private_file -lookup :: proc (use smap: ^StrMap($T), key: str) -> StrMapLookupResult { - lr := StrMapLookupResult.{}; - - hash: u32 = 5381; - for ch: key do hash += (hash << 5) + ~~ch; - - lr.hash_index = hash % hashes.count; - lr.entry_index = hashes[lr.hash_index]; - - while lr.entry_index >= 0 { - if string.equal(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/tests/i32map.onyx b/tests/i32map.onyx index 7e808edc..4bf31cd7 100644 --- a/tests/i32map.onyx +++ b/tests/i32map.onyx @@ -5,23 +5,23 @@ package main use package core main :: proc (args: [] cstr) { - imap : i32map.I32Map(str); - i32map.init(^imap); + imap : map.Map(i32, str); + map.init(^imap); defer { print("Freeing map\n"); - i32map.free(^imap); + map.free(^imap); } - i32map.put(^imap, 50, "Hello "); - i32map.put(^imap, 1234, "World!"); + map.put(^imap, 50, "Hello "); + map.put(^imap, 1234, "World!"); - println(i32map.has(^imap, 50)); - println(i32map.has(^imap, 51)); + println(map.has(^imap, 50)); + println(map.has(^imap, 51)); - printf("%s%s\n", i32map.get(^imap, 50, ""), i32map.get(^imap, 1234, "")); + printf("%s%s\n", map.get(^imap, 50, ""), map.get(^imap, 1234, "")); - i32map.delete(^imap, 50); - println(i32map.has(^imap, 50)); + map.delete(^imap, 50); + println(map.has(^imap, 50)); - i32map.clear(^imap); - println(i32map.has(^imap, 1234)); + map.clear(^imap); + println(map.has(^imap, 1234)); } -- 2.25.1