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