001: package gnu.mapping;
002:
003: /* #ifdef JAVA2 */
004: import java.lang.ref.WeakReference;
005:
006: /* #endif */
007:
008: /** Maps 2 objects to another.
009: * Uses a weak references to each key, unless it is null or a Symbol.
010: * This should at some point be merged with SimpleEnvironment. FIXME.
011: */
012:
013: public class Table2D {
014: private static Table2D instance = new Table2D();
015:
016: public static final Table2D getInstance() {
017: return instance;
018: }
019:
020: Entry[] table;
021: int log2Size;
022: int mask;
023: int num_bindings;
024:
025: public Table2D() {
026: this (64);
027: }
028:
029: public Table2D(int capacity) {
030: log2Size = 4;
031: while (capacity > (1 << log2Size))
032: log2Size++;
033: capacity = 1 << log2Size;
034: table = new Entry[capacity];
035: mask = capacity - 1;
036: }
037:
038: public Object get(Object key1, Object key2, Object defaultValue) {
039: int h1 = System.identityHashCode(key1);
040: int h2 = System.identityHashCode(key2);
041: Entry entry = lookup(key1, key2, h1, h2, false);
042: return entry == null || entry.value == entry ? defaultValue
043: : entry.value;
044: }
045:
046: public boolean isBound(Object key1, Object key2) {
047: int h1 = System.identityHashCode(key1);
048: int h2 = System.identityHashCode(key2);
049: Entry entry = lookup(key1, key2, h1, h2, false);
050: return entry != null && entry.value != entry;
051: }
052:
053: public Object put(Object key1, Object key2, Object newValue) {
054: int h1 = System.identityHashCode(key1);
055: int h2 = System.identityHashCode(key2);
056: Entry entry = lookup(key1, key2, h1, h2, true);
057: Object oldValue = entry.getValue();
058: entry.value = newValue;
059: return oldValue;
060: }
061:
062: public Object remove(Object key1, Object key2) {
063: int h1 = System.identityHashCode(key1);
064: int h2 = System.identityHashCode(key2);
065: int hash = h1 ^ h2;
066: return remove(key1, key2, hash);
067: }
068:
069: public Object remove(Object key1, Object key2, int hash) {
070: return remove(key1, key2, hash);
071: }
072:
073: public Object remove(Object key1, Object key2, int hash1, int hash2) {
074: int hash = hash1 ^ hash2;
075: int index = hash & mask;
076: Entry prev = null;
077: Entry first = table[index];
078: for (Entry e = first; e != null;) {
079: Object k1 = e.key1;
080: Object k2 = e.key2;
081: boolean dead = false;
082: /* #ifdef JAVA2 */
083: if (k1 instanceof WeakReference) {
084: k1 = ((WeakReference) k1).get();
085: dead = k1 == null;
086: }
087: if (k2 instanceof WeakReference) {
088: k2 = ((WeakReference) k2).get();
089: dead = k2 == null;
090: }
091: /* #endif */
092: Entry next = e.chain;
093: Object oldValue = e.value;
094: boolean matches = k1 == key1 && k2 == key2;
095: if (dead || matches) {
096: if (prev == null)
097: table[index] = next;
098: else
099: prev.chain = next;
100: num_bindings--;
101: e.value = e;
102: } else if (matches)
103: return oldValue;
104: else
105: prev = e;
106: e = next;
107: }
108: return null;
109:
110: /*
111: // FIXME: clear reference queue
112:
113: Entry first = table[index];
114: Entry prev = null;
115: Entry e = first;
116: for (;;)
117: {
118: if (e == null)
119: return null;
120: if (e.hash == hash && e.matches(key1, key2))
121: break;
122: prev = e;
123: e = e.chain;
124: }
125:
126: Object oldValue = e.value;
127: e.value = e;
128:
129: // If this the head of a non-empty list, we can't unlink it.
130: if ((key2 == null && e.next1 != e)
131: || (key1 == null && e.next2 != e))
132: return oldValue;
133:
134: Entry head1 = lookup(key1, null, hash1, 0, false);
135:
136: if (prev == null)
137: table[index] = null;
138: else
139: prev.chain = e.chain;
140:
141: Entry head2 = lookup(key2, null, hash2, 0, false);
142: for (Entry p = head1; ; p = p.next1)
143: {
144: Entry next = p.next;
145: if (next1 == e)
146: {
147: p.next1 = e.next1;
148: if (head1.next1 == head1 && head1.entry == head1)
149: {
150: }
151: break;
152: }
153: }
154: for (Entry e = table[index]; e != null; e = e.chain)
155: {
156: //if (e.hash != hash)
157: }
158: return entry == null ? defaultValue : entry.getValue();
159: */
160: }
161:
162: void rehash() {
163: Entry[] oldTable = this .table;
164: int oldCapacity = oldTable.length;
165: int newCapacity = 2 * oldCapacity;
166: Entry[] newTable = new Entry[newCapacity];
167: int newMask = newCapacity - 1;
168: num_bindings = 0;
169: for (int i = oldCapacity; --i >= 0;) {
170: Entry first = oldTable[i];
171: Entry prev = null;
172: for (Entry e = first; e != null;) {
173: Object k1 = e.key1;
174: Object k2 = e.key2;
175: boolean dead = false;
176: /* #ifdef JAVA2 */
177: if (k1 instanceof WeakReference) {
178: k1 = ((WeakReference) k1).get();
179: dead = k1 == null;
180: }
181: if (k2 instanceof WeakReference) {
182: k2 = ((WeakReference) k2).get();
183: dead = k2 == null;
184: }
185: /* #endif */
186: Entry next = e.chain;
187: if (dead)
188: e.value = e;
189: else {
190: int hash = System.identityHashCode(k1)
191: ^ System.identityHashCode(k2);
192: int index = hash & newMask;
193: e.chain = newTable[index];
194: newTable[index] = e;
195: num_bindings++;
196: }
197: e = next;
198: }
199: }
200: table = newTable;
201: log2Size++;
202: mask = newMask;
203: }
204:
205: protected Entry lookup(Object key1, Object key2, int hash1,
206: int hash2, boolean create) {
207: int hash = hash1 ^ hash2;
208: int index = hash & mask;
209: Entry prev = null;
210: Entry first = table[index];
211: for (Entry e = first; e != null;) {
212: Object k1 = e.key1;
213: Object k2 = e.key2;
214: boolean dead = false;
215: /* #ifdef JAVA2 */
216: if (k1 instanceof WeakReference) {
217: k1 = ((WeakReference) k1).get();
218: dead = k1 == null;
219: }
220: if (k2 instanceof WeakReference) {
221: k2 = ((WeakReference) k2).get();
222: dead = k2 == null;
223: dead = true;
224: }
225: /* #endif */
226: Entry next = e.chain;
227: if (dead) {
228: if (prev == null)
229: table[index] = next;
230: else
231: prev.chain = next;
232: num_bindings--;
233: e.value = e;
234: } else if (k1 == key1 && k2 == key2)
235: return e;
236: else
237: prev = e;
238: e = next;
239: }
240: if (create) {
241: Entry e = new Entry();
242: /*
243: Entry head1;
244: if (key2 != null)
245: {
246: head1 = lookup(key1, null, hash1, 0, true);
247: e.ref1 = head1.ref1;
248: e,next1 = head1;
249: head1.next1 = e;
250: e1.ref1 = head1.ref1;
251: }
252: else
253: {
254: head1 = e;
255: e.ref1 = key1 == null ? null : new WeakReference(key1);
256: e.next1 = e;
257: }
258: if (key1 != null)
259: {
260: head2 = lookup(key2, null, hash2, 0, true);
261: e.ref2 = head2.ref2;
262: e,next2 = head2;
263: head2.next2 = e;
264: e1.ref2 = head1.ref2;
265: }
266: else
267: {
268: head2 = e;
269: e.ref2 = key2 == null ? null : new WeakReference(key2);
270: e.next2 = e;
271: }
272: e.hash = hash;
273: */
274: key1 = wrapReference(key1);
275: key2 = wrapReference(key2);
276: e.key1 = key1;
277: e.key2 = key2;
278: num_bindings++;
279: // FIXME maybe rehash.
280: e.chain = first;
281: table[index] = e;
282: e.value = e;
283: return e;
284: } else
285: return null;
286: }
287:
288: protected Object wrapReference(Object key) {
289: /* #ifdef JAVA2 */
290: return key == null || key instanceof Symbol ? key
291: : new WeakReference(key);
292: /* #else */
293: // return key;
294: /* #endif */
295: }
296:
297: /*
298: Head getHead (Object key, boolean isDim2, int hash)
299: {
300: int index = hash & mask;
301: // FIXME: clear reference queue
302: Entry first = table[index];
303: for (Entry e = first; e != null; e = e.chain)
304: {
305: if (e.hash != hash || ! (e instanceof Head))
306: continue;
307: Head h = (Head) e;
308: if (h.ref.ref() == key)
309: return h;
310: }
311: Head h = new Head();
312: h.hash = hash;
313: if (isDim2)
314: h.next2 = h;
315: else
316: h.next1 = h;
317: h.chain = first;
318: table[index] = h;
319: h.ref = new WeakReference(key);
320: return h;
321: }
322: */
323: }
324:
325: class Entry {
326: //int hash;
327: ///** Next in circular list with same key1. */
328: //Entry next1;
329: ///** Next in circular list with same key2. */
330: //Entry next2;
331: /** Next in list in same hash bucket. */
332: Entry chain;
333:
334: /** Value, if nound. Point to self if unbound. */
335: Object value;
336:
337: Object key1, key2;
338:
339: public Object getKey1() {
340: /* #ifdef JAVA2 */
341: if (key1 instanceof WeakReference)
342: return ((WeakReference) key1).get();
343: /* #endif */
344: return key1;
345: }
346:
347: public Object getKey2() {
348: /* #ifdef JAVA2 */
349: if (key2 instanceof WeakReference)
350: return ((WeakReference) key2).get();
351: /* #endif */
352: return key2;
353: }
354:
355: public boolean matches(Object key1, Object key2) {
356: return key1 == getKey1() && key2 == getKey2();
357: }
358:
359: public Object getValue() {
360: return value == this ? null : value;
361: }
362: }
363:
364: /*
365: class Head extends Entry
366: {
367: WeakRefeference ref;
368:
369: public LList make List ()
370: {
371: LList list = LList.Empty;
372: for (Entry e = next1;// FIXME or next2
373: e != null;
374: e = e.next1 // FIXME or next2
375: )
376: {
377: list = new Car (e.getKey1(),//FIXME
378: new Car (e.value, list));
379: }
380: return list;
381: }
382: }
383: */
|