--- a/langtools/src/share/classes/com/sun/tools/javac/code/Scope.java Tue Oct 26 14:29:48 2010 -0700
+++ b/langtools/src/share/classes/com/sun/tools/javac/code/Scope.java Thu Oct 28 10:17:47 2010 -0700
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1999, 2008, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -31,7 +31,8 @@
/** A scope represents an area of visibility in a Java program. The
* Scope class is a container for symbols which provides
* efficient access to symbols given their names. Scopes are implemented
- * as hash tables. Scopes can be nested; the next field of a scope points
+ * as hash tables with "open addressing" and "double hashing".
+ * Scopes can be nested; the next field of a scope points
* to its next outer scope. Nested scopes can share their hash tables.
*
* <p><b>This is NOT part of any supported API.
@@ -67,6 +68,7 @@
public Entry elems;
/** The number of elements in this scope.
+ * This includes deleted elements, whose value is the sentinel.
*/
public int nelems = 0;
@@ -109,7 +111,8 @@
}
}
- /** Every hash bucket is a list of Entry's which ends in sentinel.
+ /** Use as a "not-found" result for lookup.
+ * Also used to mark deleted entries in the table.
*/
private static final Entry sentinel = new Entry(null, null, null, null);
@@ -130,12 +133,15 @@
this.owner = owner;
this.table = table;
this.hashMask = table.length - 1;
- this.elems = null;
- this.nelems = 0;
- this.shared = 0;
this.scopeCounter = scopeCounter;
}
+ /** Convenience constructor used for dup and dupUnshared. */
+ private Scope(Scope next, Symbol owner, Entry[] table) {
+ this(next, owner, table, next.scopeCounter);
+ this.nelems = next.nelems;
+ }
+
/** Construct a new scope, within scope next, with given owner,
* using a fresh table of length INITIAL_SIZE.
*/
@@ -145,7 +151,6 @@
protected Scope(Symbol owner, ScopeCounter scopeCounter) {
this(null, owner, new Entry[INITIAL_SIZE], scopeCounter);
- for (int i = 0; i < INITIAL_SIZE; i++) table[i] = sentinel;
}
/** Construct a fresh scope within this scope, with same owner,
@@ -154,11 +159,7 @@
* of fresh tables.
*/
public Scope dup() {
- Scope result = new Scope(this, this.owner, this.table, scopeCounter);
- shared++;
- // System.out.println("====> duping scope " + this.hashCode() + " owned by " + this.owner + " to " + result.hashCode());
- // new Error().printStackTrace(System.out);
- return result;
+ return dup(this.owner);
}
/** Construct a fresh scope within this scope, with new owner,
@@ -167,7 +168,7 @@
* of fresh tables.
*/
public Scope dup(Symbol newOwner) {
- Scope result = new Scope(this, newOwner, this.table, scopeCounter);
+ Scope result = new Scope(this, newOwner, this.table);
shared++;
// System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode());
// new Error().printStackTrace(System.out);
@@ -179,7 +180,7 @@
* the table of its outer scope.
*/
public Scope dupUnshared() {
- return new Scope(this, this.owner, this.table.clone(), scopeCounter);
+ return new Scope(this, this.owner, this.table.clone());
}
/** Remove all entries of this scope from its table, if shared
@@ -189,7 +190,7 @@
assert shared == 0;
if (table != next.table) return next;
while (elems != null) {
- int hash = elems.sym.name.hashCode() & hashMask;
+ int hash = getIndex(elems.sym.name);
Entry e = table[hash];
assert e == elems : elems.sym;
table[hash] = elems.shadowed;
@@ -197,6 +198,7 @@
}
assert next.shared > 0;
next.shared--;
+ next.nelems = nelems;
// System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode());
// new Error().printStackTrace(System.out);
return next;
@@ -215,19 +217,17 @@
s.hashMask = newtable.length - 1;
}
}
- for (int i = 0; i < newtable.length; i++) newtable[i] = sentinel;
- for (int i = 0; i < oldtable.length; i++) copy(oldtable[i]);
- }
-
- /** Copy the given entry and all entries shadowed by it to table
- */
- private void copy(Entry e) {
- if (e.sym != null) {
- copy(e.shadowed);
- int hash = e.sym.name.hashCode() & hashMask;
- e.shadowed = table[hash];
- table[hash] = e;
+ int n = 0;
+ for (int i = oldtable.length; --i >= 0; ) {
+ Entry e = oldtable[i];
+ if (e != null && e != sentinel) {
+ table[getIndex(e.sym.name)] = e;
+ n++;
+ }
}
+ // We don't need to update nelems for shared inherited scopes,
+ // since that gets handled by leave().
+ nelems = n;
}
/** Enter symbol sym in this scope.
@@ -248,13 +248,17 @@
*/
public void enter(Symbol sym, Scope s, Scope origin) {
assert shared == 0;
- // Temporarily disabled (bug 6460352):
- // if (nelems * 3 >= hashMask * 2) dble();
- int hash = sym.name.hashCode() & hashMask;
- Entry e = makeEntry(sym, table[hash], elems, s, origin);
+ if (nelems * 3 >= hashMask * 2)
+ dble();
+ int hash = getIndex(sym.name);
+ Entry old = table[hash];
+ if (old == null) {
+ old = sentinel;
+ nelems++;
+ }
+ Entry e = makeEntry(sym, old, elems, s, origin);
table[hash] = e;
elems = e;
- nelems++;
scopeCounter.inc();
}
@@ -268,15 +272,15 @@
public void remove(Symbol sym) {
assert shared == 0;
Entry e = lookup(sym.name);
- while (e.scope == this && e.sym != sym) e = e.next();
if (e.scope == null) return;
scopeCounter.inc();
// remove e from table and shadowed list;
- Entry te = table[sym.name.hashCode() & hashMask];
+ int i = getIndex(sym.name);
+ Entry te = table[i];
if (te == e)
- table[sym.name.hashCode() & hashMask] = e.shadowed;
+ table[i] = e.shadowed;
else while (true) {
if (te.shadowed == e) {
te.shadowed = e.shadowed;
@@ -335,12 +339,50 @@
return lookup(name, noFilter);
}
public Entry lookup(Name name, Filter<Symbol> sf) {
- Entry e = table[name.hashCode() & hashMask];
+ Entry e = table[getIndex(name)];
+ if (e == null || e == sentinel)
+ return sentinel;
while (e.scope != null && (e.sym.name != name || !sf.accepts(e.sym)))
e = e.shadowed;
return e;
}
+ /*void dump (java.io.PrintStream out) {
+ out.println(this);
+ for (int l=0; l < table.length; l++) {
+ Entry le = table[l];
+ out.print("#"+l+": ");
+ if (le==sentinel) out.println("sentinel");
+ else if(le == null) out.println("null");
+ else out.println(""+le+" s:"+le.sym);
+ }
+ }*/
+
+ /** Look for slot in the table.
+ * We use open addressing with double hashing.
+ */
+ int getIndex (Name name) {
+ int h = name.hashCode();
+ int i = h & hashMask;
+ // The expression below is always odd, so it is guaranteed
+ // be be mutually prime with table.length, a power of 2.
+ int x = hashMask - ((h + (h >> 16)) << 1);
+ int d = -1; // Index of a deleted item.
+ for (;;) {
+ Entry e = table[i];
+ if (e == null)
+ return d >= 0 ? d : i;
+ if (e == sentinel) {
+ // We have to keep searching even if we see a deleted item.
+ // However, remember the index in case we fail to find the name.
+ if (d < 0)
+ d = i;
+ } else if (e.sym.name == name)
+ return i;
+ i = (i + x) & hashMask;
+ }
+ }
+
public Iterable<Symbol> getElements() {
return getElements(noFilter);
}
@@ -470,10 +512,11 @@
}
public Entry lookup(Name name) {
- Entry e = table[name.hashCode() & hashMask];
+ Entry e = table[getIndex(name)];
+ if (e == null)
+ return sentinel;
while (e.scope != null &&
- (e.sym.name != name ||
- /* Since an inner class will show up in package and
+ (/* Since an inner class will show up in package and
* import scopes until its inner class attribute has
* been processed, we have to weed it out here. This
* is done by comparing the owners of the entry's