C++ Client API Reference for Oracle Coherence
14c (14.1.2.0.0)

F79659-03

coherence/util/SafeHashMap.hpp

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