001 package railo.commons.collections; 002 003 import java.util.AbstractCollection; 004 import java.util.AbstractSet; 005 import java.util.Collection; 006 import java.util.ConcurrentModificationException; 007 import java.util.Enumeration; 008 import java.util.Iterator; 009 import java.util.Map; 010 import java.util.NoSuchElementException; 011 import java.util.Set; 012 013 import railo.runtime.type.Collection.Key; 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 KeyImplMap implements 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 KeyImplMap(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 KeyImplMap(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 KeyImplMap() { 171 this(11, 0.75f); 172 } 173 174 /** 175 * Returns the number of keys in this hashtable. 176 * 177 * @return the number of keys in this hashtable. 178 */ 179 public int size() { 180 return count; 181 } 182 183 /** 184 * Tests if this hashtable maps no keys to values. 185 * 186 * @return <code>true</code> if this hashtable maps no keys to values; 187 * <code>false</code> otherwise. 188 */ 189 public boolean isEmpty() { 190 return count == 0; 191 } 192 193 /** 194 * Returns an enumeration of the keys in this hashtable. 195 * 196 * @return an enumeration of the keys in this hashtable. 197 * @see Enumeration 198 * @see #elements() 199 * @see #keySet() 200 * @see Map 201 */ 202 public Enumeration keys() { 203 return getEnumeration(KEYS); 204 } 205 206 /** 207 * Returns an enumeration of the values in this hashtable. 208 * Use the Enumeration methods on the returned object to fetch the elements 209 * sequentially. 210 * 211 * @return an enumeration of the values in this hashtable. 212 * @see java.util.Enumeration 213 * @see #keys() 214 * @see #values() 215 * @see Map 216 */ 217 public Enumeration elements() { 218 return getEnumeration(VALUES); 219 } 220 221 /** 222 * Tests if some key maps into the specified value in this hashtable. 223 * This operation is more expensive than the <code>containsKey</code> 224 * method.<p> 225 * 226 * Note that this method is identical in functionality to containsValue, 227 * (which is part of the Map interface in the collections framework). 228 * 229 * @param value a value to search for. 230 * @return <code>true</code> if and only if some key maps to the 231 * <code>value</code> argument in this hashtable as 232 * determined by the <tt>equals</tt> method; 233 * <code>false</code> otherwise. 234 * @exception NullPointerException if the value is <code>null</code>. 235 * @see #containsKey(Object) 236 * @see #containsValue(Object) 237 * @see Map 238 */ 239 public boolean contains(Object value) { 240 if (value == null) { 241 throw new NullPointerException(); 242 } 243 244 Entry tab[] = table; 245 for (int i = tab.length ; i-- > 0 ;) { 246 for (Entry e = tab[i] ; e != null ; e = e.next) { 247 if (e.value.equals(value)) { 248 return true; 249 } 250 } 251 } 252 return false; 253 } 254 255 /** 256 * Returns true if this Hashtable maps one or more keys to this value.<p> 257 * 258 * Note that this method is identical in functionality to contains 259 * (which predates the Map interface). 260 * 261 * @param value value whose presence in this Hashtable is to be tested. 262 * @return <tt>true</tt> if this map maps one or more keys to the 263 * specified value. 264 * @see Map 265 * 266 */ 267 public boolean containsValue(Object value) { 268 return contains(value); 269 } 270 271 /** 272 * Tests if the specified object is a key in this hashtable. 273 * 274 * @param key possible key. 275 * @return <code>true</code> if and only if the specified object 276 * is a key in this hashtable, as determined by the 277 * <tt>equals</tt> method; <code>false</code> otherwise. 278 * @see #contains(Object) 279 */ 280 public boolean containsKey(Object key) { 281 Entry tab[] = table; 282 int hash = key.hashCode(); 283 int index = (hash & 0x7FFFFFFF) % tab.length; 284 for (Entry e = tab[index] ; e != null ; e = e.next) { 285 if ((e.hash == hash) && e.key.equals(key)) { 286 return true; 287 } 288 } 289 return false; 290 } 291 292 /** 293 * Returns the value to which the specified key is mapped in this hashtable. 294 * 295 * @param key a key in the hashtable. 296 * @return the value to which the key is mapped in this hashtable; 297 * <code>null</code> if the key is not mapped to any value in 298 * this hashtable. 299 * @see #put(Object, Object) 300 */ 301 public Key get(Object key) { 302 Entry tab[] = table; 303 int hash = key.hashCode(); 304 int index = (hash & 0x7FFFFFFF) % tab.length; 305 for (Entry e = tab[index] ; e != null ; e = e.next) { 306 if ((e.hash == hash)) { 307 return e.value; 308 } 309 } 310 return null; 311 } 312 313 /** 314 * Increases the capacity of and internally reorganizes this 315 * hashtable, in order to accommodate and access its entries more 316 * efficiently. This method is called automatically when the 317 * number of keys in the hashtable exceeds this hashtable's capacity 318 * and load factor. 319 */ 320 protected void rehash() { 321 int oldCapacity = table.length; 322 Entry oldMap[] = table; 323 324 int newCapacity = oldCapacity * 2 + 1; 325 Entry newMap[] = new Entry[newCapacity]; 326 327 modCount++; 328 threshold = (int)(newCapacity * loadFactor); 329 table = newMap; 330 331 for (int i = oldCapacity ; i-- > 0 ;) { 332 for (Entry old = oldMap[i] ; old != null ; ) { 333 Entry e = old; 334 old = old.next; 335 336 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 337 e.next = newMap[index]; 338 newMap[index] = e; 339 } 340 } 341 } 342 343 /** 344 * Maps the specified <code>key</code> to the specified 345 * <code>value</code> in this hashtable. Neither the key nor the 346 * value can be <code>null</code>. <p> 347 * 348 * The value can be retrieved by calling the <code>get</code> method 349 * with a key that is equal to the original key. 350 * 351 * @param key the hashtable key. 352 * @param value the value. 353 * @return the previous value of the specified key in this hashtable, 354 * or <code>null</code> if it did not have one. 355 * @exception NullPointerException if the key or value is 356 * <code>null</code>. 357 * @see Object#equals(Object) 358 * @see #get(Object) 359 */ 360 public Object put(Object key, Key value) { 361 // Makes sure the key is not already in the hashtable. 362 Entry tab[] = table; 363 int hash = key.hashCode(); 364 int index = (hash & 0x7FFFFFFF) % tab.length; 365 for (Entry e = tab[index] ; e != null ; e = e.next) { 366 if ((e.hash == hash) ) { 367 Object old = e.value; 368 e.value = value; 369 return old; 370 } 371 } 372 373 modCount++; 374 if (count >= threshold) { 375 // Rehash the table if the threshold is exceeded 376 rehash(); 377 378 tab = table; 379 index = (hash & 0x7FFFFFFF) % tab.length; 380 } 381 382 // Creates the new entry. 383 Entry e = new Entry(hash, key, value, tab[index]); 384 tab[index] = e; 385 count++; 386 return null; 387 } 388 389 /** 390 * Removes the key (and its corresponding value) from this 391 * hashtable. This method does nothing if the key is not in the hashtable. 392 * 393 * @param key the key that needs to be removed. 394 * @return the value to which the key had been mapped in this hashtable, 395 * or <code>null</code> if the key did not have a mapping. 396 */ 397 public Object remove(Object key) { 398 Entry tab[] = table; 399 int hash = key.hashCode(); 400 int index = (hash & 0x7FFFFFFF) % tab.length; 401 for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 402 if ((e.hash == hash) && e.key.equals(key)) { 403 modCount++; 404 if (prev != null) { 405 prev.next = e.next; 406 } else { 407 tab[index] = e.next; 408 } 409 count--; 410 Object oldValue = e.value; 411 e.value = null; 412 return oldValue; 413 } 414 } 415 return null; 416 } 417 418 /** 419 * Clears this hashtable so that it contains no keys. 420 */ 421 public void clear() { 422 Entry tab[] = table; 423 modCount++; 424 for (int index = tab.length; --index >= 0; ) 425 tab[index] = null; 426 count = 0; 427 } 428 429 /** 430 * Creates a shallow copy of this hashtable. All the structure of the 431 * hashtable itself is copied, but the keys and values are not cloned. 432 * This is a relatively expensive operation. 433 * 434 * @return a clone of the hashtable. 435 */ 436 public Object clone() { 437 try { 438 KeyImplMap t = (KeyImplMap)super.clone(); 439 t.table = new Entry[table.length]; 440 for (int i = table.length ; i-- > 0 ; ) { 441 t.table[i] = (table[i] != null) 442 ? (Entry)table[i].clone() : null; 443 } 444 t.keySet = null; 445 t.entrySet = null; 446 t.values = null; 447 t.modCount = 0; 448 return t; 449 } catch (CloneNotSupportedException e) { 450 // this shouldn't happen, since we are Cloneable 451 throw new InternalError(); 452 } 453 } 454 455 /** 456 * Returns a string representation of this <tt>Hashtable</tt> object 457 * in the form of a set of entries, enclosed in braces and separated 458 * by the ASCII characters "<tt>, </tt>" (comma and space). Each 459 * entry is rendered as the key, an equals sign <tt>=</tt>, and the 460 * associated element, where the <tt>toString</tt> method is used to 461 * convert the key and element to strings. <p>Overrides to 462 * <tt>toString</tt> method of <tt>Object</tt>. 463 * 464 * @return a string representation of this hashtable. 465 */ 466 public String toString() { 467 int max = size() - 1; 468 StringBuffer buf = new StringBuffer(); 469 Iterator it = entrySet().iterator(); 470 471 buf.append("{"); 472 for (int i = 0; i <= max; i++) { 473 Entry e = (Entry) (it.next()); 474 Object key = e.getKey(); 475 Object value = e.getValue(); 476 buf.append((key == this ? "(this Map)" : key) + "=" + 477 (value == this ? "(this Map)" : value)); 478 479 if (i < max) 480 buf.append(", "); 481 } 482 buf.append("}"); 483 return buf.toString(); 484 } 485 486 487 private Enumeration getEnumeration(int type) { 488 if (count == 0) { 489 return emptyEnumerator; 490 } 491 return new Enumerator(type, false); 492 493 } 494 495 private Iterator getIterator(int type) { 496 if (count == 0) { 497 return emptyIterator; 498 } 499 return new Enumerator(type, true); 500 } 501 502 // Views 503 504 /** 505 * Each of these fields are initialized to contain an instance of the 506 * appropriate view the first time this view is requested. The views are 507 * stateless, so there's no reason to create more than one of each. 508 */ 509 private transient volatile Set keySet = null; 510 private transient volatile Set entrySet = null; 511 private transient volatile Collection values = null; 512 513 /** 514 * Returns a Set view of the keys contained in this Hashtable. The Set 515 * is backed by the Hashtable, so changes to the Hashtable are reflected 516 * in the Set, and vice-versa. The Set supports element removal 517 * (which removes the corresponding entry from the Hashtable), but not 518 * element addition. 519 * 520 * @return a set view of the keys contained in this map. 521 * 522 */ 523 public Set keySet() { 524 if (keySet == null) 525 keySet = Collections.synchronizedSet(new KeySet(), this); 526 return keySet; 527 } 528 529 private class KeySet extends AbstractSet { 530 /** 531 * @see java.util.Set#iterator() 532 */ 533 public Iterator iterator() { 534 return getIterator(KEYS); 535 } 536 /** 537 * @see java.util.Set#size() 538 */ 539 public int size() { 540 return count; 541 } 542 /** 543 * @see java.util.Set#contains(java.lang.Object) 544 */ 545 public boolean contains(Object o) { 546 return containsKey(o); 547 } 548 /** 549 * @see java.util.Set#remove(java.lang.Object) 550 */ 551 public boolean remove(Object o) { 552 return KeyImplMap.this.remove(o) != null; 553 } 554 /** 555 * @see java.util.Set#clear() 556 */ 557 public void clear() { 558 KeyImplMap.this.clear(); 559 } 560 } 561 562 /** 563 * Returns a Set view of the entries contained in this Hashtable. 564 * Each element in this collection is a Map.Entry. The Set is 565 * backed by the Hashtable, so changes to the Hashtable are reflected in 566 * the Set, and vice-versa. The Set supports element removal 567 * (which removes the corresponding entry from the Hashtable), 568 * but not element addition. 569 * 570 * @return a set view of the mappings contained in this map. 571 * @see Map.Entry 572 * 573 */ 574 public Set entrySet() { 575 if (entrySet==null) 576 entrySet = Collections.synchronizedSet(new EntrySet(), this); 577 return entrySet; 578 } 579 580 private class EntrySet extends AbstractSet { 581 /** 582 * @see java.util.Set#iterator() 583 */ 584 public Iterator iterator() { 585 return getIterator(ENTRIES); 586 } 587 588 /** 589 * @see java.util.Set#contains(java.lang.Object) 590 */ 591 public boolean contains(Object o) { 592 if (!(o instanceof Entry)) 593 return false; 594 Entry entry = (Entry)o; 595 Object key = entry.getKey(); 596 Entry tab[] = table; 597 int hash = key.hashCode(); 598 int index = (hash & 0x7FFFFFFF) % tab.length; 599 600 for (Entry e = tab[index]; e != null; e = e.next) 601 if (e.hash==hash && e.equals(entry)) 602 return true; 603 return false; 604 } 605 606 /** 607 * @see java.util.Set#remove(java.lang.Object) 608 */ 609 public boolean remove(Object o) { 610 if (!(o instanceof Entry)) 611 return false; 612 Entry entry = (Entry)o; 613 Object key = entry.getKey(); 614 Entry tab[] = table; 615 int hash = key.hashCode(); 616 int index = (hash & 0x7FFFFFFF) % tab.length; 617 618 for (Entry e = tab[index], prev = null; e != null; 619 prev = e, e = e.next) { 620 if (e.hash==hash && e.equals(entry)) { 621 modCount++; 622 if (prev != null) 623 prev.next = e.next; 624 else 625 tab[index] = e.next; 626 627 count--; 628 e.value = null; 629 return true; 630 } 631 } 632 return false; 633 } 634 635 /** 636 * @see java.util.Set#size() 637 */ 638 public int size() { 639 return count; 640 } 641 642 /** 643 * @see java.util.Set#clear() 644 */ 645 public void clear() { 646 KeyImplMap.this.clear(); 647 } 648 } 649 650 /** 651 * Returns a Collection view of the values contained in this Hashtable. 652 * The Collection is backed by the Hashtable, so changes to the Hashtable 653 * are reflected in the Collection, and vice-versa. The Collection 654 * supports element removal (which removes the corresponding entry from 655 * the Hashtable), but not element addition. 656 * 657 * @return a collection view of the values contained in this map. 658 * 659 */ 660 public Collection values() { 661 if (values==null) 662 values = Collections.synchronizedCollection(new ValueCollection(), 663 this); 664 return values; 665 } 666 667 private class ValueCollection extends AbstractCollection { 668 /** 669 * @see java.util.AbstractCollection#iterator() 670 */ 671 public Iterator iterator() { 672 return getIterator(VALUES); 673 } 674 /** 675 * @see java.util.AbstractCollection#size() 676 */ 677 public int size() { 678 return count; 679 } 680 /** 681 * @see java.util.AbstractCollection#contains(java.lang.Object) 682 */ 683 public boolean contains(Object o) { 684 return containsValue(o); 685 } 686 /** 687 * @see java.util.AbstractCollection#clear() 688 */ 689 public void clear() { 690 KeyImplMap.this.clear(); 691 } 692 } 693 694 /** 695 * Returns the hash code value for this Map as per the definition in the 696 * Map interface. 697 * 698 * @see Map#hashCode() 699 * 700 */ 701 public int hashCode() { 702 /* 703 * This code detects the recursion caused by computing the hash code 704 * of a self-referential hash table and prevents the stack overflow 705 * that would otherwise result. This allows certain 1.1-era 706 * applets with self-referential hash tables to work. This code 707 * abuses the loadFactor field to do double-duty as a hashCode 708 * in progress flag, so as not to worsen the space performance. 709 * A negative load factor indicates that hash code computation is 710 * in progress. 711 */ 712 int h = 0; 713 if (count == 0 || loadFactor < 0) 714 return h; // Returns zero 715 716 loadFactor = -loadFactor; // Mark hashCode computation in progress 717 Entry tab[] = table; 718 for (int i = 0; i < tab.length; i++) 719 for (Entry e = tab[i]; e != null; e = e.next) 720 h += e.key.hashCode() ^ e.value.hashCode(); 721 loadFactor = -loadFactor; // Mark hashCode computation complete 722 723 return h; 724 } 725 726 /** 727 * Hashtable collision list. 728 */ 729 private static class Entry { 730 int hash; 731 Object key; 732 Key value; 733 Entry next; 734 735 /** 736 * @param hash 737 * @param key 738 * @param value 739 * @param next 740 */ 741 protected Entry(int hash, Object key, Key value, Entry next) { 742 this.hash = hash; 743 this.key = key; 744 this.value = value; 745 this.next = next; 746 } 747 748 /** 749 * @see java.lang.Object#clone() 750 */ 751 protected Object clone() { 752 return new Entry(hash, key, value, 753 (next==null ? null : (Entry)next.clone())); 754 } 755 756 // Map.Entry Ops 757 758 /** 759 * @see java.util.Map.Entry#getKey() 760 */ 761 public Object getKey() { 762 return key; 763 } 764 765 /** 766 * @see java.util.Map.Entry#getValue() 767 */ 768 public Key getValue() { 769 return value; 770 } 771 772 /** 773 * @see java.util.Map.Entry#setValue(java.lang.Object) 774 */ 775 public Object setValue(Key value) { 776 if (value == null) 777 throw new NullPointerException(); 778 779 Object oldValue = this.value; 780 this.value = value; 781 return oldValue; 782 } 783 784 /** 785 * @see java.util.Map.Entry#equals(java.lang.Object) 786 */ 787 public boolean equals(Object o) { 788 if (!(o instanceof Entry)) 789 return false; 790 Entry e = (Entry)o; 791 792 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 793 (value==null ? e.getValue()==null : value.equals(e.getValue())); 794 } 795 796 /** 797 * @see java.util.Map.Entry#hashCode() 798 */ 799 public int hashCode() { 800 return hash ^ (value==null ? 0 : value.hashCode()); 801 } 802 803 /** 804 * @see java.lang.Object#toString() 805 */ 806 public String toString() { 807 return key.toString()+"="+value.toString(); 808 } 809 } 810 811 // Types of Enumerations/Iterations 812 private static final int KEYS = 0; 813 private static final int VALUES = 1; 814 private static final int ENTRIES = 2; 815 816 /** 817 * A hashtable enumerator class. This class implements both the 818 * Enumeration and Iterator interfaces, but individual instances 819 * can be created with the Iterator methods disabled. This is necessary 820 * to avoid unintentionally increasing the capabilities granted a user 821 * by passing an Enumeration. 822 */ 823 private class Enumerator implements Enumeration, Iterator { 824 Entry[] table = KeyImplMap.this.table; 825 int index = table.length; 826 Entry entry = null; 827 Entry lastReturned = null; 828 int type; 829 830 /** 831 * Indicates whether this Enumerator is serving as an Iterator 832 * or an Enumeration. (true -> Iterator). 833 */ 834 boolean iterator; 835 836 /** 837 * The modCount value that the iterator believes that the backing 838 * List should have. If this expectation is violated, the iterator 839 * has detected concurrent modification. 840 */ 841 protected int expectedModCount = modCount; 842 843 Enumerator(int type, boolean iterator) { 844 this.type = type; 845 this.iterator = iterator; 846 } 847 848 /** 849 * @see java.util.Enumeration#hasMoreElements() 850 */ 851 public boolean hasMoreElements() { 852 Entry e = entry; 853 int i = index; 854 Entry t[] = table; 855 /* Use locals for faster loop iteration */ 856 while (e == null && i > 0) { 857 e = t[--i]; 858 } 859 entry = e; 860 index = i; 861 return e != null; 862 } 863 864 /** 865 * @see java.util.Enumeration#nextElement() 866 */ 867 public Object nextElement() { 868 869 throw new NoSuchElementException("not impl"); 870 } 871 872 /** 873 * @see java.util.Iterator#hasNext() 874 */ 875 // Iterator methods 876 public boolean hasNext() { 877 return hasMoreElements(); 878 } 879 880 /** 881 * @see java.util.Iterator#next() 882 */ 883 public Object next() { 884 if (modCount != expectedModCount) 885 throw new ConcurrentModificationException(); 886 return nextElement(); 887 } 888 889 /** 890 * @see java.util.Iterator#remove() 891 */ 892 public void remove() { 893 if (!iterator) 894 throw new UnsupportedOperationException(); 895 if (lastReturned == null) 896 throw new IllegalStateException("Hashtable Enumerator"); 897 if (modCount != expectedModCount) 898 throw new ConcurrentModificationException(); 899 900 synchronized(KeyImplMap.this) { 901 Entry[] tab = KeyImplMap.this.table; 902 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 903 904 for (Entry e = tab[index], prev = null; e != null; 905 prev = e, e = e.next) { 906 if (e == lastReturned) { 907 modCount++; 908 expectedModCount++; 909 if (prev == null) 910 tab[index] = e.next; 911 else 912 prev.next = e.next; 913 count--; 914 lastReturned = null; 915 return; 916 } 917 } 918 throw new ConcurrentModificationException(); 919 } 920 } 921 } 922 923 924 private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator(); 925 private static EmptyIterator emptyIterator = new EmptyIterator(); 926 927 /** 928 * A hashtable enumerator class for empty hash tables, specializes 929 * the general Enumerator 930 */ 931 private static class EmptyEnumerator implements Enumeration { 932 933 EmptyEnumerator() { 934 } 935 936 /** 937 * @see java.util.Enumeration#hasMoreElements() 938 */ 939 public boolean hasMoreElements() { 940 return false; 941 } 942 943 /** 944 * @see java.util.Enumeration#nextElement() 945 */ 946 public Object nextElement() { 947 throw new NoSuchElementException("Hashtable Enumerator"); 948 } 949 } 950 951 952 /** 953 * A hashtable iterator class for empty hash tables 954 */ 955 private static class EmptyIterator implements Iterator { 956 957 EmptyIterator() { 958 } 959 960 /** 961 * @see java.util.Iterator#hasNext() 962 */ 963 public boolean hasNext() { 964 return false; 965 } 966 967 /** 968 * @see java.util.Iterator#next() 969 */ 970 public Object next() { 971 throw new NoSuchElementException("Hashtable Iterator"); 972 } 973 974 /** 975 * @see java.util.Iterator#remove() 976 */ 977 public void remove() { 978 throw new IllegalStateException("Hashtable Iterator"); 979 } 980 981 } 982 983 }