Hashtable.h

/* This file is Copyright 2000-2008 Meyer Sound Laboratories Inc.  See the included LICENSE.txt file for details. */

#ifndef MuscleHashtable_h
#define MuscleHashtable_h

#include "support/MuscleSupport.h"

#ifdef _MSC_VER
# pragma warning(disable: 4786)
#endif

#ifndef MUSCLE_HASHTABLE_DEFAULT_CAPACITY
# define MUSCLE_HASHTABLE_DEFAULT_CAPACITY 7
#endif

BEGIN_NAMESPACE(muscle);

// implementation detail; please ignore this!
static const uint32 MUSCLE_HASHTABLE_INVALID_HASH_CODE = (uint32)-1;

template <class T> class HashFunctor
{
public:
   uint32 operator()(const T x) const {return (uint32)((unsigned long)x);}  // double-cast for AMD64
};

template <class KeyType, class ValueType, class HashFunctorType> class Hashtable;  // forward declaration

enum {
   HTIT_FLAG_BACKWARDS  = (1<<0), // iterate backwards.  Conveniently equal to ((bool)true), for backwards compatibility with old code
   HTIT_FLAG_NOREGISTER = (1<<1), // don't register with Hashtable object, for thread-safety (at the expense of modification-safety)
   NUM_HTIT_FLAGS = 2             // number of HTIT_FLAG_* constants that have been defined
};

template <class KeyType, class ValueType, class HashFunctorType = HashFunctor<KeyType> > class HashtableIterator
{
public:
   HashtableIterator();

   HashtableIterator(const HashtableIterator<KeyType, ValueType, HashFunctorType> & rhs);

   HashtableIterator(const Hashtable<KeyType, ValueType, HashFunctorType> & table, uint32 flags = 0);

   HashtableIterator(const Hashtable<KeyType, ValueType, HashFunctorType> & table, const KeyType & startAt, uint32 flags);

   ~HashtableIterator();

   HashtableIterator<KeyType, ValueType, HashFunctorType> & operator=(const HashtableIterator<KeyType, ValueType, HashFunctorType> & rhs);

   void operator++(int) {(void) GetNextKey(); (void) GetNextValue();}

   void operator--(int) {bool b = IsBackwards(); SetBackwards(!b); (void) GetNextKey(); (void) GetNextValue(); SetBackwards(b);}

   bool HasMoreKeys() const {return ((_nextKeyCookie != NULL)||((_owner)&&(_owner->HasItems())&&(_flags&HTIT_INTERNAL_FLAG_RESTARTKEY)));}

   const KeyType & GetKey() const {return *PeekNextKey();}

   ValueType & GetValue() const {return *PeekNextValue();}

   status_t GetNextKey(KeyType & setNextKey);

   status_t GetNextKey(const KeyType * & setNextKeyPtr);

   const KeyType * GetNextKey();

   status_t PeekNextKey(KeyType & setKey) const;

   status_t PeekNextKey(const KeyType * & setKey) const;

   const KeyType * PeekNextKey() const;

   bool HasMoreValues() const {return ((_nextValueCookie != NULL)||((_owner)&&(_owner->HasItems())&&(_flags & HTIT_INTERNAL_FLAG_RESTARTVALUE)));}

   status_t GetNextValue(ValueType & setNextValue);

   status_t GetNextValue(ValueType * & setValuePtr);

   status_t GetNextValue(const ValueType * & setValuePtr);

   ValueType * GetNextValue();

   status_t PeekNextValue(ValueType & setValue) const;

   status_t PeekNextValue(const ValueType * & setValue) const;

   status_t PeekNextValue(ValueType * & setValue) const;

   ValueType * PeekNextValue() const;

   status_t GetNextKeyAndValue(KeyType & setKey, ValueType & setValue);

   status_t GetNextKeyAndValue(KeyType & setKey, ValueType * & setValuePtr);

   status_t GetNextKeyAndValue(KeyType & setKey, const ValueType * & setValuePtr);

   status_t GetNextKeyAndValue(const KeyType * & setKeyPtr, ValueType & setValue);

   status_t GetNextKeyAndValue(const KeyType * & setKeyPtr, ValueType * & setValuePtr);

   status_t GetNextKeyAndValue(const KeyType * & setKeyPtr, const ValueType * & setValuePtr);

   uint32 GetFlags() const {return _flags;}

   void SetBackwards(bool backwards) {if (backwards) _flags |= HTIT_FLAG_BACKWARDS; else _flags &= ~HTIT_FLAG_BACKWARDS;}

   bool IsBackwards() const {return ((_flags & HTIT_FLAG_BACKWARDS) != 0);}

private:
   enum {
      HTIT_INTERNAL_FLAG_RESTARTKEY   = (1<<31), // tells GetNextKey() not to iterate on the next iteration
      HTIT_INTERNAL_FLAG_RESTARTVALUE = (1<<30)  // tells GetNextValue() not to iterate on the next iteration
   };

   friend class Hashtable<KeyType, ValueType, HashFunctorType>;

   void * _scratchSpace[2];   // ignore this; it's temp scratch space used by EnsureSize().

   void * _nextKeyCookie;
   void * _nextValueCookie;
   uint32 _flags;

   HashtableIterator<KeyType, ValueType, HashFunctorType> * _prevIter;  // for the doubly linked list so that the table can notify us if it is modified
   HashtableIterator<KeyType, ValueType, HashFunctorType> * _nextIter;  // for the doubly linked list so that the table can notify us if it is modified
   const Hashtable<KeyType, ValueType, HashFunctorType>   * _owner;     // table that we are associated with
};

