compiler/
kernel/
lib/
examples/
std/
arch/
char/
collections/
lang/
alloc/
ast/
gen/
il/
module/
parser/
resolver/
scanner/
alloc.rad
7.1 KiB
ast.rad
26.7 KiB
gen.rad
513 B
il.rad
19.5 KiB
lower.rad
308.1 KiB
module.rad
14.9 KiB
package.rad
1.3 KiB
parser.rad
89.5 KiB
resolver.rad
439.6 KiB
scanner.rad
18.0 KiB
sexpr.rad
6.4 KiB
strings.rad
2.2 KiB
types.rad
1.6 KiB
sys/
arch.rad
68 B
char.rad
855 B
collections.rad
39 B
fmt.rad
8.3 KiB
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
276 B
mem.rad
2.3 KiB
sys.rad
179 B
testing.rad
2.4 KiB
tests.rad
15.7 KiB
vec.rad
3.2 KiB
std.rad
281 B
scripts/
seed/
sublime/
test/
vim/
.gitignore
336 B
.gitsigners
112 B
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
9.2 KiB
README
2.5 KiB
STYLE
2.5 KiB
std.lib
1.5 KiB
std.lib.test
662 B
lib/std/lang/strings.rad
raw
| 1 | //! String interning for efficient identifier comparison. |
| 2 | //! |
| 3 | //! This module provides a hash-based string pool that enables fast pointer-based |
| 4 | //! equality checks for identifiers and module names. |
| 5 | //! |
| 6 | //! Instead of comparing string contents repeatedly during symbol lookup, |
| 7 | //! we intern strings once and compare pointers. |
| 8 | |
| 9 | use std::mem; |
| 10 | use std::collections::dict; |
| 11 | |
| 12 | /// Table size. |
| 13 | constant TABLE_SIZE: u32 = 32768; |
| 14 | |
| 15 | /// String interning pool using open-addressed hash table. |
| 16 | /// |
| 17 | /// Each unique string content is stored only once, allowing pointer equality |
| 18 | /// to be used instead of content comparison for symbol lookups and module names. |
| 19 | export record Pool: Copy { |
| 20 | /// Hash table slots. |
| 21 | table: [*[u8]; TABLE_SIZE], |
| 22 | /// Number of strings currently in the pool. |
| 23 | count: u32, |
| 24 | } |
| 25 | |
| 26 | /// Lookup result. |
| 27 | union Lookup: Copy { |
| 28 | /// Found. |
| 29 | Found(*[u8]), |
| 30 | /// Not found, contains empty slot index. |
| 31 | Empty(u32), |
| 32 | } |
| 33 | |
| 34 | /// Look up a string, returning either the found entry or the empty slot index. |
| 35 | fn lookup(sp: &Pool, str: *[u8]) -> Lookup { |
| 36 | let mut idx = dict::hash(str) & (TABLE_SIZE - 1); |
| 37 | |
| 38 | loop { |
| 39 | let entry = sp.table[idx]; |
| 40 | if entry.len > 0 { |
| 41 | if mem::eq(entry, str) { |
| 42 | return Lookup::Found(entry); |
| 43 | } |
| 44 | set idx = (idx + 1) & (TABLE_SIZE - 1); |
| 45 | } else { |
| 46 | return Lookup::Empty(idx); |
| 47 | } |
| 48 | } |
| 49 | } |
| 50 | |
| 51 | /// Look up a string in the pool. |
| 52 | /// Returns the canonical interned pointer if the string exists. |
| 53 | export fn find(sp: &Pool, str: *[u8]) -> ?*[u8] { |
| 54 | match lookup(sp, str) { |
| 55 | case Lookup::Found(entry) => return entry, |
| 56 | case Lookup::Empty(_) => return nil, |
| 57 | } |
| 58 | } |
| 59 | |
| 60 | /// Intern a string, returning a canonical pointer for equality comparison. |
| 61 | /// |
| 62 | /// If the string content already exists in the pool, returns the existing pointer. |
| 63 | /// Otherwise, adds the string pointer to the pool and returns it. |
| 64 | export fn intern(sp: &mut Pool, str: *[u8]) -> *[u8] { |
| 65 | match lookup(sp, str) { |
| 66 | case Lookup::Found(entry) => return entry, |
| 67 | case Lookup::Empty(idx) => { |
| 68 | assert sp.count < TABLE_SIZE / 2, "intern: string pool is full"; |
| 69 | set sp.table[idx] = str; |
| 70 | set sp.count += 1; |
| 71 | |
| 72 | return str; |
| 73 | } |
| 74 | } |
| 75 | } |