001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections.map; 018 019 import java.util.AbstractCollection; 020 import java.util.AbstractSet; 021 import java.util.ArrayList; 022 import java.util.Collection; 023 import java.util.Iterator; 024 import java.util.Map; 025 import java.util.NoSuchElementException; 026 import java.util.Set; 027 028 import org.apache.commons.collections.KeyValue; 029 030 /** 031 * A StaticBucketMap is an efficient, thread-safe implementation of 032 * <code>java.util.Map</code> that performs well in in a highly 033 * thread-contentious environment. The map supports very efficient 034 * {@link #get(Object) get}, {@link #put(Object,Object) put}, 035 * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey} 036 * operations, assuming (approximate) uniform hashing and 037 * that the number of entries does not exceed the number of buckets. If the 038 * number of entries exceeds the number of buckets or if the hash codes of the 039 * objects are not uniformly distributed, these operations have a worst case 040 * scenario that is proportional to the number of elements in the map 041 * (<i>O(n)</i>).<p> 042 * 043 * Each bucket in the hash table has its own monitor, so two threads can 044 * safely operate on the map at the same time, often without incurring any 045 * monitor contention. This means that you don't have to wrap instances 046 * of this class with {@link java.util.Collections#synchronizedMap(Map)}; 047 * instances are already thread-safe. Unfortunately, however, this means 048 * that this map implementation behaves in ways you may find disconcerting. 049 * Bulk operations, such as {@link #putAll(Map) putAll} or the 050 * {@link Collection#retainAll(Collection) retainAll} operation in collection 051 * views, are <i>not</i> atomic. If two threads are simultaneously 052 * executing 053 * 054 * <pre> 055 * staticBucketMapInstance.putAll(map); 056 * </pre> 057 * 058 * and 059 * 060 * <pre> 061 * staticBucketMapInstance.entrySet().removeAll(map.entrySet()); 062 * </pre> 063 * 064 * then the results are generally random. Those two statement could cancel 065 * each other out, leaving <code>staticBucketMapInstance</code> essentially 066 * unchanged, or they could leave some random subset of <code>map</code> in 067 * <code>staticBucketMapInstance</code>.<p> 068 * 069 * Also, much like an encyclopedia, the results of {@link #size()} and 070 * {@link #isEmpty()} are out-of-date as soon as they are produced.<p> 071 * 072 * The iterators returned by the collection views of this class are <i>not</i> 073 * fail-fast. They will <i>never</i> raise a 074 * {@link java.util.ConcurrentModificationException}. Keys and values 075 * added to the map after the iterator is created do not necessarily appear 076 * during iteration. Similarly, the iterator does not necessarily fail to 077 * return keys and values that were removed after the iterator was created.<p> 078 * 079 * Finally, unlike {@link java.util.HashMap}-style implementations, this 080 * class <i>never</i> rehashes the map. The number of buckets is fixed 081 * at construction time and never altered. Performance may degrade if 082 * you do not allocate enough buckets upfront.<p> 083 * 084 * The {@link #atomic(Runnable)} method is provided to allow atomic iterations 085 * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic} 086 * will basically result in a map that's slower than an ordinary synchronized 087 * {@link java.util.HashMap}. 088 * 089 * Use this class if you do not require reliable bulk operations and 090 * iterations, or if you can make your own guarantees about how bulk 091 * operations will affect the map.<p> 092 * 093 * @since Commons Collections 3.0 (previously in main package v2.1) 094 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 095 * 096 * @author Berin Loritsch 097 * @author Gerhard Froehlich 098 * @author Michael A. Smith 099 * @author Paul Jack 100 * @author Leo Sutic 101 * @author Janek Bogucki 102 * @author Kazuya Ujihara 103 */ 104 public final class StaticBucketMap implements Map { 105 106 /** The default number of buckets to use */ 107 private static final int DEFAULT_BUCKETS = 255; 108 /** The array of buckets, where the actual data is held */ 109 private Node[] buckets; 110 /** The matching array of locks */ 111 private Lock[] locks; 112 113 /** 114 * Initializes the map with the default number of buckets (255). 115 */ 116 public StaticBucketMap() { 117 this(DEFAULT_BUCKETS); 118 } 119 120 /** 121 * Initializes the map with a specified number of buckets. The number 122 * of buckets is never below 17, and is always an odd number (StaticBucketMap 123 * ensures this). The number of buckets is inversely proportional to the 124 * chances for thread contention. The fewer buckets, the more chances for 125 * thread contention. The more buckets the fewer chances for thread 126 * contention. 127 * 128 * @param numBuckets the number of buckets for this map 129 */ 130 public StaticBucketMap(int numBuckets) { 131 int size = Math.max(17, numBuckets); 132 133 // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution) 134 if (size % 2 == 0) { 135 size--; 136 } 137 138 buckets = new Node[size]; 139 locks = new Lock[size]; 140 141 for (int i = 0; i < size; i++) { 142 locks[i] = new Lock(); 143 } 144 } 145 146 //----------------------------------------------------------------------- 147 /** 148 * Determine the exact hash entry for the key. The hash algorithm 149 * is rather simplistic, but it does the job: 150 * 151 * <pre> 152 * He = |Hk mod n| 153 * </pre> 154 * 155 * <p> 156 * He is the entry's hashCode, Hk is the key's hashCode, and n is 157 * the number of buckets. 158 * </p> 159 */ 160 private final int getHash(Object key) { 161 if (key == null) { 162 return 0; 163 } 164 int hash = key.hashCode(); 165 hash += ~(hash << 15); 166 hash ^= (hash >>> 10); 167 hash += (hash << 3); 168 hash ^= (hash >>> 6); 169 hash += ~(hash << 11); 170 hash ^= (hash >>> 16); 171 hash %= buckets.length; 172 return (hash < 0) ? hash * -1 : hash; 173 } 174 175 /** 176 * Gets the current size of the map. 177 * The value is computed fresh each time the method is called. 178 * 179 * @return the current size 180 */ 181 public int size() { 182 int cnt = 0; 183 184 for (int i = 0; i < buckets.length; i++) { 185 cnt += locks[i].size; 186 } 187 return cnt; 188 } 189 190 /** 191 * Checks if the size is currently zero. 192 * 193 * @return true if empty 194 */ 195 public boolean isEmpty() { 196 return (size() == 0); 197 } 198 199 /** 200 * Gets the value associated with the key. 201 * 202 * @param key the key to retrieve 203 * @return the associated value 204 */ 205 public Object get(final Object key) { 206 int hash = getHash(key); 207 208 synchronized (locks[hash]) { 209 Node n = buckets[hash]; 210 211 while (n != null) { 212 if (n.key == key || (n.key != null && n.key.equals(key))) { 213 return n.value; 214 } 215 216 n = n.next; 217 } 218 } 219 return null; 220 } 221 222 /** 223 * Checks if the map contains the specified key. 224 * 225 * @param key the key to check 226 * @return true if found 227 */ 228 public boolean containsKey(final Object key) { 229 int hash = getHash(key); 230 231 synchronized (locks[hash]) { 232 Node n = buckets[hash]; 233 234 while (n != null) { 235 if (n.key == key || (n.key != null && n.key.equals(key))) { 236 return true; 237 } 238 239 n = n.next; 240 } 241 } 242 return false; 243 } 244 245 /** 246 * Checks if the map contains the specified value. 247 * 248 * @param value the value to check 249 * @return true if found 250 */ 251 public boolean containsValue(final Object value) { 252 for (int i = 0; i < buckets.length; i++) { 253 synchronized (locks[i]) { 254 Node n = buckets[i]; 255 256 while (n != null) { 257 if (n.value == value || (n.value != null && n.value.equals(value))) { 258 return true; 259 } 260 261 n = n.next; 262 } 263 } 264 } 265 return false; 266 } 267 268 //----------------------------------------------------------------------- 269 /** 270 * Puts a new key value mapping into the map. 271 * 272 * @param key the key to use 273 * @param value the value to use 274 * @return the previous mapping for the key 275 */ 276 public Object put(final Object key, final Object value) { 277 int hash = getHash(key); 278 279 synchronized (locks[hash]) { 280 Node n = buckets[hash]; 281 282 if (n == null) { 283 n = new Node(); 284 n.key = key; 285 n.value = value; 286 buckets[hash] = n; 287 locks[hash].size++; 288 return null; 289 } 290 291 // Set n to the last node in the linked list. Check each key along the way 292 // If the key is found, then change the value of that node and return 293 // the old value. 294 for (Node next = n; next != null; next = next.next) { 295 n = next; 296 297 if (n.key == key || (n.key != null && n.key.equals(key))) { 298 Object returnVal = n.value; 299 n.value = value; 300 return returnVal; 301 } 302 } 303 304 // The key was not found in the current list of nodes, add it to the end 305 // in a new node. 306 Node newNode = new Node(); 307 newNode.key = key; 308 newNode.value = value; 309 n.next = newNode; 310 locks[hash].size++; 311 } 312 return null; 313 } 314 315 /** 316 * Removes the specified key from the map. 317 * 318 * @param key the key to remove 319 * @return the previous value at this key 320 */ 321 public Object remove(Object key) { 322 int hash = getHash(key); 323 324 synchronized (locks[hash]) { 325 Node n = buckets[hash]; 326 Node prev = null; 327 328 while (n != null) { 329 if (n.key == key || (n.key != null && n.key.equals(key))) { 330 // Remove this node from the linked list of nodes. 331 if (null == prev) { 332 // This node was the head, set the next node to be the new head. 333 buckets[hash] = n.next; 334 } else { 335 // Set the next node of the previous node to be the node after this one. 336 prev.next = n.next; 337 } 338 locks[hash].size--; 339 return n.value; 340 } 341 342 prev = n; 343 n = n.next; 344 } 345 } 346 return null; 347 } 348 349 //----------------------------------------------------------------------- 350 /** 351 * Gets the key set. 352 * 353 * @return the key set 354 */ 355 public Set keySet() { 356 return new KeySet(); 357 } 358 359 /** 360 * Gets the values. 361 * 362 * @return the values 363 */ 364 public Collection values() { 365 return new Values(); 366 } 367 368 /** 369 * Gets the entry set. 370 * 371 * @return the entry set 372 */ 373 public Set entrySet() { 374 return new EntrySet(); 375 } 376 377 //----------------------------------------------------------------------- 378 /** 379 * Puts all the entries from the specified map into this map. 380 * This operation is <b>not atomic</b> and may have undesired effects. 381 * 382 * @param map the map of entries to add 383 */ 384 public void putAll(Map map) { 385 Iterator i = map.keySet().iterator(); 386 387 while (i.hasNext()) { 388 Object key = i.next(); 389 put(key, map.get(key)); 390 } 391 } 392 393 /** 394 * Clears the map of all entries. 395 */ 396 public void clear() { 397 for (int i = 0; i < buckets.length; i++) { 398 Lock lock = locks[i]; 399 synchronized (lock) { 400 buckets[i] = null; 401 lock.size = 0; 402 } 403 } 404 } 405 406 /** 407 * Compares this map to another, as per the Map specification. 408 * 409 * @param obj the object to compare to 410 * @return true if equal 411 */ 412 public boolean equals(Object obj) { 413 if (obj == this) { 414 return true; 415 } 416 if (obj instanceof Map == false) { 417 return false; 418 } 419 Map other = (Map) obj; 420 return entrySet().equals(other.entrySet()); 421 } 422 423 /** 424 * Gets the hash code, as per the Map specification. 425 * 426 * @return the hash code 427 */ 428 public int hashCode() { 429 int hashCode = 0; 430 431 for (int i = 0; i < buckets.length; i++) { 432 synchronized (locks[i]) { 433 Node n = buckets[i]; 434 435 while (n != null) { 436 hashCode += n.hashCode(); 437 n = n.next; 438 } 439 } 440 } 441 return hashCode; 442 } 443 444 //----------------------------------------------------------------------- 445 /** 446 * The Map.Entry for the StaticBucketMap. 447 */ 448 private static final class Node implements Map.Entry, KeyValue { 449 protected Object key; 450 protected Object value; 451 protected Node next; 452 453 public Object getKey() { 454 return key; 455 } 456 457 public Object getValue() { 458 return value; 459 } 460 461 public int hashCode() { 462 return ((key == null ? 0 : key.hashCode()) ^ 463 (value == null ? 0 : value.hashCode())); 464 } 465 466 public boolean equals(Object obj) { 467 if (obj == this) { 468 return true; 469 } 470 if (obj instanceof Map.Entry == false) { 471 return false; 472 } 473 474 Map.Entry e2 = (Map.Entry) obj; 475 return ( 476 (key == null ? e2.getKey() == null : key.equals(e2.getKey())) && 477 (value == null ? e2.getValue() == null : value.equals(e2.getValue()))); 478 } 479 480 public Object setValue(Object obj) { 481 Object retVal = value; 482 value = obj; 483 return retVal; 484 } 485 } 486 487 488 /** 489 * The lock object, which also includes a count of the nodes in this lock. 490 */ 491 private final static class Lock { 492 public int size; 493 } 494 495 496 //----------------------------------------------------------------------- 497 private class EntryIterator implements Iterator { 498 499 private ArrayList current = new ArrayList(); 500 private int bucket; 501 private Map.Entry last; 502 503 504 public boolean hasNext() { 505 if (current.size() > 0) return true; 506 while (bucket < buckets.length) { 507 synchronized (locks[bucket]) { 508 Node n = buckets[bucket]; 509 while (n != null) { 510 current.add(n); 511 n = n.next; 512 } 513 bucket++; 514 if (current.size() > 0) return true; 515 } 516 } 517 return false; 518 } 519 520 protected Map.Entry nextEntry() { 521 if (!hasNext()) throw new NoSuchElementException(); 522 last = (Map.Entry)current.remove(current.size() - 1); 523 return last; 524 } 525 526 public Object next() { 527 return nextEntry(); 528 } 529 530 public void remove() { 531 if (last == null) throw new IllegalStateException(); 532 StaticBucketMap.this.remove(last.getKey()); 533 last = null; 534 } 535 536 } 537 538 private class ValueIterator extends EntryIterator { 539 540 public Object next() { 541 return nextEntry().getValue(); 542 } 543 544 } 545 546 private class KeyIterator extends EntryIterator { 547 548 public Object next() { 549 return nextEntry().getKey(); 550 } 551 552 } 553 554 private class EntrySet extends AbstractSet { 555 556 public int size() { 557 return StaticBucketMap.this.size(); 558 } 559 560 public void clear() { 561 StaticBucketMap.this.clear(); 562 } 563 564 public Iterator iterator() { 565 return new EntryIterator(); 566 } 567 568 public boolean contains(Object obj) { 569 Map.Entry entry = (Map.Entry) obj; 570 int hash = getHash(entry.getKey()); 571 synchronized (locks[hash]) { 572 for (Node n = buckets[hash]; n != null; n = n.next) { 573 if (n.equals(entry)) return true; 574 } 575 } 576 return false; 577 } 578 579 public boolean remove(Object obj) { 580 if (obj instanceof Map.Entry == false) { 581 return false; 582 } 583 Map.Entry entry = (Map.Entry) obj; 584 int hash = getHash(entry.getKey()); 585 synchronized (locks[hash]) { 586 for (Node n = buckets[hash]; n != null; n = n.next) { 587 if (n.equals(entry)) { 588 StaticBucketMap.this.remove(n.getKey()); 589 return true; 590 } 591 } 592 } 593 return false; 594 } 595 596 } 597 598 599 private class KeySet extends AbstractSet { 600 601 public int size() { 602 return StaticBucketMap.this.size(); 603 } 604 605 public void clear() { 606 StaticBucketMap.this.clear(); 607 } 608 609 public Iterator iterator() { 610 return new KeyIterator(); 611 } 612 613 public boolean contains(Object obj) { 614 return StaticBucketMap.this.containsKey(obj); 615 } 616 617 public boolean remove(Object obj) { 618 int hash = getHash(obj); 619 synchronized (locks[hash]) { 620 for (Node n = buckets[hash]; n != null; n = n.next) { 621 Object k = n.getKey(); 622 if ((k == obj) || ((k != null) && k.equals(obj))) { 623 StaticBucketMap.this.remove(k); 624 return true; 625 } 626 } 627 } 628 return false; 629 630 } 631 632 } 633 634 635 private class Values extends AbstractCollection { 636 637 public int size() { 638 return StaticBucketMap.this.size(); 639 } 640 641 public void clear() { 642 StaticBucketMap.this.clear(); 643 } 644 645 public Iterator iterator() { 646 return new ValueIterator(); 647 } 648 649 } 650 651 652 /** 653 * Prevents any operations from occurring on this map while the 654 * given {@link Runnable} executes. This method can be used, for 655 * instance, to execute a bulk operation atomically: 656 * 657 * <pre> 658 * staticBucketMapInstance.atomic(new Runnable() { 659 * public void run() { 660 * staticBucketMapInstance.putAll(map); 661 * } 662 * }); 663 * </pre> 664 * 665 * It can also be used if you need a reliable iterator: 666 * 667 * <pre> 668 * staticBucketMapInstance.atomic(new Runnable() { 669 * public void run() { 670 * Iterator iterator = staticBucketMapInstance.iterator(); 671 * while (iterator.hasNext()) { 672 * foo(iterator.next(); 673 * } 674 * } 675 * }); 676 * </pre> 677 * 678 * <b>Implementation note:</b> This method requires a lot of time 679 * and a ton of stack space. Essentially a recursive algorithm is used 680 * to enter each bucket's monitor. If you have twenty thousand buckets 681 * in your map, then the recursive method will be invoked twenty thousand 682 * times. You have been warned. 683 * 684 * @param r the code to execute atomically 685 */ 686 public void atomic(Runnable r) { 687 if (r == null) throw new NullPointerException(); 688 atomic(r, 0); 689 } 690 691 private void atomic(Runnable r, int bucket) { 692 if (bucket >= buckets.length) { 693 r.run(); 694 return; 695 } 696 synchronized (locks[bucket]) { 697 atomic(r, bucket + 1); 698 } 699 } 700 701 }