Public API Reference

                 

---

csutil/hash.h

/*
    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 "array.h"

CS_CSUTIL_EXPORT unsigned int csHashCompute (char const*);

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

template <class T>
class csIntegralHashKeyHandler
{
public:
  static unsigned int ComputeHash (const T& key)
  {
#if (_MSC_VER >= 1300)
    /*
      VC7 with 64bit warnings complains about a pointer truncation when T is
      a pointer. This isn't serious (as csHash<> does not rely on the hash of
      a key alone to retrieve a value). The __w64 causes VC7 to not emit that
      warning (on 32bit compilers at least).
     */
    return (unsigned int __w64)key;  
#else
    return (unsigned int)key;  
#endif
  }

  static bool CompareKeys (const T& key1, const T& key2)
  {
    return (key1 == key2);
  }
};

template <class T, class K = unsigned int, 
  class KeyHandler = csIntegralHashKeyHandler<K> > 
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) {}
  };
  csArray< csArray<Element> > Elements;

  int Modulo;

private:
  int InitModulo;
  int GrowRate;
  int MaxSize;
  int Size;

  void Grow ()
  {
    static const int 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 int *p;
    int elen = Elements.Length ();
    for (p = Primes; *p && *p <= elen; p++) ;
    Modulo = *p;
    CS_ASSERT (Modulo);

    Elements.SetLength (Modulo);

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

public:
  csHash (int size = 257, int grow_rate = 64, int max_size = 20000)
    : Elements (size), Modulo (size), InitModulo (size),
      GrowRate (grow_rate), MaxSize (max_size), Size (0)
  {
    Elements.SetLength (size, csArray<Element> (0, 8));
  }

  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)
  {
    csArray<Element> &values = 
      Elements[KeyHandler::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
  {
    const csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    csArray<T> ret (values.Length () / 2);
    const int len = values.Length ();
    for (int i = 0; i < len; ++i)
    {
      const Element& v = values[i];
      if (KeyHandler::CompareKeys (v.key, key)) 
        ret.Push (v.value);
    }
    return ret;
  }

  void PutFirst (const K& key, const T &value)
  {
    csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    const int len = values.Length ();
    for (int i = 0; i < len; ++i)
    {
      Element& v = values[i];
      if (KeyHandler::CompareKeys (v.key, key))
      {
        v.value = value;
        return;
      }
    }

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

  bool In (const K& key) const
  {
    const csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    const int len = values.Length ();
    for (int i = 0; i < len; ++i)
      if (KeyHandler::CompareKeys (values[i].key, key)) 
        return true;

    return false;
  }

  const T* GetElementPointer (const K& key) const
  {
    const csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    const int len = values.Length ();
    for (int i = 0; i < len; ++i)
    {
      const Element& v = values[i];
      if (KeyHandler::CompareKeys (v.key, key))
        return &v.value;
    }

    return 0;
  }

  T* GetElementPointer (const K& key)
  {
    csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    const int len = values.Length ();
    for (int i = 0; i < len; ++i)
    {
      Element& v = values[i];
      if (KeyHandler::CompareKeys (v.key, key))
        return &v.value;
    }

    return 0;
  }

  const T& Get (const K& key, const T& fallback) const
  {
    const csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    const int len = values.Length ();
    for (int i = 0; i < len; ++i)
    {
      const Element& v = values[i];
      if (KeyHandler::CompareKeys (v.key, key))
        return v.value;
    }

    return fallback;
  }

  T& Get (const K& key, T& fallback)
  {
    csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    const int len = values.Length ();
    for (int i = 0; i < len; ++i)
    {
      Element& v = values[i];
      if (KeyHandler::CompareKeys (v.key, key))
        return v.value;
    }

    return fallback;
  }

  void DeleteAll ()
  {
    Elements.SetLength (Modulo = InitModulo);
    int elen = Elements.Length ();
    for (int i = 0; i < elen; i++)
      Elements[i].Empty ();
    Size = 0;
  }

  bool DeleteAll (const K& key)
  {
    bool ret = false;
    csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    for (int i = values.Length () - 1; i >= 0; i--)
      if (KeyHandler::CompareKeys (values[i].key, key))
      {
        values.DeleteIndex (i);
        ret = true;
        Size--;
      }
    return ret;
  }
  
  bool Delete (const K& key, const T &value)
  {
    bool ret = false;
    csArray<Element> &values = 
      Elements[KeyHandler::ComputeHash (key) % Modulo];
    for (int i = values.Length () - 1; i >= 0; i--)
      if (KeyHandler::CompareKeys (values[i].key, key) && 
        (values[i].value == value))
      {
        values.DeleteIndex (i);
        ret = true;
        Size--;
      }
    return ret;
  }

  int GetSize () const
  {
    return Size;
  }

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

    void Seek ()
    {
      while ((element < size) && 
        ! KeyHandler::CompareKeys (hash->Elements[bucket][element].key, key))
          element++;
    }

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

    friend class csHash;
  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;
    }

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

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

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

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

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

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

    friend class csHash;
  public:
    GlobalIterator (const Iterator &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 ();
    }

    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 GlobalIterator;

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

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

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

template <class T, class KeyHandler = csIntegralHashKeyHandler<T> > 
class csSet
{
private:
  csHash<T, T, KeyHandler> map;

public:
  class Iterator : public csHash<T, T, KeyHandler>::Iterator
  {
  protected:
    Iterator () {}
  public:
  };
  class GlobalIterator : public csHash<T, T, KeyHandler>::GlobalIterator
  {
  protected:
    GlobalIterator () {}
    GlobalIterator (const csSet<T, KeyHandler> *set0) : 
      csHash<T, T, KeyHandler>::GlobalIterator(&set0->map)
    { }

  public:
    friend class csSet;
  };
  friend class GlobalIterator;

  csSet (int size = 257, int grow_rate = 64, int max_size = 20000)
        : map (size, grow_rate, max_size)
  {
  }

  void Add (const T& object)
  {
    if (In (object)) return;
    AddNoTest (object);
  }

  void AddNoTest (const T& object)
  {
    map.Put (object, object);
  }

  bool In (const T& object) const
  {
    return map.In (object);
  }

  void DeleteAll ()
  {
    map.DeleteAll ();
  }

  bool Delete (const T& object)
  {
    return map.Delete (object, object);
  }

  int GetSize () const
  {
    return map.GetSize ();
  }

  csHash<T, T, KeyHandler>* GetHash () { return &map; }

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


#endif

---