libjava/java/util/IdentityHashMap.java

   1 /* IdentityHashMap.java -- a class providing a hashtable data structure,
   2    mapping Object --> Object, which uses object identity for hashing.
   3    Copyright (C) 2001 Free Software Foundation, Inc.
   4
   5 This file is part of GNU Classpath.
   6
   7 GNU Classpath is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU Classpath is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU Classpath; see the file COPYING.  If not, write to the
  19 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  20 02111-1307 USA.
  21
  22 As a special exception, if you link this library with other files to
  23 produce an executable, this library does not by itself cause the
  24 resulting executable to be covered by the GNU General Public License.
  25 This exception does not however invalidate any other reasons why the
  26 executable file might be covered by the GNU General Public License. */
  27
  28 package java.util;
  29
  30 import java.io.*;
  31
  32 /**
  33  * This class provides a hashtable-backed implementation of the
  34  * Map interface.  Unlike HashMap, it uses object identity to
  35  * do its hashing.  Also, it uses a linear-probe hash table.
  36  *
  37  * @author Tom Tromey <tromey@redhat.com>
  38  * @since 1.4
  39  */
  40 public class IdentityHashMap extends AbstractMap
  41   implements Map, Serializable, Cloneable
  42 {
  43   private static final int DEFAULT_CAPACITY = 21;
  44
  45   /** Create a new IdentityHashMap with the default capacity (21
  46    * entries).
  47    */
  48   public IdentityHashMap ()
  49   {
  50     this (DEFAULT_CAPACITY);
  51   }
  52
  53   /** Create a new IdentityHashMap with the indicated number of
  54    * entries.  If the number of elements added to this hash map
  55    * exceeds this maximum, the map will grow itself; however, that
  56    * incurs a performance penalty.
  57    * @param max Initial size
  58    */
  59   public IdentityHashMap (int max)
  60   {
  61     if (max < 0)
  62       throw new IllegalArgumentException ();
  63     table = new Object[2 * max];
  64     Arrays.fill (table, emptyslot);
  65     size = 0;
  66   }
  67
  68   /** Create a new IdentityHashMap whose contents are taken from the
  69    * given Map.
  70    * @param m The map whose elements are to be put in this map.
  71    */
  72   public IdentityHashMap (Map m)
  73   {
  74     int len = 2 * Math.max (m.size (), DEFAULT_CAPACITY);
  75     table = new Object[len];
  76     Arrays.fill (table, emptyslot);
  77     putAll (m);
  78   }
  79
  80   public void clear ()
  81   {
  82     Arrays.fill (table, emptyslot);
  83     size = 0;
  84   }
  85
  86   /**
  87    * Creates a shallow copy where keys and values are not cloned.
  88    */
  89   public Object clone ()
  90   {
  91     try
  92       {
  93         IdentityHashMap copy = (IdentityHashMap) super.clone ();
  94         copy.table = (Object[]) table.clone ();
  95         return copy;
  96       }
  97     catch (CloneNotSupportedException e)
  98       {
  99         // Can't happen.
 100         return null;
 101       }
 102   }
 103
 104   public boolean containsKey (Object key)
 105   {
 106     int h = Math.abs (2 * System.identityHashCode (key) % table.length);
 107     int save = h;
 108     while (true)
 109       {
 110         if (table[h] == key)
 111           return true;
 112         if (table[h] == emptyslot)
 113           return false;
 114         h += 2;
 115         if (h > table.length)
 116           h = 0;
 117         if (h == save)
 118           return false;
 119       }
 120   }
 121
 122   public boolean containsValue (Object value)
 123   {
 124     for (int i = 1; i < table.length; i += 2)
 125       if (table[i] == value)
 126         return true;
 127     return false;
 128   }
 129
 130   public Set entrySet ()
 131   {
 132     return new AbstractSet ()
 133     {
 134       public int size ()
 135       {
 136         return size;
 137       }
 138
 139       public Iterator iterator ()
 140       {
 141         return new IdentityIterator (IdentityIterator.ENTRIES);
 142       }
 143
 144       public void clear ()
 145       {
 146         IdentityHashMap.this.clear ();
 147       }
 148
 149       public boolean contains (Object o)
 150       {
 151         if (! (o instanceof Map.Entry))
 152           return false;
 153         Map.Entry m = (Map.Entry) o;
 154         return (IdentityHashMap.this.containsKey (m.getKey ())
 155                 && IdentityHashMap.this.get (m.getKey ()) == m.getValue ());
 156       }
 157
 158       public boolean remove (Object o)
 159       {
 160         if (! (o instanceof Map.Entry))
 161           return false;
 162         Map.Entry m = (Map.Entry) o;
 163         if (IdentityHashMap.this.containsKey (m.getKey ())
 164             && IdentityHashMap.this.get (m.getKey ()) == m.getValue ())
 165           {
 166             int oldsize = size;
 167             IdentityHashMap.this.remove (m.getKey ());
 168             return oldsize != size;
 169           }
 170         return false;
 171       }
 172     };
 173   }
 174
 175   public Object get (Object key)
 176   {
 177     int h = Math.abs (2 * System.identityHashCode (key) % table.length);
 178     int save = h;
 179     while (true)
 180       {
 181         if (table[h] == key)
 182           return table[h + 1];
 183         if (table[h] == emptyslot)
 184           return null;
 185         h += 2;
 186         if (h >= table.length)
 187           h = 0;
 188         if (h == save)
 189           return null;
 190       }
 191   }
 192
 193   public boolean isEmpty ()
 194   {
 195     return size == 0;
 196   }
 197
 198   public Set keySet ()
 199   {
 200     return new AbstractSet ()
 201     {
 202       public int size ()
 203       {
 204         return size;
 205       }
 206
 207       public Iterator iterator ()
 208       {
 209         return new IdentityIterator (IdentityIterator.KEYS);
 210       }
 211
 212       public void clear ()
 213       {
 214         IdentityHashMap.this.clear ();
 215       }
 216
 217       public boolean contains (Object o)
 218       {
 219         return IdentityHashMap.this.containsKey (o);
 220       }
 221
 222       public boolean remove (Object o)
 223       {
 224         int oldsize = size;
 225         IdentityHashMap.this.remove (o);
 226         return oldsize != size;
 227       }
 228     };
 229   }
 230
 231   public Object put (Object key, Object value)
 232   {
 233     // Rehash is the load factor is too high.
 234     if (size * 3 / 2 > table.length)
 235       {
 236         Object[] old = table;
 237         table = new Object[old.length * 2];
 238         Arrays.fill (table, emptyslot);
 239         size = 0;
 240         for (int i = 0; i < old.length; ++i)
 241           {
 242             if (old[i] != tombstone && old[i] != emptyslot)
 243               {
 244                 // Just use put.  This isn't very efficient, but it is
 245                 // ok.
 246                 put (old[i], old[i + 1]);
 247               }
 248           }
 249       }
 250
 251     int h = Math.abs (2 * System.identityHashCode (key) % table.length);
 252     int save = h;
 253     int del = -1;
 254     while (true)
 255       {
 256         if (table[h] == key)
 257           {
 258             Object r = table[h + 1];
 259             table[h + 1] = value;
 260             return r;
 261           }
 262         else if (table[h] == tombstone && del == -1)
 263           del = h;
 264         else if (table[h] == emptyslot)
 265           {
 266             if (del == -1)
 267               del = h;
 268             break;
 269           }
 270         h += 2;
 271         if (h >= table.length)
 272           h = 0;
 273         if (h == save)
 274           break;
 275       }
 276
 277     if (del != -1)
 278       {
 279         table[del] = key;
 280         table[del + 1] = value;
 281         ++size;
 282         return null;
 283       }
 284
 285     // This is an error.
 286     return null;
 287   }
 288
 289   public Object remove (Object key)
 290   {
 291     int h = Math.abs (2 * System.identityHashCode (key) % table.length);
 292     int save = h;
 293     while (true)
 294       {
 295         if (table[h] == key)
 296           {
 297             Object r = table[h + 1];
 298             table[h] = tombstone;
 299             table[h + 1] = tombstone;
 300             --size;
 301             return r;
 302           }
 303         h += 2;
 304         if (h > table.length)
 305           h = 0;
 306         if (h == save)
 307           break;
 308       }
 309
 310     return null;
 311   }
 312
 313   public int size ()
 314   {
 315     return size;
 316   }
 317
 318   public Collection values ()
 319   {
 320     return new AbstractCollection ()
 321     {
 322       public int size ()
 323       {
 324         return size;
 325       }
 326
 327       public Iterator iterator ()
 328       {
 329         return new IdentityIterator (IdentityIterator.VALUES);
 330       }
 331
 332       public void clear ()
 333       {
 334         IdentityHashMap.this.clear ();
 335       }
 336     };
 337   }
 338
 339   private class IdentityIterator implements Iterator
 340   {
 341     static final int KEYS = 0;
 342     static final int VALUES = 1;
 343     static final int ENTRIES = 2;
 344
 345     // Type of iterator.
 346     int type;
 347     // Location in the table.
 348     int loc;
 349     // How many items we've seen.
 350     int seen;
 351
 352     IdentityIterator (int type)
 353     {
 354       this.type = type;
 355       loc = 0;
 356       seen = 0;
 357     }
 358
 359     public boolean hasNext ()
 360     {
 361       return seen < size;
 362     }
 363
 364     public Object next ()
 365     {
 366       while (true)
 367         {
 368           loc += 2;
 369           if (loc >= table.length)
 370             throw new NoSuchElementException ();
 371           if (table[loc] != tombstone && table[loc] != emptyslot)
 372             {
 373               ++seen;
 374               return table[loc];
 375             }
 376         }
 377     }
 378
 379     public void remove ()
 380     {
 381       if (loc >= table.length
 382           || table[loc] == tombstone
 383           || table[loc] == emptyslot)
 384         throw new IllegalStateException ();
 385       table[loc] = tombstone;
 386       table[loc + 1] = tombstone;
 387       --size;
 388     }
 389   }
 390
 391   private void readObject (ObjectInputStream s)
 392     throws IOException, ClassNotFoundException
 393   {
 394     int num = s.readInt ();
 395     for (int i = 0; i < num; ++i)
 396       {
 397         Object key = s.readObject ();
 398         Object value = s.readObject ();
 399         put (key, value);
 400       }
 401   }
 402
 403   private void writeObject (ObjectOutputStream s)
 404     throws IOException
 405   {
 406     s.writeInt (size);
 407     Iterator it = entrySet ().iterator ();
 408     while (it.hasNext ())
 409       {
 410         Map.Entry entry = (Map.Entry) it.next ();
 411         s.writeObject (entry.getKey ());
 412         s.writeObject (entry.getValue ());
 413       }
 414   }
 415
 416   // Number of items in hash table.
 417   private int size;
 418   // The table itself.
 419   private Object[] table;
 420
 421   // This object is used to mark deleted items.
 422   private Object tombstone = new Object ();
 423   // This object is used to mark empty slots.  We need this because
 424   // using null is ambiguous.
 425   private Object emptyslot = new Object ();
 426 }