EST_THash.h

Go to the documentation of this file.

 /************************************************************************/
 /*                                                                      */
 /*                Centre for Speech Technology Research                 */
 /*                     University of Edinburgh, UK                      */
 /*                       Copyright (c) 1996,1997                        */
 /*                        All Rights Reserved.                          */
 /*                                                                      */
 /*  Permission is hereby granted, free of charge, to use and distribute */
 /*  this software and its documentation without restriction, including  */
 /*  without limitation the rights to use, copy, modify, merge, publish, */
 /*  distribute, sublicense, and/or sell copies of this work, and to     */
 /*  permit persons to whom this work is furnished to do so, subject to  */
 /*  the following conditions:                                           */
 /*   1. The code must retain the above copyright notice, this list of   */
 /*      conditions and the following disclaimer.                        */
 /*   2. Any modifications must be clearly marked as such.               */
 /*   3. Original authors' names are not deleted.                        */
 /*   4. The authors' names are not used to endorse or promote products  */
 /*      derived from this software without specific prior written       */
 /*      permission.                                                     */
 /*                                                                      */
 /*  THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK       */
 /*  DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING     */
 /*  ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT  */
 /*  SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE    */
 /*  FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   */
 /*  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN  */
 /*  AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,         */
 /*  ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF      */
 /*  THIS SOFTWARE.                                                      */
 /*                                                                      */
 /************************************************************************/
 /*                 Author: Richard Caley (rjc@cstr.ed.ac.uk)            */
 /************************************************************************/

#ifndef __EST_THASH_H__
#define __EST_THASH_H__

#include <iostream>

#include "EST_String.h"
#include "EST_system.h"
#include "EST_bool.h"
#include "EST_TIterator.h"

#include "instantiate/EST_THashI.h"
#include "instantiate/EST_TStringHashI.h"

/**@defgroup HashTables Hash Tables
 * @ingroup containerclasses
  *
  * @author Richard Caley <rjc@cstr.ed.ac.uk>
  * @version $Id: EST_THash.h,v 1.6 2004/09/29 08:24:17 robert Exp $
  */
///@{

/** \class EST_HashFunctions
 *  \brief This is just a convenient place to put some useful hash functions.
  */
class EST_HashFunctions {
public:
  /// A generally useful hash function.
  static unsigned int DefaultHash(const void *data, ssize_t size, unsigned int n);

  /// A hash function for strings.
  static  unsigned int StringHash(const EST_String &key, unsigned int size);
};

template<class K, class V>  class EST_THash;

/** \class EST_Hash_Pair
 *  \brief This class is used in hash tables to hold a key value pair.
  * Not much to say beyond that.
  */
template<class K, class V>
class EST_Hash_Pair {
public:
  /// The key
  K k;
  /// The value
  V v;

  /// A constructor:
  EST_Hash_Pair() {
      k=K();
      v=V();
      next=0;
  }
private:
  /// Pointer used to chain entries into buckets.
  EST_Hash_Pair<K,V> *next;

  /// The hash table must be a friend so it can see the pointer.
  friend class EST_THash<K, V>;
};

/** \class EST_THash
 *  \brief An open hash table. The number of buckets should be set to allow
  * enough space that there are relatively few entries per bucket on
  * average.
  */
template<class K, class V>
class EST_THash : protected EST_HashFunctions {

private:
  /// Something to return when there is no entry in the table.
  static V Dummy_Value;
  static K Dummy_Key;

  /// Total number of entries.
  unsigned int p_num_entries;

  /// Number of buckets.
  unsigned int p_num_buckets;

  /// Pointer to an array of <variable>p_num_buckets</variable>buckets.
  EST_Hash_Pair<K,V> **p_buckets;

  /// The hash function to use on this table.
  unsigned int (*p_hash_function)(const K &key, unsigned int size);

public:
  /** Create a table with the given number of buckets. Optionally setting
    * a custom hash function.
    */
  EST_THash(int size,  
        unsigned int (*hash_function)(const K &key, unsigned int size)= NULL);

