1 21 package oracle.toplink.essentials.internal.helper; 23 24 25 37 38 import java.io.*; 40 import java.util.*; 41 42 public class TopLinkIdentityHashMap extends AbstractMap implements Map, Cloneable , Serializable { 43 static final long serialVersionUID = -5176951017503351630L; 44 45 static final int DEFAULT_INITIAL_CAPACITY = 32; 47 48 static final int MAXIMUM_CAPACITY = 1 << 30; 50 51 static final float DEFAULT_LOAD_FACTOR = 0.75f; 53 protected transient Entry[] entries; protected transient int count = 0; 55 private transient int modCount = 0; protected int threshold = 0; 57 protected float loadFactor = 0; 58 59 69 public TopLinkIdentityHashMap(int initialCapacity, float loadFactor) { 70 if (initialCapacity < 0) { 71 throw new IllegalArgumentException ("Illegal initialCapacity: " + initialCapacity); 72 } 73 if (initialCapacity > MAXIMUM_CAPACITY) { 74 initialCapacity = MAXIMUM_CAPACITY; 75 } 76 if ((loadFactor <= 0) || Float.isNaN(loadFactor)) { 77 throw new IllegalArgumentException ("Illegal loadFactor: " + loadFactor); 78 } 79 80 int capacity = 1; 82 while (capacity < initialCapacity) { 83 capacity <<= 1; 84 } 85 this.loadFactor = loadFactor; 86 threshold = (int)(capacity * loadFactor); 87 entries = new Entry[capacity]; 88 } 89 90 99 public TopLinkIdentityHashMap(int initialCapacity) { 100 this(initialCapacity, DEFAULT_LOAD_FACTOR); 101 } 102 103 107 public TopLinkIdentityHashMap() { 108 loadFactor = DEFAULT_LOAD_FACTOR; 109 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 110 entries = new Entry[DEFAULT_INITIAL_CAPACITY]; 111 } 112 113 121 public TopLinkIdentityHashMap(Map m) { 122 this(Math.max((int)(m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); 123 putAll(m); 124 } 125 126 129 public int size() { 130 return count; 131 } 132 133 136 public boolean isEmpty() { 137 return (count == 0); 138 } 139 140 149 public boolean containsValue(Object obj) { 150 if (obj == null) { 151 throw new NullPointerException (); 152 } 153 154 Entry[] copyOfEntries = entries; 155 for (int i = copyOfEntries.length; i-- > 0;) { 156 for (Entry e = copyOfEntries[i]; e != null; e = e.next) { 157 if (e.value.equals(obj)) { 158 return true; 159 } 160 } 161 } 162 return false; 163 } 164 165 174 public boolean containsKey(Object key) { 175 Entry[] copyOfEntries = entries; 176 int hash = System.identityHashCode(key); 177 int index = (hash & 0x7FFFFFFF) % copyOfEntries.length; 178 for (Entry e = copyOfEntries[index]; e != null; e = e.next) { 179 if (e.key == key) { 180 return true; 181 } 182 } 183 return false; 184 } 185 186 195 public Object get(Object key) { 196 Entry[] copyOfEntries = entries; 197 int hash = System.identityHashCode(key); 198 int index = (hash & 0x7FFFFFFF) % copyOfEntries.length; 199 for (Entry e = copyOfEntries[index]; e != null; e = e.next) { 200 if (e.key == key) { 201 return e.value; 202 } 203 } 204 return null; 205 } 206 207 213 private void rehash() { 214 int oldCapacity = entries.length; 215 Entry[] oldEntries = entries; 216 int newCapacity = (oldCapacity * 2) + 1; 217 Entry[] newEntries = new Entry[newCapacity]; 218 modCount++; 219 threshold = (int)(newCapacity * loadFactor); 220 entries = newEntries; 221 for (int i = oldCapacity; i-- > 0;) { 222 for (Entry old = oldEntries[i]; old != null;) { 223 Entry e = old; 224 old = old.next; 225 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 226 e.next = newEntries[index]; 227 newEntries[index] = e; 228 } 229 } 230 } 231 232 242 public Object put(Object key, Object obj) { 243 if (obj == null) { 244 throw new NullPointerException (); 245 } 246 247 Entry[] copyOfEntries = entries; 248 int hash = System.identityHashCode(key); 249 int index = (hash & 0x7FFFFFFF) % copyOfEntries.length; 250 for (Entry e = copyOfEntries[index]; e != null; e = e.next) { 251 if (e.key == key) { 252 Object old = e.value; 253 e.value = obj; 254 return old; 255 } 256 } 257 258 modCount++; 259 if (count >= threshold) { 260 rehash(); 261 copyOfEntries = entries; 262 index = (hash & 0x7FFFFFFF) % copyOfEntries.length; 263 } 264 Entry e = new Entry(hash, key, obj, copyOfEntries[index]); 265 copyOfEntries[index] = e; 266 count++; 267 return null; 268 } 269 270 278 public Object remove(Object key) { 279 Entry[] copyOfEntries = entries; 280 int hash = System.identityHashCode(key); 281 int index = (hash & 0x7FFFFFFF) % copyOfEntries.length; 282 for (Entry e = copyOfEntries[index], prev = null; e != null; prev = e, e = e.next) { 283 if (e.key == key) { 284 if (prev != null) { 285 prev.next = e.next; 286 } else { 287 copyOfEntries[index] = e.next; 288 } 289 count--; 290 return e.value; 291 } 292 } 293 return null; 294 } 295 296 303 public void putAll(Map m) { 304 if (m == null) { 305 throw new NullPointerException (); 306 } 307 308 Iterator i = m.entrySet().iterator(); 309 while (i.hasNext()) { 310 Map.Entry me = (Map.Entry)i.next(); 311 put(me.getKey(), me.getValue()); 312 } 313 } 314 315 318 public void clear() { 319 if (count > 0) { 320 modCount++; 321 Entry[] copyOfEntries = entries; 322 for (int i = copyOfEntries.length; --i >= 0;) { 323 copyOfEntries[i] = null; 324 } 325 count = 0; 326 } 327 } 328 329 335 public Object clone() { 336 try { 337 Entry[] copyOfEntries = entries; 338 TopLinkIdentityHashMap clone = (TopLinkIdentityHashMap)super.clone(); 339 clone.entries = new Entry[copyOfEntries.length]; 340 for (int i = copyOfEntries.length; i-- > 0;) { 341 clone.entries[i] = (copyOfEntries[i] != null) ? (Entry)copyOfEntries[i].clone() : null; 342 } 343 clone.keySet = null; 344 clone.entrySet = null; 345 clone.values = null; 346 clone.modCount = 0; 347 return clone; 348 } catch (CloneNotSupportedException e) { 349 throw new InternalError (); 351 } 352 } 353 354 private transient Set keySet = null; 356 private transient Set entrySet = null; 357 private transient Collection values = null; 358 359 371 public Set keySet() { 372 if (keySet == null) { 373 keySet = new AbstractSet() { 374 public Iterator iterator() { 375 return getHashIterator(KEYS); 376 } 377 378 public int size() { 379 return count; 380 } 381 382 public boolean contains(Object o) { 383 return containsKey(o); 384 } 385 386 public boolean remove(Object o) { 387 int oldSize = count; 388 TopLinkIdentityHashMap.this.remove(o); 389 return count != oldSize; 390 } 391 392 public void clear() { 393 TopLinkIdentityHashMap.this.clear(); 394 } 395 }; 396 } 397 return keySet; 398 } 399 400 413 public Collection values() { 414 if (values == null) { 415 values = new AbstractCollection() { 416 public Iterator iterator() { 417 return getHashIterator(VALUES); 418 } 419 420 public int size() { 421 return count; 422 } 423 424 public boolean contains(Object o) { 425 return containsValue(o); 426 } 427 428 public void clear() { 429 TopLinkIdentityHashMap.this.clear(); 430 } 431 }; 432 } 433 return values; 434 } 435 436 450 public Set entrySet() { 451 if (entrySet == null) { 452 entrySet = new AbstractSet() { 453 public Iterator iterator() { 454 return getHashIterator(ENTRIES); 455 } 456 457 public boolean contains(Object o) { 458 if (!(o instanceof Map.Entry)) { 459 return false; 460 } 461 462 Map.Entry entry = (Map.Entry)o; 463 Object key = entry.getKey(); 464 Entry[] copyOfEntries = entries; 465 int hash = System.identityHashCode(key); 466 int index = (hash & 0x7FFFFFFF) % copyOfEntries.length; 467 for (Entry e = copyOfEntries[index]; e != null; e = e.next) { 468 if ((e.hash == hash) && e.equals(entry)) { 469 return true; 470 } 471 } 472 return false; 473 } 474 475 public boolean remove(Object o) { 476 if (!(o instanceof Map.Entry)) { 477 return false; 478 } 479 480 Map.Entry entry = (Map.Entry)o; 481 Object key = entry.getKey(); 482 Entry[] copyOfEntries = entries; 483 int hash = System.identityHashCode(key); 484 int index = (hash & 0x7FFFFFFF) % copyOfEntries.length; 485 for (Entry e = copyOfEntries[index], prev = null; e != null; 486 prev = e, e = e.next) { 487 if ((e.hash == hash) && e.equals(entry)) { 488 modCount++; 489 if (prev != null) { 490 prev.next = e.next; 491 } else { 492 copyOfEntries[index] = e.next; 493 } 494 count--; 495 e.value = null; 496 return true; 497 } 498 } 499 return false; 500 } 501 502 public int size() { 503 return count; 504 } 505 506 public void clear() { 507 TopLinkIdentityHashMap.this.clear(); 508 } 509 }; 510 } 511 return entrySet; 512 } 513 514 private Iterator getHashIterator(int type) { 515 if (count == 0) { 516 return emptyHashIterator; 517 } else { 518 return new HashIterator(type); 519 } 520 } 521 522 525 private static class Entry implements Map.Entry { 526 int hash; 527 Object key; 528 Object value; 529 Entry next; 530 531 Entry(int hash, Object key, Object value, Entry next) { 532 this.hash = hash; 533 this.key = key; 534 this.value = value; 535 this.next = next; 536 } 537 538 protected Object clone() { 539 return new Entry(hash, key, value, ((next == null) ? null : (Entry)next.clone())); 540 } 541 542 public Object getKey() { 544 return key; 545 } 546 547 public Object getValue() { 548 return value; 549 } 550 551 public Object setValue(Object value) { 552 Object oldValue = this.value; 553 this.value = value; 554 return oldValue; 555 } 556 557 public boolean equals(Object o) { 558 if (!(o instanceof Map.Entry)) { 559 return false; 560 } 561 562 Map.Entry e = (Map.Entry)o; 563 return (key == e.getKey()) && ((value == null) ? (e.getValue() == null) : value.equals(e.getValue())); 564 } 565 566 public int hashCode() { 567 return hash ^ ((value == null) ? 0 : value.hashCode()); 568 } 569 570 public String toString() { 571 return key + "=" + value; 572 } 573 } 574 575 private static final int KEYS = 0; 577 private static final int VALUES = 1; 578 private static final int ENTRIES = 2; 579 private static EmptyHashIterator emptyHashIterator = new EmptyHashIterator(); 580 581 private static class EmptyHashIterator implements Iterator { 582 EmptyHashIterator() { 583 } 584 585 public boolean hasNext() { 586 return false; 587 } 588 589 public Object next() { 590 throw new NoSuchElementException(); 591 } 592 593 public void remove() { 594 throw new IllegalStateException (); 595 } 596 } 597 598 private class HashIterator implements Iterator { 599 Entry[] entries = TopLinkIdentityHashMap.this.entries; 600 int index = entries.length; 601 Entry entry = null; 602 Entry lastReturned = null; 603 int type; 604 605 610 private int expectedModCount = modCount; 611 612 HashIterator(int type) { 613 this.type = type; 614 } 615 616 public boolean hasNext() { 617 Entry e = entry; 618 int i = index; 619 Entry[] copyOfEntries = TopLinkIdentityHashMap.this.entries; 620 while ((e == null) && (i > 0)) { 621 e = copyOfEntries[--i]; 622 } 623 entry = e; 624 index = i; 625 return e != null; 626 } 627 628 public Object next() { 629 if (modCount != expectedModCount) { 630 throw new ConcurrentModificationException(); 631 } 632 633 Entry et = entry; 634 int i = index; 635 Entry[] copyOfEntries = TopLinkIdentityHashMap.this.entries; 636 while ((et == null) && (i > 0)) { 637 et = copyOfEntries[--i]; 638 } 639 entry = et; 640 index = i; 641 if (et != null) { 642 Entry e = lastReturned = entry; 643 entry = e.next; 644 return (type == KEYS) ? e.key : ((type == VALUES) ? e.value : e); 645 } 646 throw new NoSuchElementException(); 647 } 648 649 public void remove() { 650 if (lastReturned == null) { 651 throw new IllegalStateException (); 652 } 653 if (modCount != expectedModCount) { 654 throw new ConcurrentModificationException(); 655 } 656 657 Entry[] copyOfEntries = TopLinkIdentityHashMap.this.entries; 658 int index = (lastReturned.hash & 0x7FFFFFFF) % copyOfEntries.length; 659 for (Entry e = copyOfEntries[index], prev = null; e != null; prev = e, e = e.next) { 660 if (e == lastReturned) { 661 modCount++; 662 expectedModCount++; 663 if (prev == null) { 664 copyOfEntries[index] = e.next; 665 } else { 666 prev.next = e.next; 667 } 668 count--; 669 lastReturned = null; 670 return; 671 } 672 } 673 throw new ConcurrentModificationException(); 674 } 675 } 676 677 685 private void writeObject(ObjectOutputStream s) throws IOException { 686 s.defaultWriteObject(); 688 689 s.writeInt(entries.length); 691 s.writeInt(count); 693 for (int i = entries.length - 1; i >= 0; i--) { 695 Entry entry = entries[i]; 696 while (entry != null) { 697 s.writeObject(entry.key); 698 s.writeObject(entry.value); 699 entry = entry.next; 700 } 701 } 702 } 703 704 707 private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException { 708 s.defaultReadObject(); 710 711 int numBuckets = s.readInt(); 713 entries = new Entry[numBuckets]; 714 int size = s.readInt(); 716 717 for (int i = 0; i < size; i++) { 719 Object key = s.readObject(); 720 Object value = s.readObject(); 721 put(key, value); 722 } 723 } 724 } 725 | Popular Tags |