Public API Reference

csutil/hash.h

Go to the documentation of this file.

/*
    Copyright (C) 2003 by Mat Sutcliffe <[email protected]>

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef __CS_UTIL_HASH_H__
#define __CS_UTIL_HASH_H__

#include "csextern.h"
#include "csutil/array.h"
#include "csutil/comparator.h"
#include "csutil/util.h"


CS_CRYSTALSPACE_EXPORT unsigned int csHashCompute (char const*);

CS_CRYSTALSPACE_EXPORT unsigned int csHashCompute (char const*, size_t length);

template <class T>
class csHashComputer
{
public:
  static uint ComputeHash (const T& key)
  {
    return key.GetHash();
  }
};

template <class T>
class csHashComputerIntegral
{
public:
  static uint ComputeHash (const T& key)
  {
    return (uintptr_t)key;
  }
};


template<>
class csHashComputer<void*> : public csHashComputerIntegral<void*> {};
  
template<>
class csHashComputer<int> : public csHashComputerIntegral<int> {}; 
template<>
class csHashComputer<unsigned int> : 
  public csHashComputerIntegral<unsigned int> {}; 
    
template<>
class csHashComputer<long> : public csHashComputerIntegral<long> {}; 
template<>
class csHashComputer<unsigned long> : 
  public csHashComputerIntegral<unsigned long> {}; 

#if (CS_LONG_SIZE < 8)    
template<>
class csHashComputer<longlong> : 
  public csHashComputerIntegral<longlong> {}; 
template<>
class csHashComputer<ulonglong> : 
  public csHashComputerIntegral<ulonglong> {}; 
#endif
    
template<>
class csHashComputer<float>
{
public:
  static uint ComputeHash (float key)
  {
    union
    {
      float f;
      uint u;
    } float2uint;
    float2uint.f = key;
    return float2uint.u;
  }
};
template<>
class csHashComputer<double>
{
public:
  static uint ComputeHash (double key)
  {
    union
    {
      double f;
      uint u;
    } double2uint;
    double2uint.f = key;
    return double2uint.u;
  }
};

template <typename T>
class csPtrKey
{
  T* ptr;
public:
  csPtrKey () : ptr(0) {}
  csPtrKey (T* ptr) : ptr(ptr) {}
  csPtrKey (csPtrKey const& other) : ptr (other.ptr) {}

  uint GetHash () const { return (uintptr_t)ptr; }
  inline friend bool operator < (const csPtrKey& r1, const csPtrKey& r2)
  { return r1.ptr < r2.ptr; }
  operator T* () const
  { return ptr; }
  T* operator -> () const
  { return ptr; }
  csPtrKey& operator = (csPtrKey const& other)
  { ptr = other.ptr; return *this; }
};

template <class T>
class csHashComputerString
{
public:
  static uint ComputeHash (const T& key)
  {
    return csHashCompute ((const char*)key);
  }
};

template<>
class csHashComputer<const char*> : public csHashComputerString<const char*> {};

template <class T>
class csHashComputerStruct
{
public:
  static uint ComputeHash (const T& key)
  {
    return csHashCompute ((char*)&key, sizeof (T));
  }
};

#include "csutil/win32/msvc_deprecated_warn_off.h"

class CS_DEPRECATED_TYPE_MSG("csString can also be used for hash keys") 
  csStrKey
{
private:
  char* str;

public:
  csStrKey () { str = 0; }
  csStrKey (const char* s) { str = csStrNew (s); }
  csStrKey (const csStrKey& c) { str = csStrNew (c.str); }
  ~csStrKey () { delete[] str; }
  csStrKey& operator=(const csStrKey& o)
  {
    delete[] str; str = csStrNew (o.str);
    return *this;
  }
  operator const char* () const { return str; }
  uint GetHash() const { return csHashCompute (str); }
};

template<>
class csComparator<csStrKey, csStrKey> : public csComparatorString<csStrKey> {};

#include "csutil/win32/msvc_deprecated_warn_on.h"

template <class T, class K = unsigned int, 
  class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc> 
class csHash
{
protected:
  struct Element
  {
    const K key;
    T value;

    Element (const K& key0, const T &value0) : key (key0), value (value0) {}
    Element (const Element &other) : key (other.key), value (other.value) {}
  };
  typedef csArray<Element, csArrayElementHandler<Element>,
    ArrayMemoryAlloc> ElementArray;
  csArray<ElementArray, csArrayElementHandler<ElementArray>,
    ArrayMemoryAlloc> Elements;

  size_t Modulo;

private:
  size_t InitModulo;
  size_t GrowRate;
  size_t MaxSize;
  size_t Size;

  void Grow ()
  {
    static const size_t Primes[] =
    {
      53,         97,         193,       389,       769, 
      1543,       3079,       6151,      12289,     24593,
      49157,      98317,      196613,    393241,    786433,
      1572869,    3145739,    6291469,   12582917,  25165843,
      50331653,   100663319,  201326611, 402653189, 805306457,
      1610612741, 0
    };

    const size_t *p;
    size_t elen = Elements.Length ();
    for (p = Primes; *p && *p <= elen; p++) ;
    Modulo = *p;
    CS_ASSERT (Modulo);

    Elements.SetLength(Modulo, ElementArray (0, MIN(Modulo / GrowRate, 4)));

    for (size_t i = 0; i < elen; i++)
    {
      ElementArray& src = Elements[i];
      size_t slen = src.Length ();
      for (size_t j = slen; j > 0; j--)
      {
        const Element& srcElem = src[j - 1];
        ElementArray& dst = 
          Elements.Get (csHashComputer<K>::ComputeHash (srcElem.key) % Modulo);
        if (&src != &dst)
        {
          dst.Push (srcElem);
          src.DeleteIndex (j - 1);
        }
      }
    }
  }

public:
  csHash (size_t size = 23, size_t grow_rate = 5, size_t max_size = 20000)
    : Modulo (size), InitModulo (size),
      GrowRate (MIN (grow_rate, size)), MaxSize (max_size), Size (0)
  {
  }

  csHash (const csHash<T> &o) : Elements (o.Elements),
    Modulo (o.Modulo), InitModulo (o.InitModulo),
    GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {}

  void Put (const K& key, const T &value)
  {
    if (Elements.GetSize() == 0) Elements.SetLength (Modulo);
    ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    values.Push (Element (key, value));
    Size++;
    if (values.Length () > Elements.Length () / GrowRate
     && Elements.Length () < MaxSize) Grow ();
  }

  csArray<T> GetAll (const K& key) const
  {
    return GetAll<typename csArray<T>::ElementHandlerType, 
      typename csArray<T>::AllocatorType> (key);
  }

  template<typename H, typename M>
  csArray<T, H, M> GetAll (const K& key) const
  {
    if (Elements.GetSize() == 0) return csArray<T> ();
    const ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    csArray<T> ret (values.Length () / 2);
    const size_t len = values.Length ();
    for (size_t i = 0; i < len; ++i)
    {
      const Element& v = values[i];
      if (csComparator<K, K>::Compare (v.key, key) == 0) 
        ret.Push (v.value);
    }
    return ret;
  }

  void PutUnique (const K& key, const T &value)
  {
    if (Elements.GetSize() == 0) Elements.SetLength (Modulo);
    ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    const size_t len = values.Length ();
    for (size_t i = 0; i < len; ++i)
    {
      Element& v = values[i];
      if (csComparator<K, K>::Compare (v.key, key) == 0)
      {
        v.value = value;
        return;
      }
    }

    values.Push (Element (key, value));
    Size++;
    if (values.Length () > Elements.Length () / GrowRate
     && Elements.Length () < MaxSize) Grow ();
  }

  CS_DEPRECATED_METHOD_MSG("Use PutUnique() instead.")
  void PutFirst (const K& key, const T &value)
  {
    PutUnique(key, value);
  }

  bool Contains (const K& key) const
  {
    if (Elements.GetSize() == 0) return false;
    const ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    const size_t len = values.Length ();
    for (size_t i = 0; i < len; ++i)
      if (csComparator<K, K>::Compare (values[i].key, key) == 0) 
        return true;
    return false;
  }

  bool In (const K& key) const
  { return Contains(key); }

  const T* GetElementPointer (const K& key) const
  {
    if (Elements.GetSize() == 0) return 0;
    const ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    const size_t len = values.Length ();
    for (size_t i = 0; i < len; ++i)
    {
      const Element& v = values[i];
      if (csComparator<K, K>::Compare (v.key, key) == 0)
        return &v.value;
    }

    return 0;
  }

  T* GetElementPointer (const K& key)
  {
    if (Elements.GetSize() == 0) return 0;
    ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    const size_t len = values.Length ();
    for (size_t i = 0; i < len; ++i)
    {
      Element& v = values[i];
      if (csComparator<K, K>::Compare (v.key, key) == 0)
        return &v.value;
    }

    return 0;
  }

  const T& Get (const K& key, const T& fallback) const
  {
    if (Elements.GetSize() == 0) return fallback;
    const ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    const size_t len = values.Length ();
    for (size_t i = 0; i < len; ++i)
    {
      const Element& v = values[i];
      if (csComparator<K, K>::Compare (v.key, key) == 0)
        return v.value;
    }

    return fallback;
  }

  T& Get (const K& key, T& fallback)
  {
    if (Elements.GetSize() == 0) return fallback;
    ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    const size_t len = values.Length ();
    for (size_t i = 0; i < len; ++i)
    {
      Element& v = values[i];
      if (csComparator<K, K>::Compare (v.key, key) == 0)
        return v.value;
    }

    return fallback;
  }

  void DeleteAll ()
  {
    Elements.DeleteAll();
    Modulo = InitModulo;
    Size = 0;
  }

  void Empty() { DeleteAll(); }

  bool DeleteAll (const K& key)
  {
    bool ret = false;
    if (Elements.GetSize() == 0) return ret;
    ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    for (size_t i = values.Length (); i > 0; i--)
    {
      const size_t idx = i - 1;
      if (csComparator<K, K>::Compare (values[idx].key, key) == 0)
      {
        values.DeleteIndexFast (idx);
        ret = true;
        Size--;
      }
    }
    return ret;
  }
  
  bool Delete (const K& key, const T &value)
  {
    bool ret = false;
    if (Elements.GetSize() == 0) return ret;
    ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    for (size_t i = values.Length (); i > 0; i--)
    {
      const size_t idx = i - 1;
      if ((csComparator<K, K>::Compare (values[idx].key, key) == 0) && 
          (csComparator<T, T>::Compare (values[idx].value, value) == 0 ))
      {
        values.DeleteIndexFast (idx);
        ret = true;
        Size--;
      }
    }
    return ret;
  }

  size_t GetSize () const
  {
    return Size;
  }

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

  class Iterator
  {
  private:
    csHash<T, K>* hash;
    const K key;
    size_t bucket, size, element;

    void Seek ()
    {
      while ((element < size) && 
        (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 
        key) != 0))
          element++;
    }

  protected:
    Iterator (csHash<T, K>* hash0, const K& key0) :
      hash(hash0),
      key(key0), 
      bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo),
      size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].Length () : 0)
      { Reset (); }

    friend class csHash<T, K>;
  public:
    Iterator (const Iterator &o) :
      hash (o.hash),
      key(o.key),
      bucket(o.bucket),
      size(o.size),
      element(o.element) {}

    Iterator& operator=(const Iterator& o)
    {
      hash = o.hash;
      key = o.key;
      bucket = o.bucket;
      size = o.size;
      element = o.element;
      return *this;
    }

    bool HasNext () const
    {
      return element < size;
    }

    T& Next ()
    {
      T &ret = hash->Elements[bucket][element].value;
      element++;
      Seek ();
      return ret;
    }

    void Reset () { element = 0; Seek (); }
  };
  friend class Iterator;

  class GlobalIterator
  {
  private:
    csHash<T, K> *hash;
    size_t bucket, size, element;

    void Zero () { bucket = element = 0; }
    void Init () 
    { 
      size = 
        (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].Length () : 0;
    }

    void FindItem ()
    {
      if (element >= size)
      {
        while (++bucket < hash->Elements.Length ())
        {
          Init ();
          if (size != 0)
          {
            element = 0;
            break;
          }
        }
      }
    }

  protected:
    GlobalIterator (csHash<T, K> *hash0) : hash (hash0) 
    { 
      Zero (); 
      Init (); 
      FindItem ();
    }

    friend class csHash<T, K>;
  public:
    GlobalIterator (const GlobalIterator &o) :
      hash (o.hash),
      bucket (o.bucket),
      size (o.size),
      element (o.element) {}

    GlobalIterator& operator=(const GlobalIterator& o)
    {
      hash = o.hash;
      bucket = o.bucket;
      size = o.size;
      element = o.element;
      return *this;
    }

    bool HasNext () const
    {
      if (hash->Elements.Length () == 0) return false;
      return element < size || bucket < hash->Elements.Length ();
    }

    void Advance ()
    {
      element++;
      FindItem ();
    }

    T& NextNoAdvance ()
    {
      return hash->Elements[bucket][element].value;
    }

    T& Next ()
    {
      T &ret = NextNoAdvance ();
      Advance ();
      return ret;
    }

    T& NextNoAdvance (K &key)
    {
      key = hash->Elements[bucket][element].key;
      return NextNoAdvance ();
    }

    T& Next (K &key)
    {
      key = hash->Elements[bucket][element].key;
      return Next ();
    }

    void Reset () { Zero (); Init (); FindItem (); }
  };
  friend class GlobalIterator;

  class ConstIterator
  {
  private:
    const csHash<T, K>* hash;
    const K key;
    size_t bucket, size, element;

    void Seek ()
    {
      while ((element < size) && 
        (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 
        key) != 0))
          element++;
    }

  protected:
    ConstIterator (const csHash<T, K>* hash0, const K& key0) :
      hash(hash0),
      key(key0), 
      bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo),
      size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].Length () : 0)
      { Reset (); }

    friend class csHash<T, K>;
  public:
    ConstIterator (const ConstIterator &o) :
      hash (o.hash),
      key(o.key),
      bucket(o.bucket),
      size(o.size),
      element(o.element) {}

    ConstIterator& operator=(const ConstIterator& o)
    {
      hash = o.hash;
      key = o.key;
      bucket = o.bucket;
      size = o.size;
      element = o.element;
      return *this;
    }

    bool HasNext () const
    {
      return element < size;
    }

    const T& Next ()
    {
      const T &ret = hash->Elements[bucket][element].value;
      element++;
      Seek ();
      return ret;
    }

    void Reset () { element = 0; Seek (); }
  };
  friend class ConstIterator;

  class ConstGlobalIterator
  {
  private:
    const csHash<T, K> *hash;
    size_t bucket, size, element;

    void Zero () { bucket = element = 0; }
    void Init () 
    { 
      size = 
        (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].Length () : 0;
    }

    void FindItem ()
    {
      if (element >= size)
      {
        while (++bucket < hash->Elements.Length ())
        {
          Init ();
          if (size != 0)
          {
            element = 0;
            break;
          }
        }
      }
    }

  protected:
    ConstGlobalIterator (const csHash<T, K> *hash0) : hash (hash0) 
    { 
      Zero (); 
      Init (); 
      FindItem ();
    }

    friend class csHash<T, K>;
  public:
    ConstGlobalIterator (const ConstGlobalIterator &o) :
      hash (o.hash),
      bucket (o.bucket),
      size (o.size),
      element (o.element) {}

    ConstGlobalIterator& operator=(const ConstGlobalIterator& o)
    {
      hash = o.hash;
      bucket = o.bucket;
      size = o.size;
      element = o.element;
      return *this;
    }

    bool HasNext () const
    {
      if (hash->Elements.Length () == 0) return false;
      return element < size || bucket < hash->Elements.Length ();
    }

    void Advance ()
    {
      element++;
      FindItem ();
    }

    const T& NextNoAdvance ()
    {
      return hash->Elements[bucket][element].value;
    }

    const T& Next ()
    {
      const T &ret = NextNoAdvance ();
      Advance ();
      return ret;
    }

    const T& NextNoAdvance (K &key)
    {
      key = hash->Elements[bucket][element].key;
      return NextNoAdvance ();
    }

    const T& Next (K &key)
    {
      key = hash->Elements[bucket][element].key;
      return Next ();
    }

    void Reset () { Zero (); Init (); FindItem (); }
  };
  friend class ConstGlobalIterator;

  void DeleteElement (GlobalIterator& iterator)
  {
    Elements[iterator.bucket].DeleteIndex(iterator.element);
    Size--;
    iterator.size--;
    iterator.FindItem ();
  }

  void DeleteElement (ConstGlobalIterator& iterator)
  {
    Elements[iterator.bucket].DeleteIndex(iterator.element);
    Size--;
    iterator.size--;
    iterator.FindItem ();
  }

  Iterator GetIterator (const K& key)
  {
    return Iterator (this, key);
  }

  GlobalIterator GetIterator ()
  {
    return GlobalIterator (this);
  }

  ConstIterator GetIterator (const K& key) const
  {
    return ConstIterator (this, key);
  }

  ConstGlobalIterator GetIterator () const
  {
    return ConstGlobalIterator (this);
  }
};

#endif

---