From ddcca62a276c528a4390c8e3d58403b865f81869 Mon Sep 17 00:00:00 2001 From: lemon Date: Sat, 13 Aug 2022 20:53:39 +0200 Subject: ok.. --- src/all.hff | 17 +++++++++-- src/env.cff | 28 ++++++++++++++++++ src/map.hff | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/mem.hff | 23 ++++++--------- src/parse.cff | 9 ++++++ src/set.hff | 8 ++++-- src/type.cff | 1 + 7 files changed, 159 insertions(+), 18 deletions(-) create mode 100644 src/env.cff create mode 100644 src/map.hff (limited to 'src') diff --git a/src/all.hff b/src/all.hff index 63ca996..4ae3e26 100644 --- a/src/all.hff +++ b/src/all.hff @@ -1,3 +1,4 @@ +import "mem.hff"; import "libc.hff"; import "option.hff"; @@ -26,8 +27,6 @@ defmacro foreach(x, i, a, ...body) [ } ] -defmacro ALIGNUP(x,a) [ (((x) + ((a) - 1)) & -(a)) ] - defmacro streq(a,b) [ (strcmp(a,b) == 0) ] /// Types @@ -35,6 +34,7 @@ defmacro streq(a,b) [ (strcmp(a,b) == 0) ] struct Type; struct Decl; struct Expr; +struct Env; struct Loc { fileid i16, @@ -103,13 +103,22 @@ struct Type { struct Parser { fp *FILE, + alloc *Allocator, curfile *const u8, tokloc Loc, curloc Loc, eof bool, peekchr Option, peektok Option, +} + +struct Decl { + name *const u8, +} +struct DeclList { + link *DeclList, + decl Decl, } struct Targ { @@ -150,6 +159,10 @@ extern fn efmt(fmt *const u8, ...) void; // type.cff +// env.cff +extern fn mkenv(parent *Env, alloc *Allocator) *Env; +extern fn envput(*Env, *const Decl) *Decl; + // targ.cff extern static g_targ *const Targ; extern fn targ_ini(name *const u8) bool; diff --git a/src/env.cff b/src/env.cff new file mode 100644 index 0000000..8878238 --- /dev/null +++ b/src/env.cff @@ -0,0 +1,28 @@ +import "map.hff"; +import "all.hff"; + +struct StringKeyTraits { + fn hash(s *const u8) u32 { return fnv1a_s(FNV1A_INI, s); } + fn eq(a *const u8, b *const u8) bool { return streq(a, b); } +} + +struct Env { + parent *Env, + alloc *Allocator, + decls Map<*const u8, *DeclList, StringKeyTraits>, +} + +extern fn mkenv(parent *Env, alloc *Allocator) *Env { + let env *Env = xmalloc(sizeof Env); + *env = { parent, alloc }; + return env; +} + +extern fn envput(env *Env, decl *const Decl) *Decl { + let l **DeclList = env.decls->get_slot(decl.name); + let n *DeclList = env.alloc->alloc(sizeof *DeclList); + n.link = *l; + n.decl = *decl; + *l = n; + return &n.decl; +} diff --git a/src/map.hff b/src/map.hff new file mode 100644 index 0000000..d8bbf52 --- /dev/null +++ b/src/map.hff @@ -0,0 +1,91 @@ +import "all.hff"; + +// KTraits: +// :hash(K) u32 +// :eq(T, T) bool +struct Map { + keys *K, + vals *V, + bitmap *u8, + N int, + count int, + + fn _iempty(self *Map, i int) bool { + return (self.bitmap[i/8] & (1 << (i%8))) == 0; + } + + fn get(self *Map, key K) *V { + if self.N == 0 { + return #null; + } + let i0 u32 = KTraits:hash(key); + let i = i0 & (self.N - 1); + do { + if self->_iempty(i) { + return #null; + } else if KTraits:eq(self.keys[i], key) { + return &self.vals[i]; + } + i = (i + 1) & (self.N - 1); + } while i != i0; + assert(#f, "unreachable"); + } + + fn put(self *Map, key K, val V) void { + if self.keys == #null { + assert(self.vals == #null and self.bitmap == #null and self.N == 0 and self.count == 0, + "?"); + self.keys = xcalloc(self.N = 16, sizeof K); + self.vals = xcalloc(self.N, sizeof V); + self.bitmap = xcalloc(self.N / 8, 1); + } + + if self.count == self.N / 2 { + // rehash + } + let i0 u32 = KTraits:hash(key); + let i = i0 & (self.N - 1); + do { + if self->_iempty(i) { + self.bitmap[i/8] |= (1 << (i%8)); + ++self.count; + self.vals[i] = val; + return; + } else if KTraits:eq(self.keys[i], key) { + self.vals[i] = val; + return; + } + i = (i + 1) & (self.N - 1); + } while i != i0; + assert(#f, "unreachable"); + } + + fn get_slot(self *Map, key K) *V { + if self.keys == #null { + assert(self.vals == #null and self.bitmap == #null and self.N == 0 and self.count == 0, + "?"); + self.keys = xcalloc(self.N = 16, sizeof K); + self.vals = xcalloc(self.N, sizeof V); + self.bitmap = xcalloc(self.N / 8, 1); + } + + if self.count == self.N / 2 { + // rehash + } + let i0 u32 = KTraits:hash(key); + let i = i0 & (self.N - 1); + do { + if self->_iempty(i) { + self.bitmap[i/8] |= (1 << (i%8)); + ++self.count; + self.vals[i] = {}; + return &self.vals[i]; + } else if KTraits:eq(self.keys[i], key) { + return &self.vals[i]; + } + i = (i + 1) & (self.N - 1); + } while i != i0; + assert(#f, "unreachable"); + } + +} diff --git a/src/mem.hff b/src/mem.hff index 9fee910..84064f3 100644 --- a/src/mem.hff +++ b/src/mem.hff @@ -1,6 +1,11 @@ +import "libc.hff"; import "all.hff"; def ARENA_SIZE = 16 * 1024; +defmacro ALIGNUP(x,a) [ (((x) + ((a) - 1)) & -(a)) ] +extern fn xmalloc(n usize) *void; +extern fn xcalloc(n usize, m usize) *void; +extern fn xrealloc(p *void, n usize) *void; struct ArenaRegion { prev *ArenaRegion, @@ -24,28 +29,18 @@ struct Arena { a.r.idx += n; return ptr; } else { - let rp = xmalloc(sizeof ArenaRegion); - *rp = a.r; + let rp *ArenaRegion = xmalloc(sizeof ArenaRegion); + *rp = *a.r; let r = ArenaRegion { .prev: rp }; return allocf(a, n); } } } -struct Mallocator { - fn allocf(*void, n usize) *void { - return xmalloc(n); - } - - fn freef(*void, ptr *void) void { - free(ptr); - } -} - struct Allocator { a *void, - allocf *fn(a *void, n usize) *void, - freef *fn(a *void, ptr *void) void, + allocf *fn(*void, usize) *void, + freef *fn(*void, *void) void, fn alloc(self *Allocator, n usize) *void { if self.allocf { diff --git a/src/parse.cff b/src/parse.cff index ef01da5..ba8e35d 100644 --- a/src/parse.cff +++ b/src/parse.cff @@ -415,6 +415,15 @@ fn lex(P *Parser) Tok { } extern fn parse(P *Parser) [#]Decl { + fn mallocator_allocf(*void, n usize) *void { + return xmalloc(n); + } + + fn mallocator_freef(*void, ptr *void) void { + free(ptr); + } + + let alloc = Allocator { #null, &mallocator_allocf, &mallocator_freef }; while not P.eof { let tok = lex(P); if tok.t == :eof { break; } diff --git a/src/set.hff b/src/set.hff index 955eac3..28e67be 100644 --- a/src/set.hff +++ b/src/set.hff @@ -1,6 +1,10 @@ import "vec.hff"; import "all.hff"; +// KTraits: +// :hash(K) u32 +// :eq(T, T) bool +// :dup(T) T struct Set { buf Vec, set **const T, @@ -27,7 +31,7 @@ struct Set { ) } - let i0 = Traits:hash(x) & (self.N - 1); + let i0 u32 = Traits:hash(x) & (self.N - 1); let i int = i0; do { if self.set[i] == #null { @@ -43,7 +47,7 @@ struct Set { } fn contains(self *Set, x T) bool { - let i0 = Traits:hash(x) & (self.N - 1); + let i0 u32 = Traits:hash(x) & (self.N - 1); let i int = i0; do { if self.set[i] == #null { diff --git a/src/type.cff b/src/type.cff index bd56503..a6987b7 100644 --- a/src/type.cff +++ b/src/type.cff @@ -3,6 +3,7 @@ import "all.hff"; fn hashtype(ty *const Type) u32 { let h = FNV1A_INI; h = fnv1a_i(h, ty.konst ? 1 : 0); + switch ty.u { case Void; case Bool; -- cgit v1.2.3