Oracle Coherence for C++ API
Release 3.6.0.0
E15728-01

- Main Page
- Namespaces
- Classes
- Files

# coherence/util/SafeHashMap.hpp

    00001 /*
    00002 * SafeHashMap.hpp
    00003 *
    00004 * Copyright (c) 2000, 2010, 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         * Due to custom serialization this field cannot be marked as "final",
    00707         * but must be treated as such.
    00708         */
    00709         FinalView<Object> RESIZING;
    00710
    00711         /**
    00712         * The number of entries stored in the hash map, 0 <= n.
    00713         */
    00714         size32_t m_cEntries;
    00715
    00716         /**
    00717         * The array of hash buckets.  This field is declared volatile in
    00718         * order to reduce synchronization.
    00719         */
    00720         MemberHandle<ObjectArray> m_haeBucket;
    00721
    00722         /**
    00723         * The capacity of the hash map (the point at which it must resize),
    00724         *  1 <= n.
    00725         */
    00726         size32_t m_cCapacity;
    00727
    00728         /**
    00729         * The determining factor for the hash map capacity given a certain
    00730         * number of buckets, such that capactiy = bucketcount * loadfactor.
    00731         */
    00732         float32_t m_flLoadFactor;
    00733
    00734         /**
    00735         * The rate of growth as a fraction of the current number of buckets,
    00736         * 0 < n, such that the hash map grows to bucketcount * (1 +
    00737         * growthrate)
    00738         */
    00739         float32_t m_flGrowthRate;
    00740
    00741         /**
    00742         * A count of the number of active Iterators on this map.
    00743         */
    00744         mutable MemberHandle<AtomicCounter> m_hAtomicIterators;
    00745
    00746
    00747     // ----- friends --------------------------------------------------------
    00748
    00749     friend class Entry;
    00750     friend class EntrySet;
    00751     friend class EntrySetIterator;
    00752     };
    00753
    00754 COH_CLOSE_NAMESPACE2
    00755
    00756 #endif // COH_SAFE_HASH_MAP_HPP

Copyright © 2000, 2010, Oracle and/or its affiliates. All rights reserved.