template <class KeyType, class ValueType, class HashFunctorType = HashFunctor<KeyType> > class Hashtable
{
public:
   typedef int (*KeyCompareFunc)(const KeyType& key1, const KeyType& key2, void * cookie);

   typedef int (*ValueCompareFunc)(const ValueType& key1, const ValueType& key2, void * cookie);

   enum {
      AUTOSORT_DISABLED = 0,  
      AUTOSORT_BY_KEY,        
      AUTOSORT_BY_VALUE       
   };

   Hashtable();

   explicit Hashtable(uint32 initialCapacity);

   Hashtable(const Hashtable<KeyType,ValueType,HashFunctorType> & rhs);

   ~Hashtable();

   Hashtable<KeyType,ValueType,HashFunctorType> & operator= (const Hashtable<KeyType,ValueType,HashFunctorType> & rhs);

   bool operator== (const Hashtable<KeyType,ValueType,HashFunctorType> & rhs) const;

   bool operator!= (const Hashtable<KeyType,ValueType,HashFunctorType> & rhs) const {return !(*this == rhs);}

   status_t CopyFrom(const Hashtable<KeyType,ValueType,HashFunctorType> & rhs);

   uint32 GetNumItems() const {return _count;}

   bool IsEmpty() const {return (_count == 0);}

   bool HasItems() const {return (_count > 0);}

   bool ContainsKey(const KeyType& key) const {return (GetEntry(ComputeHash(key), key) != NULL);}

   bool ContainsValue(const ValueType& value) const;

   int32 IndexOfKey(const KeyType& key) const;

   int32 IndexOfValue(const ValueType& value, bool searchBackwards = false) const;

   status_t GetValue(const KeyType& key, ValueType& setValue) const; 

   ValueType * GetValue(const KeyType & key) const;

   status_t GetKey(const KeyType & lookupKey, KeyType & setKey) const;

   const KeyType * GetKey(const KeyType & lookupKey) const;

   HashtableIterator<KeyType,ValueType,HashFunctorType> GetIterator(uint32 flags = 0) const 
   {
      return HashtableIterator<KeyType,ValueType,HashFunctorType>(*this, flags); 
   }

   HashtableIterator<KeyType,ValueType,HashFunctorType> GetIteratorAt(const KeyType & startAt, uint32 flags = 0) const 
   {
      return HashtableIterator<KeyType,ValueType,HashFunctorType>(*this, startAt, flags);
   }

   const KeyType * GetKeyAt(uint32 index) const;

   status_t GetKeyAt(uint32 index, KeyType & retKey) const;

   status_t Put(const KeyType& key, const ValueType& value, ValueType & setPreviousValue, bool * optSetReplaced = NULL) {return (PutAux(ComputeHash(key), key, value, &setPreviousValue, optSetReplaced) != NULL) ? B_NO_ERROR : B_ERROR;}

   status_t Put(const KeyType& key, const ValueType& value) {return (PutAux(ComputeHash(key), key, value, NULL, NULL) != NULL) ? B_NO_ERROR : B_ERROR;}

   status_t Put(const Hashtable<KeyType, ValueType, HashFunctorType> & pairs);

   status_t Remove(const KeyType& key) {return RemoveAux(key, NULL);}

   status_t Remove(const KeyType& key, ValueType & setRemovedValue) {return RemoveAux(key, &setRemovedValue);}

   uint32 Remove(const Hashtable<KeyType, ValueType, HashFunctorType> & pairs);

   status_t RemoveFirst() {return _iterHead ? RemoveEntry(_iterHead, NULL) : B_ERROR;}

   status_t RemoveFirst(KeyType & setRemovedKey) 
   {
      if (_iterHead == NULL) return B_ERROR;
      setRemovedKey = _iterHead->_key;
      return RemoveEntry(_iterHead, NULL);
   }

   status_t RemoveFirst(KeyType & setRemovedKey, ValueType & setRemovedValue) 
   {
      if (_iterHead == NULL) return B_ERROR;
      setRemovedKey = _iterHead->_key;
      return RemoveEntry(_iterHead, &setRemovedValue);
   }

   status_t RemoveLast() {return _iterTail ? RemoveEntry(_iterTail, NULL) : B_ERROR;}

   status_t RemoveLast(KeyType & setRemovedKey) 
   {
      if (_iterTail == NULL) return B_ERROR;
      setRemovedKey = _iterTail->_key;
      return RemoveEntry(_iterTail, NULL);
   }

   status_t RemoveLast(KeyType & setRemovedKey, ValueType & setRemovedValue) 
   {
      if (_iterTail == NULL) return B_ERROR;
      setRemovedKey = _iterTail->_key;
      return RemoveEntry(_iterTail, &setRemovedValue);
   }

   void Clear(bool releaseCachedData = false);

   status_t Reposition(const KeyType & key);

   void SetAutoSortMode(int mode, bool sortNow = true) {_autoSortMode = mode; if (sortNow) (void) Sort();}

   int GetAutoSortMode() const {return _autoSortMode;}

   void SetCompareCookie(void * cookie) {_compareCookie = cookie;}

   void * GetCompareCookie() const {return _compareCookie;}

   void SetKeyCompareFunction(KeyCompareFunc func) {_userKeyCompareFunc = func;}

   KeyCompareFunc GetKeyCompareFunction() const {return _userKeyCompareFunc;}

   void SetValueCompareFunction(ValueCompareFunc func) {_userValueCompareFunc = func;}

   ValueCompareFunc GetValueCompareFunction() const {return _userValueCompareFunc;}

   void SwapContents(Hashtable<KeyType,ValueType,HashFunctorType> & swapMe);

   status_t MoveToFront(const KeyType & moveMe);

   status_t MoveToBack(const KeyType & moveMe);

   status_t MoveToBefore(const KeyType & moveMe, const KeyType & toBeforeMe);

   status_t MoveToBehind(const KeyType & moveMe, const KeyType & toBehindMe);

   status_t MoveToTable(const KeyType & moveMe, Hashtable<KeyType, ValueType> & toTable);

   status_t CopyToTable(const KeyType & copyMe, Hashtable<KeyType, ValueType> & toTable) const;

   status_t Sort() {return SortByAux((_autoSortMode != AUTOSORT_BY_VALUE) ? _userKeyCompareFunc : NULL, (_autoSortMode != AUTOSORT_BY_KEY) ? _userValueCompareFunc : NULL, _compareCookie);}

   void SortByKey(KeyCompareFunc func, void * optCompareCookie = NULL) {(void) SortByAux(func, NULL, optCompareCookie);}

   void SortByValue(ValueCompareFunc func, void * optCompareCookie = NULL) {(void) SortByAux(NULL, func, optCompareCookie);}

   status_t Get(const KeyType& key, ValueType& setValue) const {return GetValue(key, setValue);}

   ValueType * Get(const KeyType & key) const {return GetValue(key);}

   ValueType * GetOrPut(const KeyType & key, const ValueType & defValue)
   {
      uint32 hash = ComputeHash(key);
      HashtableEntry * e = GetEntry(hash, key);
      if (e == NULL) e = PutAux(hash, key, defValue, NULL, NULL);
      return e ? &e->_value : NULL;
   }

   ValueType * GetOrPut(const KeyType & key)
   {
      uint32 hash = ComputeHash(key);
      HashtableEntry * e = GetEntry(hash, key);
      if (e == NULL) e = PutAux(hash, key, ValueType(), NULL, NULL);
      return e ? &e->_value : NULL;
   }

   ValueType GetWithDefault(const KeyType & key) const
   {
      const ValueType * v = Get(key);
      return v ? *v : ValueType();
   }

   ValueType GetWithDefault(const KeyType & key, const ValueType & defaultValue) const
   {
      const ValueType * v = Get(key);
      return v ? *v : defaultValue;
   }

   ValueType * PutAndGet(const KeyType & key, const ValueType & value = ValueType()) 
   { 
       HashtableEntry * e = PutAux(ComputeHash(key), key, value, NULL, NULL);
       return e ? &e->_value : NULL;
   }

   ValueType * PutIfNotAlreadyPresent(const KeyType & key, const ValueType & value) 
   {
       uint32 hash = ComputeHash(key);
       HashtableEntry * e = GetEntry(hash, key);
       if (e) return NULL;
       else
       {
          e = PutAux(hash, key, value, NULL, NULL);
          return e ? &e->_value : NULL;
       }
   }

   ValueType * PutIfNotAlreadyPresent(const KeyType & key) 
   {
       uint32 hash = ComputeHash(key);
       HashtableEntry * e = GetEntry(hash, key);
       if (e) return NULL;
       else
       {
          e = PutAux(hash, key, ValueType(), NULL, NULL);
          return e ? &e->_value : NULL;
       }
   }

   const KeyType * GetFirstKey() const {return _iterHead ? &_iterHead->_key : NULL;}

   const KeyType * GetLastKey() const {return _iterTail ? &_iterTail->_key : NULL;}

   ValueType * GetFirstValue() const {return _iterHead ? &_iterHead->_value : NULL;}

   ValueType * GetLastValue() const {return _iterTail ? &_iterTail->_value : NULL;}

   status_t EnsureSize(uint32 newTableSize);

   uint32 GetNumAllocatedSlots() const {return _tableSize;}

private:
   friend class HashtableIterator<KeyType, ValueType, HashFunctorType>;

   void InitializeIterator(HashtableIterator<KeyType,ValueType,HashFunctorType> & iter) const
   {
      RegisterIterator(&iter);
      iter._nextKeyCookie = iter._nextValueCookie = (iter._flags & HTIT_FLAG_BACKWARDS) ? _iterTail : _iterHead;
   }

   void InitializeIteratorAt(HashtableIterator<KeyType,ValueType,HashFunctorType> & iter, const KeyType & startAt) const
   {
      RegisterIterator(&iter);
      iter._nextKeyCookie = iter._nextValueCookie = GetEntry(ComputeHash(startAt), startAt);
   }

   class HashtableEntry
   {
   public:
      // Note:  _bucketPrev and _bucketNext are intentionally not set here
      HashtableEntry() : _hash(MUSCLE_HASHTABLE_INVALID_HASH_CODE), _iterPrev(NULL), _iterNext(NULL)
#ifndef _MSC_VER
                         , _mapTo(this), _mappedFrom(this)  // this is slightly more efficient...
#endif
      {
#ifdef _MSC_VER
         _mapTo      = this;  // ... but VC++ complains if (this) is in the init list, so for VC++ we do it here
         _mappedFrom = this;
#endif
      }

      ~HashtableEntry() {/* empty */}

      // Frees up our memory and returns us to the free-list.
      void ReturnToFreeList(const KeyType & defaultKey, const ValueType & defaultValue, HashtableEntry ** freeHead)
      {
         _hash  = MUSCLE_HASHTABLE_INVALID_HASH_CODE;
         _key   = defaultKey;
         _value = defaultValue;

         _iterPrev = _iterNext = _bucketPrev = NULL;
         _bucketNext = *freeHead; 
         if (_bucketNext) _bucketNext->_bucketPrev = this;
         *freeHead = this;
      }

      HashtableEntry * RemoveFromFreeList(HashtableEntry * freeHead) 
      {
         if (_bucketNext) _bucketNext->_bucketPrev = _bucketPrev;
         if (_bucketPrev) _bucketPrev->_bucketNext = _bucketNext;
         HashtableEntry * ret = (freeHead == this) ? _bucketNext : freeHead;
         _bucketPrev = _bucketNext = NULL;
         return ret;
      }

      void SwapMaps(HashtableEntry * e)
      {
         muscleSwap(e->_mapTo, _mapTo);
         _mapTo->_mappedFrom = this;
         e->_mapTo->_mappedFrom = e;
      }

      inline HashtableEntry * GetMapTo() const {return _mapTo;}
      inline HashtableEntry * GetMappedFrom() const {return _mappedFrom;}

      static HashtableEntry * CreateEntriesArray(uint32 size)
      {
         HashtableEntry * ret = newnothrow_array(HashtableEntry,size);
         if (ret)
         {
            HashtableEntry * prev = NULL;
            for (uint32 i=0; i<size; i++) 
            {
               HashtableEntry * cur = &ret[i];
               cur->_bucketPrev = prev;
               if (prev) prev->_bucketNext = cur;
               prev = cur;
            }
            ret[size-1]._bucketNext = NULL;
         }
         else WARN_OUT_OF_MEMORY;
         return ret;
      }
  
      uint32 _hash;                // precalculated for efficiency
      KeyType _key;                // used for '==' checking
      ValueType _value;            // payload
      HashtableEntry* _bucketPrev; // for making linked lists in our bucket
      HashtableEntry* _bucketNext; // for making linked lists in our bucket
      HashtableEntry* _iterPrev;   // for user's table iteration
      HashtableEntry* _iterNext;   // for user's table iteration

   private:
      HashtableEntry* _mapTo;
      HashtableEntry* _mappedFrom;
   };

private:
   // Auxilliary methods
   HashtableEntry * PutAux(uint32 hash, const KeyType& key, const ValueType& value, ValueType * optSetPreviousValue, bool * optReplacedFlag);
   status_t RemoveAux(uint32 hash, const KeyType& key, ValueType * optSetValue)
   {
      HashtableEntry * e = GetEntry(hash, key);
      return e ? RemoveEntry(e, optSetValue) : B_ERROR;
   }
   status_t RemoveAux(const KeyType& key, ValueType * optSetValue)
   {
      HashtableEntry * e = GetEntry(ComputeHash(key), key);
      return e ? RemoveEntry(e, optSetValue) : B_ERROR;
   }
   status_t RemoveEntry(HashtableEntry * e, ValueType * optSetValue);

   status_t SortByAux(KeyCompareFunc optKeyFunc, ValueCompareFunc optValueFunc, void * cookie);
   void RepositionAux(HashtableEntry * e);

   inline uint32 ComputeHash(const KeyType & key) const
   {
      uint32 ret = _functor(key);
      if (ret == MUSCLE_HASHTABLE_INVALID_HASH_CODE) ret++;  // avoid using the guard value as a hash code (unlikely but possible)
      return ret;
   }

   // Linked list maintainence
   void InsertSortedIterationEntry(HashtableEntry * e, KeyCompareFunc optKeyFunc, ValueCompareFunc optValueCompareFunc, void * cookie);
   void InsertIterationEntry(HashtableEntry * e, HashtableEntry * optBehindThisOne);
   void RemoveIterationEntry(HashtableEntry * e);
   HashtableEntry * GetEntry(uint32 hash, const KeyType& key) const;
   HashtableEntry * GetEntryAt(uint32 idx) const;
   bool IsBucketHead(const HashtableEntry * e) const {return ((e->_hash != MUSCLE_HASHTABLE_INVALID_HASH_CODE)&&(_table[e->_hash%_tableSize].GetMapTo() == e));}

   int CompareEntries(const HashtableEntry & left, const HashtableEntry & right, KeyCompareFunc optKeyFunc, ValueCompareFunc optValueFunc, void * cookie) const;

   // HashtableIterator's private API
   void RegisterIterator(HashtableIterator<KeyType,ValueType,HashFunctorType> * iter) const
   {
      if (iter->_flags & HTIT_FLAG_NOREGISTER) iter->_prevIter = iter->_nextIter = NULL;
      else
      {
         // add him to the head of our linked list of iterators
         iter->_prevIter = NULL;
         iter->_nextIter = _iterList;  
         if (_iterList) _iterList->_prevIter = iter;
         _iterList = iter;
      }
   }

   void UnregisterIterator(HashtableIterator<KeyType,ValueType,HashFunctorType> * iter) const
   {
      if (iter->_flags & HTIT_FLAG_NOREGISTER) iter->_prevIter = iter->_nextIter = NULL;
      else
      {
         if (iter->_prevIter) iter->_prevIter->_nextIter = iter->_nextIter;
         if (iter->_nextIter) iter->_nextIter->_prevIter = iter->_prevIter;
         if (iter == _iterList) _iterList = iter->_nextIter;
         iter->_prevIter = iter->_nextIter = NULL;
      }
   }

   KeyType * GetKeyFromCookie(void * c) const {return c ? &(((HashtableEntry *)c)->_key) : NULL;}
   ValueType * GetValueFromCookie(void * c) const  {return c ? &(((HashtableEntry *)c)->_value) : NULL;}

   HashtableEntry * GetInitialEntry(uint32 flags) const {return (flags & HTIT_FLAG_BACKWARDS) ? _iterTail : _iterHead;}
   HashtableEntry * GetSubsequentEntry(void * entryPtr, uint32 flags) const 
   {
      HashtableEntry * ep = static_cast<HashtableEntry *>(entryPtr);
      return ep ? ((flags & HTIT_FLAG_BACKWARDS) ? ep->_iterPrev : ep->_iterNext) : NULL;
   }

   void MoveToBackAux(HashtableEntry * moveMe)
   {
      if (moveMe->_iterNext)
      {
         RemoveIterationEntry(moveMe);
         InsertIterationEntry(moveMe, _iterTail);
      }
   }

   void MoveToFrontAux(HashtableEntry * moveMe)
   {
      if (moveMe->_iterPrev)
      {
         RemoveIterationEntry(moveMe);
         InsertIterationEntry(moveMe, NULL);
      }
   }

   void MoveToBeforeAux(HashtableEntry * moveMe, HashtableEntry * toBeforeMe)
   {
      if (moveMe->_iterNext != toBeforeMe)
      {
         RemoveIterationEntry(moveMe);
         InsertIterationEntry(moveMe, toBeforeMe->_iterPrev);
      }
   }

   void MoveToBehindAux(HashtableEntry * moveMe, HashtableEntry * toBehindMe)
   {
      if (moveMe->_iterPrev != toBehindMe)
      {
         RemoveIterationEntry(moveMe);
         InsertIterationEntry(moveMe, toBehindMe);
      }
   }

   uint32 NextPrime(uint32 start) const;

   const uint32 _initialCapacity;
   uint32 _count;       // the number of valid elements in the hashtable
   uint32 _tableSize;   // the number of entries in _table (or the number to allocate if _table is NULL)

   HashtableEntry * _table;       // our array of table entries
   HashtableEntry * _iterHead;    // start of linked list to iterate through
   HashtableEntry * _iterTail;    // end of linked list to iterate through

   HashtableEntry * _freeHead;    // head of the list of unused HashtableEntries in our _table array

   KeyCompareFunc _userKeyCompareFunc;       // (optional) used to compare two Keys
   ValueCompareFunc _userValueCompareFunc;   // (optional) used to compare two Values
   int _autoSortMode;                        // one of the AUTOSORT_BY_* tokens
   void * _compareCookie;                    // (optional) passed to the CompareFuncs

   HashFunctorType _functor;  // used to compute hash codes for key objects

   mutable HashtableIterator<KeyType, ValueType, HashFunctorType> * _iterList;  // list of existing iterators for this table
};

