1. /*
  2. * Copyright 2001-2004 The Apache Software Foundation
  3. *
  4. * Licensed under the Apache License, Version 2.0 (the "License");
  5. * you may not use this file except in compliance with the License.
  6. * You may obtain a copy of the License at
  7. *
  8. * http://www.apache.org/licenses/LICENSE-2.0
  9. *
  10. * Unless required by applicable law or agreed to in writing, software
  11. * distributed under the License is distributed on an "AS IS" BASIS,
  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. * See the License for the specific language governing permissions and
  14. * limitations under the License.
  15. */
  16. package org.apache.commons.collections;
  17. import java.util.Collection;
  18. import java.util.ConcurrentModificationException;
  19. import java.util.HashMap;
  20. import java.util.Iterator;
  21. import java.util.Map;
  22. import java.util.Set;
  23. /**
  24. * <p>A customized implementation of <code>java.util.HashMap</code> designed
  25. * to operate in a multithreaded environment where the large majority of
  26. * method calls are read-only, instead of structural changes. When operating
  27. * in "fast" mode, read calls are non-synchronized and write calls perform the
  28. * following steps:</p>
  29. * <ul>
  30. * <li>Clone the existing collection
  31. * <li>Perform the modification on the clone
  32. * <li>Replace the existing collection with the (modified) clone
  33. * </ul>
  34. * <p>When first created, objects of this class default to "slow" mode, where
  35. * all accesses of any type are synchronized but no cloning takes place. This
  36. * is appropriate for initially populating the collection, followed by a switch
  37. * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
  38. * is complete.</p>
  39. *
  40. * <p><strong>NOTE</strong>: If you are creating and accessing a
  41. * <code>HashMap</code> only within a single thread, you should use
  42. * <code>java.util.HashMap</code> directly (with no synchronization), for
  43. * maximum performance.</p>
  44. *
  45. * <p><strong>NOTE</strong>: <i>This class is not cross-platform.
  46. * Using it may cause unexpected failures on some architectures.</i>
  47. * It suffers from the same problems as the double-checked locking idiom.
  48. * In particular, the instruction that clones the internal collection and the
  49. * instruction that sets the internal reference to the clone can be executed
  50. * or perceived out-of-order. This means that any read operation might fail
  51. * unexpectedly, as it may be reading the state of the internal collection
  52. * before the internal collection is fully formed.
  53. * For more information on the double-checked locking idiom, see the
  54. * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
  55. * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
  56. *
  57. * @since Commons Collections 1.0
  58. * @version $Revision: 1.1 $ $Date: 2004/05/10 19:51:13 $
  59. *
  60. * @author Craig R. McClanahan
  61. * @author Stephen Colebourne
  62. */
  63. public class FastHashMap extends HashMap {
  64. /**
  65. * The underlying map we are managing.
  66. */
  67. protected HashMap map = null;
  68. /**
  69. * Are we currently operating in "fast" mode?
  70. */
  71. protected boolean fast = false;
  72. // Constructors
  73. // ----------------------------------------------------------------------
  74. /**
  75. * Construct an empty map.
  76. */
  77. public FastHashMap() {
  78. super();
  79. this.map = new HashMap();
  80. }
  81. /**
  82. * Construct an empty map with the specified capacity.
  83. *
  84. * @param capacity the initial capacity of the empty map
  85. */
  86. public FastHashMap(int capacity) {
  87. super();
  88. this.map = new HashMap(capacity);
  89. }
  90. /**
  91. * Construct an empty map with the specified capacity and load factor.
  92. *
  93. * @param capacity the initial capacity of the empty map
  94. * @param factor the load factor of the new map
  95. */
  96. public FastHashMap(int capacity, float factor) {
  97. super();
  98. this.map = new HashMap(capacity, factor);
  99. }
  100. /**
  101. * Construct a new map with the same mappings as the specified map.
  102. *
  103. * @param map the map whose mappings are to be copied
  104. */
  105. public FastHashMap(Map map) {
  106. super();
  107. this.map = new HashMap(map);
  108. }
  109. // Property access
  110. // ----------------------------------------------------------------------
  111. /**
  112. * Returns true if this map is operating in fast mode.
  113. *
  114. * @return true if this map is operating in fast mode
  115. */
  116. public boolean getFast() {
  117. return (this.fast);
  118. }
  119. /**
  120. * Sets whether this map is operating in fast mode.
  121. *
  122. * @param fast true if this map should operate in fast mode
  123. */
  124. public void setFast(boolean fast) {
  125. this.fast = fast;
  126. }
  127. // Map access
  128. // ----------------------------------------------------------------------
  129. // These methods can forward straight to the wrapped Map in 'fast' mode.
  130. // (because they are query methods)
  131. /**
  132. * Return the value to which this map maps the specified key. Returns
  133. * <code>null</code> if the map contains no mapping for this key, or if
  134. * there is a mapping with a value of <code>null</code>. Use the
  135. * <code>containsKey()</code> method to disambiguate these cases.
  136. *
  137. * @param key the key whose value is to be returned
  138. * @return the value mapped to that key, or null
  139. */
  140. public Object get(Object key) {
  141. if (fast) {
  142. return (map.get(key));
  143. } else {
  144. synchronized (map) {
  145. return (map.get(key));
  146. }
  147. }
  148. }
  149. /**
  150. * Return the number of key-value mappings in this map.
  151. *
  152. * @return the current size of the map
  153. */
  154. public int size() {
  155. if (fast) {
  156. return (map.size());
  157. } else {
  158. synchronized (map) {
  159. return (map.size());
  160. }
  161. }
  162. }
  163. /**
  164. * Return <code>true</code> if this map contains no mappings.
  165. *
  166. * @return is the map currently empty
  167. */
  168. public boolean isEmpty() {
  169. if (fast) {
  170. return (map.isEmpty());
  171. } else {
  172. synchronized (map) {
  173. return (map.isEmpty());
  174. }
  175. }
  176. }
  177. /**
  178. * Return <code>true</code> if this map contains a mapping for the
  179. * specified key.
  180. *
  181. * @param key the key to be searched for
  182. * @return true if the map contains the key
  183. */
  184. public boolean containsKey(Object key) {
  185. if (fast) {
  186. return (map.containsKey(key));
  187. } else {
  188. synchronized (map) {
  189. return (map.containsKey(key));
  190. }
  191. }
  192. }
  193. /**
  194. * Return <code>true</code> if this map contains one or more keys mapping
  195. * to the specified value.
  196. *
  197. * @param value the value to be searched for
  198. * @return true if the map contains the value
  199. */
  200. public boolean containsValue(Object value) {
  201. if (fast) {
  202. return (map.containsValue(value));
  203. } else {
  204. synchronized (map) {
  205. return (map.containsValue(value));
  206. }
  207. }
  208. }
  209. // Map modification
  210. // ----------------------------------------------------------------------
  211. // These methods perform special behaviour in 'fast' mode.
  212. // The map is cloned, updated and then assigned back.
  213. // See the comments at the top as to why this won't always work.
  214. /**
  215. * Associate the specified value with the specified key in this map.
  216. * If the map previously contained a mapping for this key, the old
  217. * value is replaced and returned.
  218. *
  219. * @param key the key with which the value is to be associated
  220. * @param value the value to be associated with this key
  221. * @return the value previously mapped to the key, or null
  222. */
  223. public Object put(Object key, Object value) {
  224. if (fast) {
  225. synchronized (this) {
  226. HashMap temp = (HashMap) map.clone();
  227. Object result = temp.put(key, value);
  228. map = temp;
  229. return (result);
  230. }
  231. } else {
  232. synchronized (map) {
  233. return (map.put(key, value));
  234. }
  235. }
  236. }
  237. /**
  238. * Copy all of the mappings from the specified map to this one, replacing
  239. * any mappings with the same keys.
  240. *
  241. * @param in the map whose mappings are to be copied
  242. */
  243. public void putAll(Map in) {
  244. if (fast) {
  245. synchronized (this) {
  246. HashMap temp = (HashMap) map.clone();
  247. temp.putAll(in);
  248. map = temp;
  249. }
  250. } else {
  251. synchronized (map) {
  252. map.putAll(in);
  253. }
  254. }
  255. }
  256. /**
  257. * Remove any mapping for this key, and return any previously
  258. * mapped value.
  259. *
  260. * @param key the key whose mapping is to be removed
  261. * @return the value removed, or null
  262. */
  263. public Object remove(Object key) {
  264. if (fast) {
  265. synchronized (this) {
  266. HashMap temp = (HashMap) map.clone();
  267. Object result = temp.remove(key);
  268. map = temp;
  269. return (result);
  270. }
  271. } else {
  272. synchronized (map) {
  273. return (map.remove(key));
  274. }
  275. }
  276. }
  277. /**
  278. * Remove all mappings from this map.
  279. */
  280. public void clear() {
  281. if (fast) {
  282. synchronized (this) {
  283. map = new HashMap();
  284. }
  285. } else {
  286. synchronized (map) {
  287. map.clear();
  288. }
  289. }
  290. }
  291. // Basic object methods
  292. // ----------------------------------------------------------------------
  293. /**
  294. * Compare the specified object with this list for equality. This
  295. * implementation uses exactly the code that is used to define the
  296. * list equals function in the documentation for the
  297. * <code>Map.equals</code> method.
  298. *
  299. * @param o the object to be compared to this list
  300. * @return true if the two maps are equal
  301. */
  302. public boolean equals(Object o) {
  303. // Simple tests that require no synchronization
  304. if (o == this) {
  305. return (true);
  306. } else if (!(o instanceof Map)) {
  307. return (false);
  308. }
  309. Map mo = (Map) o;
  310. // Compare the two maps for equality
  311. if (fast) {
  312. if (mo.size() != map.size()) {
  313. return (false);
  314. }
  315. Iterator i = map.entrySet().iterator();
  316. while (i.hasNext()) {
  317. Map.Entry e = (Map.Entry) i.next();
  318. Object key = e.getKey();
  319. Object value = e.getValue();
  320. if (value == null) {
  321. if (!(mo.get(key) == null && mo.containsKey(key))) {
  322. return (false);
  323. }
  324. } else {
  325. if (!value.equals(mo.get(key))) {
  326. return (false);
  327. }
  328. }
  329. }
  330. return (true);
  331. } else {
  332. synchronized (map) {
  333. if (mo.size() != map.size()) {
  334. return (false);
  335. }
  336. Iterator i = map.entrySet().iterator();
  337. while (i.hasNext()) {
  338. Map.Entry e = (Map.Entry) i.next();
  339. Object key = e.getKey();
  340. Object value = e.getValue();
  341. if (value == null) {
  342. if (!(mo.get(key) == null && mo.containsKey(key))) {
  343. return (false);
  344. }
  345. } else {
  346. if (!value.equals(mo.get(key))) {
  347. return (false);
  348. }
  349. }
  350. }
  351. return (true);
  352. }
  353. }
  354. }
  355. /**
  356. * Return the hash code value for this map. This implementation uses
  357. * exactly the code that is used to define the list hash function in the
  358. * documentation for the <code>Map.hashCode</code> method.
  359. *
  360. * @return suitable integer hash code
  361. */
  362. public int hashCode() {
  363. if (fast) {
  364. int h = 0;
  365. Iterator i = map.entrySet().iterator();
  366. while (i.hasNext()) {
  367. h += i.next().hashCode();
  368. }
  369. return (h);
  370. } else {
  371. synchronized (map) {
  372. int h = 0;
  373. Iterator i = map.entrySet().iterator();
  374. while (i.hasNext()) {
  375. h += i.next().hashCode();
  376. }
  377. return (h);
  378. }
  379. }
  380. }
  381. /**
  382. * Return a shallow copy of this <code>FastHashMap</code> instance.
  383. * The keys and values themselves are not copied.
  384. *
  385. * @return a clone of this map
  386. */
  387. public Object clone() {
  388. FastHashMap results = null;
  389. if (fast) {
  390. results = new FastHashMap(map);
  391. } else {
  392. synchronized (map) {
  393. results = new FastHashMap(map);
  394. }
  395. }
  396. results.setFast(getFast());
  397. return (results);
  398. }
  399. // Map views
  400. // ----------------------------------------------------------------------
  401. /**
  402. * Return a collection view of the mappings contained in this map. Each
  403. * element in the returned collection is a <code>Map.Entry</code>.
  404. */
  405. public Set entrySet() {
  406. return new EntrySet();
  407. }
  408. /**
  409. * Return a set view of the keys contained in this map.
  410. */
  411. public Set keySet() {
  412. return new KeySet();
  413. }
  414. /**
  415. * Return a collection view of the values contained in this map.
  416. */
  417. public Collection values() {
  418. return new Values();
  419. }
  420. // Map view inner classes
  421. // ----------------------------------------------------------------------
  422. /**
  423. * Abstract collection implementation shared by keySet(), values() and entrySet().
  424. */
  425. private abstract class CollectionView implements Collection {
  426. public CollectionView() {
  427. }
  428. protected abstract Collection get(Map map);
  429. protected abstract Object iteratorNext(Map.Entry entry);
  430. public void clear() {
  431. if (fast) {
  432. synchronized (FastHashMap.this) {
  433. map = new HashMap();
  434. }
  435. } else {
  436. synchronized (map) {
  437. get(map).clear();
  438. }
  439. }
  440. }
  441. public boolean remove(Object o) {
  442. if (fast) {
  443. synchronized (FastHashMap.this) {
  444. HashMap temp = (HashMap) map.clone();
  445. boolean r = get(temp).remove(o);
  446. map = temp;
  447. return r;
  448. }
  449. } else {
  450. synchronized (map) {
  451. return get(map).remove(o);
  452. }
  453. }
  454. }
  455. public boolean removeAll(Collection o) {
  456. if (fast) {
  457. synchronized (FastHashMap.this) {
  458. HashMap temp = (HashMap) map.clone();
  459. boolean r = get(temp).removeAll(o);
  460. map = temp;
  461. return r;
  462. }
  463. } else {
  464. synchronized (map) {
  465. return get(map).removeAll(o);
  466. }
  467. }
  468. }
  469. public boolean retainAll(Collection o) {
  470. if (fast) {
  471. synchronized (FastHashMap.this) {
  472. HashMap temp = (HashMap) map.clone();
  473. boolean r = get(temp).retainAll(o);
  474. map = temp;
  475. return r;
  476. }
  477. } else {
  478. synchronized (map) {
  479. return get(map).retainAll(o);
  480. }
  481. }
  482. }
  483. public int size() {
  484. if (fast) {
  485. return get(map).size();
  486. } else {
  487. synchronized (map) {
  488. return get(map).size();
  489. }
  490. }
  491. }
  492. public boolean isEmpty() {
  493. if (fast) {
  494. return get(map).isEmpty();
  495. } else {
  496. synchronized (map) {
  497. return get(map).isEmpty();
  498. }
  499. }
  500. }
  501. public boolean contains(Object o) {
  502. if (fast) {
  503. return get(map).contains(o);
  504. } else {
  505. synchronized (map) {
  506. return get(map).contains(o);
  507. }
  508. }
  509. }
  510. public boolean containsAll(Collection o) {
  511. if (fast) {
  512. return get(map).containsAll(o);
  513. } else {
  514. synchronized (map) {
  515. return get(map).containsAll(o);
  516. }
  517. }
  518. }
  519. public Object[] toArray(Object[] o) {
  520. if (fast) {
  521. return get(map).toArray(o);
  522. } else {
  523. synchronized (map) {
  524. return get(map).toArray(o);
  525. }
  526. }
  527. }
  528. public Object[] toArray() {
  529. if (fast) {
  530. return get(map).toArray();
  531. } else {
  532. synchronized (map) {
  533. return get(map).toArray();
  534. }
  535. }
  536. }
  537. public boolean equals(Object o) {
  538. if (o == this) return true;
  539. if (fast) {
  540. return get(map).equals(o);
  541. } else {
  542. synchronized (map) {
  543. return get(map).equals(o);
  544. }
  545. }
  546. }
  547. public int hashCode() {
  548. if (fast) {
  549. return get(map).hashCode();
  550. } else {
  551. synchronized (map) {
  552. return get(map).hashCode();
  553. }
  554. }
  555. }
  556. public boolean add(Object o) {
  557. throw new UnsupportedOperationException();
  558. }
  559. public boolean addAll(Collection c) {
  560. throw new UnsupportedOperationException();
  561. }
  562. public Iterator iterator() {
  563. return new CollectionViewIterator();
  564. }
  565. private class CollectionViewIterator implements Iterator {
  566. private Map expected;
  567. private Map.Entry lastReturned = null;
  568. private Iterator iterator;
  569. public CollectionViewIterator() {
  570. this.expected = map;
  571. this.iterator = expected.entrySet().iterator();
  572. }
  573. public boolean hasNext() {
  574. if (expected != map) {
  575. throw new ConcurrentModificationException();
  576. }
  577. return iterator.hasNext();
  578. }
  579. public Object next() {
  580. if (expected != map) {
  581. throw new ConcurrentModificationException();
  582. }
  583. lastReturned = (Map.Entry)iterator.next();
  584. return iteratorNext(lastReturned);
  585. }
  586. public void remove() {
  587. if (lastReturned == null) {
  588. throw new IllegalStateException();
  589. }
  590. if (fast) {
  591. synchronized (FastHashMap.this) {
  592. if (expected != map) {
  593. throw new ConcurrentModificationException();
  594. }
  595. FastHashMap.this.remove(lastReturned.getKey());
  596. lastReturned = null;
  597. expected = map;
  598. }
  599. } else {
  600. iterator.remove();
  601. lastReturned = null;
  602. }
  603. }
  604. }
  605. }
  606. /**
  607. * Set implementation over the keys of the FastHashMap
  608. */
  609. private class KeySet extends CollectionView implements Set {
  610. protected Collection get(Map map) {
  611. return map.keySet();
  612. }
  613. protected Object iteratorNext(Map.Entry entry) {
  614. return entry.getKey();
  615. }
  616. }
  617. /**
  618. * Collection implementation over the values of the FastHashMap
  619. */
  620. private class Values extends CollectionView {
  621. protected Collection get(Map map) {
  622. return map.values();
  623. }
  624. protected Object iteratorNext(Map.Entry entry) {
  625. return entry.getValue();
  626. }
  627. }
  628. /**
  629. * Set implementation over the entries of the FastHashMap
  630. */
  631. private class EntrySet extends CollectionView implements Set {
  632. protected Collection get(Map map) {
  633. return map.entrySet();
  634. }
  635. protected Object iteratorNext(Map.Entry entry) {
  636. return entry;
  637. }
  638. }
  639. }