Table2D


1   package gnu.mapping;
2   /* #ifdef JAVA2 */
3   import java.lang.ref.WeakReference  ;
4   /* #endif */
5   
6   /** Maps 2 objects to another.
7    * Uses a weak references to each key, unless it is null or a Symbol.
8    * This should at some point be merged with SimpleEnvironment.  FIXME.
9    */
10  
11  public class Table2D
12  {
13    private static Table2D instance = new Table2D();
14    public static final Table2D getInstance () { return instance; }
15  
16    Entry[] table;
17    int log2Size;
18    int mask;
19    int num_bindings;
20  
21    public Table2D ()
22    {
23      this(64);
24    }
25  
26    public Table2D (int capacity)
27    {
28      log2Size = 4;
29      while (capacity > (1 << log2Size))
30        log2Size++;
31      capacity = 1 << log2Size;
32      table = new Entry[capacity];
33      mask = capacity - 1;
34    }
35  
36    public Object   get (Object   key1, Object   key2, Object   defaultValue)
37    {
38      int h1 = System.identityHashCode(key1);
39      int h2 = System.identityHashCode(key2);
40      Entry entry = lookup(key1, key2, h1, h2, false);
41      return entry == null || entry.value == entry ? defaultValue : entry.value;
42    }
43  
44    public boolean isBound (Object   key1, Object   key2)
45    {
46      int h1 = System.identityHashCode(key1);
47      int h2 = System.identityHashCode(key2);
48      Entry entry = lookup(key1, key2, h1, h2, false);
49      return entry != null && entry.value != entry;
50    }
51  
52    public Object   put (Object   key1, Object   key2, Object   newValue)
53    {
54      int h1 = System.identityHashCode(key1);
55      int h2 = System.identityHashCode(key2);
56      Entry entry = lookup(key1, key2, h1, h2, true);
57      Object   oldValue = entry.getValue();
58      entry.value = newValue;
59      return oldValue;
60    }
61  
62    public Object   remove (Object   key1, Object   key2)
63    {
64      int h1 = System.identityHashCode(key1);
65      int h2 = System.identityHashCode(key2);
66      int hash = h1 ^ h2;
67      return remove (key1, key2, hash);
68    }
69  
70    public Object   remove (Object   key1, Object   key2, int hash)
71    {
72      return remove (key1, key2, hash);
73    }
74  
75    public Object   remove (Object   key1, Object   key2, int hash1, int hash2)
76    {
77      int hash = hash1 ^ hash2;
78      int index = hash & mask;
79      Entry prev = null;
80      Entry first = table[index];
81      for (Entry e = first; e != null; )
82        {
83          Object   k1 = e.key1;
84          Object   k2 = e.key2;
85          boolean dead = false;
86          /* #ifdef JAVA2 */
87          if (k1 instanceof WeakReference  )
88            {
89              k1 = ((WeakReference  ) k1).get();
90              dead = k1 == null;
91            }
92          if (k2 instanceof WeakReference  )
93            {
94              k2 = ((WeakReference  ) k2).get();
95              dead = k2 == null;
96            }
97          /* #endif */
98          Entry next = e.chain;
99          Object   oldValue = e.value;
100         boolean matches = k1 == key1 && k2 == key2;
101         if (dead || matches)
102           {
103             if (prev == null)
104               table[index] = next;
105             else
106               prev.chain = next;
107             num_bindings--;
108             e.value = e;
109           }
110         else if (matches)
111           return oldValue;
112         else
113           prev = e;
114         e = next;
115       }
116     return null;
117 
118     /*
119     // FIXME: clear reference queue
120     
121     Entry first = table[index];
122     Entry prev = null;
123     Entry e = first;
124     for (;;)
125       {
126         if (e == null)
127           return null;
128         if (e.hash == hash && e.matches(key1, key2))
129           break;
130         prev = e;
131         e = e.chain;
132       }
133 
134     Object oldValue = e.value;
135     e.value = e;
136 
137     // If this the head of a non-empty list, we can't unlink it.
138     if ((key2 == null && e.next1 != e)
139         || (key1 == null && e.next2 != e))
140       return oldValue;
141 
142     Entry head1 = lookup(key1, null, hash1, 0, false);
143 
144     if (prev == null)
145       table[index] = null;
146     else
147       prev.chain = e.chain;
148 
149     Entry head2 = lookup(key2, null, hash2, 0, false);
150     for (Entry p = head1;  ;  p = p.next1)
151       {
152         Entry next = p.next;
153         if (next1 == e)
154           {
155             p.next1 = e.next1;
156             if (head1.next1 == head1 && head1.entry == head1)
157               {
158               }
159             break;
160           }
161       }
162     for (Entry e = table[index];  e != null;  e = e.chain)
163       {
164         //if (e.hash != hash)
165       }
166     return entry == null ? defaultValue : entry.getValue();
167     */
168   }
169 
170   void rehash ()
171   {
172     Entry[] oldTable = this.table;
173     int oldCapacity = oldTable.length;
174     int newCapacity = 2 * oldCapacity;
175     Entry[] newTable = new Entry[newCapacity];
176     int newMask = newCapacity - 1;
177     num_bindings = 0;
178     for (int i = oldCapacity;  --i >= 0;)
179       {
180         Entry first = oldTable[i];
181         Entry prev = null;
182     for (Entry e = first; e != null; )
183       {
184             Object   k1 = e.key1;
185             Object   k2 = e.key2;
186             boolean dead = false;
187             /* #ifdef JAVA2 */
188             if (k1 instanceof WeakReference  )
189               {
190                 k1 = ((WeakReference  ) k1).get();
191                 dead = k1 == null;
192               }
193             if (k2 instanceof WeakReference  )
194               {
195                 k2 = ((WeakReference  ) k2).get();
196                 dead = k2 == null;
197               }
198             /* #endif */
199             Entry next = e.chain;
200             if (dead)
201               e.value = e;
202             else
203               {
204                 int hash = System.identityHashCode(k1)
205                   ^ System.identityHashCode(k2);
206                 int index = hash & newMask;
207                 e.chain = newTable[index];
208                 newTable[index] = e;
209                 num_bindings++;
210               }
211             e = next;
212           }
213       }
214     table = newTable;
215     log2Size++;
216     mask = newMask;
217   }
218 
219   protected Entry lookup (Object   key1, Object   key2, int hash1, int hash2,
220                           boolean create)
221   {
222     int hash = hash1 ^ hash2;
223     int index = hash & mask;
224     Entry prev = null;
225     Entry first = table[index];
226     for (Entry e = first; e != null; )
227       {
228         Object   k1 = e.key1;
229         Object   k2 = e.key2;
230         boolean dead = false;
231         /* #ifdef JAVA2 */
232         if (k1 instanceof WeakReference  )
233           {
234             k1 = ((WeakReference  ) k1).get();
235             dead = k1 == null;
236           }
237         if (k2 instanceof WeakReference  )
238           {
239             k2 = ((WeakReference  ) k2).get();
240             dead = k2 == null;
241               dead = true;
242           }
243         /* #endif */
244         Entry next = e.chain;
245         if (dead)
246           {
247             if (prev == null)
248               table[index] = next;
249             else
250               prev.chain = next;
251             num_bindings--;
252             e.value = e;
253           }
254         else if (k1 == key1 && k2 == key2)
255           return e;
256         else 
257           prev = e;
258         e = next;
259       }
260     if (create)
261       {
262         Entry e = new Entry();
263         /*
264         Entry head1;
265         if (key2 != null)
266           {
267             head1 = lookup(key1, null, hash1, 0, true);
268             e.ref1 = head1.ref1;
269             e,next1 = head1;
270             head1.next1 = e;
271             e1.ref1 = head1.ref1;
272           }
273         else
274           {
275             head1 = e;
276             e.ref1 = key1 == null ? null : new WeakReference(key1);
277             e.next1 = e;
278           }
279         if (key1 != null)
280           {
281             head2 = lookup(key2, null, hash2, 0, true);
282             e.ref2 = head2.ref2;
283             e,next2 = head2;
284             head2.next2 = e;
285             e1.ref2 = head1.ref2;
286           }
287         else
288           {
289             head2 = e;
290             e.ref2 = key2 == null ? null : new WeakReference(key2);
291             e.next2 = e;
292           }
293         e.hash = hash;
294         */
295         key1 = wrapReference(key1);
296         key2 = wrapReference(key2);
297         e.key1 = key1;
298         e.key2 = key2;
299         num_bindings++;
300         // FIXME maybe rehash.
301         e.chain = first;
302         table[index] = e;
303         e.value = e;
304         return e;
305       }
306     else
307       return null;
308   }
309 
310   protected Object   wrapReference (Object   key)
311   {
312     /* #ifdef JAVA2 */
313     return key == null || key instanceof Symbol ? key : new WeakReference  (key);
314     /* #else */
315     // return key;
316     /* #endif */
317   }
318 
319   /*
320   Head getHead (Object key, boolean isDim2, int hash)
321   {
322     int index = hash & mask;
323     // FIXME: clear reference queue
324     Entry first = table[index];
325     for (Entry e = first;  e != null;  e = e.chain)
326       {
327         if (e.hash != hash || ! (e instanceof Head))
328           continue;
329         Head h = (Head) e;
330         if (h.ref.ref() == key)
331           return h;
332       }
333     Head h = new Head();
334     h.hash = hash;
335     if (isDim2)
336       h.next2 = h;
337     else
338       h.next1 = h;
339     h.chain = first;
340     table[index] = h;
341     h.ref = new WeakReference(key);
342     return h;
343   }
344   */
345 }
346 
347 class Entry
348 {
349   //int hash;
350   ///** Next in circular list with same key1. */
351   //Entry next1;
352   ///** Next in circular list with same key2. */
353   //Entry next2;
354   /** Next in list in same hash bucket. */
355   Entry chain;
356 
357   /** Value, if nound.  Point to self if unbound. */
358   Object   value;
359 
360   Object   key1, key2;
361 
362   public Object   getKey1 ()
363   {
364     /* #ifdef JAVA2 */
365     if (key1 instanceof WeakReference  )
366       return ((WeakReference  ) key1).get();
367     /* #endif */
368     return key1;
369   }
370 
371   public Object   getKey2 ()
372   {
373     /* #ifdef JAVA2 */
374     if (key2 instanceof WeakReference  )
375       return ((WeakReference  ) key2).get();
376     /* #endif */
377     return key2;
378   }
379 
380   public boolean matches (Object   key1, Object   key2)
381   {
382     return key1 == getKey1() && key2 == getKey2();
383   }
384 
385   public Object   getValue() { return value == this ? null : value; }
386 }
387 
388   /*
389 class Head extends Entry
390 {
391   WeakRefeference ref;
392 
393   public LList make List ()
394   {
395     LList list = LList.Empty;
396     for (Entry e = next1;// FIXME or next2
397          e != null;
398          e = e.next1 // FIXME or next2
399            )
400       {
401         list = new Car (e.getKey1(),//FIXME
402                           new Car (e.value, list));
403       }
404     return list;
405   }
406 }
407 */
408
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags