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