diff options
author | Ken Thompson <ken@golang.org> | 2010-11-20 15:58:28 -0800 |
---|---|---|
committer | Ken Thompson <ken@golang.org> | 2010-11-20 15:58:28 -0800 |
commit | 8cb8ba14a5c2d196105ba2c47c788610ad8d1971 (patch) | |
tree | 70a1401a008fc8044cd52ad9948913ee48f89d68 | |
parent | b1fd0860df0683ebe94267a78020864b26b44d7a (diff) | |
download | go-8cb8ba14a5c2d196105ba2c47c788610ad8d1971.tar.gz go-8cb8ba14a5c2d196105ba2c47c788610ad8d1971.zip |
more on dynamic hash in compound literals.
thanks to vskrap, andrey mirtchovski,
and Eoghan Sherry.
R=rsc
CC=golang-dev
https://golang.org/cl/3245041
-rw-r--r-- | src/cmd/gc/typecheck.c | 34 |
1 files changed, 24 insertions, 10 deletions
diff --git a/src/cmd/gc/typecheck.c b/src/cmd/gc/typecheck.c index ec73aebfa5..919d99ecf7 100644 --- a/src/cmd/gc/typecheck.c +++ b/src/cmd/gc/typecheck.c @@ -1809,14 +1809,11 @@ indexdup(Node *n, Node *hash[], ulong nhash) } static int -prime(ulong h) +prime(ulong h, ulong sr) { - ulong n, sr; + ulong n; - sr = h; - for(n=0; n<3; n++) - sr = (sr + h/sr)/2; - for(n=3; n<sr; n+=2) + for(n=3; n<=sr; n+=2) if(h%n == 0) return 0; return 1; @@ -1825,20 +1822,37 @@ prime(ulong h) static ulong inithash(Node *n, Node ***hash, Node **autohash, ulong nautohash) { - ulong h; + ulong h, sr; NodeList *ll; + int i; + // count the number of entries h = 0; for(ll=n->list; ll; ll=ll->next) h++; - h = 9*h/8; + + // if the auto hash table is + // large enough use it. if(h <= nautohash) { *hash = autohash; memset(*hash, 0, nautohash * sizeof(**hash)); return nautohash; } - while(!prime(h)) - h++; + + // make hash size odd and 12% larger than entries + h += h/8; + h |= 1; + + // calculate sqrt of h + sr = h/2; + for(i=0; i<5; i++) + sr = (sr + h/sr)/2; + + // check for primeality + while(!prime(h, sr)) + h += 2; + + // build and return a throw-away hash table *hash = mal(h * sizeof(**hash)); memset(*hash, 0, h * sizeof(**hash)); return h; |