Public API Reference

csutil/hash.h

Go to the documentation of this file.

/*
    Copyright (C) 2003 by Mat Sutcliffe <oktal@gmx.co.uk>

    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 "csgeom/math.h"
#include "csutil/array.h"
#include "csutil/comparator.h"
#include "csutil/util.h"
#include "csutil/tuple.h"
#include "csutil/hashcomputer.h"

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 <typename T>
class csConstPtrKey
{
  const T* ptr;
public:
  csConstPtrKey () : ptr(0) {}
  csConstPtrKey (const T* ptr) : ptr(ptr) {}
  csConstPtrKey (csConstPtrKey const& other) : ptr (other.ptr) {}

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

template <class T, class K, 
  class ArrayMemoryAlloc, class ArrayElementHandler> class csHash;

namespace CS
{
  namespace Container
  {
    template <class T, class K>
    class HashElement
    {
    private:
      template <class _T, class _K, class ArrayMemoryAlloc,
        class ArrayElementHandler> friend class csHash;
      
      K key;
      T value;
    public:
      HashElement (const K& key0, const T &value0) : key (key0), value (value0) {}
      HashElement (const HashElement& other) : key (other.key), value (other.value) {}
      
      const K& GetKey() const { return key; }
      const T& GetValue() const { return value; }
      T& GetValue() { return value; }
    };
  } // namespace Container
} // namespace CS

template <class T, class K = unsigned int, 
  class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc,
  class ArrayElementHandler = csArrayElementHandler<
    CS::Container::HashElement<T, K> > > 
class csHash
{
public:
  typedef csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> ThisType;
  typedef T ValueType;
  typedef K KeyType;
  typedef ArrayMemoryAlloc AllocatorType;

protected:
  typedef CS::Container::HashElement<T, K> Element;
  typedef csArray<Element, ArrayElementHandler,
    ArrayMemoryAlloc, csArrayCapacityDefault> ElementArray;
  csArray<ElementArray, csArrayElementHandler<ElementArray>,
    ArrayMemoryAlloc> Elements;

  size_t Modulo;
  size_t Size;

  size_t InitModulo;
  size_t GrowRate;
  size_t MaxSize;

  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.GetSize ();
    for (p = Primes; *p && *p <= elen; p++) ;
    Modulo = *p;
    CS_ASSERT (Modulo);

    Elements.SetSize (Modulo, ElementArray (size_t (0), csMin (Modulo / GrowRate, size_t (4))));

    for (size_t i = 0; i < elen; i++)
    {
      ElementArray& src = Elements[i];
      size_t slen = src.GetSize ();
      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), Size(0), InitModulo (size),
      GrowRate (csMin (grow_rate, size)), MaxSize (max_size)
  {
  }

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

  T& Put (const K& key, const T &value)
  {
    if (Elements.GetSize() == 0) Elements.SetSize (Modulo);
    ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    size_t idx = values.Push (Element (key, value));
    Size++;
    if (values.GetSize () > Elements.GetSize () / GrowRate
     && Elements.GetSize () < MaxSize)
    {
      Grow ();
      /* can't use 'values[idx]' since that is no longer the place where
         the item is stored. */
      return *(GetElementPointer (key));
    }
    return values[idx].value;
  }

  csArray<T> GetAll () const
  {
    if (Elements.GetSize() == 0) return csArray<T> ();

    ConstGlobalIterator itr = GetIterator();
    csArray<T> ret;
    while(itr.HasNext())
    {
      ret.Push(itr.Next());
    }

    return ret;
  }

  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.GetSize () / 2);
    const size_t len = values.GetSize ();
    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;
  }

  T& PutUnique (const K& key, const T &value)
  {
    if (Elements.GetSize() == 0) Elements.SetSize (Modulo);
    ElementArray& values = 
      Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    const size_t len = values.GetSize ();
    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 v.value;
      }
    }

    size_t idx = values.Push (Element (key, value));
    Size++;
    if (values.GetSize () > Elements.GetSize () / GrowRate
     && Elements.GetSize () < MaxSize)
    {
      Grow ();
      /* can't use 'values[idx]' since that is no longer the place where
         the item is stored. */
      return *(GetElementPointer (key));
    }
    return values[idx].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.GetSize ();
    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.GetSize ();
    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.GetSize ();
    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;
  }

  T* operator[] (const K& key)
  {
    return GetElementPointer (key);
  }

  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.GetSize ();
    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.GetSize ();
    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;
  }

  T& GetOrCreate (const K& key, const T& defaultValue = T())
  {
    if (Elements.GetSize() != 0)
    {
      ElementArray& values = 
        Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
      const size_t len = values.GetSize ();
      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 Put (key, defaultValue);
  }

  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.GetSize (); 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.GetSize (); 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, ArrayMemoryAlloc, ArrayElementHandler>* hash;
    const K key;
    size_t bucket, size, element;

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

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

    friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>;
  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].GetValue();
      element++;
      Seek ();
      return ret;
    }

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

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

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

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

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

    friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>;
  public:
    GlobalIterator () : hash (0), size (0) { Zero (); }

    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.GetSize () == 0) return false;
      return element < size || bucket < hash->Elements.GetSize ();
    }

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

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

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

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

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

    const csTuple2<T, K> NextTuple ()
    {
      csTuple2<T, K> t (NextNoAdvance (),
        hash->Elements[bucket][element].GetKey());
      Advance ();
      return t;
    }

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

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

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

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

    friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>;
  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].GetValue();
      element++;
      Seek ();
      return ret;
    }

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

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

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

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

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

    friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>;
  public:
    ConstGlobalIterator () : hash (0), size (0) { Zero (); }

    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.GetSize () == 0) return false;
      return element < size || bucket < hash->Elements.GetSize ();
    }

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

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

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

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

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

    const csTuple2<T, K> NextTuple ()
    {
      csTuple2<T, K> t (NextNoAdvance (),
        hash->Elements[bucket][element].GetKey());
      Advance ();
      return t;
    }

    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

---