UtlHashMap.h

Go to the documentation of this file.

//  
// Copyright (C) 2008-2011 SIPez LLC. All rights reserved.
// Licensed to SIPfoundry under a Contributor Agreement. 
//
// Copyright (C) 2004-2008 SIPfoundry Inc.
// Licensed by SIPfoundry under the LGPL license.
//
// Copyright (C) 2004-2006 Pingtel Corp.  All rights reserved.
// Licensed to SIPfoundry under a Contributor Agreement.
//
// $$


#ifndef _UtlHashMap_h_
#define _UtlHashMap_h_

// SYSTEM INCLUDES
// APPLICATION INCLUDES
#include "utl/UtlDefs.h"
#include "utl/UtlContainer.h"

// DEFINES
// MACROS
#if defined(_WIN64) || defined(__x86_64__) || defined(__ppc64__)
#define NUM_HASHMAP_BUCKETS(bits) (1ull<<bits)
#else
#define NUM_HASHMAP_BUCKETS(bits) (1<<bits)
#endif

// EXTERNAL FUNCTIONS
// EXTERNAL VARIABLES
// CONSTANTS
// STRUCTS
// TYPEDEFS
// FORWARD DECLARATIONS
class UtlContainable;
class UtlPair;

class UtlHashMap : public UtlContainer
{
/* //////////////////////////// PUBLIC //////////////////////////////////// */
public:
    static const UtlContainableType TYPE;

/* ============================ CREATORS ================================== */

    UtlHashMap();

    virtual ~UtlHashMap();

    virtual UtlHashMap* clone() const;

/* ============================ MANIPULATORS ============================== */

    UtlContainable* insertKeyAndValue(UtlContainable* key, UtlContainable* value);
    UtlContainable* insert(UtlContainable* obj);
    UtlContainable* remove(UtlContainable* key);
    UtlContainable* removeReference(const UtlContainable* key);
    UtlContainable* removeKeyAndValue(const UtlContainable* key, UtlContainable*& value);
    virtual UtlBoolean destroy(UtlContainable* key);    
    virtual void destroyAll();


    virtual void removeAll();

/* ============================ ACCESSORS ================================= */

    UtlContainable* findValue(const UtlContainable* key) const;


    virtual UtlContainable* find(const UtlContainable* key) const;

/* ============================ INQUIRY =================================== */

    size_t entries() const;


    UtlBoolean isEmpty() const;


    UtlBoolean contains(const UtlContainable* key) const;
  

    virtual UtlContainableType getContainableType() const;

    void copyInto(UtlHashMap& map) const;
    OsStatus deepCopyInto(UtlHashMap& map) const;
    size_t numberOfBuckets() const
       {
          return NUM_HASHMAP_BUCKETS(mBucketBits);
       }
    

/* //////////////////////////// PROTECTED ///////////////////////////////// */
protected:
    friend class UtlHashMapIterator;

    static const UtlContainable* INTERNAL_NULL;

    inline
    void resizeIfNeededAndSafe();
    size_t    mElements;   
    size_t    mBucketBits; 
    UtlChain* mpBucket;    
    
/* //////////////////////////// PRIVATE /////////////////////////////////// */
private:

    void resize();
    bool lookup(const UtlContainable* key,
                UtlChain*&      bucket,
                UtlPair*&       pair) const;
    void insert(UtlPair*        pair,
                UtlChain*       bucket);
    size_t bucketNumber(unsigned hash) const;
    
    UtlHashMap(UtlHashMap&);

    UtlHashMap& operator=(const UtlHashMap&);
    
    void notifyIteratorsOfRemove(const UtlPair* pair);
};

void UtlHashMap::resizeIfNeededAndSafe()
{
   // IF mean bucket 3 or more AND there are no iterators.
   // Resizing moves elements to new buckets, which could cause an iterator
   // to miss some and to return others more than once.
   if (   ( mElements / NUM_HASHMAP_BUCKETS(mBucketBits) >= 3 ) 
       && ( mIteratorList.isUnLinked() ))
   {
      resize();
   }
}

#endif    // _UtlHashMap_h_