00001 /* 00002 * SafeHashMap.hpp 00003 * 00004 * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved. 00005 * 00006 * Oracle is a registered trademarks of Oracle Corporation and/or its 00007 * affiliates. 00008 * 00009 * This software is the confidential and proprietary information of Oracle 00010 * Corporation. You shall not disclose such confidential and proprietary 00011 * information and shall use it only in accordance with the terms of the 00012 * license agreement you entered into with Oracle. 00013 * 00014 * This notice may not be removed or altered. 00015 */ 00016 #ifndef COH_SAFE_HASH_MAP_HPP 00017 #define COH_SAFE_HASH_MAP_HPP 00018 00019 #include "coherence/lang.ns" 00020 00021 #include "coherence/util/AbstractMap.hpp" 00022 #include "coherence/util/AbstractSet.hpp" 00023 #include "coherence/util/AbstractStableIterator.hpp" 00024 #include "coherence/util/AtomicCounter.hpp" 00025 #include "coherence/util/Iterator.hpp" 00026 #include "coherence/util/Map.hpp" 00027 00028 00029 COH_OPEN_NAMESPACE2(coherence,util) 00030 00031 00032 /** 00033 * An implementation of coherence::util::Map that is synchronized, but 00034 * minimally so. This class is for use in situation where high concurrency is 00035 * required, but so is data integrity. 00036 * 00037 * All additions and removals are synchronized on the map, so to temporarily 00038 * prevent changes to the map contents, synchronize on the map object. 00039 * 00040 * @author mf 2008.02.25 00041 */ 00042 class COH_EXPORT SafeHashMap 00043 : public cloneable_spec<SafeHashMap, 00044 extends<AbstractMap> > 00045 { 00046 friend class factory<SafeHashMap>; 00047 00048 // ----- handle definitions (needed for nested classes) ----------------- 00049 00050 public: 00051 typedef this_spec::Handle Handle; 00052 typedef this_spec::View View; 00053 typedef this_spec::Holder Holder; 00054 00055 // ----- constructors --------------------------------------------------- 00056 00057 protected: 00058 /** 00059 * Construct a thread-safe hash map using the specified settings. 00060 * 00061 * @param cInitialBuckets the initial number of hash buckets, 00062 * 0 < n 00063 * @param flLoadFactor the acceptable load factor before resizing 00064 * occurs, 0 < n, such that a load factor 00065 * of 1.0 causes resizing when the number of 00066 * entries exceeds the number of buckets 00067 * @param flGrowthRate the rate of bucket growth when a resize 00068 * occurs, 0 < n, such that a growth rate 00069 * of 1.0 will double the number of buckets: 00070 * bucketcount = bucketcount * (1 + growthrate) 00071 */ 00072 SafeHashMap(size32_t cInitialBuckets = 17, 00073 float32_t flLoadFactor = 1.0F, float32_t flGrowthRate = 3.0F); 00074 00075 /** 00076 * Copy constructor. 00077 */ 00078 SafeHashMap(const SafeHashMap& that); 00079 00080 00081 // ----- forward declarations ------------------------------------------- 00082 00083 class Entry; 00084 class EntrySet; 00085 class EntrySetIterator; 00086 00087 00088 // ----- Map interface -------------------------------------------------- 00089 00090 public: 00091 /** 00092 * {@inheritDoc} 00093 */ 00094 virtual size32_t size() const; 00095 00096 /** 00097 * {@inheritDoc} 00098 */ 00099 virtual bool isEmpty() const; 00100 00101 /** 00102 * {@inheritDoc} 00103 */ 00104 virtual bool containsKey(Object::View vKey) const; 00105 00106 /** 00107 * {@inheritDoc} 00108 */ 00109 virtual Object::Holder get(Object::View vKey) const; 00110 00111 /** 00112 * {@inheritDoc} 00113 */ 00114 using Map::get; 00115 00116 /** 00117 * {@inheritDoc} 00118 */ 00119 virtual Object::Holder put(Object::View vKey, Object::Holder ohValue); 00120 00121 /** 00122 * {@inheritDoc} 00123 */ 00124 virtual Object::Holder remove(Object::View vKey); 00125 00126 /** 00127 * {@inheritDoc} 00128 */ 00129 virtual void clear(); 00130 00131 /** 00132 * {@inheritDoc} 00133 */ 00134 virtual Set::View entrySet() const; 00135 00136 /** 00137 * {@inheritDoc} 00138 */ 00139 virtual Set::Handle entrySet(); 00140 00141 00142 // ----- inner class: Entry --------------------------------------------- 00143 00144 protected: 00145 /** 00146 * A map entry (key-value pair). The <tt>Map.entrySet</tt> method 00147 * returns a collection-view of the map, whose elements are of this 00148 * class. 00149 */ 00150 class COH_EXPORT Entry 00151 : public cloneable_spec<Entry, 00152 extends<Object>, 00153 implements<Map::Entry> > 00154 { 00155 friend class factory<Entry>; 00156 00157 // ----- constructors --------------------------------------- 00158 00159 protected: 00160 /** 00161 * Create a new Map::Entry. 00162 * 00163 * @param vKey the assocaited key 00164 * @param ohValue the associated value 00165 * @param hHash the associated hash code 00166 * 00167 * @return a new Map::Entry 00168 */ 00169 Entry(Object::View vKey, Object::Holder ohValue, 00170 size32_t nHash); 00171 00172 /** 00173 * Copy Constructor 00174 */ 00175 Entry(const Entry& that); 00176 00177 /** 00178 * Instantiate an Entry shallow copying the key and value from 00179 * the Entry provided. 00180 * 00181 * @param vThat the entry to copy from 00182 */ 00183 Entry(Entry::View vThat); 00184 00185 // ----- SafeHashMap::Entry interface ----------------------- 00186 00187 public: 00188 /** 00189 * Return true if the supplied key is equal to the entries 00190 * key. 00191 */ 00192 virtual bool isKeyEqual(Object::View vKey) const; 00193 00194 // ----- Map::Entry interface ------------------------------- 00195 00196 public: 00197 /** 00198 * {@inheritDoc} 00199 */ 00200 virtual Object::View getKey() const; 00201 00202 /** 00203 * {@inheritDoc} 00204 */ 00205 virtual Object::Holder getValue() const; 00206 00207 /** 00208 * {@inheritDoc} 00209 */ 00210 virtual Object::Holder getValue(); 00211 00212 /** 00213 * {@inheritDoc} 00214 */ 00215 virtual Object::Holder setValue(Object::Holder ohValue); 00216 00217 // ----- class methods -------------------------------------- 00218 00219 /** 00220 * This method is invoked when the containing Map has actually 00221 * added this Entry to itself. 00222 */ 00223 virtual void onAdd(); 00224 00225 // ----- Object interface ----------------------------------- 00226 00227 public: 00228 /** 00229 * {@inheritDoc} 00230 */ 00231 virtual bool equals(Object::View vThat) const; 00232 00233 /** 00234 * {@inheritDoc} 00235 */ 00236 virtual size32_t hashCode() const; 00237 00238 /** 00239 * {@inheritDoc} 00240 */ 00241 virtual void toStream(std::ostream& out) const; 00242 00243 // ----- data members --------------------------------------- 00244 00245 protected: 00246 /** 00247 * The key. 00248 */ 00249 FinalView<Object> f_vKey; 00250 00251 /** 00252 * The value. This object reference can change within the life 00253 * of the Entry. 00254 */ 00255 MemberHolder<Object> m_ohValue; 00256 00257 /** 00258 * The key's hash code. This value will not change for the 00259 * life of the Entry. 00260 */ 00261 const size32_t m_nHash; 00262 00263 /** 00264 * The next entry in the linked list (an open hashing 00265 * implementation). 00266 */ 00267 MemberHandle<Entry> m_hNext; 00268 00269 // ----- friends -------------------------------------------- 00270 00271 friend class SafeHashMap; 00272 friend class EntrySet; 00273 friend class EntrySetIterator; 00274 }; 00275 00276 /** 00277 * Factory pattern, initialized with the specified valued 00278 * 00279 * @param vKey the associated key 00280 * @param ohValue the assocaited value 00281 * @param nHash the associated hash code 00282 * 00283 * @return a new instance of the Entry class (or a subclass thereof) 00284 */ 00285 virtual Entry::Handle instantiateEntry(Object::View vKey, 00286 Object::Holder ohValue, size32_t nHash); 00287 00288 /** 00289 * Factory pattern, instantiate an Entry that is either a deep or 00290 * shalow copy. 00291 * 00292 * @param vEntry the Entry to copy 00293 * @param fDeep whether to make a deep copy of the Entry or not 00294 */ 00295 virtual Entry::Handle instantiateEntry(Entry::View vEntry); 00296 00297 // ----- inner class: EntrySet ------------------------------------------ 00298 00299 protected: 00300 /** 00301 * A set of entries backed by this map. 00302 */ 00303 class COH_EXPORT EntrySet 00304 : public class_spec<EntrySet, 00305 extends<AbstractCollection>, 00306 implements<Set> > 00307 { 00308 friend class factory<EntrySet>; 00309 00310 // ----- constructors -------------------------------------- 00311 00312 protected: 00313 /** 00314 * Return a new EntrySet. 00315 */ 00316 EntrySet(SafeHashMap::Holder hMap); 00317 00318 00319 // ----- Set interface -------------------------------------- 00320 00321 public: 00322 /** 00323 * {@inheritDoc} 00324 */ 00325 using Collection::add; 00326 00327 /** 00328 * {@inheritDoc} 00329 */ 00330 virtual Iterator::Handle iterator() const; 00331 00332 /** 00333 * {@inheritDoc} 00334 */ 00335 virtual Muterator::Handle iterator(); 00336 00337 /** 00338 * {@inheritDoc} 00339 */ 00340 virtual size32_t size() const; 00341 00342 /** 00343 * {@inheritDoc} 00344 */ 00345 virtual bool contains(Object::View v) const; 00346 00347 /** 00348 * {@inheritDoc} 00349 */ 00350 virtual bool remove(Object::View v); 00351 00352 /** 00353 * {@inheritDoc} 00354 */ 00355 virtual void clear(); 00356 00357 /** 00358 * {@inheritDoc} 00359 */ 00360 virtual ObjectArray::Handle toArray( 00361 ObjectArray::Handle hao = NULL) const; 00362 00363 // ----- Object interface ----------------------------------- 00364 00365 public: 00366 /** 00367 * {@inheritDoc} 00368 */ 00369 virtual bool equals(Object::View that) const; 00370 00371 /** 00372 * {@inheritDoc} 00373 */ 00374 virtual size32_t hashCode() const; 00375 00376 // ----- helper methods -------------------------------------- 00377 00378 protected: 00379 /** 00380 * Factory pattern. 00381 * 00382 * @return a new instance of an Iterator over the EntrySet 00383 */ 00384 virtual Iterator::Handle instantiateIterator() const; 00385 00386 /** 00387 * Factory pattern. 00388 * 00389 * @return a new instance of an Iterator over the EntrySet 00390 */ 00391 virtual Muterator::Handle instantiateIterator(); 00392 00393 /** 00394 * Return a handle to the assocaited Map. 00395 */ 00396 virtual SafeHashMap::Handle getDelegate(); 00397 00398 /** 00399 * Return a view to the assocaited Map. 00400 */ 00401 virtual SafeHashMap::View getDelegate() const; 00402 00403 // ----- data members --------------------------------------- 00404 00405 protected: 00406 /** 00407 * The SafeHashMap associated with the EntrySet. 00408 */ 00409 FinalHolder<SafeHashMap> f_ohMap; 00410 00411 // ----- friends -------------------------------------------- 00412 00413 friend class SafeHashMap; 00414 friend class EntrySetIterator; 00415 }; 00416 00417 00418 // ----- inner class: EntrySetIterator ------------------------------ 00419 00420 protected: 00421 /** 00422 * An Iterator over the EntrySet that is backed by the 00423 * SafeHashMap. 00424 */ 00425 class COH_EXPORT EntrySetIterator 00426 : public class_spec<EntrySetIterator, 00427 extends<AbstractStableIterator> > 00428 { 00429 friend class factory<EntrySetIterator>; 00430 00431 protected: 00432 /** 00433 * Construct an Iterator over the Entries in the 00434 * SafeHashMap. Special care must be taken to handle 00435 * the condition in which the SafeHashMap is currently 00436 * resizing. 00437 * 00438 * @param ohMap the set to iterate 00439 */ 00440 EntrySetIterator(SafeHashMap::Holder ohMap); 00441 00442 /** 00443 * @internal 00444 */ 00445 virtual ~EntrySetIterator(); 00446 00447 00448 // ----- AbstractStableIterator interface ------------------- 00449 00450 public: 00451 /** 00452 * {@inheritDoc} 00453 */ 00454 using Muterator::remove; 00455 00456 protected: 00457 /** 00458 * Advance to the next object. 00459 */ 00460 virtual void advance(); 00461 00462 /** 00463 * Shut down the Iterator. This is done on exhaustion of the 00464 * contents of the Iterator, or on destruction of the Iterator. 00465 */ 00466 virtual void deactivate() const; 00467 00468 /** 00469 * {@inheritDoc} 00470 */ 00471 virtual void remove(Object::Holder oh); 00472 00473 // ----- data members --------------------------------------- 00474 00475 private: 00476 /** 00477 * The EntrySet's Map being iterated. 00478 */ 00479 FinalHolder<SafeHashMap> f_ohMap; 00480 00481 /** 00482 * Array of buckets in the hash map. This is a 00483 * purposeful copy of the hash map's reference to its 00484 * buckets in order to detect that a resize has 00485 * occurred. 00486 */ 00487 MemberView<ObjectArray> m_vaeBucket; 00488 00489 /** 00490 * Current bucket being iterated. 00491 */ 00492 size32_t m_iBucket; 00493 00494 /** 00495 * The most recent Entry object internally iterated. 00496 * This is not necessarily the same Entry object that 00497 * was reported to the stable iterator (via the 00498 * setNext() method), since when a resize occurs, the 00499 * entries that are being iterated over internally are 00500 * the "old" Entry objects (pre-resize) while the 00501 * entries being returned from the Iterator are the 00502 * "new" Entry objects (post-resize). 00503 */ 00504 MemberHandle<Entry> m_hEntryPrev; 00505 00506 /** 00507 * Set to true when a resize has been detected. 00508 */ 00509 bool m_fResized; 00510 00511 /** 00512 * Set to true when the Iterator is complete. 00513 */ 00514 mutable bool m_fDeactivated; 00515 00516 /** 00517 * True if the iterator will only return views. 00518 */ 00519 const bool m_fViewer; 00520 }; 00521 00522 00523 // ----- helper methods ------------------------------------------------- 00524 00525 public: 00526 /** 00527 * Locate an Entry in the hash map based on its key. 00528 * 00529 * @param vKey the key object to search for 00530 * 00531 * @return the Entry or NULL 00532 */ 00533 virtual Entry::View getEntry(Object::View vKey) const; 00534 00535 /** 00536 * Locate an Entry in the hash map based on its key. 00537 * 00538 * @param vKey the key object to search for 00539 * 00540 * @return the Entry or NULL 00541 */ 00542 virtual Entry::Handle getEntry(Object::View vKey); 00543 00544 protected: 00545 /** 00546 * Factory pattern. 00547 * 00548 * @return a new instance of the EntrySet class (or a subclass 00549 * thereof) 00550 */ 00551 virtual Set::Handle instantiateEntrySet(); 00552 00553 /** 00554 * Factory pattern. 00555 * 00556 * @return a new instance of the EntrySet class (or a subclass 00557 * thereof) 00558 */ 00559 virtual Set::View instantiateEntrySet() const; 00560 00561 /** 00562 * Resize the bucket array, rehashing all Entries. 00563 */ 00564 virtual void grow(); 00565 00566 /** 00567 * Return the hash code to use for the specified key. 00568 * 00569 * @param vKey the key to hash 00570 * 00571 * @return the hash code to use for the key 00572 */ 00573 virtual size32_t getHashCode(Object::View vKey) const; 00574 00575 /** 00576 * Clone an entire linked list of entries. 00577 * 00578 * This method must be called on the map that will contain the clones, 00579 * to allow the map to be the parent of the entries if the entries are 00580 * not static inner classes. 00581 * 00582 * @param vEntryThat the entry that is the head of the list to clone 00583 * 00584 * @return NULL if the entry is NULL, otherwise an entry that is a 00585 * clone of the passed entry, and a linked list of clones for 00586 * each entry in the linked list that was passed 00587 */ 00588 virtual Entry::Handle cloneEntryList(Entry::View vEntryThat) const; 00589 00590 /** 00591 * Locate an Entry in the hash map based on its key. 00592 * 00593 * Unlike the #getEntry method, there must be no side-effects 00594 * of calling this method. 00595 * 00596 * @param vKey the key object to search for 00597 * 00598 * @return the Entry or null 00599 */ 00600 virtual Entry::Handle getEntryInternal(Object::View vKey) const; 00601 00602 /** 00603 * Removes the passed Entry from the map. 00604 * 00605 * <b>Note:</b> Unlike calling the "remove" method, which is overriden 00606 * at subclasses, calling this method directly does not generate any 00607 * events. 00608 * 00609 * @param hEntry the entry to remove from this map 00610 */ 00611 virtual void removeEntryInternal(Entry::Handle hEntry); 00612 00613 /** 00614 * Calculate the bucket number for a particular hash code. 00615 * 00616 * @param nHash the hash code 00617 * @param cBuckets the number of buckets 00618 * 00619 * @return the bucket index for the specified hash code 00620 */ 00621 virtual size32_t getBucketIndex(size32_t nHash, size32_t cBuckets) const; 00622 00623 /** 00624 * Get the bucket array, or if a resize is occurring, wait for the 00625 * resize to complete and return the new bucket array. 00626 * 00627 * @return the latest bucket array 00628 */ 00629 virtual ObjectArray::View getStableBucketArray() const; 00630 00631 /** 00632 * Register the activation of an Iterator. 00633 */ 00634 virtual void iteratorActivated() const; 00635 00636 /** 00637 * Unregister the (formerly active) Iterator. 00638 */ 00639 virtual void iteratorDeactivated() const; 00640 00641 /** 00642 * Determine if there are any active Iterators, which may mean that 00643 * they are in the middle of iterating over the Map. 00644 * 00645 * @return true iff there is at least one active Iterator 00646 */ 00647 virtual bool isActiveIterator() const; 00648 00649 /** 00650 * Invaldiate the Map so it's no longer useable 00651 */ 00652 virtual void invalidate(); 00653 00654 /** 00655 * Retrun wither the Map is still valid or not 00656 * 00657 * @return whether the Map is still valid or not. 00658 */ 00659 virtual bool isValid() const; 00660 00661 private: 00662 /** 00663 * Copy a list of Entries. 00664 * 00665 * @param vEntry the Entry to copy 00666 * @param fDeep whether to deep copy each Entry in the list or not 00667 * 00668 * @return a copy of the list of Entries passed in 00669 */ 00670 virtual Entry::Handle copyEntryList(Entry::View vEntry, bool fDeep); 00671 00672 /** 00673 * Copy an individual Entry. 00674 * 00675 * @param vEntry the Entry to copy 00676 * @param fDeep whether to deep copy the Entry or not 00677 * 00678 * @return a copy of the Entry passed in 00679 */ 00680 virtual Entry::Handle copyEntry(Entry::View vEntry, bool fDeep); 00681 00682 00683 // ----- constants ------------------------------------------------------ 00684 00685 public: 00686 /** 00687 * Default initial size provides a prime modulo and is large enough 00688 * that resize is not immediate. (A hash map probably uses less than 00689 * 128 bytes initially.) 00690 */ 00691 static const size32_t default_initialsize = 17; 00692 00693 /** 00694 * Biggest possible modulo. 00695 */ 00696 static const size32_t biggest_modulo = 2147483647; 00697 00698 00699 // ----- data members --------------------------------------------------- 00700 00701 protected: 00702 /** 00703 * When resizing completes, a notification is issued against this 00704 * object. 00705 */ 00706 FinalView<Object> f_vResizing; 00707 00708 /** 00709 * The number of entries stored in the hash map, 0 <= n. 00710 */ 00711 size32_t m_cEntries; 00712 00713 /** 00714 * The array of hash buckets. This field is declared volatile in 00715 * order to reduce synchronization. 00716 */ 00717 MemberHandle<ObjectArray> m_haeBucket; 00718 00719 /** 00720 * The capacity of the hash map (the point at which it must resize), 00721 * 1 <= n. 00722 */ 00723 size32_t m_cCapacity; 00724 00725 /** 00726 * The determining factor for the hash map capacity given a certain 00727 * number of buckets, such that capactiy = bucketcount * loadfactor. 00728 */ 00729 float32_t m_flLoadFactor; 00730 00731 /** 00732 * The rate of growth as a fraction of the current number of buckets, 00733 * 0 < n, such that the hash map grows to bucketcount * (1 + 00734 * growthrate) 00735 */ 00736 float32_t m_flGrowthRate; 00737 00738 /** 00739 * A count of the number of active Iterators on this map. 00740 */ 00741 mutable NativeAtomic64 m_cIterators; 00742 00743 00744 // ----- friends -------------------------------------------------------- 00745 00746 friend class Entry; 00747 friend class EntrySet; 00748 friend class EntrySetIterator; 00749 }; 00750 00751 COH_CLOSE_NAMESPACE2 00752 00753 #endif // COH_SAFE_HASH_MAP_HPP