Oracle Coherence for C++ API
Release 3.7.0.0

E18684-01

coherence/util/SafeHashMap.hpp

00001 /*
00002 * SafeHashMap.hpp
00003 *
00004 * Copyright (c) 2000, 2011, 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 &lt; n
00063         * @param flLoadFactor     the acceptable load factor before resizing
00064         *                         occurs, 0 &lt; 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 &lt; 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> m_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> m_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> m_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> m_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 MemberHandle<AtomicCounter> m_hAtomicIterators;
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
Copyright © 2000, 2011, Oracle and/or its affiliates. All rights reserved.