| 1 | package felix.util; |
| 2 | |
| 3 | /* |
| 4 | * Copyright 2009 Google Inc. |
| 5 | * |
| 6 | * Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| 7 | * use this file except in compliance with the License. You may obtain a copy of |
| 8 | * the License at |
| 9 | * |
| 10 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 11 | * |
| 12 | * Unless required by applicable law or agreed to in writing, software |
| 13 | * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| 14 | * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| 15 | * License for the specific language governing permissions and limitations under |
| 16 | * the License. |
| 17 | */ |
| 18 | |
| 19 | import java.io.IOException; |
| 20 | import java.io.ObjectInputStream; |
| 21 | import java.io.ObjectOutputStream; |
| 22 | import java.io.Serializable; |
| 23 | import java.util.AbstractCollection; |
| 24 | import java.util.AbstractSet; |
| 25 | import java.util.Collection; |
| 26 | import java.util.Iterator; |
| 27 | import java.util.Map; |
| 28 | import java.util.NoSuchElementException; |
| 29 | import java.util.Set; |
| 30 | |
| 31 | /** |
| 32 | * A memory-efficient hash map. |
| 33 | * |
| 34 | * @param <K> the key type |
| 35 | * @param <V> the value type |
| 36 | */ |
| 37 | public class MemoryFriendlyHashMap<K, V> implements Map<K, V>, Serializable { |
| 38 | |
| 39 | /** |
| 40 | * In the interest of memory-savings, we start with the smallest feasible |
| 41 | * power-of-two table size that can hold three items without rehashing. If we |
| 42 | * started with a size of 2, we'd have to expand as soon as the second item |
| 43 | * was added. |
| 44 | */ |
| 45 | private static final int INITIAL_TABLE_SIZE = 4; |
| 46 | |
| 47 | private class EntryIterator implements Iterator<Entry<K, V>> { |
| 48 | private int index = 0; |
| 49 | private int last = -1; |
| 50 | |
| 51 | { |
| 52 | advanceToItem(); |
| 53 | } |
| 54 | |
| 55 | /** |
| 56 | * Returns true if there is another key. |
| 57 | */ |
| 58 | public boolean hasNext() { |
| 59 | return index < keys.length; |
| 60 | } |
| 61 | |
| 62 | /** |
| 63 | * Returns next key-value pair. |
| 64 | */ |
| 65 | public Entry<K, V> next() { |
| 66 | if (!hasNext()) { |
| 67 | throw new NoSuchElementException(); |
| 68 | } |
| 69 | last = index; |
| 70 | Entry<K, V> toReturn = new HashEntry(index++); |
| 71 | advanceToItem(); |
| 72 | return toReturn; |
| 73 | } |
| 74 | |
| 75 | /** |
| 76 | * Removes last key-value pair. |
| 77 | */ |
| 78 | public void remove() { |
| 79 | if (last < 0) { |
| 80 | throw new IllegalStateException(); |
| 81 | } |
| 82 | internalRemove(last); |
| 83 | if (keys[last] != null) { |
| 84 | index = last; |
| 85 | } |
| 86 | last = -1; |
| 87 | } |
| 88 | |
| 89 | /** |
| 90 | * Advances to next key. |
| 91 | */ |
| 92 | private void advanceToItem() { |
| 93 | for (; index < keys.length; ++index) { |
| 94 | if (keys[index] != null) { |
| 95 | return; |
| 96 | } |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | /** |
| 102 | * Represents a set of key-value pairs. |
| 103 | */ |
| 104 | private class EntrySet extends AbstractSet<Entry<K, V>> { |
| 105 | /** |
| 106 | * Adds key-value pair to set. |
| 107 | */ |
| 108 | @Override |
| 109 | public boolean add(Entry<K, V> entry) { |
| 110 | boolean result = !MemoryFriendlyHashMap.this.containsKey(entry.getKey()); |
| 111 | MemoryFriendlyHashMap.this.put(entry.getKey(), entry.getValue()); |
| 112 | return result; |
| 113 | } |
| 114 | |
| 115 | /** |
| 116 | * Adds all key-value pairs to set. |
| 117 | */ |
| 118 | @Override |
| 119 | public boolean addAll(Collection<? extends Entry<K, V>> c) { |
| 120 | MemoryFriendlyHashMap.this.ensureSizeFor(size() + c.size()); |
| 121 | return super.addAll(c); |
| 122 | } |
| 123 | |
| 124 | /** |
| 125 | * Clears set. |
| 126 | */ |
| 127 | @Override |
| 128 | public void clear() { |
| 129 | MemoryFriendlyHashMap.this.clear(); |
| 130 | } |
| 131 | |
| 132 | /** |
| 133 | * Returns true if set contains given object. |
| 134 | */ |
| 135 | @Override |
| 136 | @SuppressWarnings("unchecked") |
| 137 | public boolean contains(Object o) { |
| 138 | if (!(o instanceof Entry)) { |
| 139 | return false; |
| 140 | } |
| 141 | Entry<K, V> entry = (Entry<K, V>) o; |
| 142 | V value = MemoryFriendlyHashMap.this.get(entry.getKey()); |
| 143 | return MemoryFriendlyHashMap.this.valueEquals(value, entry.getValue()); |
| 144 | } |
| 145 | |
| 146 | /** |
| 147 | * Returns hash code of set. |
| 148 | */ |
| 149 | @Override |
| 150 | public int hashCode() { |
| 151 | return MemoryFriendlyHashMap.this.hashCode(); |
| 152 | } |
| 153 | |
| 154 | /** |
| 155 | * Returns iterator for set. |
| 156 | */ |
| 157 | @Override |
| 158 | public Iterator<java.util.Map.Entry<K, V>> iterator() { |
| 159 | return new EntryIterator(); |
| 160 | } |
| 161 | |
| 162 | /** |
| 163 | * Removes given object from set. |
| 164 | */ |
| 165 | @Override |
| 166 | @SuppressWarnings("unchecked") |
| 167 | public boolean remove(Object o) { |
| 168 | if (!(o instanceof Entry)) { |
| 169 | return false; |
| 170 | } |
| 171 | Entry<K, V> entry = (Entry<K, V>) o; |
| 172 | int index = findKey(entry.getKey()); |
| 173 | if (index >= 0 && valueEquals(values[index], entry.getValue())) { |
| 174 | internalRemove(index); |
| 175 | return true; |
| 176 | } |
| 177 | return false; |
| 178 | } |
| 179 | |
| 180 | /** |
| 181 | * Removes all given objects from set. |
| 182 | */ |
| 183 | @Override |
| 184 | public boolean removeAll(Collection<?> c) { |
| 185 | boolean didRemove = false; |
| 186 | for (Object o : c) { |
| 187 | didRemove |= remove(o); |
| 188 | } |
| 189 | return didRemove; |
| 190 | } |
| 191 | |
| 192 | /** |
| 193 | * Returns size of set. |
| 194 | */ |
| 195 | @Override |
| 196 | public int size() { |
| 197 | return MemoryFriendlyHashMap.this.size; |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | /** |
| 202 | * Represents a key-value pair in a hashmap. |
| 203 | */ |
| 204 | private class HashEntry implements Entry<K, V> { |
| 205 | private final int index; |
| 206 | |
| 207 | /** |
| 208 | * The constructor. |
| 209 | * @param index |
| 210 | */ |
| 211 | public HashEntry(int index) { |
| 212 | this.index = index; |
| 213 | } |
| 214 | |
| 215 | /** |
| 216 | * Returns true if this entry equals the given object. |
| 217 | */ |
| 218 | @Override |
| 219 | @SuppressWarnings("unchecked") |
| 220 | public boolean equals(Object o) { |
| 221 | if (!(o instanceof Entry)) { |
| 222 | return false; |
| 223 | } |
| 224 | Entry<K, V> entry = (Entry<K, V>) o; |
| 225 | return keyEquals(getKey(), entry.getKey()) |
| 226 | && valueEquals(getValue(), entry.getValue()); |
| 227 | } |
| 228 | |
| 229 | /** |
| 230 | * Returns key. |
| 231 | */ |
| 232 | @SuppressWarnings("unchecked") |
| 233 | public K getKey() { |
| 234 | return (K) unmaskNullKey(keys[index]); |
| 235 | } |
| 236 | |
| 237 | /** |
| 238 | * Returns value. |
| 239 | */ |
| 240 | @SuppressWarnings("unchecked") |
| 241 | public V getValue() { |
| 242 | return (V) values[index]; |
| 243 | } |
| 244 | |
| 245 | /** |
| 246 | * Returns hash code. |
| 247 | */ |
| 248 | @Override |
| 249 | public int hashCode() { |
| 250 | return keyHashCode(getKey()) ^ valueHashCode(getValue()); |
| 251 | } |
| 252 | |
| 253 | /** |
| 254 | * Sets value to given value. |
| 255 | */ |
| 256 | @SuppressWarnings("unchecked") |
| 257 | public V setValue(V value) { |
| 258 | V previous = (V) values[index]; |
| 259 | values[index] = value; |
| 260 | return previous; |
| 261 | } |
| 262 | |
| 263 | /** |
| 264 | * Returns string representation of entry. |
| 265 | */ |
| 266 | @Override |
| 267 | public String toString() { |
| 268 | return getKey() + "=" + getValue(); |
| 269 | } |
| 270 | } |
| 271 | |
| 272 | /** |
| 273 | * Iterator for keys. |
| 274 | */ |
| 275 | private class KeyIterator implements Iterator<K> { |
| 276 | private int index = 0; |
| 277 | private int last = -1; |
| 278 | |
| 279 | { |
| 280 | advanceToItem(); |
| 281 | } |
| 282 | |
| 283 | /** |
| 284 | * Returns true if there is another key. |
| 285 | */ |
| 286 | public boolean hasNext() { |
| 287 | return index < keys.length; |
| 288 | } |
| 289 | |
| 290 | /** |
| 291 | * Returns next key. |
| 292 | */ |
| 293 | @SuppressWarnings("unchecked") |
| 294 | public K next() { |
| 295 | if (!hasNext()) { |
| 296 | throw new NoSuchElementException(); |
| 297 | } |
| 298 | last = index; |
| 299 | Object toReturn = unmaskNullKey(keys[index++]); |
| 300 | advanceToItem(); |
| 301 | return (K) toReturn; |
| 302 | } |
| 303 | |
| 304 | /** |
| 305 | * Removes last key. |
| 306 | */ |
| 307 | public void remove() { |
| 308 | if (last < 0) { |
| 309 | throw new IllegalStateException(); |
| 310 | } |
| 311 | internalRemove(last); |
| 312 | if (keys[last] != null) { |
| 313 | index = last; |
| 314 | } |
| 315 | last = -1; |
| 316 | } |
| 317 | |
| 318 | /** |
| 319 | * Advances to next key. |
| 320 | */ |
| 321 | private void advanceToItem() { |
| 322 | for (; index < keys.length; ++index) { |
| 323 | if (keys[index] != null) { |
| 324 | return; |
| 325 | } |
| 326 | } |
| 327 | } |
| 328 | } |
| 329 | |
| 330 | /** |
| 331 | * Represents a set of keys |
| 332 | */ |
| 333 | private class KeySet extends AbstractSet<K> { |
| 334 | |
| 335 | /** |
| 336 | * Clears all keys. |
| 337 | */ |
| 338 | @Override |
| 339 | public void clear() { |
| 340 | MemoryFriendlyHashMap.this.clear(); |
| 341 | } |
| 342 | |
| 343 | /** |
| 344 | * Returns true if this set contains given object. |
| 345 | */ |
| 346 | @Override |
| 347 | public boolean contains(Object o) { |
| 348 | return MemoryFriendlyHashMap.this.containsKey(o); |
| 349 | } |
| 350 | |
| 351 | /** |
| 352 | * Returns hash code for set. |
| 353 | */ |
| 354 | @Override |
| 355 | public int hashCode() { |
| 356 | int result = 0; |
| 357 | for (int i = 0; i < keys.length; ++i) { |
| 358 | Object key = keys[i]; |
| 359 | if (key != null) { |
| 360 | result += keyHashCode(unmaskNullKey(key)); |
| 361 | } |
| 362 | } |
| 363 | return result; |
| 364 | } |
| 365 | |
| 366 | /** |
| 367 | * Returns iterator for set. |
| 368 | */ |
| 369 | @Override |
| 370 | public Iterator<K> iterator() { |
| 371 | return new KeyIterator(); |
| 372 | } |
| 373 | |
| 374 | /** |
| 375 | * Removes given object from set. |
| 376 | */ |
| 377 | @Override |
| 378 | public boolean remove(Object o) { |
| 379 | int index = findKey(o); |
| 380 | if (index >= 0) { |
| 381 | internalRemove(index); |
| 382 | return true; |
| 383 | } |
| 384 | return false; |
| 385 | } |
| 386 | |
| 387 | /** |
| 388 | * Remove all given objects from set. |
| 389 | */ |
| 390 | @Override |
| 391 | public boolean removeAll(Collection<?> c) { |
| 392 | boolean didRemove = false; |
| 393 | for (Object o : c) { |
| 394 | didRemove |= remove(o); |
| 395 | } |
| 396 | return didRemove; |
| 397 | } |
| 398 | |
| 399 | /** |
| 400 | * Returns size of set. |
| 401 | */ |
| 402 | @Override |
| 403 | public int size() { |
| 404 | return MemoryFriendlyHashMap.this.size; |
| 405 | } |
| 406 | } |
| 407 | |
| 408 | /** |
| 409 | * Represents an iterator for values. |
| 410 | */ |
| 411 | private class ValueIterator implements Iterator<V> { |
| 412 | private int index = 0; |
| 413 | private int last = -1; |
| 414 | |
| 415 | { |
| 416 | advanceToItem(); |
| 417 | } |
| 418 | |
| 419 | /** |
| 420 | * Returns true if there is another value. |
| 421 | */ |
| 422 | public boolean hasNext() { |
| 423 | return index < keys.length; |
| 424 | } |
| 425 | |
| 426 | /** |
| 427 | * Returns next value. |
| 428 | */ |
| 429 | @SuppressWarnings("unchecked") |
| 430 | public V next() { |
| 431 | if (!hasNext()) { |
| 432 | throw new NoSuchElementException(); |
| 433 | } |
| 434 | last = index; |
| 435 | Object toReturn = values[index++]; |
| 436 | advanceToItem(); |
| 437 | return (V) toReturn; |
| 438 | } |
| 439 | |
| 440 | /** |
| 441 | * Removes last value. |
| 442 | */ |
| 443 | public void remove() { |
| 444 | if (last < 0) { |
| 445 | throw new IllegalStateException(); |
| 446 | } |
| 447 | internalRemove(last); |
| 448 | if (keys[last] != null) { |
| 449 | index = last; |
| 450 | } |
| 451 | last = -1; |
| 452 | } |
| 453 | |
| 454 | /** |
| 455 | * Advance to next value. |
| 456 | */ |
| 457 | private void advanceToItem() { |
| 458 | for (; index < keys.length; ++index) { |
| 459 | if (keys[index] != null) { |
| 460 | return; |
| 461 | } |
| 462 | } |
| 463 | } |
| 464 | } |
| 465 | |
| 466 | /** |
| 467 | * Represents a collection of values. |
| 468 | */ |
| 469 | private class Values extends AbstractCollection<V> { |
| 470 | |
| 471 | /** |
| 472 | * Clears all values. |
| 473 | */ |
| 474 | @Override |
| 475 | public void clear() { |
| 476 | MemoryFriendlyHashMap.this.clear(); |
| 477 | } |
| 478 | |
| 479 | /** |
| 480 | * Returns true if this contains the given object. |
| 481 | */ |
| 482 | @Override |
| 483 | public boolean contains(Object o) { |
| 484 | return MemoryFriendlyHashMap.this.containsValue(o); |
| 485 | } |
| 486 | |
| 487 | /** |
| 488 | * Returns hash code. |
| 489 | */ |
| 490 | @Override |
| 491 | public int hashCode() { |
| 492 | int result = 0; |
| 493 | for (int i = 0; i < keys.length; ++i) { |
| 494 | if (keys[i] != null) { |
| 495 | result += valueHashCode(values[i]); |
| 496 | } |
| 497 | } |
| 498 | return result; |
| 499 | } |
| 500 | |
| 501 | /** |
| 502 | * Returns iterator. |
| 503 | */ |
| 504 | @Override |
| 505 | public Iterator<V> iterator() { |
| 506 | return new ValueIterator(); |
| 507 | } |
| 508 | |
| 509 | /** |
| 510 | * Removes given object. |
| 511 | */ |
| 512 | @Override |
| 513 | public boolean remove(Object o) { |
| 514 | if (o == null) { |
| 515 | for (int i = 0; i < keys.length; ++i) { |
| 516 | if (keys[i] != null && values[i] == null) { |
| 517 | internalRemove(i); |
| 518 | return true; |
| 519 | } |
| 520 | } |
| 521 | } else { |
| 522 | for (int i = 0; i < keys.length; ++i) { |
| 523 | if (valueEquals(values[i], o)) { |
| 524 | internalRemove(i); |
| 525 | return true; |
| 526 | } |
| 527 | } |
| 528 | } |
| 529 | return false; |
| 530 | } |
| 531 | |
| 532 | /** |
| 533 | * Remove all given objects. |
| 534 | */ |
| 535 | @Override |
| 536 | public boolean removeAll(Collection<?> c) { |
| 537 | boolean didRemove = false; |
| 538 | for (Object o : c) { |
| 539 | didRemove |= remove(o); |
| 540 | } |
| 541 | return didRemove; |
| 542 | } |
| 543 | |
| 544 | @Override |
| 545 | public int size() { |
| 546 | return MemoryFriendlyHashMap.this.size; |
| 547 | } |
| 548 | } |
| 549 | |
| 550 | private static final Object NULL_KEY = new Serializable() { |
| 551 | Object readResolve() { |
| 552 | return NULL_KEY; |
| 553 | } |
| 554 | }; |
| 555 | |
| 556 | /** |
| 557 | * Returns masked version of NULL key. |
| 558 | * @param k |
| 559 | * @return |
| 560 | */ |
| 561 | static Object maskNullKey(Object k) { |
| 562 | return (k == null) ? NULL_KEY : k; |
| 563 | } |
| 564 | |
| 565 | /** |
| 566 | * Returns unmasked version of NULL key. |
| 567 | * @param k |
| 568 | * @return |
| 569 | */ |
| 570 | static Object unmaskNullKey(Object k) { |
| 571 | return (k == NULL_KEY) ? null : k; |
| 572 | } |
| 573 | |
| 574 | /** |
| 575 | * Backing store for all the keys; transient due to custom serialization. |
| 576 | * Default access to avoid synthetic accessors from inner classes. |
| 577 | */ |
| 578 | transient Object[] keys; |
| 579 | |
| 580 | /** |
| 581 | * Number of pairs in this set; transient due to custom serialization. Default |
| 582 | * access to avoid synthetic accessors from inner classes. |
| 583 | */ |
| 584 | transient int size = 0; |
| 585 | |
| 586 | /** |
| 587 | * Backing store for all the values; transient due to custom serialization. |
| 588 | * Default access to avoid synthetic accessors from inner classes. |
| 589 | */ |
| 590 | transient Object[] values; |
| 591 | |
| 592 | /** |
| 593 | * The constructor. |
| 594 | */ |
| 595 | public MemoryFriendlyHashMap() { |
| 596 | initTable(INITIAL_TABLE_SIZE); |
| 597 | } |
| 598 | |
| 599 | /** |
| 600 | * The constructor with a map. |
| 601 | * @param m |
| 602 | */ |
| 603 | public MemoryFriendlyHashMap(Map<? extends K, ? extends V> m) { |
| 604 | int newCapacity = INITIAL_TABLE_SIZE; |
| 605 | int expectedSize = m.size(); |
| 606 | while (newCapacity * 3 < expectedSize * 4) { |
| 607 | newCapacity <<= 1; |
| 608 | } |
| 609 | |
| 610 | initTable(newCapacity); |
| 611 | internalPutAll(m); |
| 612 | } |
| 613 | |
| 614 | /** |
| 615 | * Clears hashmap. |
| 616 | */ |
| 617 | public void clear() { |
| 618 | initTable(INITIAL_TABLE_SIZE); |
| 619 | size = 0; |
| 620 | } |
| 621 | |
| 622 | /** |
| 623 | * Returns true if this hashmap contains the given key. |
| 624 | */ |
| 625 | public boolean containsKey(Object key) { |
| 626 | return findKey(key) >= 0; |
| 627 | } |
| 628 | |
| 629 | /** |
| 630 | * Returns true if this hashmap contains the given value. |
| 631 | */ |
| 632 | public boolean containsValue(Object value) { |
| 633 | if (value == null) { |
| 634 | for (int i = 0; i < keys.length; ++i) { |
| 635 | if (keys[i] != null && values[i] == null) { |
| 636 | return true; |
| 637 | } |
| 638 | } |
| 639 | } else { |
| 640 | for (Object existing : values) { |
| 641 | if (valueEquals(existing, value)) { |
| 642 | return true; |
| 643 | } |
| 644 | } |
| 645 | } |
| 646 | return false; |
| 647 | } |
| 648 | |
| 649 | /** |
| 650 | * Returns the set of entries for this hashmap. |
| 651 | */ |
| 652 | public Set<Entry<K, V>> entrySet() { |
| 653 | return new EntrySet(); |
| 654 | } |
| 655 | |
| 656 | /** |
| 657 | * Returns true if this hashmap equals the given object. |
| 658 | */ |
| 659 | @Override |
| 660 | @SuppressWarnings("unchecked") |
| 661 | public boolean equals(Object o) { |
| 662 | if (!(o instanceof Map)) { |
| 663 | return false; |
| 664 | } |
| 665 | Map<K, V> other = (Map<K, V>) o; |
| 666 | return entrySet().equals(other.entrySet()); |
| 667 | } |
| 668 | |
| 669 | /** |
| 670 | * Returns value associated with the given key. |
| 671 | */ |
| 672 | @SuppressWarnings("unchecked") |
| 673 | public V get(Object key) { |
| 674 | int index = findKey(key); |
| 675 | return (index < 0) ? null : (V) values[index]; |
| 676 | } |
| 677 | |
| 678 | @Override |
| 679 | public int hashCode() { |
| 680 | int result = 0; |
| 681 | for (int i = 0; i < keys.length; ++i) { |
| 682 | Object key = keys[i]; |
| 683 | if (key != null) { |
| 684 | result += keyHashCode(unmaskNullKey(key)) ^ valueHashCode(values[i]); |
| 685 | } |
| 686 | } |
| 687 | return result; |
| 688 | } |
| 689 | |
| 690 | /** |
| 691 | * Returns true if this hashmap is empty. |
| 692 | */ |
| 693 | public boolean isEmpty() { |
| 694 | return size == 0; |
| 695 | } |
| 696 | |
| 697 | /** |
| 698 | * Returns the keyset for this hashmap. |
| 699 | */ |
| 700 | public Set<K> keySet() { |
| 701 | return new KeySet(); |
| 702 | } |
| 703 | |
| 704 | /** |
| 705 | * Adds the given key-value pair to this hashmap. |
| 706 | */ |
| 707 | @SuppressWarnings("unchecked") |
| 708 | public V put(K key, V value) { |
| 709 | ensureSizeFor(size + 1); |
| 710 | int index = findKeyOrEmpty(key); |
| 711 | if (keys[index] == null) { |
| 712 | ++size; |
| 713 | keys[index] = maskNullKey(key); |
| 714 | values[index] = value; |
| 715 | return null; |
| 716 | } else { |
| 717 | Object previousValue = values[index]; |
| 718 | values[index] = value; |
| 719 | return (V) previousValue; |
| 720 | } |
| 721 | } |
| 722 | |
| 723 | /** |
| 724 | * Adds all the given key-value pairs to this hashmap. |
| 725 | */ |
| 726 | public void putAll(Map<? extends K, ? extends V> m) { |
| 727 | ensureSizeFor(size + m.size()); |
| 728 | internalPutAll(m); |
| 729 | } |
| 730 | |
| 731 | /** |
| 732 | * Removes the key-value pair associated with the given key |
| 733 | * and return the value. |
| 734 | */ |
| 735 | @SuppressWarnings("unchecked") |
| 736 | public V remove(Object key) { |
| 737 | int index = findKey(key); |
| 738 | if (index < 0) { |
| 739 | return null; |
| 740 | } |
| 741 | Object previousValue = values[index]; |
| 742 | internalRemove(index); |
| 743 | return (V) previousValue; |
| 744 | } |
| 745 | |
| 746 | /** |
| 747 | * Returns the size of this hashmap. |
| 748 | */ |
| 749 | public int size() { |
| 750 | return size; |
| 751 | } |
| 752 | |
| 753 | /** |
| 754 | * Returns a string representation of this hashmap. |
| 755 | */ |
| 756 | @Override |
| 757 | public String toString() { |
| 758 | if (size == 0) { |
| 759 | return "{}"; |
| 760 | } |
| 761 | StringBuilder buf = new StringBuilder(32 * size()); |
| 762 | buf.append('{'); |
| 763 | |
| 764 | boolean needComma = false; |
| 765 | for (int i = 0; i < keys.length; ++i) { |
| 766 | Object key = keys[i]; |
| 767 | if (key != null) { |
| 768 | if (needComma) { |
| 769 | buf.append(',').append(' '); |
| 770 | } |
| 771 | key = unmaskNullKey(key); |
| 772 | Object value = values[i]; |
| 773 | buf.append(key == this ? "(this Map)" : key).append('=').append( |
| 774 | value == this ? "(this Map)" : value); |
| 775 | needComma = true; |
| 776 | } |
| 777 | } |
| 778 | buf.append('}'); |
| 779 | return buf.toString(); |
| 780 | } |
| 781 | |
| 782 | /** |
| 783 | * Returns the values in this hashmap. |
| 784 | */ |
| 785 | public Collection<V> values() { |
| 786 | return new Values(); |
| 787 | } |
| 788 | |
| 789 | /** |
| 790 | * Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}. |
| 791 | */ |
| 792 | @SuppressWarnings("unchecked") |
| 793 | protected void doReadObject(ObjectInputStream in) throws IOException, |
| 794 | ClassNotFoundException { |
| 795 | int capacity = in.readInt(); |
| 796 | initTable(capacity); |
| 797 | int items = in.readInt(); |
| 798 | for (int i = 0; i < items; i++) { |
| 799 | Object key = in.readObject(); |
| 800 | Object value = in.readObject(); |
| 801 | put((K) key, (V) value); |
| 802 | } |
| 803 | } |
| 804 | |
| 805 | /** |
| 806 | * Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}. |
| 807 | */ |
| 808 | protected void doWriteObject(ObjectOutputStream out) throws IOException { |
| 809 | out.writeInt(keys.length); |
| 810 | out.writeInt(size); |
| 811 | for (int i = 0; i < keys.length; ++i) { |
| 812 | Object key = keys[i]; |
| 813 | if (key != null) { |
| 814 | out.writeObject(unmaskNullKey(key)); |
| 815 | out.writeObject(values[i]); |
| 816 | } |
| 817 | } |
| 818 | } |
| 819 | |
| 820 | /** |
| 821 | * Returns whether two keys are equal for the purposes of this set. |
| 822 | */ |
| 823 | protected boolean keyEquals(Object a, Object b) { |
| 824 | return (a == null) ? (b == null) : a.equals(b); |
| 825 | } |
| 826 | |
| 827 | /** |
| 828 | * Returns the hashCode for a key. |
| 829 | */ |
| 830 | protected int keyHashCode(Object k) { |
| 831 | return (k == null) ? 0 : k.hashCode(); |
| 832 | } |
| 833 | |
| 834 | /** |
| 835 | * Returns whether two values are equal for the purposes of this set. |
| 836 | */ |
| 837 | protected boolean valueEquals(Object a, Object b) { |
| 838 | return (a == null) ? (b == null) : a.equals(b); |
| 839 | } |
| 840 | |
| 841 | /** |
| 842 | * Returns the hashCode for a value. |
| 843 | */ |
| 844 | protected int valueHashCode(Object v) { |
| 845 | return (v == null) ? 0 : v.hashCode(); |
| 846 | } |
| 847 | |
| 848 | /** |
| 849 | * Ensures the map is large enough to contain the specified number of entries. |
| 850 | * Default access to avoid synthetic accessors from inner classes. |
| 851 | */ |
| 852 | void ensureSizeFor(int expectedSize) { |
| 853 | if (keys.length * 3 >= expectedSize * 4) { |
| 854 | return; |
| 855 | } |
| 856 | |
| 857 | int newCapacity = keys.length << 1; |
| 858 | while (newCapacity * 3 < expectedSize * 4) { |
| 859 | newCapacity <<= 1; |
| 860 | } |
| 861 | |
| 862 | Object[] oldKeys = keys; |
| 863 | Object[] oldValues = values; |
| 864 | initTable(newCapacity); |
| 865 | for (int i = 0; i < oldKeys.length; ++i) { |
| 866 | Object k = oldKeys[i]; |
| 867 | if (k != null) { |
| 868 | int newIndex = getKeyIndex(unmaskNullKey(k)); |
| 869 | while (keys[newIndex] != null) { |
| 870 | if (++newIndex == keys.length) { |
| 871 | newIndex = 0; |
| 872 | } |
| 873 | } |
| 874 | keys[newIndex] = k; |
| 875 | values[newIndex] = oldValues[i]; |
| 876 | } |
| 877 | } |
| 878 | } |
| 879 | |
| 880 | /** |
| 881 | * Returns the index in the key table at which a particular key resides, or -1 |
| 882 | * if the key is not in the table. Default access to avoid synthetic accessors |
| 883 | * from inner classes. |
| 884 | */ |
| 885 | int findKey(Object k) { |
| 886 | int index = getKeyIndex(k); |
| 887 | while (true) { |
| 888 | Object existing = keys[index]; |
| 889 | if (existing == null) { |
| 890 | return -1; |
| 891 | } |
| 892 | if (keyEquals(k, unmaskNullKey(existing))) { |
| 893 | return index; |
| 894 | } |
| 895 | if (++index == keys.length) { |
| 896 | index = 0; |
| 897 | } |
| 898 | } |
| 899 | } |
| 900 | |
| 901 | /** |
| 902 | * Returns the index in the key table at which a particular key resides, or |
| 903 | * the index of an empty slot in the table where this key should be inserted |
| 904 | * if it is not already in the table. Default access to avoid synthetic |
| 905 | * accessors from inner classes. |
| 906 | */ |
| 907 | int findKeyOrEmpty(Object k) { |
| 908 | int index = getKeyIndex(k); |
| 909 | while (true) { |
| 910 | Object existing = keys[index]; |
| 911 | if (existing == null) { |
| 912 | return index; |
| 913 | } |
| 914 | if (keyEquals(k, unmaskNullKey(existing))) { |
| 915 | return index; |
| 916 | } |
| 917 | if (++index == keys.length) { |
| 918 | index = 0; |
| 919 | } |
| 920 | } |
| 921 | } |
| 922 | |
| 923 | /** |
| 924 | * Removes the entry at the specified index, and performs internal management |
| 925 | * to make sure we don't wind up with a hole in the table. Default access to |
| 926 | * avoid synthetic accessors from inner classes. |
| 927 | */ |
| 928 | void internalRemove(int index) { |
| 929 | keys[index] = null; |
| 930 | values[index] = null; |
| 931 | --size; |
| 932 | plugHole(index); |
| 933 | } |
| 934 | |
| 935 | private int getKeyIndex(Object k) { |
| 936 | int h = keyHashCode(k); |
| 937 | // Copied from Apache's AbstractHashedMap; prevents power-of-two collisions. |
| 938 | h += ~(h << 9); |
| 939 | h ^= (h >>> 14); |
| 940 | h += (h << 4); |
| 941 | h ^= (h >>> 10); |
| 942 | // Power of two trick. |
| 943 | return h & (keys.length - 1); |
| 944 | } |
| 945 | |
| 946 | private void initTable(int capacity) { |
| 947 | keys = new Object[capacity]; |
| 948 | values = new Object[capacity]; |
| 949 | } |
| 950 | |
| 951 | private void internalPutAll(Map<? extends K, ? extends V> m) { |
| 952 | for (Entry<? extends K, ? extends V> entry : m.entrySet()) { |
| 953 | K key = entry.getKey(); |
| 954 | V value = entry.getValue(); |
| 955 | int index = findKeyOrEmpty(key); |
| 956 | if (keys[index] == null) { |
| 957 | ++size; |
| 958 | keys[index] = maskNullKey(key); |
| 959 | values[index] = value; |
| 960 | } else { |
| 961 | values[index] = value; |
| 962 | } |
| 963 | } |
| 964 | } |
| 965 | |
| 966 | /** |
| 967 | * Tricky, we left a hole in the map, which we have to fill. The only way to |
| 968 | * do this is to search forwards through the map shuffling back values that |
| 969 | * match this index until we hit a null. |
| 970 | */ |
| 971 | private void plugHole(int hole) { |
| 972 | int index = hole + 1; |
| 973 | if (index == keys.length) { |
| 974 | index = 0; |
| 975 | } |
| 976 | while (keys[index] != null) { |
| 977 | int targetIndex = getKeyIndex(unmaskNullKey(keys[index])); |
| 978 | if (hole < index) { |
| 979 | /* |
| 980 | * "Normal" case, the index is past the hole and the "bad range" is from |
| 981 | * hole (exclusive) to index (inclusive). |
| 982 | */ |
| 983 | if (!(hole < targetIndex && targetIndex <= index)) { |
| 984 | // Plug it! |
| 985 | keys[hole] = keys[index]; |
| 986 | values[hole] = values[index]; |
| 987 | keys[index] = null; |
| 988 | values[index] = null; |
| 989 | hole = index; |
| 990 | } |
| 991 | } else { |
| 992 | /* |
| 993 | * "Wrapped" case, the index is before the hole (we've wrapped) and the |
| 994 | * "good range" is from index (exclusive) to hole (inclusive). |
| 995 | */ |
| 996 | if (index < targetIndex && targetIndex <= hole) { |
| 997 | // Plug it! |
| 998 | keys[hole] = keys[index]; |
| 999 | values[hole] = values[index]; |
| 1000 | keys[index] = null; |
| 1001 | values[index] = null; |
| 1002 | hole = index; |
| 1003 | } |
| 1004 | } |
| 1005 | if (++index == keys.length) { |
| 1006 | index = 0; |
| 1007 | } |
| 1008 | } |
| 1009 | } |
| 1010 | |
| 1011 | private void readObject(ObjectInputStream in) throws IOException, |
| 1012 | ClassNotFoundException { |
| 1013 | in.defaultReadObject(); |
| 1014 | doReadObject(in); |
| 1015 | } |
| 1016 | |
| 1017 | private void writeObject(ObjectOutputStream out) throws IOException { |
| 1018 | out.defaultWriteObject(); |
| 1019 | doWriteObject(out); |
| 1020 | } |
| 1021 | } |
| 1022 | |
| 1023 | |
| 1024 | |