001 package railo.commons.collections; 002 003 import java.io.IOException; 004 import java.util.AbstractCollection; 005 import java.util.AbstractSet; 006 import java.util.Collection; 007 import java.util.ConcurrentModificationException; 008 import java.util.Dictionary; 009 import java.util.Enumeration; 010 import java.util.Iterator; 011 import java.util.Map; 012 import java.util.NoSuchElementException; 013 import java.util.Set; 014 015 /** 016 * This class implements a hashtable, which maps keys to values. Any 017 * non-<code>null</code> object can be used as a key or as a value. <p> 018 * 019 * To successfully store and retrieve objects from a hashtable, the 020 * objects used as keys must implement the <code>hashCode</code> 021 * method and the <code>equals</code> method. <p> 022 * 023 * An instance of <code>Hashtable</code> has two parameters that affect its 024 * performance: <i>initial capacity</i> and <i>load factor</i>. The 025 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the 026 * <i>initial capacity</i> is simply the capacity at the time the hash table 027 * is created. Note that the hash table is <i>open</i>: in the case a "hash 028 * collision", a single bucket stores multiple entries, which must be searched 029 * sequentially. The <i>load factor</i> is a measure of how full the hash 030 * table is allowed to get before its capacity is automatically increased. 031 * When the number of entries in the hashtable exceeds the product of the load 032 * factor and the current capacity, the capacity is increased by calling the 033 * <code>rehash</code> method.<p> 034 * 035 * Generally, the default load factor (.75) offers a good tradeoff between 036 * time and space costs. Higher values decrease the space overhead but 037 * increase the time cost to look up an entry (which is reflected in most 038 * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p> 039 * 040 * The initial capacity controls a tradeoff between wasted space and the 041 * need for <code>rehash</code> operations, which are time-consuming. 042 * No <code>rehash</code> operations will <i>ever</i> occur if the initial 043 * capacity is greater than the maximum number of entries the 044 * <tt>Hashtable</tt> will contain divided by its load factor. However, 045 * setting the initial capacity too high can waste space.<p> 046 * 047 * If many entries are to be made into a <code>Hashtable</code>, 048 * creating it with a sufficiently large capacity may allow the 049 * entries to be inserted more efficiently than letting it perform 050 * automatic rehashing as needed to grow the table. <p> 051 * 052 * This example creates a hashtable of numbers. It uses the names of 053 * the numbers as keys: 054 * <p><blockquote><pre> 055 * Hashtable numbers = new Hashtable(); 056 * numbers.put("one", new Integer(1)); 057 * numbers.put("two", new Integer(2)); 058 * numbers.put("three", new Integer(3)); 059 * </pre></blockquote> 060 * <p> 061 * To retrieve a number, use the following code: 062 * <p><blockquote><pre> 063 * Integer n = (Integer)numbers.get("two"); 064 * if (n != null) { 065 * System.out.println("two = " + n); 066 * } 067 * </pre></blockquote> 068 * <p> 069 * As of the Java 2 platform v1.2, this class has been retrofitted to 070 * implement Map, so that it becomes a part of Java's collection framework. 071 * Unlike the new collection implementations, Hashtable is synchronized.<p> 072 * 073 * The Iterators returned by the iterator and listIterator methods 074 * of the Collections returned by all of Hashtable's "collection view methods" 075 * are <em>fail-fast</em>: if the Hashtable is structurally modified 076 * at any time after the Iterator is created, in any way except through the 077 * Iterator's own remove or add methods, the Iterator will throw a 078 * ConcurrentModificationException. Thus, in the face of concurrent 079 * modification, the Iterator fails quickly and cleanly, rather than risking 080 * arbitrary, non-deterministic behavior at an undetermined time in the future. 081 * The Enumerations returned by Hashtable's keys and values methods are 082 * <em>not</em> fail-fast. 083 * 084 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 085 * as it is, generally speaking, impossible to make any hard guarantees in the 086 * presence of unsynchronized concurrent modification. Fail-fast iterators 087 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 088 * Therefore, it would be wrong to write a program that depended on this 089 * exception for its correctness: <i>the fail-fast behavior of iterators 090 * should be used only to detect bugs.</i> 091 */ 092 public final class HTNS extends Dictionary implements Map, Cloneable, 093 java.io.Serializable { 094 /** 095 * The hash table data. 096 */ 097 private transient Entry table[]; 098 099 /** 100 * The total number of entries in the hash table. 101 */ 102 private transient int count; 103 104 /** 105 * The table is rehashed when its size exceeds this threshold. (The 106 * value of this field is (int)(capacity * loadFactor).) 107 * 108 * @serial 109 */ 110 private int threshold; 111 112 /** 113 * The load factor for the hashtable. 114 * 115 * @serial 116 */ 117 private float loadFactor; 118 119 /** 120 * The number of times this Hashtable has been structurally modified 121 * Structural modifications are those that change the number of entries in 122 * the Hashtable or otherwise modify its internal structure (e.g., 123 * rehash). This field is used to make iterators on Collection-views of 124 * the Hashtable fail-fast. (See ConcurrentModificationException). 125 */ 126 private transient int modCount = 0; 127 128 /** use serialVersionUID from JDK 1.0.2 for interoperability */ 129 private static final long serialVersionUID = 1421746759512286392L; 130 131 /** 132 * Constructs a new, empty hashtable with the specified initial 133 * capacity and the specified load factor. 134 * 135 * @param initialCapacity the initial capacity of the hashtable. 136 * @param loadFactor the load factor of the hashtable. 137 * @exception IllegalArgumentException if the initial capacity is less 138 * than zero, or if the load factor is nonpositive. 139 */ 140 public HTNS(int initialCapacity, float loadFactor) { 141 if (initialCapacity < 0) 142 throw new IllegalArgumentException("Illegal Capacity: "+ 143 initialCapacity); 144 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 145 throw new IllegalArgumentException("Illegal Load: "+loadFactor); 146 147 if (initialCapacity==0) 148 initialCapacity = 1; 149 this.loadFactor = loadFactor; 150 table = new Entry[initialCapacity]; 151 threshold = (int)(initialCapacity * loadFactor); 152 } 153 154 /** 155 * Constructs a new, empty hashtable with the specified initial capacity 156 * and default load factor, which is <tt>0.75</tt>. 157 * 158 * @param initialCapacity the initial capacity of the hashtable. 159 * @exception IllegalArgumentException if the initial capacity is less 160 * than zero. 161 */ 162 public HTNS(int initialCapacity) { 163 this(initialCapacity, 0.75f); 164 } 165 166 /** 167 * Constructs a new, empty hashtable with a default initial capacity (11) 168 * and load factor, which is <tt>0.75</tt>. 169 */ 170 public HTNS() { 171 this(11, 0.75f); 172 } 173 174 /** 175 * Constructs a new hashtable with the same mappings as the given 176 * Map. The hashtable is created with an initial capacity sufficient to 177 * hold the mappings in the given Map and a default load factor, which is 178 * <tt>0.75</tt>. 179 * 180 * @param t the map whose mappings are to be placed in this map. 181 * @throws NullPointerException if the specified map is null. 182 * 183 */ 184 public HTNS(Map t) { 185 this(Math.max(2*t.size(), 11), 0.75f); 186 putAll(t); 187 } 188 189 /** 190 * Returns the number of keys in this hashtable. 191 * 192 * @return the number of keys in this hashtable. 193 */ 194 public int size() { 195 return count; 196 } 197 198 /** 199 * Tests if this hashtable maps no keys to values. 200 * 201 * @return <code>true</code> if this hashtable maps no keys to values; 202 * <code>false</code> otherwise. 203 */ 204 public boolean isEmpty() { 205 return count == 0; 206 } 207 208 @Override 209 public Enumeration keys() { 210 return getEnumeration(KEYS); 211 } 212 213 @Override 214 public Enumeration elements() { 215 return getEnumeration(VALUES); 216 } 217 218 public boolean contains(Object value) { 219 if (value == null) { 220 throw new NullPointerException(); 221 } 222 223 Entry tab[] = table; 224 for (int i = tab.length ; i-- > 0 ;) { 225 for (Entry e = tab[i] ; e != null ; e = e.next) { 226 if (e.value.equals(value)) { 227 return true; 228 } 229 } 230 } 231 return false; 232 } 233 234 @Override 235 public boolean containsValue(Object value) { 236 return contains(value); 237 } 238 239 @Override 240 public boolean containsKey(Object key) { 241 Entry tab[] = table; 242 int hash = key.hashCode(); 243 int index = (hash & 0x7FFFFFFF) % tab.length; 244 for (Entry e = tab[index] ; e != null ; e = e.next) { 245 if ((e.hash == hash) && e.key.equals(key)) { 246 return true; 247 } 248 } 249 return false; 250 } 251 252 @Override 253 public Object get(Object key) { 254 Entry tab[] = table; 255 int hash = key.hashCode(); 256 //int index = (hash & 0x7FFFFFFF) % tab.length; 257 int index = (hash) % tab.length; 258 for (Entry e = tab[index] ; e != null ; e = e.next) { 259 if ((e.hash == hash)) { 260 return e.value; 261 } 262 } 263 return null; 264 } 265 266 /** 267 * Increases the capacity of and internally reorganizes this 268 * hashtable, in order to accommodate and access its entries more 269 * efficiently. This method is called automatically when the 270 * number of keys in the hashtable exceeds this hashtable's capacity 271 * and load factor. 272 */ 273 protected void rehash() { 274 int oldCapacity = table.length; 275 Entry oldMap[] = table; 276 277 int newCapacity = oldCapacity * 2 + 1; 278 Entry newMap[] = new Entry[newCapacity]; 279 280 modCount++; 281 threshold = (int)(newCapacity * loadFactor); 282 table = newMap; 283 284 for (int i = oldCapacity ; i-- > 0 ;) { 285 for (Entry old = oldMap[i] ; old != null ; ) { 286 Entry e = old; 287 old = old.next; 288 289 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 290 e.next = newMap[index]; 291 newMap[index] = e; 292 } 293 } 294 } 295 296 @Override 297 public Object put(Object key, Object value) { 298 // Make sure the value is not null 299 if (value == null) { 300 return remove(key); 301 } 302 303 // Makes sure the key is not already in the hashtable. 304 Entry tab[] = table; 305 int hash = key.hashCode(); 306 int index = (hash & 0x7FFFFFFF) % tab.length; 307 for (Entry e = tab[index] ; e != null ; e = e.next) { 308 if ((e.hash == hash) && e.key.equals(key)) { 309 Object old = e.value; 310 e.value = value; 311 return old; 312 } 313 } 314 315 modCount++; 316 if (count >= threshold) { 317 // Rehash the table if the threshold is exceeded 318 rehash(); 319 320 tab = table; 321 index = (hash & 0x7FFFFFFF) % tab.length; 322 } 323 324 // Creates the new entry. 325 Entry e = new Entry(hash, key, value, tab[index]); 326 tab[index] = e; 327 count++; 328 return null; 329 } 330 331 /** 332 * Removes the key (and its corresponding value) from this 333 * hashtable. This method does nothing if the key is not in the hashtable. 334 * 335 * @param key the key that needs to be removed. 336 * @return the value to which the key had been mapped in this hashtable, 337 * or <code>null</code> if the key did not have a mapping. 338 */ 339 public Object remove(Object key) { 340 Entry tab[] = table; 341 int hash = key.hashCode(); 342 int index = (hash & 0x7FFFFFFF) % tab.length; 343 for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 344 if ((e.hash == hash) && e.key.equals(key)) { 345 modCount++; 346 if (prev != null) { 347 prev.next = e.next; 348 } else { 349 tab[index] = e.next; 350 } 351 count--; 352 Object oldValue = e.value; 353 e.value = null; 354 return oldValue; 355 } 356 } 357 return null; 358 } 359 360 /** 361 * Copies all of the mappings from the specified Map to this Hashtable 362 * These mappings will replace any mappings that this Hashtable had for any 363 * of the keys currently in the specified Map. 364 * 365 * @param t Mappings to be stored in this map. 366 * @throws NullPointerException if the specified map is null. 367 * 368 */ 369 public void putAll(Map t) { 370 Iterator i = t.entrySet().iterator(); 371 while (i.hasNext()) { 372 Map.Entry e = (Map.Entry) i.next(); 373 put(e.getKey(), e.getValue()); 374 } 375 } 376 377 /** 378 * Clears this hashtable so that it contains no keys. 379 */ 380 public void clear() { 381 Entry tab[] = table; 382 modCount++; 383 for (int index = tab.length; --index >= 0; ) 384 tab[index] = null; 385 count = 0; 386 } 387 388 /** 389 * Creates a shallow copy of this hashtable. All the structure of the 390 * hashtable itself is copied, but the keys and values are not cloned. 391 * This is a relatively expensive operation. 392 * 393 * @return a clone of the hashtable. 394 */ 395 public Object clone() { 396 try { 397 HTNS t = (HTNS)super.clone(); 398 t.table = new Entry[table.length]; 399 for (int i = table.length ; i-- > 0 ; ) { 400 t.table[i] = (table[i] != null) 401 ? (Entry)table[i].clone() : null; 402 } 403 t.keySet = null; 404 t.entrySet = null; 405 t.values = null; 406 t.modCount = 0; 407 return t; 408 } catch (CloneNotSupportedException e) { 409 // this shouldn't happen, since we are Cloneable 410 throw new InternalError(); 411 } 412 } 413 414 /** 415 * Returns a string representation of this <tt>Hashtable</tt> object 416 * in the form of a set of entries, enclosed in braces and separated 417 * by the ASCII characters "<tt>, </tt>" (comma and space). Each 418 * entry is rendered as the key, an equals sign <tt>=</tt>, and the 419 * associated element, where the <tt>toString</tt> method is used to 420 * convert the key and element to strings. <p>Overrides to 421 * <tt>toString</tt> method of <tt>Object</tt>. 422 * 423 * @return a string representation of this hashtable. 424 */ 425 public String toString() { 426 int max = size() - 1; 427 StringBuffer buf = new StringBuffer(); 428 Iterator it = entrySet().iterator(); 429 430 buf.append("{"); 431 for (int i = 0; i <= max; i++) { 432 Map.Entry e = (Map.Entry) (it.next()); 433 Object key = e.getKey(); 434 Object value = e.getValue(); 435 buf.append((key == this ? "(this Map)" : key) + "=" + 436 (value == this ? "(this Map)" : value)); 437 438 if (i < max) 439 buf.append(", "); 440 } 441 buf.append("}"); 442 return buf.toString(); 443 } 444 445 446 private Enumeration getEnumeration(int type) { 447 if (count == 0) { 448 return emptyEnumerator; 449 } 450 return new Enumerator(type, false); 451 452 } 453 454 private Iterator getIterator(int type) { 455 if (count == 0) { 456 return emptyIterator; 457 } 458 return new Enumerator(type, true); 459 } 460 461 // Views 462 463 /** 464 * Each of these fields are initialized to contain an instance of the 465 * appropriate view the first time this view is requested. The views are 466 * stateless, so there's no reason to create more than one of each. 467 */ 468 private transient volatile Set keySet = null; 469 private transient volatile Set entrySet = null; 470 private transient volatile Collection values = null; 471 472 /** 473 * Returns a Set view of the keys contained in this Hashtable. The Set 474 * is backed by the Hashtable, so changes to the Hashtable are reflected 475 * in the Set, and vice-versa. The Set supports element removal 476 * (which removes the corresponding entry from the Hashtable), but not 477 * element addition. 478 * 479 * @return a set view of the keys contained in this map. 480 * 481 */ 482 public Set keySet() { 483 if (keySet == null) 484 keySet = Collections.synchronizedSet(new KeySet(), this); 485 return keySet; 486 } 487 488 private class KeySet extends AbstractSet { 489 @Override 490 public Iterator iterator() { 491 return getIterator(KEYS); 492 } 493 @Override 494 public int size() { 495 return count; 496 } 497 @Override 498 public boolean contains(Object o) { 499 return containsKey(o); 500 } 501 @Override 502 public boolean remove(Object o) { 503 return HTNS.this.remove(o) != null; 504 } 505 @Override 506 public void clear() { 507 HTNS.this.clear(); 508 } 509 } 510 511 @Override 512 public Set entrySet() { 513 if (entrySet==null) 514 entrySet = Collections.synchronizedSet(new EntrySet(), this); 515 return entrySet; 516 } 517 518 private class EntrySet extends AbstractSet { 519 @Override 520 public Iterator iterator() { 521 return getIterator(ENTRIES); 522 } 523 524 @Override 525 public boolean contains(Object o) { 526 if (!(o instanceof Map.Entry)) 527 return false; 528 Map.Entry entry = (Map.Entry)o; 529 Object key = entry.getKey(); 530 Entry tab[] = table; 531 int hash = key.hashCode(); 532 int index = (hash & 0x7FFFFFFF) % tab.length; 533 534 for (Entry e = tab[index]; e != null; e = e.next) 535 if (e.hash==hash && e.equals(entry)) 536 return true; 537 return false; 538 } 539 540 @Override 541 public boolean remove(Object o) { 542 if (!(o instanceof Map.Entry)) 543 return false; 544 Map.Entry entry = (Map.Entry)o; 545 Object key = entry.getKey(); 546 Entry tab[] = table; 547 int hash = key.hashCode(); 548 int index = (hash & 0x7FFFFFFF) % tab.length; 549 550 for (Entry e = tab[index], prev = null; e != null; 551 prev = e, e = e.next) { 552 if (e.hash==hash && e.equals(entry)) { 553 modCount++; 554 if (prev != null) 555 prev.next = e.next; 556 else 557 tab[index] = e.next; 558 559 count--; 560 e.value = null; 561 return true; 562 } 563 } 564 return false; 565 } 566 567 @Override 568 public int size() { 569 return count; 570 } 571 572 @Override 573 public void clear() { 574 HTNS.this.clear(); 575 } 576 } 577 578 /** 579 * Returns a Collection view of the values contained in this Hashtable. 580 * The Collection is backed by the Hashtable, so changes to the Hashtable 581 * are reflected in the Collection, and vice-versa. The Collection 582 * supports element removal (which removes the corresponding entry from 583 * the Hashtable), but not element addition. 584 * 585 * @return a collection view of the values contained in this map. 586 * 587 */ 588 public Collection values() { 589 if (values==null) 590 values = Collections.synchronizedCollection(new ValueCollection(), 591 this); 592 return values; 593 } 594 595 private class ValueCollection extends AbstractCollection { 596 @Override 597 public Iterator iterator() { 598 return getIterator(VALUES); 599 } 600 @Override 601 public int size() { 602 return count; 603 } 604 @Override 605 public boolean contains(Object o) { 606 return containsValue(o); 607 } 608 @Override 609 public void clear() { 610 HTNS.this.clear(); 611 } 612 } 613 614 // Comparison and hashing 615 616 @Override 617 public boolean equals(Object o) { 618 if (o == this) 619 return true; 620 621 if (!(o instanceof Map)) 622 return false; 623 Map t = (Map) o; 624 if (t.size() != size()) 625 return false; 626 627 try { 628 Iterator i = entrySet().iterator(); 629 while (i.hasNext()) { 630 Map.Entry e = (Map.Entry) i.next(); 631 Object key = e.getKey(); 632 Object value = e.getValue(); 633 if (value == null) { 634 if (!(t.get(key)==null && t.containsKey(key))) 635 return false; 636 } else { 637 if (!value.equals(t.get(key))) 638 return false; 639 } 640 } 641 } catch(ClassCastException unused) { 642 return false; 643 } catch(NullPointerException unused) { 644 return false; 645 } 646 647 return true; 648 } 649 650 @Override 651 public int hashCode() { 652 /* 653 * This code detects the recursion caused by computing the hash code 654 * of a self-referential hash table and prevents the stack overflow 655 * that would otherwise result. This allows certain 1.1-era 656 * applets with self-referential hash tables to work. This code 657 * abuses the loadFactor field to do double-duty as a hashCode 658 * in progress flag, so as not to worsen the space performance. 659 * A negative load factor indicates that hash code computation is 660 * in progress. 661 */ 662 int h = 0; 663 if (count == 0 || loadFactor < 0) 664 return h; // Returns zero 665 666 loadFactor = -loadFactor; // Mark hashCode computation in progress 667 Entry tab[] = table; 668 for (int i = 0; i < tab.length; i++) 669 for (Entry e = tab[i]; e != null; e = e.next) 670 h += e.key.hashCode() ^ e.value.hashCode(); 671 loadFactor = -loadFactor; // Mark hashCode computation complete 672 673 return h; 674 } 675 676 /** 677 * Save the state of the Hashtable to a stream (i.e., serialize it). 678 * @param s 679 * @throws IOException 680 * 681 * @serialData The <i>capacity</i> of the Hashtable (the length of the 682 * bucket array) is emitted (int), followed by the 683 * <i>size</i> of the Hashtable (the number of key-value 684 * mappings), followed by the key (Object) and value (Object) 685 * for each key-value mapping represented by the Hashtable 686 * The key-value mappings are emitted in no particular order. 687 */ 688 private void writeObject(java.io.ObjectOutputStream s) 689 throws IOException 690 { 691 // Write out the length, threshold, loadfactor 692 s.defaultWriteObject(); 693 694 // Write out length, count of elements and then the key/value objects 695 s.writeInt(table.length); 696 s.writeInt(count); 697 for (int index = table.length-1; index >= 0; index--) { 698 Entry entry = table[index]; 699 700 while (entry != null) { 701 s.writeObject(entry.key); 702 s.writeObject(entry.value); 703 entry = entry.next; 704 } 705 } 706 } 707 708 /** 709 * Reconstitute the Hashtable from a stream (i.e., deserialize it). 710 * @param s 711 * @throws IOException 712 * @throws ClassNotFoundException 713 */ 714 private void readObject(java.io.ObjectInputStream s) 715 throws IOException, ClassNotFoundException 716 { 717 // Read in the length, threshold, and loadfactor 718 s.defaultReadObject(); 719 720 // Read the original length of the array and number of elements 721 int origlength = s.readInt(); 722 int elements = s.readInt(); 723 724 // Compute new size with a bit of room 5% to grow but 725 // No larger than the original size. Make the length 726 // odd if it's large enough, this helps distribute the entries. 727 // Guard against the length ending up zero, that's not valid. 728 int length = (int)(elements * loadFactor) + (elements / 20) + 3; 729 if (length > elements && (length & 1) == 0) 730 length--; 731 if (origlength > 0 && length > origlength) 732 length = origlength; 733 734 table = new Entry[length]; 735 count = 0; 736 737 // Read the number of elements and then all the key/value objects 738 for (; elements > 0; elements--) { 739 Object key = s.readObject(); 740 Object value = s.readObject(); 741 put(key, value); 742 } 743 } 744 745 746 /** 747 * Hashtable collision list. 748 */ 749 private static class Entry implements Map.Entry { 750 int hash; 751 Object key; 752 Object value; 753 Entry next; 754 755 /** 756 * @param hash 757 * @param key 758 * @param value 759 * @param next 760 */ 761 protected Entry(int hash, Object key, Object value, Entry next) { 762 this.hash = hash; 763 this.key = key; 764 this.value = value; 765 this.next = next; 766 } 767 768 @Override 769 protected Object clone() { 770 return new Entry(hash, key, value, 771 (next==null ? null : (Entry)next.clone())); 772 } 773 774 // Map.Entry Ops 775 776 @Override 777 public Object getKey() { 778 return key; 779 } 780 781 @Override 782 public Object getValue() { 783 return value; 784 } 785 786 @Override 787 public Object setValue(Object value) { 788 if (value == null) 789 throw new NullPointerException(); 790 791 Object oldValue = this.value; 792 this.value = value; 793 return oldValue; 794 } 795 796 @Override 797 public boolean equals(Object o) { 798 if (!(o instanceof Map.Entry)) 799 return false; 800 Map.Entry e = (Map.Entry)o; 801 802 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 803 (value==null ? e.getValue()==null : value.equals(e.getValue())); 804 } 805 806 @Override 807 public int hashCode() { 808 return hash ^ (value==null ? 0 : value.hashCode()); 809 } 810 811 @Override 812 public String toString() { 813 return key.toString()+"="+value.toString(); 814 } 815 } 816 817 // Types of Enumerations/Iterations 818 private static final int KEYS = 0; 819 private static final int VALUES = 1; 820 private static final int ENTRIES = 2; 821 822 /** 823 * A hashtable enumerator class. This class implements both the 824 * Enumeration and Iterator interfaces, but individual instances 825 * can be created with the Iterator methods disabled. This is necessary 826 * to avoid unintentionally increasing the capabilities granted a user 827 * by passing an Enumeration. 828 */ 829 private class Enumerator implements Enumeration, Iterator { 830 Entry[] table = HTNS.this.table; 831 int index = table.length; 832 Entry entry = null; 833 Entry lastReturned = null; 834 int type; 835 836 /** 837 * Indicates whether this Enumerator is serving as an Iterator 838 * or an Enumeration. (true -> Iterator). 839 */ 840 boolean iterator; 841 842 /** 843 * The modCount value that the iterator believes that the backing 844 * List should have. If this expectation is violated, the iterator 845 * has detected concurrent modification. 846 */ 847 protected int expectedModCount = modCount; 848 849 Enumerator(int type, boolean iterator) { 850 this.type = type; 851 this.iterator = iterator; 852 } 853 854 @Override 855 public boolean hasMoreElements() { 856 Entry e = entry; 857 int i = index; 858 Entry t[] = table; 859 /* Use locals for faster loop iteration */ 860 while (e == null && i > 0) { 861 e = t[--i]; 862 } 863 entry = e; 864 index = i; 865 return e != null; 866 } 867 868 @Override 869 public Object nextElement() { 870 Entry et = entry; 871 int i = index; 872 Entry t[] = table; 873 /* Use locals for faster loop iteration */ 874 while (et == null && i > 0) { 875 et = t[--i]; 876 } 877 entry = et; 878 index = i; 879 if (et != null) { 880 Entry e = lastReturned = entry; 881 entry = e.next; 882 return type == KEYS ? e.key : (type == VALUES ? e.value : e); 883 } 884 throw new NoSuchElementException("Hashtable Enumerator"); 885 } 886 887 @Override 888 // Iterator methods 889 public boolean hasNext() { 890 return hasMoreElements(); 891 } 892 893 @Override 894 public Object next() { 895 if (modCount != expectedModCount) 896 throw new ConcurrentModificationException(); 897 return nextElement(); 898 } 899 900 @Override 901 public void remove() { 902 if (!iterator) 903 throw new UnsupportedOperationException(); 904 if (lastReturned == null) 905 throw new IllegalStateException("Hashtable Enumerator"); 906 if (modCount != expectedModCount) 907 throw new ConcurrentModificationException(); 908 909 synchronized(HTNS.this) { 910 Entry[] tab = HTNS.this.table; 911 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 912 913 for (Entry e = tab[index], prev = null; e != null; 914 prev = e, e = e.next) { 915 if (e == lastReturned) { 916 modCount++; 917 expectedModCount++; 918 if (prev == null) 919 tab[index] = e.next; 920 else 921 prev.next = e.next; 922 count--; 923 lastReturned = null; 924 return; 925 } 926 } 927 throw new ConcurrentModificationException(); 928 } 929 } 930 } 931 932 933 private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator(); 934 private static EmptyIterator emptyIterator = new EmptyIterator(); 935 936 /** 937 * A hashtable enumerator class for empty hash tables, specializes 938 * the general Enumerator 939 */ 940 private static class EmptyEnumerator implements Enumeration { 941 942 EmptyEnumerator() { 943 } 944 945 @Override 946 public boolean hasMoreElements() { 947 return false; 948 } 949 950 @Override 951 public Object nextElement() { 952 throw new NoSuchElementException("Hashtable Enumerator"); 953 } 954 } 955 956 957 /** 958 * A hashtable iterator class for empty hash tables 959 */ 960 private static class EmptyIterator implements Iterator { 961 962 EmptyIterator() { 963 } 964 965 @Override 966 public boolean hasNext() { 967 return false; 968 } 969 970 @Override 971 public Object next() { 972 throw new NoSuchElementException("Hashtable Iterator"); 973 } 974 975 @Override 976 public void remove() { 977 throw new IllegalStateException("Hashtable Iterator"); 978 } 979 980 } 981 982 }