/*---------------------------------------------------------------------------- * (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