1 16 17 package org.cojen.util; 18 19 import java.lang.ref.Reference ; 20 import java.lang.ref.ReferenceQueue ; 21 import java.lang.ref.WeakReference ; 22 23 import java.util.AbstractCollection ; 24 import java.util.AbstractMap ; 25 import java.util.AbstractSet ; 26 import java.util.Collection ; 27 import java.util.Collections ; 28 import java.util.ConcurrentModificationException ; 29 import java.util.Iterator ; 30 import java.util.Map ; 31 import java.util.NoSuchElementException ; 32 import java.util.Set ; 33 34 53 public class WeakIdentityMap extends AbstractMap implements Map , Cloneable { 54 55 static final int KEYS = 0; 57 static final int VALUES = 1; 58 static final int ENTRIES = 2; 59 60 64 static String toString(Collection c) { 65 if (c.size() == 0) { 66 return "[]"; 67 } 68 StringBuffer buf = new StringBuffer (32 * c.size()); 69 buf.append('['); 70 71 Iterator it = c.iterator(); 72 boolean hasNext = it.hasNext(); 73 while (hasNext) { 74 Object obj = it.next(); 75 buf.append(obj == c ? "(this Collection)" : obj); 76 if (hasNext) { 77 buf.append(", "); 78 } 79 } 80 buf.append("]"); 81 return buf.toString(); 82 } 83 84 87 static String toString(Map m) { 88 if (m.size() == 0) { 89 return "{}"; 90 } 91 StringBuffer buf = new StringBuffer (32 * m.size()); 92 buf.append('{'); 93 94 Iterator it = m.entrySet().iterator(); 95 boolean hasNext = it.hasNext(); 96 while (hasNext) { 97 Map.Entry entry = (Map.Entry )it.next(); 98 Object key = entry.getKey(); 99 Object value = entry.getValue(); 100 buf.append(key == m ? "(this Map)" : key) 101 .append('=') 102 .append(value == m ? "(this Map)" : value); 103 104 hasNext = it.hasNext(); 105 if (hasNext) { 106 buf.append(',').append(' '); 107 } 108 } 109 110 buf.append('}'); 111 return buf.toString(); 112 } 113 114 private transient Entry[] table; 115 private transient int count; 116 private int threshold; 117 private final float loadFactor; 118 private final ReferenceQueue queue; 119 private transient volatile int modCount; 120 121 123 private transient Set keySet; 124 private transient Set entrySet; 125 private transient Collection values; 126 127 public WeakIdentityMap(int initialCapacity, float loadFactor) { 128 if (initialCapacity <= 0) { 129 throw new IllegalArgumentException ("Initial capacity must be greater than 0"); 130 } 131 if (loadFactor <= 0 || Float.isNaN(loadFactor)) { 132 throw new IllegalArgumentException ("Load factor must be greater than 0"); 133 } 134 this.loadFactor = loadFactor; 135 this.table = new Entry[initialCapacity]; 136 this.threshold = (int)(initialCapacity * loadFactor); 137 this.queue = new ReferenceQueue (); 138 } 139 140 public WeakIdentityMap(int initialCapacity) { 141 this(initialCapacity, 0.75f); 142 } 143 144 public WeakIdentityMap() { 145 this(11, 0.75f); 146 } 147 148 public WeakIdentityMap(Map t) { 149 this(Math.max(2 * t.size(), 11), 0.75f); 150 putAll(t); 151 } 152 153 public int size() { 154 cleanup(); 156 return this.count; 157 } 158 159 public boolean isEmpty() { 160 return this.count == 0; 161 } 162 163 public boolean containsValue(Object value) { 164 Entry[] tab = this.table; 165 166 if (value == null) { 167 for (int i = tab.length ; i-- > 0 ;) { 168 for (Entry e = tab[i], prev = null; e != null; e = e.next) { 169 if (e.get() == null) { 170 this.modCount++; 172 if (prev != null) { 173 prev.next = e.next; 174 } else { 175 tab[i] = e.next; 176 } 177 this.count--; 178 } else if (e.value == null) { 179 return true; 180 } else { 181 prev = e; 182 } 183 } 184 } 185 } else { 186 for (int i = tab.length ; i-- > 0 ;) { 187 for (Entry e = tab[i], prev = null; e != null; e = e.next) { 188 if (e.get() == null) { 189 this.modCount++; 191 if (prev != null) { 192 prev.next = e.next; 193 } else { 194 tab[i] = e.next; 195 } 196 this.count--; 197 } else if (value.equals(e.value)) { 198 return true; 199 } else { 200 prev = e; 201 } 202 } 203 } 204 } 205 206 return false; 207 } 208 209 public boolean containsKey(Object key) { 210 if (key == null) { 211 key = KeyFactory.NULL; 212 } 213 214 Entry[] tab = this.table; 215 int hash = System.identityHashCode(key); 216 int index = (hash & 0x7fffffff) % tab.length; 217 218 for (Entry e = tab[index], prev = null; e != null; e = e.next) { 219 Object entryKey = e.get(); 220 221 if (entryKey == null) { 222 this.modCount++; 224 if (prev != null) { 225 prev.next = e.next; 226 } else { 227 tab[index] = e.next; 228 } 229 this.count--; 230 } else if (e.hash == hash && key == entryKey) { 231 return true; 232 } else { 233 prev = e; 234 } 235 } 236 237 return false; 238 } 239 240 public Object get(Object key) { 241 if (key == null) { 242 key = KeyFactory.NULL; 243 } 244 245 Entry[] tab = this.table; 246 int hash = System.identityHashCode(key); 247 int index = (hash & 0x7fffffff) % tab.length; 248 249 for (Entry e = tab[index], prev = null; e != null; e = e.next) { 250 Object entryKey = e.get(); 251 252 if (entryKey == null) { 253 this.modCount++; 255 if (prev != null) { 256 prev.next = e.next; 257 } else { 258 tab[index] = e.next; 259 } 260 this.count--; 261 } else if (e.hash == hash && key == entryKey) { 262 return e.value; 263 } else { 264 prev = e; 265 } 266 } 267 268 return null; 269 } 270 271 private void cleanup() { 272 Entry[] tab = this.table; 274 ReferenceQueue queue = this.queue; 275 Reference ref; 276 while ((ref = queue.poll()) != null) { 277 int index = (((Entry) ref).hash & 0x7fffffff) % tab.length; 280 for (Entry e = tab[index], prev = null; e != null; e = e.next) { 281 if (e.get() == null) { 282 this.modCount++; 283 if (prev != null) { 284 prev.next = e.next; 285 } else { 286 tab[index] = e.next; 287 } 288 this.count--; 289 } else { 290 prev = e; 291 } 292 } 293 } 294 } 295 296 private void rehash() { 297 int oldCapacity = this.table.length; 298 Entry[] oldMap = this.table; 299 300 int newCapacity = oldCapacity * 2 + 1; 301 if (newCapacity <= 0) { 302 if ((newCapacity = Integer.MAX_VALUE) == oldCapacity) { 304 return; 305 } 306 } 307 Entry[] newMap = new Entry[newCapacity]; 308 309 this.modCount++; 310 this.threshold = (int)(newCapacity * this.loadFactor); 311 this.table = newMap; 312 313 for (int i = oldCapacity ; i-- > 0 ;) { 314 for (Entry old = oldMap[i] ; old != null ; ) { 315 Entry e = old; 316 old = old.next; 317 318 if (e.get() == null) { 320 this.count--; 321 } else { 322 int index = (e.hash & 0x7fffffff) % newCapacity; 323 e.next = newMap[index]; 324 newMap[index] = e; 325 } 326 } 327 } 328 } 329 330 public Object put(Object key, Object value) { 331 if (key == null) { 332 key = KeyFactory.NULL; 333 } 334 335 cleanup(); 336 337 Entry[] tab = this.table; 339 int hash = System.identityHashCode(key); 340 int index = (hash & 0x7fffffff) % tab.length; 341 342 for (Entry e = tab[index], prev = null; e != null; e = e.next) { 343 Object entryKey = e.get(); 344 345 if (entryKey == null) { 346 this.modCount++; 348 if (prev != null) { 349 prev.next = e.next; 350 } else { 351 tab[index] = e.next; 352 } 353 this.count--; 354 } else if (e.hash == hash && key == entryKey) { 355 Object old = e.value; 356 e.value = value; 357 return old; 358 } else { 359 prev = e; 360 } 361 } 362 363 this.modCount++; 364 365 if (this.count >= this.threshold) { 366 rehash(); 368 tab = this.table; 369 index = (hash & 0x7fffffff) % tab.length; 370 } 371 372 Entry e = new Entry(hash, key, this.queue, value, tab[index]); 374 tab[index] = e; 375 this.count++; 376 return null; 377 } 378 379 public Object remove(Object key) { 380 if (key == null) { 381 key = KeyFactory.NULL; 382 } 383 384 Entry[] tab = this.table; 385 int hash = System.identityHashCode(key); 386 int index = (hash & 0x7fffffff) % tab.length; 387 388 for (Entry e = tab[index], prev = null; e != null; e = e.next) { 389 Object entryKey = e.get(); 390 391 if (entryKey == null) { 392 this.modCount++; 394 if (prev != null) { 395 prev.next = e.next; 396 } else { 397 tab[index] = e.next; 398 } 399 this.count--; 400 } else if (e.hash == hash && key == entryKey) { 401 this.modCount++; 402 if (prev != null) { 403 prev.next = e.next; 404 } else { 405 tab[index] = e.next; 406 } 407 this.count--; 408 409 Object oldValue = e.value; 410 e.value = null; 411 return oldValue; 412 } else { 413 prev = e; 414 } 415 } 416 417 return null; 418 } 419 420 public void putAll(Map t) { 421 Iterator i = t.entrySet().iterator(); 422 while (i.hasNext()) { 423 Map.Entry e = (Map.Entry ) i.next(); 424 put(e.getKey(), e.getValue()); 425 } 426 } 427 428 public void clear() { 429 Entry[] tab = this.table; 430 this.modCount++; 431 for (int index = tab.length; --index >= 0; ) { 432 tab[index] = null; 433 } 434 this.count = 0; 435 } 436 437 public Object clone() { 438 try { 439 WeakIdentityMap t = (WeakIdentityMap)super.clone(); 440 t.table = new Entry[this.table.length]; 441 for (int i = this.table.length ; i-- > 0 ; ) { 442 t.table[i] = (this.table[i] != null) 443 ? (Entry)this.table[i].copy(this.queue) : null; 444 } 445 t.keySet = null; 446 t.entrySet = null; 447 t.values = null; 448 t.modCount = 0; 449 return t; 450 } 451 catch (CloneNotSupportedException e) { 452 throw new InternalError (); 454 } 455 } 456 457 public Set keySet() { 458 if (this.keySet == null) { 459 this.keySet = new AbstractSet () { 460 public Iterator iterator() { 461 return createHashIterator(KEYS); 462 } 463 public int size() { 464 return WeakIdentityMap.this.count; 465 } 466 public boolean contains(Object o) { 467 return containsKey(o); 468 } 469 public boolean remove(Object o) { 470 return o == null ? false : WeakIdentityMap.this.remove(o) == o; 471 } 472 public void clear() { 473 WeakIdentityMap.this.clear(); 474 } 475 public String toString() { 476 return WeakIdentityMap.this.toString(this); 477 } 478 }; 479 } 480 return this.keySet; 481 } 482 483 public Collection values() { 484 if (this.values==null) { 485 this.values = new AbstractCollection () { 486 public Iterator iterator() { 487 return createHashIterator(VALUES); 488 } 489 public int size() { 490 return WeakIdentityMap.this.count; 491 } 492 public boolean contains(Object o) { 493 return containsValue(o); 494 } 495 public void clear() { 496 WeakIdentityMap.this.clear(); 497 } 498 public String toString() { 499 return WeakIdentityMap.this.toString(this); 500 } 501 }; 502 } 503 return this.values; 504 } 505 506 public Set entrySet() { 507 if (this.entrySet==null) { 508 this.entrySet = new AbstractSet () { 509 public Iterator iterator() { 510 return createHashIterator(ENTRIES); 511 } 512 513 public boolean contains(Object o) { 514 if (!(o instanceof Map.Entry )) { 515 return false; 516 } 517 Map.Entry entry = (Map.Entry )o; 518 Object key = entry.getKey(); 519 520 Entry[] tab = WeakIdentityMap.this.table; 521 int hash = System.identityHashCode(key); 522 int index = (hash & 0x7fffffff) % tab.length; 523 524 for (Entry e = tab[index], prev = null; e != null; e = e.next) { 525 Object entryKey = e.get(); 526 527 if (entryKey == null) { 528 WeakIdentityMap.this.modCount++; 530 if (prev != null) { 531 prev.next = e.next; 532 } else { 533 tab[index] = e.next; 534 } 535 WeakIdentityMap.this.count--; 536 } else if (e.hash == hash && e.equals(entry)) { 537 return true; 538 } else { 539 prev = e; 540 } 541 } 542 543 return false; 544 } 545 546 public boolean remove(Object o) { 547 if (!(o instanceof Map.Entry )) { 548 return false; 549 } 550 Map.Entry entry = (Map.Entry )o; 551 Object key = entry.getKey(); 552 Entry[] tab = WeakIdentityMap.this.table; 553 int hash = System.identityHashCode(key); 554 int index = (hash & 0x7fffffff) % tab.length; 555 556 for (Entry e = tab[index], prev = null; e != null; e = e.next) { 557 if (e.get() == null) { 558 WeakIdentityMap.this.modCount++; 560 if (prev != null) { 561 prev.next = e.next; 562 } else { 563 tab[index] = e.next; 564 } 565 WeakIdentityMap.this.count--; 566 } else if (e.hash == hash && e.equals(entry)) { 567 WeakIdentityMap.this.modCount++; 568 if (prev != null) { 569 prev.next = e.next; 570 } else { 571 tab[index] = e.next; 572 } 573 WeakIdentityMap.this.count--; 574 575 e.value = null; 576 return true; 577 } else { 578 prev = e; 579 } 580 } 581 return false; 582 } 583 584 public int size() { 585 return WeakIdentityMap.this.count; 586 } 587 588 public void clear() { 589 WeakIdentityMap.this.clear(); 590 } 591 592 public String toString() { 593 return WeakIdentityMap.toString(this); 594 } 595 }; 596 } 597 598 return this.entrySet; 599 } 600 601 606 public String toString() { 607 return toString(this); 608 } 609 610 private Iterator createHashIterator(int type) { 611 if (this.count == 0) { 612 return Collections.EMPTY_SET.iterator(); 613 } else { 614 return new HashIterator(type); 615 } 616 } 617 618 621 private static class Entry extends WeakReference implements Map.Entry { 622 int hash; 623 Object value; 624 Entry next; 625 626 Entry(int hash, Object key, ReferenceQueue queue, Object value, Entry next) { 627 super(key, queue); 628 this.hash = hash; 629 this.value = value; 630 this.next = next; 631 } 632 633 public void clear() { 634 } 637 638 public Object getKey() { 639 Object key = Entry.this.get(); 640 return key == KeyFactory.NULL ? null : key; 641 } 642 643 public Object getValue() { 644 return this.value; 645 } 646 647 public Object setValue(Object value) { 648 Object oldValue = this.value; 649 this.value = value; 650 return oldValue; 651 } 652 653 public boolean equals(Object obj) { 654 if (!(obj instanceof Map.Entry )) { 655 return false; 656 } 657 return equals((Map.Entry )obj); 658 } 659 660 boolean equals(Map.Entry e) { 661 Object thisKey = get(); 662 if (thisKey == null) { 663 return false; 664 } else if (thisKey == KeyFactory.NULL) { 665 thisKey = null; 666 } 667 return (thisKey == e.getKey()) && 668 (this.value == null ? e.getValue() == null : this.value.equals(e.getValue())); 669 } 670 671 public int hashCode() { 672 return this.hash ^ (this.value == null ? 0 : this.value.hashCode()); 673 } 674 675 public String toString() { 676 return getKey() + "=" + this.value; 677 } 678 679 protected Object copy(ReferenceQueue queue) { 680 return new Entry(this.hash, get(), queue, this.value, 681 (this.next == null ? null : (Entry)this.next.copy(queue))); 682 } 683 } 684 685 private class HashIterator implements Iterator { 686 private final int type; 687 private final Entry[] table; 688 689 private int index; 690 691 Object entryKey; 695 Entry entry; 696 697 Entry last; 698 699 704 private int expectedModCount = WeakIdentityMap.this.modCount; 705 706 HashIterator(int type) { 707 this.table = WeakIdentityMap.this.table; 708 this.type = type; 709 this.index = table.length; 710 } 711 712 public boolean hasNext() { 713 while (this.entry == null || (this.entryKey = this.entry.get()) == null) { 714 if (this.entry != null) { 715 remove(this.entry); 717 this.entry = this.entry.next; 718 } 719 else { 720 if (this.index <= 0) { 721 return false; 722 } 723 else { 724 this.entry = this.table[--this.index]; 725 } 726 } 727 } 728 729 return true; 730 } 731 732 public Object next() { 733 if (WeakIdentityMap.this.modCount != this.expectedModCount) { 734 throw new ConcurrentModificationException (); 735 } 736 737 if (!hasNext()) { 738 throw new NoSuchElementException (); 739 } 740 741 this.last = this.entry; 742 this.entry = this.entry.next; 743 744 return this.type == KEYS ? this.last.getKey() : 745 (this.type == VALUES ? this.last.getValue() : this.last); 746 } 747 748 public void remove() { 749 if (this.last == null) { 750 throw new IllegalStateException (); 751 } 752 if (WeakIdentityMap.this.modCount != this.expectedModCount) { 753 throw new ConcurrentModificationException (); 754 } 755 remove(this.last); 756 this.last = null; 757 } 758 759 private void remove(Entry toRemove) { 760 Entry[] tab = this.table; 761 int index = (toRemove.hash & 0x7fffffff) % tab.length; 762 763 for (Entry e = tab[index], prev = null; e != null; e = e.next) { 764 if (e == toRemove) { 765 WeakIdentityMap.this.modCount++; 766 expectedModCount++; 767 if (prev == null) { 768 tab[index] = e.next; 769 } else { 770 prev.next = e.next; 771 } 772 WeakIdentityMap.this.count--; 773 return; 774 } else { 775 prev = e; 776 } 777 } 778 779 throw new ConcurrentModificationException (); 780 } 781 782 public String toString() { 783 if (this.last != null) { 784 return "Iterator[" + this.last + ']'; 785 } else { 786 return "Iterator[]"; 787 } 788 } 789 } 790 } 791 | Popular Tags |