//===============================================================
// Implementation of Hashtable
// Necessary location for appropriate template instantiation.
//===============================================================

template <class KeyType, class ValueType, class HashFunctorType>
Hashtable<KeyType,ValueType,HashFunctorType>::Hashtable()
   : _initialCapacity(MUSCLE_HASHTABLE_DEFAULT_CAPACITY), _count(0), _tableSize(MUSCLE_HASHTABLE_DEFAULT_CAPACITY), _table(NULL), _iterHead(NULL), _iterTail(NULL), _freeHead(NULL), _userKeyCompareFunc(NULL), _userValueCompareFunc(NULL), _autoSortMode(AUTOSORT_DISABLED), _compareCookie(NULL), _iterList(NULL)
{
   // empty
}

template <class KeyType, class ValueType, class HashFunctorType>
Hashtable<KeyType,ValueType,HashFunctorType>::Hashtable(uint32 initialCapacity)
   : _initialCapacity(initialCapacity), _count(0), _tableSize(initialCapacity), _table(NULL), _iterHead(NULL), _iterTail(NULL), _freeHead(NULL), _userKeyCompareFunc(NULL), _userValueCompareFunc(NULL), _autoSortMode(AUTOSORT_DISABLED), _compareCookie(NULL), _iterList(NULL)
{
   // empty
}

