001: /*
002: * SymbolTable.java
003: *
004: * Copyright (c) 1997-2005 Sun Microsystems, Inc. All Rights Reserved.
005: *
006: * See the file "LICENSE.txt" for information on usage and redistribution of
007: * this file, and for a DISCLAIMER OF ALL WARRANTIES.
008: */
009: package pnuts.lang;
010:
011: import java.io.IOException;
012: import java.io.ObjectInputStream;
013: import java.io.ObjectOutputStream;
014: import java.io.Serializable;
015: import java.util.Enumeration;
016: import java.util.NoSuchElementException;
017:
018: class SymbolTable implements Cloneable, Serializable {
019:
020: private static final int INITIAL_CAPACITY = 8;
021: private static final float LOAD_FACTOR = 0.75f;
022:
023: transient Binding[] table;
024: int count;
025: SymbolTable parent;
026: private int threshold;
027:
028: public SymbolTable() {
029: this .threshold = (int) (INITIAL_CAPACITY * LOAD_FACTOR);
030: this .table = new Binding[INITIAL_CAPACITY];
031: }
032:
033: public SymbolTable(SymbolTable parent) {
034: this ();
035: this .parent = parent;
036: }
037:
038: /**
039: * Gets the value of a variable.
040: *
041: * @param interned
042: * the name of the variable, which must be intern'd
043: * @return the value
044: */
045: public synchronized Object get(String interned) {
046: int hash = interned.hashCode() & 0x7fffffff;
047: int i = hash & (table.length - 1);
048: Binding b = table[i];
049: while (true) {
050: if (b == null) {
051: return b;
052: }
053: if (interned == b.name) {
054: return b.value;
055: }
056: b = b.chain;
057: }
058: }
059:
060: synchronized Binding lookup0(String interned) {
061: int hash = interned.hashCode() & 0x7fffffff;
062: int i = hash & (table.length - 1);
063: Binding b = table[i];
064: while (b != null && interned != b.name) {
065: b = b.chain;
066: }
067: return b;
068: }
069:
070: /**
071: * Looks for a name-value binding in the symbol table chain.
072: *
073: * @param interned
074: * the name of the variable, which must be intern'd
075: * @return a NamedValue
076: */
077: public synchronized NamedValue lookup(String interned) {
078: int hash = interned.hashCode() & 0x7fffffff;
079: SymbolTable env = this ;
080: do {
081: Binding[] env_tab = env.table;
082: int i = hash & (env_tab.length - 1);
083: Binding b = env_tab[i];
084: while (b != null && interned != b.name) {
085: b = b.chain;
086: }
087: if (b != null) {
088: return b;
089: }
090: env = env.parent;
091: } while (env != null);
092: return null;
093: }
094:
095: /**
096: * Defines a name-value binding in the symbol table.
097: *
098: * @param interned the name of the variable, which must be intern'd
099: * @param value the new value
100: * @exception IllegalStateException
101: * thrown when the specified symbol has been defined as a
102: * constant.
103: */
104: public synchronized void set(String interned, Object value) {
105: int hash = interned.hashCode() & 0x7fffffff;
106: int i = hash & (table.length - 1);
107:
108: for (Binding b = table[i]; b != null; b = b.chain) {
109: if (interned == b.name) {
110: b.set(value);
111: return;
112: }
113: }
114: addBinding(hash, interned, value, i);
115: }
116:
117: /**
118: * Defines a constant in the symbol table.
119: *
120: * @param interned the name of the variable, which must be intern'd
121: * @param value the constant value
122: * @exception IllegalStateException
123: * thrown when the specified symbol has been defined as a
124: * constant
125: */
126: public synchronized void setConstant(String interned, Object value) {
127: int hash = interned.hashCode() & 0x7fffffff;
128: int i = hash & (table.length - 1);
129:
130: for (Binding b = table[i]; b != null; b = b.chain) {
131: if (interned == b.name) {
132: if (b instanceof ImmutableBinding) {
133: throw new IllegalStateException();
134: }
135: removeBinding(interned);
136: }
137: }
138: addConstant(hash, interned, value, i);
139: }
140:
141: synchronized void assign(String interned, Object value) {
142: int hash = interned.hashCode() & 0x7fffffff;
143: SymbolTable env = this ;
144: do {
145: Binding[] env_tab = env.table;
146: int i = hash & (env_tab.length - 1);
147: Binding b = env_tab[i];
148: while (b != null && interned != b.name) {
149: b = b.chain;
150: }
151: if (b != null) {
152: b.set(value);
153: return;
154: }
155: env = env.parent;
156: } while (env != null);
157:
158: addBinding(hash, interned, value, hash & (table.length - 1));
159: }
160:
161: synchronized void addBinding(int hash, String interned,
162: Object value, int index) {
163: table[index] = new Binding(hash, interned, value, table[index]);
164: if (count++ >= threshold) {
165: ensureCapacity(table.length * 2);
166: }
167: }
168:
169: synchronized void addConstant(int hash, String interned,
170: Object value, int index) {
171: table[index] = new ImmutableBinding(hash, interned, value,
172: table[index]);
173: if (count++ >= threshold) {
174: ensureCapacity(table.length * 2);
175: }
176: }
177:
178: void ensureCapacity(int newCapacity) {
179: Binding[] oldTable = table;
180: int oldCapacity = oldTable.length;
181: if (oldCapacity == 1 << 30) {
182: threshold = Integer.MAX_VALUE;
183: return;
184: }
185:
186: Binding[] newTable = new Binding[newCapacity];
187: Binding[] src = table;
188: for (int j = 0; j < src.length; j++) {
189: Binding b = src[j];
190: if (b != null) {
191: src[j] = null;
192: do {
193: Binding next = b.chain;
194: int i = b.hash & (newCapacity - 1);
195: b.chain = newTable[i];
196: newTable[i] = b;
197: b = next;
198: } while (b != null);
199: }
200: }
201: table = newTable;
202: threshold = (int) (newCapacity * LOAD_FACTOR);
203: }
204:
205: synchronized Binding removeBinding(String interned) {
206: int hash = interned.hashCode() & 0x7fffffff;
207: int i = hash & (table.length - 1);
208:
209: Binding prev = table[i];
210: Binding b = prev;
211:
212: while (b != null) {
213: Binding next = b.chain;
214: if (interned == b.name) {
215: count--;
216: if (prev == b) {
217: table[i] = next;
218: } else {
219: prev.chain = next;
220: }
221: return b;
222: }
223: prev = b;
224: b = next;
225: }
226:
227: return b;
228: }
229:
230: /**
231: * Deletes all name-value bindings.
232: */
233: public synchronized void clear() {
234: Binding tab[] = table;
235: for (int i = 0; i < tab.length; i++) {
236: tab[i] = null;
237: }
238: count = 0;
239: }
240:
241: public int size() {
242: return count;
243: }
244:
245: /**
246: * Deep copy
247: */
248: public Object clone() {
249: try {
250: SymbolTable copy = (SymbolTable) super .clone();
251: Binding[] newTable = new Binding[table.length];
252: for (int i = 0; i < table.length; i++) {
253: Binding b = table[i];
254: if (b != null) {
255: newTable[i] = (Binding) b.clone();
256: }
257: }
258: copy.table = newTable;
259: if (parent != null) {
260: copy.parent = (SymbolTable) parent.clone();
261: }
262: return copy;
263: } catch (CloneNotSupportedException e) {
264: throw new InternalError();
265: }
266: }
267:
268: /**
269: * Returns an enumeration of the NamedValues in the symbol table.
270: *
271: * @return an enumeration of the NamedValues
272: * @see pnuts.lang.NamedValue
273: */
274: public Enumeration bindings() {
275: return new Enumerator(0);
276: }
277:
278: /**
279: * Returns an enumeration of the keys in the symbol table.
280: *
281: * @return an enumeration of the keys
282: */
283: public Enumeration keys() {
284: return new Enumerator(1);
285: }
286:
287: /**
288: * Returns an enumeration of the values in the symbol table.
289: *
290: * @return an enumeration of the values
291: */
292: public Enumeration values() {
293: return new Enumerator(2);
294: }
295:
296: private class Enumerator implements Enumeration {
297: Binding bind = null;
298:
299: int index = table.length;
300:
301: int kind;
302:
303: Enumerator(int kind) { // 0==Binding, 1==key, 2==value
304: this .kind = kind;
305: }
306:
307: public boolean hasMoreElements() {
308: while (bind == null && index > 0) {
309: bind = table[--index];
310: }
311: return bind != null;
312: }
313:
314: public Object nextElement() {
315: while (bind == null && index > 0) {
316: bind = table[--index];
317: }
318: if (bind != null) {
319: Binding b = bind;
320: bind = b.chain;
321: if (kind == 0) {
322: return b;
323: } else if (kind == 1) {
324: return b.name;
325: } else {
326: return b.value;
327: }
328: }
329: throw new NoSuchElementException("SymbolTable Enumerator");
330: }
331: }
332:
333: static final long serialVersionUID = 61380568117862288L;
334:
335: private void writeObject(ObjectOutputStream s) throws IOException {
336: s.defaultWriteObject();
337: int count = 0;
338: for (int i = 0; i < table.length; i++) {
339: Binding b = table[i];
340: while (b != null) {
341: if (b.value instanceof Serializable) {
342: count++;
343: }
344: b = b.chain;
345: }
346: }
347: s.writeInt(count);
348: for (int i = 0; i < table.length; i++) {
349: Binding b = table[i];
350: while (b != null) {
351: if (b.value instanceof Serializable) {
352: s.writeObject(b);
353: }
354: b = b.chain;
355: }
356: }
357: }
358:
359: private void readObject(ObjectInputStream s) throws IOException,
360: ClassNotFoundException {
361: s.defaultReadObject();
362: int count = s.readInt();
363: this .table = new Binding[INITIAL_CAPACITY];
364: for (int i = 0; i < count; i++) {
365: Binding b = (Binding) s.readObject();
366: set(b.name, b.value);
367: }
368: }
369: }
|