bundles/org.simantics.scl.compiler/src/org/cojen/util/ReferencedValueHashMap.java

   1 /*
   2  *  Copyright 2006-2010 Brian S O'Neill
   3  *
   4  *  Licensed under the Apache License, Version 2.0 (the "License");
   5  *  you may not use this file except in compliance with the License.
   6  *  You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  *  Unless required by applicable law or agreed to in writing, software
  11  *  distributed under the License is distributed on an "AS IS" BASIS,
  12  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  *  See the License for the specific language governing permissions and
  14  *  limitations under the License.
  15  */
  16
  17 package org.cojen.util;
  18
  19 import java.lang.ref.Reference;
  20 import java.util.AbstractCollection;
  21 import java.util.AbstractMap;
  22 import java.util.AbstractSet;
  23 import java.util.Collection;
  24 import java.util.Collections;
  25 import java.util.ConcurrentModificationException;
  26 import java.util.Iterator;
  27 import java.util.Map;
  28 import java.util.NoSuchElementException;
  29 import java.util.Set;
  30
  31 /**
  32  * A Map that references its values and can be used as a simple cache.
  33  * Instances are not thread-safe and must be wrapped with
  34  * Collections.synchronizedMap to be made thread-safe.
  35  * <p>
  36  * Note: Referenced entries may be automatically removed during
  37  * either accessor or mutator operations, possibly causing a concurrent
  38  * modification to be detected. Therefore, even if multiple threads are only
  39  * accessing this map, be sure to synchronize this map first. Also, do not
  40  * rely on the value returned by size() when using an iterator from this map.
  41  * The iterators may return less entries than the amount reported by size().
  42  *
  43  * @author Brian S O'Neill
  44  */
  45 @SuppressWarnings({ "rawtypes", "unused", "unchecked" })
  46 public abstract class ReferencedValueHashMap<K, V> extends AbstractMap<K, V>
  47     implements Map<K, V>, Cloneable
  48 {
  49     private transient Entry<K, V>[] table;
  50     private transient int count;
  51     private int threshold;
  52     private final float loadFactor;
  53     private transient volatile int modCount;
  54
  55     // Views
  56
  57     private transient Set<K> keySet;
  58     private transient Set<Map.Entry<K, V>> entrySet;
  59     private transient Collection<V> values;
  60
  61     /**
  62      * Constructs a new, empty map with the specified initial
  63      * capacity and the specified load factor.
  64      *
  65      * @param      initialCapacity   the initial capacity of the HashMap.
  66      * @param      loadFactor        the load factor of the HashMap
  67      * @throws     IllegalArgumentException  if the initial capacity is less
  68      *               than zero, or if the load factor is nonpositive.
  69      */
  70     public ReferencedValueHashMap(int initialCapacity, float loadFactor) {
  71         if (initialCapacity < 0) {
  72             throw new IllegalArgumentException("Illegal Initial Capacity: "+
  73                                                initialCapacity);
  74         }
  75
  76         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
  77             throw new IllegalArgumentException("Illegal Load factor: "+
  78                                                loadFactor);
  79         }
  80
  81         if (initialCapacity == 0) {
  82             initialCapacity = 1;
  83         }
  84
  85         this.loadFactor = loadFactor;
  86         this.table = new Entry[initialCapacity];
  87         this.threshold = (int)(initialCapacity * loadFactor);
  88     }
  89
  90     /**
  91      * Constructs a new, empty map with the specified initial capacity
  92      * and default load factor, which is <tt>0.75</tt>.
  93      *
  94      * @param   initialCapacity   the initial capacity of the HashMap.
  95      * @throws    IllegalArgumentException if the initial capacity is less
  96      *              than zero.
  97      */
  98     public ReferencedValueHashMap(int initialCapacity) {
  99         this(initialCapacity, 0.75f);
 100     }
 101
 102     /**
 103      * Constructs a new, empty map with a default capacity and load
 104      * factor, which is <tt>0.75</tt>.
 105      */
 106     public ReferencedValueHashMap() {
 107         this(11, 0.75f);
 108     }
 109
 110     /**
 111      * Constructs a new map with the same mappings as the given map.  The
 112      * map is created with a capacity of twice the number of mappings in
 113      * the given map or 11 (whichever is greater), and a default load factor,
 114      * which is <tt>0.75</tt>.
 115      */
 116     public ReferencedValueHashMap(Map<? extends K, ? extends V> t) {
 117         this(Math.max(2 * t.size(), 11), 0.75f);
 118         putAll(t);
 119     }
 120
 121     public int size() {
 122         return this.count;
 123     }
 124
 125     public boolean isEmpty() {
 126         return this.count == 0;
 127     }
 128
 129     public boolean containsValue(Object value) {
 130         if (value == null) {
 131             value = KeyFactory.NULL;
 132         }
 133
 134         Entry[] tab = this.table;
 135
 136         for (int i = tab.length ; i-- > 0 ;) {
 137             for (Entry e = tab[i], prev = null; e != null; e = e.next) {
 138                 Object entryValue = e.get();
 139
 140                 if (entryValue == null) {
 141                     // Clean up after a cleared Reference.
 142                     this.modCount++;
 143                     if (prev != null) {
 144                         prev.next = e.next;
 145                     } else {
 146                         tab[i] = e.next;
 147                     }
 148                     this.count--;
 149                 } else if (value.equals(entryValue)) {
 150                     return true;
 151                 } else {
 152                     prev = e;
 153                 }
 154             }
 155         }
 156
 157         return false;
 158     }
 159
 160     public boolean containsKey(Object key) {
 161         Entry<K, V>[] tab = this.table;
 162
 163         if (key != null) {
 164             int hash = key.hashCode();
 165             int index = (hash & 0x7fffffff) % tab.length;
 166             for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
 167                 if (e.get() == null) {
 168                     // Clean up after a cleared Reference.
 169                     this.modCount++;
 170                     if (prev != null) {
 171                         prev.next = e.next;
 172                     } else {
 173                         tab[index] = e.next;
 174                     }
 175                     this.count--;
 176                 } else if (e.hash == hash && key.equals(e.key)) {
 177                     return true;
 178                 } else {
 179                     prev = e;
 180                 }
 181             }
 182         } else {
 183             for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
 184                 if (e.get() == null) {
 185                     // Clean up after a cleared Reference.
 186                     this.modCount++;
 187                     if (prev != null) {
 188                         prev.next = e.next;
 189                     } else {
 190                         tab[0] = e.next;
 191                     }
 192                     this.count--;
 193                 } else if (e.key == null) {
 194                     return true;
 195                 } else {
 196                     prev = e;
 197                 }
 198             }
 199         }
 200
 201         return false;
 202     }
 203
 204     public V get(Object key) {
 205         Entry<K, V>[] tab = this.table;
 206
 207         if (key != null) {
 208             int hash = key.hashCode();
 209             int index = (hash & 0x7fffffff) % tab.length;
 210
 211             for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
 212                 V entryValue = e.get();
 213
 214                 if (entryValue == null) {
 215                     // Clean up after a cleared Reference.
 216                     this.modCount++;
 217                     if (prev != null) {
 218                         prev.next = e.next;
 219                     } else {
 220                         tab[index] = e.next;
 221                     }
 222                     count--;
 223                 } else if (e.hash == hash && key.equals(e.key)) {
 224                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
 225                 } else {
 226                     prev = e;
 227                 }
 228             }
 229         } else {
 230             for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
 231                 V entryValue = e.get();
 232
 233                 if (entryValue == null) {
 234                     // Clean up after a cleared Reference.
 235                     this.modCount++;
 236                     if (prev != null) {
 237                         prev.next = e.next;
 238                     }
 239                     else {
 240                         tab[0] = e.next;
 241                     }
 242                     this.count--;
 243                 } else if (e.key == null) {
 244                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
 245                 } else {
 246                     prev = e;
 247                 }
 248             }
 249         }
 250
 251         return null;
 252     }
 253
 254     /**
 255      * Scans the contents of this map, removing all entries that have a
 256      * cleared soft value.
 257      */
 258     private void cleanup() {
 259         Entry<K, V>[] tab = this.table;
 260
 261         for (int i = tab.length ; i-- > 0 ;) {
 262             for (Entry<K, V> e = tab[i], prev = null; e != null; e = e.next) {
 263                 if (e.get() == null) {
 264                     // Clean up after a cleared Reference.
 265                     this.modCount++;
 266                     if (prev != null) {
 267                         prev.next = e.next;
 268                     } else {
 269                         tab[i] = e.next;
 270                     }
 271                     this.count--;
 272                 } else {
 273                     prev = e;
 274                 }
 275             }
 276         }
 277     }
 278
 279     /**
 280      * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
 281      * with a larger capacity. This method is called automatically when the
 282      * number of keys in this map exceeds its capacity and load factor.
 283      */
 284     private void rehash() {
 285         int oldCapacity = this.table.length;
 286         Entry<K, V>[] oldMap = this.table;
 287
 288         int newCapacity = oldCapacity * 2 + 1;
 289         Entry<K, V>[] newMap = new Entry[newCapacity];
 290
 291         this.modCount++;
 292         this.threshold = (int)(newCapacity * this.loadFactor);
 293         this.table = newMap;
 294
 295         for (int i = oldCapacity ; i-- > 0 ;) {
 296             for (Entry<K, V> old = oldMap[i] ; old != null ; ) {
 297                 Entry<K, V> e = old;
 298                 old = old.next;
 299
 300                 // Only copy entry if its value hasn't been cleared.
 301                 if (e.get() == null) {
 302                     this.count--;
 303                 } else {
 304                     int index = (e.hash & 0x7fffffff) % newCapacity;
 305                     e.next = newMap[index];
 306                     newMap[index] = e;
 307                 }
 308             }
 309         }
 310     }
 311
 312     public V put(K key, V value) {
 313         if (value == null) {
 314             value = (V) KeyFactory.NULL;
 315         }
 316
 317         // Makes sure the key is not already in the HashMap.
 318         Entry<K, V>[] tab = this.table;
 319         int hash;
 320         int index;
 321
 322         if (key != null) {
 323             hash = key.hashCode();
 324             index = (hash & 0x7fffffff) % tab.length;
 325             for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
 326                 V entryValue = e.get();
 327
 328                 if (entryValue == null) {
 329                     // Clean up after a cleared Reference.
 330                     this.modCount++;
 331                     if (prev != null) {
 332                         prev.next = e.next;
 333                     } else {
 334                         tab[index] = e.next;
 335                     }
 336                     this.count--;
 337                 } else if (e.hash == hash && key.equals(e.key)) {
 338                     e.setValue(value);
 339                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
 340                 } else {
 341                     prev = e;
 342                 }
 343             }
 344         } else {
 345             hash = 0;
 346             index = 0;
 347             for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
 348                 V entryValue = e.get();
 349
 350                 if (entryValue == null) {
 351                     // Clean up after a cleared Reference.
 352                     this.modCount++;
 353                     if (prev != null) {
 354                         prev.next = e.next;
 355                     } else {
 356                         tab[0] = e.next;
 357                     }
 358                     this.count--;
 359                 } else if (e.key == null) {
 360                     e.setValue(value);
 361                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
 362                 } else {
 363                     prev = e;
 364                 }
 365             }
 366         }
 367
 368         this.modCount++;
 369
 370         if (this.count >= this.threshold) {
 371             // Cleanup the table if the threshold is exceeded.
 372             cleanup();
 373         }
 374
 375         if (this.count >= this.threshold) {
 376             // Rehash the table if the threshold is still exceeded.
 377             rehash();
 378             tab = this.table;
 379             index = (hash & 0x7fffffff) % tab.length;
 380         }
 381
 382         // Creates the new entry.
 383         Entry<K, V> e = newEntry(hash, key, (V)value, tab[index]);
 384         tab[index] = e;
 385         this.count++;
 386         return null;
 387     }
 388
 389     public V remove(Object key) {
 390         Entry<K, V>[] tab = this.table;
 391
 392         if (key != null) {
 393             int hash = key.hashCode();
 394             int index = (hash & 0x7fffffff) % tab.length;
 395
 396             for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
 397                 V entryValue = e.get();
 398
 399                 if (entryValue == null) {
 400                     // Clean up after a cleared Reference.
 401                     this.modCount++;
 402                     if (prev != null) {
 403                         prev.next = e.next;
 404                     } else {
 405                         tab[index] = e.next;
 406                     }
 407                     this.count--;
 408                 } else if (e.hash == hash && key.equals(e.key)) {
 409                     this.modCount++;
 410                     if (prev != null) {
 411                         prev.next = e.next;
 412                     } else {
 413                         tab[index] = e.next;
 414                     }
 415                     this.count--;
 416
 417                     e.setValue(null);
 418                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
 419                 } else {
 420                     prev = e;
 421                 }
 422             }
 423         } else {
 424             for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
 425                 V entryValue = e.get();
 426
 427                 if (entryValue == null) {
 428                     // Clean up after a cleared Reference.
 429                     this.modCount++;
 430                     if (prev != null) {
 431                         prev.next = e.next;
 432                     } else {
 433                         tab[0] = e.next;
 434                     }
 435                     this.count--;
 436                 } else if (e.key == null) {
 437                     this.modCount++;
 438                     if (prev != null) {
 439                         prev.next = e.next;
 440                     } else {
 441                         tab[0] = e.next;
 442                     }
 443                     this.count--;
 444
 445                     e.setValue(null);
 446                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
 447                 } else {
 448                     prev = e;
 449                 }
 450             }
 451         }
 452
 453         return null;
 454     }
 455
 456     public void putAll(Map<? extends K, ? extends V> t) {
 457         Iterator i = t.entrySet().iterator();
 458         while (i.hasNext()) {
 459             Map.Entry<K, V> e = (Map.Entry<K, V>) i.next();
 460             put(e.getKey(), e.getValue());
 461         }
 462     }
 463
 464     public void clear() {
 465         Entry[] tab = this.table;
 466         this.modCount++;
 467         for (int index = tab.length; --index >= 0; ) {
 468             tab[index] = null;
 469         }
 470         this.count = 0;
 471     }
 472
 473     public Object clone() {
 474         try {
 475             ReferencedValueHashMap t = (ReferencedValueHashMap)super.clone();
 476             t.table = new Entry[this.table.length];
 477             for (int i = this.table.length ; i-- > 0 ; ) {
 478                 t.table[i] = (this.table[i] != null)
 479                     ? (Entry)this.table[i].clone() : null;
 480             }
 481             t.keySet = null;
 482             t.entrySet = null;
 483             t.values = null;
 484             t.modCount = 0;
 485             return t;
 486         } catch (CloneNotSupportedException e) {
 487             // this shouldn't happen, since we are Cloneable
 488             throw new InternalError();
 489         }
 490     }
 491
 492     public Set<K> keySet() {
 493         if (this.keySet == null) {
 494             this.keySet = new AbstractSet<K>() {
 495                 public Iterator iterator() {
 496                     return createHashIterator(WeakIdentityMap.KEYS);
 497                 }
 498                 public int size() {
 499                     return ReferencedValueHashMap.this.count;
 500                 }
 501                 public boolean contains(Object o) {
 502                     return containsKey(o);
 503                 }
 504                 public boolean remove(Object o) {
 505                     if (o == null) {
 506                         if (ReferencedValueHashMap.this.containsKey(null)) {
 507                             ReferencedValueHashMap.this.remove(null);
 508                             return true;
 509                         } else {
 510                             return false;
 511                         }
 512                     } else {
 513                         return ReferencedValueHashMap.this.remove(o) != null;
 514                     }
 515                 }
 516                 public void clear() {
 517                     ReferencedValueHashMap.this.clear();
 518                 }
 519                 public String toString() {
 520                     return WeakIdentityMap.toString(this);
 521                 }
 522             };
 523         }
 524         return this.keySet;
 525     }
 526
 527     public Collection<V> values() {
 528         if (this.values==null) {
 529             this.values = new AbstractCollection<V>() {
 530                 public Iterator iterator() {
 531                     return createHashIterator(WeakIdentityMap.VALUES);
 532                 }
 533                 public int size() {
 534                     return ReferencedValueHashMap.this.count;
 535                 }
 536                 public boolean contains(Object o) {
 537                     return containsValue(o);
 538                 }
 539                 public void clear() {
 540                     ReferencedValueHashMap.this.clear();
 541                 }
 542                 public String toString() {
 543                     return WeakIdentityMap.toString(this);
 544                 }
 545             };
 546         }
 547         return this.values;
 548     }
 549
 550     public Set<Map.Entry<K, V>> entrySet() {
 551         if (this.entrySet==null) {
 552             this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
 553                 public Iterator iterator() {
 554                     return createHashIterator(WeakIdentityMap.ENTRIES);
 555                 }
 556
 557                 public boolean contains(Object o) {
 558                     if (!(o instanceof Map.Entry)) {
 559                         return false;
 560                     }
 561                     Map.Entry entry = (Map.Entry)o;
 562                     Object key = entry.getKey();
 563
 564                     Entry[] tab = ReferencedValueHashMap.this.table;
 565                     int hash = key == null ? 0 : key.hashCode();
 566                     int index = (hash & 0x7fffffff) % tab.length;
 567
 568                     for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 569                         Object entryValue = e.get();
 570
 571                         if (entryValue == null) {
 572                             // Clean up after a cleared Reference.
 573                             ReferencedValueHashMap.this.modCount++;
 574                             if (prev != null) {
 575                                 prev.next = e.next;
 576                             } else {
 577                                 tab[index] = e.next;
 578                             }
 579                             ReferencedValueHashMap.this.count--;
 580                         } else if (e.hash == hash && e.equals(entry)) {
 581                             return true;
 582                         } else {
 583                             prev = e;
 584                         }
 585                     }
 586
 587                     return false;
 588                 }
 589
 590                 public boolean remove(Object o) {
 591                     if (!(o instanceof Map.Entry)) {
 592                         return false;
 593                     }
 594                     Map.Entry entry = (Map.Entry)o;
 595                     Object key = entry.getKey();
 596                     Entry[] tab = ReferencedValueHashMap.this.table;
 597                     int hash = key == null ? 0 : key.hashCode();
 598                     int index = (hash & 0x7fffffff) % tab.length;
 599
 600                     for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 601                         Object entryValue = e.get();
 602
 603                         if (entryValue == null) {
 604                             // Clean up after a cleared Reference.
 605                             ReferencedValueHashMap.this.modCount++;
 606                             if (prev != null) {
 607                                 prev.next = e.next;
 608                             } else {
 609                                 tab[index] = e.next;
 610                             }
 611                             ReferencedValueHashMap.this.count--;
 612                         } else if (e.hash == hash && e.equals(entry)) {
 613                             ReferencedValueHashMap.this.modCount++;
 614                             if (prev != null) {
 615                                 prev.next = e.next;
 616                             } else {
 617                                 tab[index] = e.next;
 618                             }
 619                             ReferencedValueHashMap.this.count--;
 620
 621                             e.setValue(null);
 622                             return true;
 623                         } else {
 624                             prev = e;
 625                         }
 626                     }
 627                     return false;
 628                 }
 629
 630                 public int size() {
 631                     return ReferencedValueHashMap.this.count;
 632                 }
 633
 634                 public void clear() {
 635                     ReferencedValueHashMap.this.clear();
 636                 }
 637
 638                 public String toString() {
 639                     return WeakIdentityMap.toString(this);
 640                 }
 641             };
 642         }
 643
 644         return this.entrySet;
 645     }
 646
 647     public String toString() {
 648         // Cleanup stale entries first, so as not to allocate a larger than
 649         // necessary StringBuffer.
 650         cleanup();
 651         return WeakIdentityMap.toString(this);
 652     }
 653
 654     abstract Entry<K, V> newEntry(int hash, K key, V value, Entry<K, V> next);
 655
 656     private Iterator createHashIterator(int type) {
 657         if (this.count == 0) {
 658             return Collections.EMPTY_SET.iterator();
 659         } else {
 660             return new HashIterator(type);
 661         }
 662     }
 663
 664     /**
 665      * Collision list entry.
 666      */
 667     abstract static class Entry<K, V> implements Map.Entry<K, V> {
 668         int hash;
 669         K key;
 670         Entry<K, V> next;
 671
 672         private Reference<V> value;
 673
 674         Entry(int hash, K key, V value, Entry<K, V> next) {
 675             this.hash = hash;
 676             this.key = key;
 677             this.value = newReference(value);
 678             this.next = next;
 679         }
 680
 681         Entry(int hash, K key, Reference<V> value, Entry<K, V> next) {
 682             this.hash = hash;
 683             this.key = key;
 684             this.value = value;
 685             this.next = next;
 686         }
 687
 688         // Map.Entry Ops
 689
 690         public K getKey() {
 691             return this.key;
 692         }
 693
 694         public V getValue() {
 695             V value = this.value.get();
 696             return value == KeyFactory.NULL ? null : value;
 697         }
 698
 699         public V setValue(V value) {
 700             V oldValue = getValue();
 701             this.value = newReference(value == null ? ((V) KeyFactory.NULL) : value);
 702             return oldValue;
 703         }
 704
 705         public boolean equals(Object obj) {
 706             if (!(obj instanceof Map.Entry)) {
 707                 return false;
 708             }
 709             return equals((Map.Entry)obj);
 710         }
 711
 712         boolean equals(Map.Entry e) {
 713             Object thisValue = get();
 714             if (thisValue == null) {
 715                 return false;
 716             } else if (thisValue == KeyFactory.NULL) {
 717                 thisValue = null;
 718             }
 719             return (this.key == null ? e.getKey() == null : this.key.equals(e.getKey())) &&
 720                 (thisValue == null ? e.getValue() == null : thisValue.equals(e.getValue()));
 721         }
 722
 723         public int hashCode() {
 724             return this.hash ^ get().hashCode();
 725         }
 726
 727         public String toString() {
 728             return this.key + "=" + getValue();
 729         }
 730
 731         protected Object clone() {
 732             return newEntry(this.hash, this.key, (Reference)this.value,
 733                             (this.next == null ? null : (Entry)this.next.clone()));
 734         }
 735
 736         abstract Entry newEntry(int hash, K key, Reference<V> value, Entry<K, V> next);
 737
 738         abstract Reference<V> newReference(V value);
 739
 740         // Like getValue(), except does not convert NULL to null.
 741         V get() {
 742             return this.value.get();
 743         }
 744     }
 745
 746     private class HashIterator implements Iterator {
 747         private final int type;
 748         private final Entry[] table;
 749
 750         private int index;
 751
 752         // To ensure that the iterator doesn't return cleared entries, keep a
 753         // hard reference to the value. Its existence will prevent the soft
 754         // value from being cleared.
 755         private Object entryValue;
 756         private Entry entry;
 757
 758         private Entry last;
 759
 760         /**
 761          * The modCount value that the iterator believes that the backing
 762          * List should have.  If this expectation is violated, the iterator
 763          * has detected concurrent modification.
 764          */
 765         private int expectedModCount = ReferencedValueHashMap.this.modCount;
 766
 767         HashIterator(int type) {
 768             this.table = ReferencedValueHashMap.this.table;
 769             this.type = type;
 770             this.index = table.length;
 771         }
 772
 773         public boolean hasNext() {
 774             while (this.entry == null || (this.entryValue = this.entry.get()) == null) {
 775                 if (this.entry != null) {
 776                     // Clean up after a cleared Reference.
 777                     remove(this.entry);
 778                     this.entry = this.entry.next;
 779                 }
 780
 781                 if (this.entry == null) {
 782                     if (this.index <= 0) {
 783                         return false;
 784                     } else {
 785                         this.entry = this.table[--this.index];
 786                     }
 787                 }
 788             }
 789
 790             return true;
 791         }
 792
 793         public Object next() {
 794             if (ReferencedValueHashMap.this.modCount != expectedModCount) {
 795                 throw new ConcurrentModificationException();
 796             }
 797
 798             if (!hasNext()) {
 799                 throw new NoSuchElementException();
 800             }
 801
 802             this.last = this.entry;
 803             this.entry = this.entry.next;
 804
 805             return this.type == WeakIdentityMap.KEYS ? this.last.getKey() :
 806                 (this.type == WeakIdentityMap.VALUES ? this.last.getValue() : this.last);
 807         }
 808
 809         public void remove() {
 810             if (this.last == null) {
 811                 throw new IllegalStateException();
 812             }
 813             if (ReferencedValueHashMap.this.modCount != expectedModCount) {
 814                 throw new ConcurrentModificationException();
 815             }
 816             remove(this.last);
 817             this.last = null;
 818         }
 819
 820         private void remove(Entry toRemove) {
 821             Entry[] tab = this.table;
 822             int index = (toRemove.hash & 0x7fffffff) % tab.length;
 823
 824             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
 825                 if (e == toRemove) {
 826                     ReferencedValueHashMap.this.modCount++;
 827                     expectedModCount++;
 828                     if (prev == null) {
 829                         tab[index] = e.next;
 830                     } else {
 831                         prev.next = e.next;
 832                     }
 833                     ReferencedValueHashMap.this.count--;
 834                     return;
 835                 } else {
 836                     prev = e;
 837                 }
 838             }
 839             throw new ConcurrentModificationException();
 840         }
 841     }
 842 }