template <class KeyType, class ValueType, class HashFunctorType>
Hashtable<KeyType,ValueType,HashFunctorType>::
Hashtable(const Hashtable<KeyType,ValueType,HashFunctorType> & rhs)
   : _initialCapacity(rhs._initialCapacity), _count(0), _tableSize(rhs._tableSize), _table(NULL), _iterHead(NULL), _iterTail(NULL), _freeHead(NULL), _userKeyCompareFunc(rhs._userKeyCompareFunc), _userValueCompareFunc(rhs._userValueCompareFunc), _autoSortMode(rhs._autoSortMode), _compareCookie(rhs._compareCookie), _iterList(NULL)
{
   *this = rhs;
}

template <class KeyType, class ValueType, class HashFunctorType>
Hashtable<KeyType, ValueType, HashFunctorType> &
Hashtable<KeyType, ValueType, HashFunctorType> ::
operator=(const Hashtable<KeyType, ValueType, HashFunctorType> & rhs)
{
   if (this != &rhs)
   {
      Clear();
      if (EnsureSize(rhs.GetNumItems()) == B_NO_ERROR)
      {
         const HashtableEntry * e = rhs._iterHead;    // start of linked list to iterate through
         while(e)
         {
            (void) PutAux(e->_hash, e->_key, e->_value, NULL, NULL);
            e = e->_iterNext;
         }
      }
   }
   return *this;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t
Hashtable<KeyType, ValueType, HashFunctorType> ::
CopyFrom(const Hashtable<KeyType, ValueType, HashFunctorType> & rhs)
{
   if (this == &rhs) return B_NO_ERROR;

   Clear();
   if (EnsureSize(rhs.GetNumItems()) != B_NO_ERROR) return B_ERROR;

   const HashtableEntry * e = rhs._iterHead;    // start of linked list to iterate through
   while(e)
   {
      (void) PutAux(e->_hash, e->_key, e->_value, NULL, NULL);
      e = e->_iterNext;
   }
   return B_NO_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
bool
Hashtable<KeyType, ValueType, HashFunctorType> ::
operator==(const Hashtable<KeyType, ValueType, HashFunctorType> & rhs) const
{
   if (this == &rhs) return true;
   if (GetNumItems() != rhs.GetNumItems()) return false;

   const HashtableEntry * e = _iterHead;
   while(e)
   {
      const HashtableEntry * hisE = rhs.GetEntry(e->_hash, e->_key);
      if ((hisE == NULL)||(hisE->_value != e->_value)) return false;
      e = e->_iterNext;
   }
   return true;
}

template <class KeyType, class ValueType, class HashFunctorType>
Hashtable<KeyType,ValueType,HashFunctorType>::~Hashtable()
{
   Clear(true);
}

template <class KeyType, class ValueType, class HashFunctorType>
bool
Hashtable<KeyType,ValueType,HashFunctorType>::ContainsValue(const ValueType & value) const
{
   const HashtableEntry * e = _iterHead;
   while(e)
   {
      if (e->_value == value) return true;
      e = e->_iterNext;
   }
   return false;
}

template <class KeyType, class ValueType, class HashFunctorType>
int32
Hashtable<KeyType,ValueType,HashFunctorType>::IndexOfKey(const KeyType& key) const
{
   const HashtableEntry * entry = GetEntry(ComputeHash(key), key);
   int32 count = -1;
   if (entry)
   {
      if (entry == _iterTail) count = GetNumItems()-1;
      else
      {
         while(entry)
         {
            entry = entry->_iterPrev; 
            count++;
         }
      }
   }
   return count;
}

template <class KeyType, class ValueType, class HashFunctorType>
int32
Hashtable<KeyType,ValueType,HashFunctorType>::IndexOfValue(const ValueType& value, bool searchBackwards) const
{
   if (searchBackwards)
   {
      int32 idx = GetNumItems();
      const HashtableEntry * entry = _iterTail;
      while(entry)
      {
         --idx;
         if (entry->_value == value) return idx;
         entry = entry->_iterPrev;
      }
   }
   else
   {
      int32 idx = 0;
      const HashtableEntry * entry = _iterHead;
      while(entry)
      {
         if (entry->_value == value) return idx;
         entry = entry->_iterNext;
         idx++;
      }
   }
   return -1;
}

template <class KeyType, class ValueType, class HashFunctorType>
const KeyType * 
Hashtable<KeyType,ValueType,HashFunctorType>::GetKeyAt(uint32 index) const
{
   HashtableEntry * e = GetEntryAt(index);
   return e ? &e->_key : NULL;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t 
Hashtable<KeyType,ValueType,HashFunctorType>::GetKeyAt(uint32 index, KeyType & retKey) const
{
   HashtableEntry * e = GetEntryAt(index);
   if (e)
   {
      retKey = e->_key;
      return B_NO_ERROR;
   }
   return B_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t
Hashtable<KeyType,ValueType,HashFunctorType>::GetValue(const KeyType& key, ValueType & setValue) const
{
   ValueType * ptr = GetValue(key);
   if (ptr)
   {
      setValue = *ptr;
      return B_NO_ERROR;
   }
   else return B_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
ValueType *
Hashtable<KeyType,ValueType,HashFunctorType>::GetValue(const KeyType& key) const
{
   HashtableEntry * e = GetEntry(ComputeHash(key), key);
   return e ? &e->_value : NULL;
}

template <class KeyType, class ValueType, class HashFunctorType>
const KeyType * 
Hashtable<KeyType,ValueType,HashFunctorType>::GetKey(const KeyType& lookupKey) const
{
   HashtableEntry * e = GetEntry(ComputeHash(lookupKey), lookupKey);
   return e ? &e->_key : NULL;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t
Hashtable<KeyType,ValueType,HashFunctorType>::GetKey(const KeyType& lookupKey, KeyType & setKey) const
{
   const KeyType * ptr = GetKey(lookupKey);
   if (ptr)
   {
      setKey = *ptr;
      return B_NO_ERROR;
   }
   else return B_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
typename Hashtable<KeyType,ValueType,HashFunctorType>::HashtableEntry *
Hashtable<KeyType,ValueType,HashFunctorType>::GetEntry(uint32 hash, const KeyType& key) const
{
   if (HasItems()) 
   {
      HashtableEntry * e = _table[hash%_tableSize].GetMapTo();
      if (IsBucketHead(e))  // if the e isn't the start of a bucket, then we know our entry doesn't exist
      {
         // While loops separated out for efficiency (one less if statement) --jaf
         if (_userKeyCompareFunc)
         {
            while(e)
            {
               if ((e->_hash == hash)&&(_userKeyCompareFunc(e->_key, key, _compareCookie) == 0)) return e;
               e = e->_bucketNext; 
            }
         }
         else
         {
            while(e)
            {
               if ((e->_hash == hash)&&(e->_key == key)) return e;
               e = e->_bucketNext; 
            }
         }
      }
   }
   return NULL;
}

template <class KeyType, class ValueType, class HashFunctorType>
typename Hashtable<KeyType,ValueType,HashFunctorType>::HashtableEntry *
Hashtable<KeyType,ValueType,HashFunctorType>::GetEntryAt(uint32 idx) const
{
   HashtableEntry * e = NULL;
   if (idx < _count)
   {
      if (idx < _count/2)
      {
         e = _iterHead;
         while((e)&&(idx--)) e = e->_iterNext;
      }
      else
      {
         idx = _count-(idx+1);
         e = _iterTail;
         while((e)&&(idx--)) e = e->_iterPrev;
      }
   }
   return e;
}

template <class KeyType, class ValueType, class HashFunctorType>
int
Hashtable<KeyType,ValueType,HashFunctorType>::CompareEntries(const HashtableEntry & left, const HashtableEntry & right, KeyCompareFunc optKeyFunc, ValueCompareFunc optValueFunc, void * cookie) const
{
   return optValueFunc ? optValueFunc(left._value, right._value, cookie) : (optKeyFunc ? optKeyFunc(left._key, right._key, cookie) : 0);
}

// Linked-list MergeSort adapted from Simon Tatham's C code at http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c
template <class KeyType, class ValueType, class HashFunctorType>
status_t 
Hashtable<KeyType,ValueType,HashFunctorType>::SortByAux(KeyCompareFunc optKeyFunc, ValueCompareFunc optValueFunc, void * cookie)
{
   if ((optKeyFunc)||(optValueFunc))
   {
      if (_iterHead)
      {
         for (uint32 mergeSize = 1; /* empty */; mergeSize *= 2)
         {
            HashtableEntry * p = _iterHead;
            _iterHead = _iterTail = NULL;

            uint32 numMerges = 0;  /* count number of merges we do in this pass */
            while(p) 
            {
               numMerges++;  /* there exists a merge to be done */

               /* step `mergeSize' places along from p */
               HashtableEntry * q = p;
               uint32 psize = 0;
               for (uint32 i=0; i<mergeSize; i++) 
               {
                   psize++;
                   q = q->_iterNext;
                   if (!q) break;
               }

               /* now we have two lists; merge them */
               for (uint32 qsize=mergeSize; ((psize > 0)||((qsize > 0)&&(q))); /* empty */) 
               {
                  HashtableEntry * e;

                  /* decide whether next element of the merge comes from p or q */
                       if (psize == 0)                                                {e = q; q = q->_iterNext; qsize--;}
                  else if ((qsize == 0)||(!q))                                        {e = p; p = p->_iterNext; psize--;}
                  else if (CompareEntries(*p,*q,optKeyFunc,optValueFunc,cookie) <= 0) {e = p; p = p->_iterNext; psize--;}
                  else                                                                {e = q; q = q->_iterNext; qsize--;}

                  /* append to our new more-sorted list */
                  if (_iterTail) _iterTail->_iterNext = e;
                            else _iterHead = e;
                  e->_iterPrev = _iterTail;
                  _iterTail = e;
               }

               p = q; /* now p has stepped `mergeSize' places along, and q has too */
            }
            _iterTail->_iterNext = NULL;
            if (numMerges <= 1) return B_NO_ERROR;
         }
      }
      return B_NO_ERROR;  // it's easy to sort an empty list :^)
   }
   return B_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t
Hashtable<KeyType,ValueType,HashFunctorType>::EnsureSize(uint32 requestedSize)
{
   if (_tableSize >= requestedSize) return B_NO_ERROR;  // no need to do anything if we're already big enough!

   // 1. Initialize the scratch space for our active iterators.
   {
      HashtableIterator<KeyType,ValueType,HashFunctorType> * nextIter = _iterList;
      while(nextIter)
      {
         nextIter->_scratchSpace[0] = nextIter->_scratchSpace[1] = NULL;  // these will hold our switch-to-on-success values
         nextIter = nextIter->_nextIter;
      }
   }
    
   // 2. Create a new, bigger table, and fill it with a copy of all of our data.
   Hashtable<KeyType,ValueType,HashFunctorType> biggerTable(NextPrime(muscleMax(_count, requestedSize)));
   biggerTable.SetKeyCompareFunction(_userKeyCompareFunc);
   biggerTable.SetValueCompareFunction(_userValueCompareFunc);
   biggerTable.SetCompareCookie(_compareCookie);
   biggerTable.SetAutoSortMode(_autoSortMode);
   {
      HashtableEntry * next = _iterHead;
      while(next)
      {
         HashtableEntry * hisClone = biggerTable.PutAux(next->_hash, next->_key, next->_value, NULL, NULL);
         if (hisClone)
         {
            // Mark any iterators that will need to be redirected to point to the new nodes.
            HashtableIterator<KeyType,ValueType,HashFunctorType> * nextIter = _iterList;
            while(nextIter)
            {
               if (nextIter->_nextKeyCookie   == next) nextIter->_scratchSpace[0] = hisClone;
               if (nextIter->_nextValueCookie == next) nextIter->_scratchSpace[1] = hisClone;
               nextIter = nextIter->_nextIter;
            }
         }
         else return B_ERROR;  // oops, out of mem, too bad.  

         next = next->_iterNext;
      }
   }

   // 3. Swap contents with the bigger table, but don't swap iterator lists (we want to keep ours!)
   {
      HashtableIterator<KeyType,ValueType,HashFunctorType> * temp = _iterList;
      _iterList = NULL;
      SwapContents(biggerTable);
      _iterList = temp;
   }

   // 4. Lastly, fix up our iterators to point to their new entries.
   {
      HashtableIterator<KeyType,ValueType,HashFunctorType> * nextIter = _iterList;
      while(nextIter)
      {
         nextIter->_nextKeyCookie   = nextIter->_scratchSpace[0];
         nextIter->_nextValueCookie = nextIter->_scratchSpace[1];
         nextIter = nextIter->_nextIter;
      }
   }

   return B_NO_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
void
Hashtable<KeyType,ValueType,HashFunctorType>::SwapContents(Hashtable<KeyType,ValueType,HashFunctorType> & swapMe)
{
   muscleSwap(_count,                swapMe._count);
   muscleSwap(_tableSize,            swapMe._tableSize);
   muscleSwap(_table,                swapMe._table);
   muscleSwap(_iterHead,             swapMe._iterHead);
   muscleSwap(_iterTail,             swapMe._iterTail);
   muscleSwap(_freeHead,             swapMe._freeHead);
   muscleSwap(_userKeyCompareFunc,   swapMe._userKeyCompareFunc);
   muscleSwap(_userValueCompareFunc, swapMe._userValueCompareFunc);
   muscleSwap(_autoSortMode,         swapMe._autoSortMode);
   muscleSwap(_compareCookie,        swapMe._compareCookie);
   muscleSwap(_iterList,             swapMe._iterList);

   // Lastly, swap the owners of all iterators, so that they will unregister from the correct table when they die
   {
      HashtableIterator<KeyType,ValueType,HashFunctorType> * next = _iterList;
      while(next)
      {
         next->_owner = &swapMe;
         next = next->_nextIter;
      }
   }
   {
      HashtableIterator<KeyType,ValueType,HashFunctorType> * next = swapMe._iterList;
      while(next)
      {
         next->_owner = this;
         next = next->_nextIter;
      }
   }
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t 
Hashtable<KeyType,ValueType,HashFunctorType>::CopyToTable(const KeyType & copyMe, Hashtable<KeyType, ValueType> & toTable) const
{
   uint32 hash = ComputeHash(copyMe);
   const HashtableEntry * e = GetEntry(hash, copyMe);
   if (e)
   { 
      if (this == &toTable) return B_NO_ERROR;  // it's already here!
      if (toTable.PutAux(hash, copyMe, e->_value, NULL, NULL) != NULL) return B_NO_ERROR;
   }
   return B_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t 
Hashtable<KeyType,ValueType,HashFunctorType>::MoveToTable(const KeyType & moveMe, Hashtable<KeyType, ValueType> & toTable)
{
   uint32 hash = ComputeHash(moveMe);
   const HashtableEntry * e = GetEntry(hash, moveMe);
   if (e)
   {
      if (this == &toTable) return B_NO_ERROR;  // it's already here!
      if (toTable.PutAux(hash, moveMe, e->_value, NULL, NULL) != NULL) return RemoveAux(e->_hash, moveMe, NULL);
   }
   return B_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t 
Hashtable<KeyType,ValueType,HashFunctorType>::MoveToFront(const KeyType & moveMe)
{
   HashtableEntry * e = GetEntry(ComputeHash(moveMe), moveMe);
   if (e == NULL) return B_ERROR;
   MoveToFrontAux(e);
   return B_NO_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t 
Hashtable<KeyType,ValueType,HashFunctorType>::MoveToBack(const KeyType & moveMe)
{
   HashtableEntry * e = GetEntry(ComputeHash(moveMe), moveMe);
   if (e == NULL) return B_ERROR;
   MoveToBackAux(e);
   return B_NO_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t 
Hashtable<KeyType,ValueType,HashFunctorType>::MoveToBefore(const KeyType & moveMe, const KeyType & toBeforeMe)
{
   if (HasItems())
   {
      HashtableEntry * e = GetEntry(ComputeHash(moveMe),     moveMe);
      HashtableEntry * f = GetEntry(ComputeHash(toBeforeMe), toBeforeMe);
      if ((e == NULL)||(f == NULL)||(e == f)) return B_ERROR;
      MoveToBeforeAux(e, f);
      return B_NO_ERROR;
   }
   else return B_ERROR;
}

template <class KeyType, class ValueType, class HashFunctorType>
status_t 
Hashtable<KeyType,ValueType,HashFunctorType>::MoveToBehind(const KeyType & moveMe, const KeyType & toBehindMe)
{
   if (HasItems())
   {
      HashtableEntry * d = GetEntry(ComputeHash(toBehindMe), toBehindMe);
      HashtableEntry * e = GetEntry(ComputeHash(moveMe),     moveMe);
      if ((d == NULL)||(e == NULL)||(d == e)) return B_ERROR;
      MoveToBehindAux(e, d);
      return B_NO_ERROR;
   }
   else return B_ERROR;
}

// Adds (e) to the end of our iteration linked list, or to an appropriate location to maintain sorting, if a sorting function is specified.
template <class KeyType, class ValueType, class HashFunctorType>
void
Hashtable<KeyType,ValueType,HashFunctorType>::InsertSortedIterationEntry(HashtableEntry * e, KeyCompareFunc optKeyFunc, ValueCompareFunc optValueFunc, void * cookie)
{
   HashtableEntry * insertAfter = _iterTail;  // default to appending to the end of the list
   if ((_iterHead)&&((optKeyFunc)||(optValueFunc)))
   {
      // We're in sorted mode, so we'll try to place this guy in the correct position.
           if (CompareEntries(*e, *_iterHead, optKeyFunc, optValueFunc, cookie) < 0) insertAfter = NULL;  // easy; append to the head of the list
      else if (CompareEntries(*e, *_iterTail, optKeyFunc, optValueFunc, cookie) < 0)  // only iterate through if we're before the tail, otherwise the tail is fine
      {
         HashtableEntry * prev = _iterHead;
         HashtableEntry * next = _iterHead->_iterNext;  // more difficult;  find where to insert into the middle
         while(next)
         {
            if (CompareEntries(*e, *next, optKeyFunc, optValueFunc, cookie) < 0)
            {
               insertAfter = prev;
               break;
            }
            else 
            {
               prev = next;
               next = next->_iterNext;
            }
         }   
      }
   }
   InsertIterationEntry(e, insertAfter);
}

// Adds (e) to the our iteration linked list, behind (optBehindThis), or at the head if (optBehindThis) is NULL.
template <class KeyType, class ValueType, class HashFunctorType>
void
Hashtable<KeyType,ValueType,HashFunctorType>::InsertIterationEntry(HashtableEntry * e, HashtableEntry * optBehindThis)
{
   e->_iterPrev = optBehindThis;
   e->_iterNext = optBehindThis ? optBehindThis->_iterNext : _iterHead;
   if (e->_iterPrev) e->_iterPrev->_iterNext = e;
                else _iterHead = e;
   if (e->_iterNext) e->_iterNext->_iterPrev = e;
                else _iterTail = e;
}

// Remove (e) from our iteration linked list
template <class KeyType, class ValueType, class HashFunctorType>
void 
Hashtable<KeyType,ValueType,HashFunctorType>::RemoveIterationEntry(HashtableEntry * e)
{
   // Update any iterators that were pointing at (e), so that they now point to the entry after e.
   HashtableIterator<KeyTyp