compiler/
lib/
examples/
std/
arch/
collections/
dict.rad
2.0 KiB
lang/
sys/
arch.rad
65 B
collections.rad
36 B
fmt.rad
3.8 KiB
intrinsics.rad
206 B
io.rad
1.2 KiB
lang.rad
222 B
mem.rad
2.2 KiB
sys.rad
167 B
testing.rad
2.4 KiB
tests.rad
11.6 KiB
vec.rad
3.1 KiB
std.rad
231 B
scripts/
seed/
test/
vim/
.gitignore
353 B
.gitsigners
112 B
LICENSE
1.1 KiB
Makefile
3.1 KiB
README
2.5 KiB
std.lib
987 B
std.lib.test
252 B
lib/std/collections/dict.rad
raw
| 1 | //! Open-addressed hash map from string keys to `i32` values. |
| 2 | //! |
| 3 | //! Uses DJB2 hashing with linear probing. The table size must be a power |
| 4 | //! of two and is provided by the caller via arena-allocated storage. |
| 5 | |
| 6 | use std::mem; |
| 7 | |
| 8 | /// Hash map entry. |
| 9 | pub record Entry { |
| 10 | /// Key. |
| 11 | key: *[u8], |
| 12 | /// Associated value. |
| 13 | value: i32, |
| 14 | } |
| 15 | |
| 16 | /// Open-addressed hash map with caller-provided storage. |
| 17 | pub record Dict { |
| 18 | /// Hash table entries. |
| 19 | entries: *mut [Entry], |
| 20 | /// Number of occupied entries. |
| 21 | count: u32, |
| 22 | } |
| 23 | |
| 24 | /// Create a dict backed by the given entry storage. |
| 25 | /// The storage length must be a power of two. |
| 26 | pub fn init(entries: *mut [Entry]) -> Dict { |
| 27 | for i in 0..entries.len { |
| 28 | entries[i] = Entry { key: &[], value: 0 }; |
| 29 | } |
| 30 | return Dict { entries, count: 0 }; |
| 31 | } |
| 32 | |
| 33 | /// Insert or update a key-value pair. Panics if the table exceeds 50% load. |
| 34 | pub fn insert(m: *mut Dict, key: *[u8], value: i32) { |
| 35 | let mask = m.entries.len - 1; |
| 36 | let mut idx = hash(key) & mask; |
| 37 | |
| 38 | loop { |
| 39 | let entry = m.entries[idx]; |
| 40 | if entry.key.len == 0 { |
| 41 | if m.count >= m.entries.len / 2 { |
| 42 | panic "dict::insert: table full"; |
| 43 | } |
| 44 | m.entries[idx] = Entry { key, value }; |
| 45 | m.count += 1; |
| 46 | return; |
| 47 | } |
| 48 | if mem::eq(entry.key, key) { |
| 49 | m.entries[idx].value = value; |
| 50 | return; |
| 51 | } |
| 52 | idx = (idx + 1) & mask; |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | /// Look up a value by key. Returns `nil` if not found. |
| 57 | pub fn get(m: *Dict, key: *[u8]) -> ?i32 { |
| 58 | let mask = m.entries.len - 1; |
| 59 | let mut idx = hash(key) & mask; |
| 60 | |
| 61 | loop { |
| 62 | let entry = m.entries[idx]; |
| 63 | if entry.key.len == 0 { |
| 64 | return nil; |
| 65 | } |
| 66 | if mem::eq(entry.key, key) { |
| 67 | return entry.value; |
| 68 | } |
| 69 | idx = (idx + 1) & mask; |
| 70 | } |
| 71 | } |
| 72 | |
| 73 | /// DJB2 hash function. |
| 74 | pub fn hash(str: *[u8]) -> u32 { |
| 75 | let mut h: u32 = 5381; |
| 76 | for b in str { |
| 77 | h = ((h << 5) + h) + b as u32; |
| 78 | } |
| 79 | return h; |
| 80 | } |