  /// Create a copy
  EST_THash(const EST_THash<K,V> &from);

  /// Destroy the table.
  ~EST_THash(void);

  /// Empty the table.
  void clear(void);

  /// Return the total number of entries in the table.
  unsigned int num_entries(void) const 
    { return p_num_entries; };

  /// Does the key have an entry?
  int present(const K &key) const;

  /** Return the value associated with the key.
    * `found` is set to whether such an entry was found.
    */
  V &val(const K &key, int &found) const;

  /// Return the value associated with the key.
  V &val(const K &key) const {int x; return val(key, x); }

  const K &key(const V &val, int &found) const;
  const K &key(const V &val) const {int x; return key(val, x); }

  /// Copy all entries
  void copy(const EST_THash<K,V> &from);

  /// Apply `func` to each entry in the table.
  void map(void (*func)(K&, V&));
    
  /// Add an entry to the table.
  int add_item(const K &key, const V &value, int no_search = 0);

  /// Remove an entry from the table.
  int remove_item(const K &rkey, int quiet = 0);

  /// Assignment is a copy operation
  EST_THash<K,V> &operator = (const EST_THash<K,V> &from);

  /// Print the table to `stream` in a human readable format.
  void dump(ostream &stream, int all=0);

  /**@name Pair Iteration
    *
    * This iterator steps through the table returning key-value pairs. 
    */
  ///@{
protected:
  /** A position in the table is given by a bucket number and a
    * pointer into the bucket.
    */
    // struct IPointer{  unsigned int b; EST_Hash_Pair<K, V> *p; };
    class IPointer{
      public:
      unsigned int b;
      EST_Hash_Pair<K, V> *p;
      IPointer() {
        b = 0;
        p = 0;
      };
    };

    //typedef class IPointer_s IPointer;

  /// Shift to point at something.
  void skip_blank(IPointer &ip) const 
    {
      while (ip.p==NULL && ip.b<p_num_buckets)
    {ip.b++; ip.p = ip.b<p_num_buckets?p_buckets[ip.b]:0; } 
    }
  
  /// Go to start of the table.
  void point_to_first(IPointer &ip) const 
    { ip.b=0; ip.p = ip.b<p_num_buckets?p_buckets[ip.b]:0; 
    skip_blank(ip);}

  /// Move pointer forwards, at the end of the bucket, move down.
  void move_pointer_forwards(IPointer &ip) const 
    { 
      ip.p = ip.p->next; 
      skip_blank(ip);
    }

  /// We are at the end if the pointer ever becomes NULL
  bool points_to_something(const IPointer &ip) const { return ip.b<p_num_buckets; }

  /// Return the contents of this entry.
  EST_Hash_Pair<K, V> &points_at(const IPointer &ip) { return *(ip.p); }

  /// The iterator must be a friend to access this private interface.
  friend class EST_TStructIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> >;
  friend class EST_TRwStructIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> >;
  friend class EST_TIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> >;
  friend class EST_TRwIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> >;

public:
  /// An entry returned by the iterator is a key value pair.
  typedef EST_Hash_Pair<K, V> Entry;

  /// Give the iterator a sensible name.
  typedef EST_TStructIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> > Entries;
  typedef EST_TRwStructIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> > RwEntries;
  ///@}

  /**@name Key Iteration
    *
    * This iterator steps through the table returning just keys.
    */
  ///@{
protected:
  /** A position in the table is given by a bucket number and a
    * pointer into the bucket.
    */
  class IPointer_k {
    public:
    unsigned int b;
    EST_Hash_Pair<K, V> *p;
    IPointer_k() {
      b=0;
      p=0;
    };
  };

  //typedef struct IPointer_k_s IPointer_k;

