From 26b357ca5b4555225803668a88c6d7145eeab59b Mon Sep 17 00:00:00 2001 From: Ken Thompson Date: Fri, 5 Dec 2008 18:24:05 -0800 Subject: [PATCH] range statement R=r OCL=20667 CL=20667 --- src/cmd/gc/dcl.c | 2 +- src/cmd/gc/go.h | 28 ++++++++++ src/cmd/gc/go.y | 48 ++++------------- src/cmd/gc/sys.go | 8 ++- src/cmd/gc/sysimport.c | 6 ++- src/cmd/gc/walk.c | 104 +++++++++++++++++++++++++++++++++++++ src/runtime/hashmap.c | 85 ++++++++++++++++++++++++++++++- src/runtime/hashmap.h | 25 ++++----- test/ken/range.go | 113 +++++++++++++++++++++++++++++++++++++++++ 9 files changed, 364 insertions(+), 55 deletions(-) create mode 100644 test/ken/range.go diff --git a/src/cmd/gc/dcl.c b/src/cmd/gc/dcl.c index 13503c5681..a7882e9add 100644 --- a/src/cmd/gc/dcl.c +++ b/src/cmd/gc/dcl.c @@ -1263,7 +1263,7 @@ void constiter(Node *vv, Type *t, Node *cc) { Iter viter, citer; - Node *v, *c, *a; + Node *v, *c; if(cc == N) cc = lastconst; diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h index 694b368446..b8429c3bd0 100644 --- a/src/cmd/gc/go.h +++ b/src/cmd/gc/go.h @@ -74,6 +74,33 @@ struct Array uchar b; // actual array - may not be contig }; +/* + * note this is the runtime representation + * of hashmap iterator. it is probably + * insafe to use it this way, but it puts + * all the changes in one place. + * only flag is referenced from go. + * actual placement does not matter as long + * as the size is >= actual size. + */ +typedef struct Hiter Hiter; +struct Hiter +{ + uchar data[8]; // return val from next + int32 elemsize; // size of elements in table */ + int32 changes; // number of changes observed last time */ + int32 i; // stack pointer in subtable_state */ + uchar last[8]; // last hash value returned */ + uchar h[8]; // the hash table */ + struct + { + uchar sub[8]; // pointer into subtable */ + uchar start[8]; // pointer into start of subtable */ + uchar end[8]; // pointer into end of subtable */ + uchar pad[8]; + } sub[4]; +}; + enum { Mpscale = 29, // safely smaller than bits in a long @@ -779,6 +806,7 @@ int isandss(Type*, Node*); Node* convas(Node*); void arrayconv(Type*, Node*); Node* colas(Node*, Node*); +Node* dorange(Node*, Node*, Node*, int); Node* reorder1(Node*); Node* reorder2(Node*); Node* reorder3(Node*); diff --git a/src/cmd/gc/go.y b/src/cmd/gc/go.y index 409838901e..2944d55101 100644 --- a/src/cmd/gc/go.y +++ b/src/cmd/gc/go.y @@ -51,8 +51,7 @@ %type stmt_list_r Astmt_list_r Bstmt_list_r %type Astmt Bstmt %type for_stmt for_body for_header -%type if_stmt if_body if_header -%type range_header range_body range_stmt select_stmt +%type if_stmt if_body if_header select_stmt %type simple_stmt osimple_stmt semi_stmt %type expr uexpr pexpr expr_list oexpr oexpr_list expr_list_r %type exprsym3_list_r exprsym3 @@ -478,11 +477,6 @@ complex_stmt: popdcl(); $$ = $2; } -| LRANGE range_stmt - { - popdcl(); - $$ = $2; - } | LCASE expr_list ':' { // will be converted to OCASE @@ -578,12 +572,20 @@ for_header: $$->ntest = $1; $$->nincr = N; } +| new_name ':' new_name LRANGE expr + { + $$ = dorange($1, $3, $5, 1); + } +| new_name LRANGE expr + { + $$ = dorange($1, N, $3, 1); + } for_body: for_header compound_stmt { $$ = $1; - $$->nbody = $2; + $$->nbody = list($$->nbody, $2); } for_stmt: @@ -625,36 +627,6 @@ if_stmt: $$ = $2; } -range_header: - new_name LCOLAS expr - { - $$ = N; - } -| new_name ',' new_name LCOLAS expr - { - $$ = N; - } -| new_name ',' new_name '=' expr - { - yyerror("range statement only allows := assignment"); - $$ = N; - } - -range_body: - range_header compound_stmt - { - $$ = $1; - $$->nbody = $2; - } - -range_stmt: - { - markdcl(); - } range_body - { - $$ = $2; - } - select_stmt: { markdcl(); diff --git a/src/cmd/gc/sys.go b/src/cmd/gc/sys.go index 775b83e51e..bc91beb043 100644 --- a/src/cmd/gc/sys.go +++ b/src/cmd/gc/sys.go @@ -51,8 +51,8 @@ export func Inf(int) float64; // return signed Inf export func NaN() float64; // return a NaN export func float32bits(float32) uint32; // raw bits export func float64bits(float64) uint64; // raw bits -export func float32frombits(uint32) float32; // raw bits -export func float64frombits(uint64) float64; // raw bits +export func float32frombits(uint32) float32; // raw bits +export func float64frombits(uint64) float64; // raw bits export func newmap(keysize int, valsize int, keyalg int, valalg int, @@ -61,6 +61,10 @@ export func mapaccess1(hmap *map[any]any, key any) (val any); export func mapaccess2(hmap *map[any]any, key any) (val any, pres bool); export func mapassign1(hmap *map[any]any, key any, val any); export func mapassign2(hmap *map[any]any, key any, val any, pres bool); +export func mapiterinit(hmap *map[any]any, hiter *any); +export func mapiternext(hiter *any); +export func mapiter1(hiter *any) (key any); +export func mapiter2(hiter *any) (key any, val any); export func newchan(elemsize int, elemalg int, hint int) (hchan *chan any); export func chanrecv1(hchan *chan any) (elem any); diff --git a/src/cmd/gc/sysimport.c b/src/cmd/gc/sysimport.c index 3a3dbcedc0..56b6b8aca6 100644 --- a/src/cmd/gc/sysimport.c +++ b/src/cmd/gc/sysimport.c @@ -1,4 +1,4 @@ -char *sysimport = +char *sysimport = "package sys\n" "export func sys.mal (? int32) (? *any)\n" "export func sys.breakpoint ()\n" @@ -48,6 +48,10 @@ char *sysimport = "export func sys.mapaccess2 (hmap *map[any] any, key any) (val any, pres bool)\n" "export func sys.mapassign1 (hmap *map[any] any, key any, val any)\n" "export func sys.mapassign2 (hmap *map[any] any, key any, val any, pres bool)\n" + "export func sys.mapiterinit (hmap *map[any] any, hiter *any)\n" + "export func sys.mapiternext (hiter *any)\n" + "export func sys.mapiter1 (hiter *any) (key any)\n" + "export func sys.mapiter2 (hiter *any) (key any, val any)\n" "export func sys.newchan (elemsize int, elemalg int, hint int) (hchan *chan any)\n" "export func sys.chanrecv1 (hchan *chan any) (elem any)\n" "export func sys.chanrecv2 (hchan *chan any) (elem any, pres bool)\n" diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c index da5917aa7f..68cf9123de 100644 --- a/src/cmd/gc/walk.c +++ b/src/cmd/gc/walk.c @@ -3033,6 +3033,110 @@ badt: return nl; } +Node* +dorange(Node *k, Node *v, Node *m, int local) +{ + Node *n, *hk, *on, *r, *a; + Type *t, *th; + + if(!local) + fatal("only local varables now"); + + n = nod(OFOR, N, N); + + walktype(m, Erv); + t = m->type; + if(t == T) + goto out; + if(t->etype == TARRAY) + goto ary; + if(isptrto(t, TARRAY)) { + t = t->type; + goto ary; + } + if(t->etype == TMAP) + goto map; + if(isptrto(t, TMAP)) { + t = t->type; + goto map; + } + + yyerror("range must be over map/array"); + goto out; + +ary: + hk = nod(OXXX, N, N); // hidden key + tempname(hk, types[TINT]); // maybe TINT32 + + n->ninit = nod(OAS, hk, literal(0)); + n->ntest = nod(OLT, hk, nod(OLEN, m, N)); + n->nincr = nod(OASOP, hk, literal(1)); + n->nincr->etype = OADD; + + k = old2new(k, hk->type); + n->nbody = nod(OAS, k, hk); + + if(v != N) { + v = old2new(v, t->type); + n->nbody = list(n->nbody, + nod(OAS, v, nod(OINDEX, m, hk)) ); + } + goto out; + +map: + th = typ(TARRAY); + th->type = ptrto(types[TUINT8]); + th->bound = (sizeof(struct Hiter) + types[tptr]->width - 1) / + types[tptr]->width; + hk = nod(OXXX, N, N); // hidden iterator + tempname(hk, th); // hashmap hash_iter + + on = syslook("mapiterinit", 1); + argtype(on, t->down); + argtype(on, t->type); + argtype(on, th); + r = nod(OADDR, hk, N); + r = list(m, r); + r = nod(OCALL, on, r); + n->ninit = r; + + r = nod(OINDEX, hk, literal(0)); + a = nod(OLITERAL, N, N); + a->val.ctype = CTNIL; + r = nod(ONE, r, a); + n->ntest = r; + + on = syslook("mapiternext", 1); + argtype(on, th); + r = nod(OADDR, hk, N); + r = nod(OCALL, on, r); + n->nincr = r; + + k = old2new(k, t->down); + if(v == N) { + on = syslook("mapiter1", 1); + argtype(on, th); + argtype(on, t->down); + r = nod(OADDR, hk, N); + r = nod(OCALL, on, r); + n->nbody = nod(OAS, k, r); + goto out; + } + v = old2new(v, t->type); + on = syslook("mapiter2", 1); + argtype(on, th); + argtype(on, t->down); + argtype(on, t->type); + r = nod(OADDR, hk, N); + r = nod(OCALL, on, r); + n->nbody = nod(OAS, nod(OLIST, k, v), r); + + goto out; + +out: + return n; +} + /* * from ascompat[te] * evaluating actual function arguments. diff --git a/src/runtime/hashmap.c b/src/runtime/hashmap.c index b70f9e952b..83fe06c665 100644 --- a/src/runtime/hashmap.c +++ b/src/runtime/hashmap.c @@ -649,7 +649,7 @@ donothing(uint32 s, void *a, void *b) USED(b); } -typedef struct hash Hmap; +typedef struct hash Hmap; static int32 debug = 0; // newmap(keysize uint32, valsize uint32, @@ -860,3 +860,86 @@ sys·mapassign2(Hmap *h, ...) prints("\n"); } } + +// mapiterinit(hmap *map[any]any, hiter *any); +void +sys·mapiterinit(Hmap *h, struct hash_iter *it) +{ + hash_iter_init(h, it); + it->data = hash_next(it); + if(debug) { + prints("sys·mapiterinit: map="); + sys·printpointer(h); + prints("; iter="); + sys·printpointer(it); + prints("; data="); + sys·printpointer(it->data); + prints("\n"); + } +} + +// mapiternext(hiter *any); +void +sys·mapiternext(struct hash_iter *it) +{ + it->data = hash_next(it); + if(debug) { + prints("sys·mapiternext: iter="); + sys·printpointer(it); + prints("; data="); + sys·printpointer(it->data); + prints("\n"); + } +} + +// mapiter1(hiter *any) (key any); +void +sys·mapiter1(struct hash_iter *it, ...) +{ + Hmap *h; + byte *ak, *res; + + h = it->h; + ak = (byte*)&it + h->ko; + + res = it->data; + if(res == nil) + throw("sys·mapiter2: key:val nil pointer"); + + h->keyalg->copy(h->keysize, ak, res); + + if(debug) { + prints("mapiter2: iter="); + sys·printpointer(it); + prints("; map="); + sys·printpointer(h); + prints("\n"); + } +} + +// mapiter2(hiter *any) (key any, val any); +void +sys·mapiter2(struct hash_iter *it, ...) +{ + Hmap *h; + byte *ak, *av, *res; + + h = it->h; + ak = (byte*)&it + h->ko; + av = (byte*)&it + h->vo; + + res = it->data; + if(res == nil) + throw("sys·mapiter2: key:val nil pointer"); + + h->keyalg->copy(h->keysize, ak, res); + h->valalg->copy(h->valsize, av, res+h->keysize); + + if(debug) { + prints("mapiter2: iter="); + sys·printpointer(it); + prints("; map="); + sys·printpointer(h); + prints("\n"); + } +} diff --git a/src/runtime/hashmap.h b/src/runtime/hashmap.h index 04bb732699..970e9e12e6 100644 --- a/src/runtime/hashmap.h +++ b/src/runtime/hashmap.h @@ -72,24 +72,25 @@ #define memcpy(a,b,c) mcpy((byte*)(a),(byte*)(b),(uint32)(c)) #define assert(a) if(!(a)) throw("assert") -struct hash; /* opaque */ -struct hash_subtable; /* opaque */ -struct hash_entry; /* opaque */ +struct hash; /* opaque */ +struct hash_subtable; /* opaque */ +struct hash_entry; /* opaque */ typedef uint64 uintptr_t; typedef uintptr_t hash_hash_t; struct hash_iter { - int32 elemsize; /* size of elements in table */ - int32 changes; /* number of changes observed last time */ - int32 i; /* stack pointer in subtable_state */ - hash_hash_t last_hash; /* last hash value returned */ - struct hash *h; /* the hash table */ + uint8* data; /* returned from next */ + int32 elemsize; /* size of elements in table */ + int32 changes; /* number of changes observed last time */ + int32 i; /* stack pointer in subtable_state */ + hash_hash_t last_hash; /* last hash value returned */ + struct hash *h; /* the hash table */ struct hash_iter_sub { - struct hash_entry *e; /* pointer into subtable */ - struct hash_entry *start; /* start of subtable */ - struct hash_entry *end; /* end of subtable */ - } subtable_state[16]; /* Should be large enough unless the hashing is + struct hash_entry *e; /* pointer into subtable */ + struct hash_entry *start; /* start of subtable */ + struct hash_entry *end; /* end of subtable */ + } subtable_state[4]; /* Should be large enough unless the hashing is so bad that many distinct data values hash to the same hash value. */ }; diff --git a/test/ken/range.go b/test/ken/range.go new file mode 100644 index 0000000000..c8a646dd30 --- /dev/null +++ b/test/ken/range.go @@ -0,0 +1,113 @@ +// $G $D/$F.go && $L $F.$A && ./$A.out + +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package main + +const size = 16; + +var a [size]byte; +var p *[]byte; +var m *map[int]byte; + +func +f(k int) byte +{ + return byte(k*10007 % size); +} + +func +init() +{ + p = new([]byte, size); + m = new(map[int]byte); + for k:=0; k