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