  /// Shift to point at something.
  void skip_blank(IPointer_k &ip) const 
    {
      while (ip.p==NULL && ip.b<p_num_buckets)
    {ip.b++; ip.p = ip.b<p_num_buckets?p_buckets[ip.b]:0; } 
    }
  
  /// Go to start of the table.
  void point_to_first(IPointer_k &ip) const 
    { ip.b=0; ip.p = ip.b<p_num_buckets?p_buckets[ip.b]:0; 
    skip_blank(ip);}

  /// Move pointer forwards, at the end of the bucket, move down.
  void move_pointer_forwards(IPointer_k &ip) const 
    { 
      ip.p = ip.p->next; 
      skip_blank(ip);
    }

   /// We are at the end if the pointer ever becomes NULL
  bool points_to_something(const IPointer_k &ip) const { return ip.b<p_num_buckets; }

  /// Return the key of this entry.
  K &points_at(const IPointer_k &ip) { return (ip.p)->k; }

  /// The iterator must be a friend to access this private interface.
  friend class EST_TIterator< EST_THash<K, V>, IPointer_k, K >;
  friend class EST_TRwIterator< EST_THash<K, V>, IPointer_k, K >;

public:
  /// An entry returned by this iterator is just a key.
  typedef K KeyEntry;

  /// Give the iterator a sensible name.
  typedef EST_TIterator< EST_THash<K, V>, IPointer_k, K > KeyEntries;
  typedef EST_TRwIterator< EST_THash<K, V>, IPointer_k, K > KeyRwEntries;
  ///@}

};

/** \class EST_TStringHash
  * \brief A specialised hash table for when the key is an EST_String.
  *
  * This is just a version of EST_THash which
  * has a different default hash function.
  */
template<class V>
class EST_TStringHash : public EST_THash<EST_String, V> {
public:

  /// Create a string hash table of `size` buckets.
  EST_TStringHash(int size) : EST_THash<EST_String, V>(size, EST_HashFunctions::StringHash) {};

  /// An entry returned by the iterator is a key value pair.
  typedef EST_Hash_Pair<EST_String, V> Entry;

/*    struct IPointer_s{  unsigned int b; Entry *p; };
      typedef struct IPointer_s IPointer; */

  // Convince GCC that the IPointer we're going to use is a typename
  typedef typename EST_THash<EST_String, V>::IPointer TN_IPointer;

  /// Give the iterator a sensible name.
   typedef EST_TStructIterator< EST_THash<EST_String, V>, typename EST_THash<EST_String, V>::IPointer,
                    EST_Hash_Pair<EST_String, V> > Entries;
  
   typedef EST_TRwStructIterator< EST_THash<EST_String, V>, typename EST_THash<EST_String, V>::IPointer,
                    EST_Hash_Pair<EST_String, V> > RwEntries;

  typedef EST_String KeyEntry;

/*  struct IPointer_k_s {  unsigned int b; EST_Hash_Pair<EST_String, V> *p; };
    typedef struct IPointer_k_s IPointer_k; */

  /// Give the iterator a sensible name.

  // Convince GCC that the IPointer_k we're going to use is a typename 
  typedef typename EST_THash<EST_String, V>::IPointer_k TN_IPointer_k;

  typedef EST_TIterator< EST_THash<EST_String, V>, typename EST_THash<EST_String, V>::IPointer_k,
                EST_String > KeyEntries;
  typedef EST_TRwIterator< EST_THash<EST_String, V>, typename EST_THash<EST_String, V>::IPointer_k,
                EST_String > KeyRwEntries;
};

  ///@}
  
/** \brief The default hash function used by EST_THash
  */
inline static unsigned int DefaultHashFunction(const void *data, ssize_t size, unsigned int n)
{
  unsigned int x=0;
  const char *p = (const char *)data;
  for(; size>0 ; p++, size--)
      x = ((x+*p)*33) % n;
  return x;
}

#endif