UtlHashBag.h

Go to the documentation of this file.

//
// Copyright (C) 2004-2006 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 _UtlHashBag_h_
#define _UtlHashBag_h_

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

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

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

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

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

   UtlHashBag();

   virtual ~UtlHashBag(); 
/* ============================ MANIPULATORS ============================== */

   virtual UtlContainable* insert(UtlContainable* object);

   virtual UtlContainable* remove(UtlContainable* object);
    
   virtual UtlContainable* removeReference(const UtlContainable* object);

   virtual UtlBoolean destroy(UtlContainable* object);    

   virtual void destroyAll();

   virtual void removeAll();

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

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


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


   size_t entries() const;

   UtlBoolean isEmpty() const;

   UtlBoolean contains(const UtlContainable* object) const;


   virtual UtlContainableType getContainableType() const;

   size_t numberOfBuckets() const
      {
         return NUM_HASHBAG_BUCKETS(mBucketBits);
      }

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

   void notifyIteratorsOfRemove(const UtlLink* pair);


   void resizeIfNeededAndSafe()
      {
         if (   ( mElements / NUM_HASHBAG_BUCKETS(mBucketBits) >= 3 ) // mean bucket 3 or more
             && ( mIteratorList.isUnLinked() )   /* 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.
                                                  */
             )
         {
            resize();
         }
      }
    
   size_t    mElements;   
   size_t    mBucketBits; 
   UtlChain* mpBucket;    

/* //////////////////////////// PRIVATE /////////////////////////////////// */
  private:


   void insert(UtlLink*       link,  
               UtlChain*      bucket 
               );

   void resize();
   bool lookup(const UtlContainable* key, 
               UtlChain*&      bucket,    
               UtlLink*&       pair       
               ) const;
   void insert(UtlPair*        pair,   
               UtlChain*       bucket  
               );

   size_t bucketNumber(unsigned hash) const;


   // Don't allow the implicit copy constructor.
   UtlHashBag(UtlHashBag&);

   UtlHashBag& operator=(UtlHashBag&);
   
};

/* ============================ INLINE METHODS ============================ */


#endif    // _UtlHashBag_h_