/*----------------------------------------------------------------------------
 * (C) 1997-1998 Armin Biere 
 *
 *     $Id: hash.h,v 1.2 2001/12/04 09:46:41 biere Exp $
 *----------------------------------------------------------------------------
 */
#ifndef _hash_h_INCLUDED
#define _hash_h_INCLUDED

/*---------------------------------------------------------------------------.
 | This is an implementation of a general hash table module.                 |
 | It assumes that keys for data stored in the hash table can                |
 | be extracted from the data.                                               |
 |                                                                           |
 | One very important feature of this implementation is that                 |
 | the data stored in the hashtable is `owned' by the hash                   |
 | table. The user should not delete it! It will be deleted                  |
 | by the destructor of the hash table or by an `overwrite'                  |
 | method. To ease the use of different allocators and to                    |
 | be able to store statically allocated data in a hash table                |
 | the user can provide his own `free' function.                             |
 |                                                                           |
 | TOF                                                                       |
 |                                                                           |
 | HashTable:                                                                |
 |                                                                           |
 |   new_HashTable                         constructor                       |
 |   free_HashTable                        destructor                        |
 |                                                                           |
 |   insert_into_HashTable                 maninpulator                      |
 |   insert_at_position_into_HashTable     maninpulator                      |
 |   overwrite_in_HashTable                maninpulator                      |
 |   overwrite_at_position_in_HashTable    maninpulator                      |
 |   remove_from_HashTable                 maninpulator                      |
 |                                                                           |
 |   get_data_from_HashTable               inspector                         |
 |   get_data_from_position_in_HashTable   inspector                         |
 |   get_position_of_key_in_HashTable      inspector                         |
 |                                                                           |
 |   get_size_of_HashTable                 inspector                         |
 |   get_statistics_of_HashTable           inspector                         |
 |                                                                           |
 | HashTableIterator:                                                        |
 |                                                                           |
 |                                         no constructors or                |
 |                                         destructors                       |
 |                                                                           |
 |   setup_HashTableIterator               maninpulator                      |
 |   increment_HashTableIterator           maninpulator                      |
 |                                                                           |
 |   is_done_HashTableIterator             inspector                         |
 |   get_data_from_HashTableIterator       inspector                         |
 |                                                                           |
 | general:                                                                  |
 |                                                                           |
 |   hashpjw_HashTable                                                       |
 `---------------------------------------------------------------------------*/

typedef struct HashTable_ *HashTable;

/* Construct a new HashTable. The first parameter gives the initial
 * minimal size of the hashtable. The hashtable resizes itself if
 * necessary and grows exponentially with each resize step.
 * This means that using 0 as minimal_size does not really hurt too much.
 *
 * The next five function parameters are used to control the
 * data and the keys stored in the hash table.
 *
 *   cmp_keys  -- is the comparison function for keys. It should
 *                return the same results as the `strcmp'function.
 *                (actually: 0 iff the two args are the same)
 *                If cmp_keys is 0 then pointer comparison is used.
 *
 *   hash_key  -- hash function (see also hashpjw_HashTable). If it
 *                is zero than a cast from `void *' to `int' is used.
 * 
 *   get_key_from_data --
 *                this function is used to get the key from
 *                the data stored in the hash table. If this parameter
 *                is zero than it is assumed that the data is the
 *                also its key.
 *
 *   free_data -- user provided deallocator of data stored in the
 *                hashtable. If zero do not deallocate data.
 * 
 *   error     -- this function is called if an internal error
 *                ocurred (f.e. interface violation). As default
 *                (set to zero) print an descriptive error message
 *                and produce a segmentation fault.
 */

extern HashTable
new_HashTable (int minimal_size,
	       int (*cmp_keys) (void *key1, void *key2),
	       int (*hash_key) (void *key),
	       void *(*get_key_from_data) (void *data),
	       void (*free_data) (void *data), void (*error) (char *errmsg));

/* Destructor of HashTables. Free all stored data with the user provided
 * deallocation function.
 */

extern void free_HashTable (HashTable);

/* insert a data into the HashTable but do not overwrite existing
 * data with the same key. The return value is true iff
 * some data with the same key is already stored in the hash table.
 * In this case the user generally has to deallocate `data_with_key'
 * on his own.
 */

extern int insert_into_HashTable (HashTable ht, void *data_with_key);

/* remove correponding data from the hash table and deallocate
 * it using the user provided deallocator.
 */

extern void remove_from_HashTable (HashTable ht, void *key);

/* overwrite an existing entry in the hash table with the same
 * key as the key of `data_with_key' or insert a new entry.
 * In the first case also deallocate the overwritten data.
 */

extern void overwrite_in_HashTable (HashTable ht, void *data_with_key);

/* search for data with this key. Return zero if not found.
 * (see also `get_data_from_position_in_HashTable')
 */

extern void *get_data_from_HashTable (HashTable ht, void *key);

/* return the number of stored key/data pairs
 */

extern int get_size_of_HashTable (HashTable ht);

/* Returns an statically allocated string with useful ;-)
 * statistical information. This string is overwritten by
 * subsequent calls to this function.
 */

extern const char *get_statistics_for_HashTable (HashTable ht);

/* For many applications of hash tables (f.e. a symbol table
 * of a compiler) the user must check if some data with a
 * given key already exists in the hash table before he
 * actually constructs the data (f.e. a new entry into the
 * symbol table). If no data with this key is found then
 * the new allocated data is inserted into the hash table.
 * This means that the same search must be done again.
 *
 * This can be avoided if we know from the first search
 * where the new allocated data will be inserted. For
 * this purpose `get_position_of_key_in_HashTable' can be used.
 * The *dereferenced* return value is exactly 0 iff the search
 * was succesfull. In this case
 * `get_data_from_position_in_HashTable' can be used to get the
 * actual data for the key. If the search is not succesfull
 * the user can now allocated the new data and insert it
 * at the returned position with 
 * `insert_at_position_into_HashTable' or
 * `overwrite_at_position_in_HashTable'.
 */

extern void **get_position_of_key_in_HashTable (HashTable ht, void *key);

extern void *get_data_from_position_in_HashTable (HashTable, void **position);

extern void
insert_at_position_into_HashTable (HashTable ht, void **position, void *data);

extern void
overwrite_at_position_in_HashTable (HashTable ht, void *position, void *data);

/* The definition of this structure is placed here
 * because it should be possible to allocate an iterator as
 * an automatic variable. This is also more convenient for
 * the user.
 */

typedef struct HashTableIterator
{
  HashTable ht;
  int pos;
  void *cursor;
}
HashTableIterator;

/* Setup an iterator. It is possible to have multiple
 * iterators for the same hash table and to traverse
 * the hash table in parallel.
 * ATTENTION: These iterators are not save with
 * respect to `remove' operations on the traversed
 * hash table.
 */

extern void setup_HashTableIterator (HashTable, HashTableIterator *);

extern void increment_HashTableIterator (HashTableIterator *);

extern void *get_data_from_HashTableIterator (HashTableIterator *);

extern int is_done_HashTableIterator (HashTableIterator *);

/* Hash function for zero terminated data (f.e. strings).
 * It is from the `dragon book' and should work very
 * well especially for strings as keys.
 */

extern int hashpjw_HashTable (void *);

#endif
