st.h

Go to the documentation of this file.

#ifndef ST_INCLUDED
#define ST_INCLUDED

/** \file st.h

\brief Hash data structures

*/

#ifdef __cplusplus
extern "C" {
#endif


/** \brief Hash table entry
*/

struct Hash_Entry_t
{
  char *key;
  char *record;
  struct Hash_Entry_t *next;
};

typedef struct Hash_Entry_t Hash_Entry_t;

typedef Hash_Entry_t st_table_entry;

// do the typedef here so we can refer to st_table before
// st_table is defined
typedef struct Hash_t Hash_t;

/** \brief Used for traversing entries in a table */

struct Hash_Generator_t
{
  Hash_t *table;
  Hash_Entry_t *entry;
  int index;
};

typedef struct Hash_Generator_t Hash_Generator_t;

typedef Hash_Generator_t st_generator;

typedef int (*Hash_GenericFunctionPointer_t)();

/** \brief Hash table

The hashtable is based on collision chaining.  The user
is to provide the hash and compare functions.  Pre-defined
functions exists for numbers, pointers, and strings.
*/

struct Hash_t
{
  int (*compare) ();
  int (*hash) ();
  int num_bins;
  int num_entries;
  int max_density;
  int reorder_flag;
  double grow_factor;
  Hash_Entry_t **bins;
  // AA : added this to make the code
  // st_foreach_item macro easier to write down
  Hash_Generator_t *gen;
};

typedef Hash_t st_table;

enum st_retval
{ ST_CONTINUE, ST_STOP, ST_DELETE };

typedef enum st_retval (*ST_PFSR) ();
typedef int (*ST_PFI) ();

extern void Hash_Test();

extern Hash_t *Hash_InitTableWithParams (ST_PFI, ST_PFI, int, int, double, int);
// static inline Hash_t *st_init_table_with_params( ST_PFI a, ST_PFI b, int c, int d, double e, int f) { 
//   return Hash_InitTableWithParams (a, b, c, d, e, f ); 
// }

extern Hash_t *Hash_InitTable(ST_PFI a, ST_PFI b);
// static inline Hash_t *st_init_table (ST_PFI a, ST_PFI b) {
//   return Hash_InitTable( a, b );
// }

extern void Hash_FreeTable (Hash_t *);
// static inline void st_free_table (Hash_t * a) {
// return Hash_FreeTable( a );
// }

extern int Hash_Lookup(Hash_t *, char *, char **);
// static inline int st_lookup (Hash_t * a, char * b, char ** c) {
//   return Hash_Lookup( a, b, c );
// }

extern int Hash_LookupInt (Hash_t *, char *, int *);
// static inline int st_lookup_int (Hash_t * a, char * b, int * c) {
//   return Hash_LookupInt( a, b,c );
// }

extern int Hash_Insert (Hash_t *, char *, char *);
// static inline int st_insert (Hash_t * a, char * b, char * c) {
//   return Hash_Insert( a, b, c );
// }

extern int Hash_AddDirect (Hash_t *, char *, char *);
// static inline int st_add_direct (Hash_t * a, char * b, char * c) {
//   return Hash_AddDirect( a, b, c );
// }

extern int Hash_FindOrAdd (Hash_t *, char *, char ***);
// static inline int st_find_or_add (Hash_t * a, char * b, char *** c){
//   return Hash_FindOrAdd( a, b, c );
// }

extern int Hash_Find (Hash_t * a, char *b, char *** c);
// static inline int st_find (Hash_t * a, char * b, char *** c) {
//   return Hash_Find( a, b, c );
// }

extern Hash_t *Hash_Copy (Hash_t *);
// static inline Hash_t *st_copy (Hash_t * a) {
//   return Hash_Copy( a );
// }

extern int Hash_Delete (Hash_t *, char **, char **);
// static inline int st_delete (Hash_t * a, char ** b, char ** c) {
//   return Hash_Delete( a, b, c );
// }

extern int Hash_DeleteInt (Hash_t *, int *, char **);
// static inline int st_delete_int (Hash_t * a, int * b, char ** c) {
//   return Hash_DeleteInt( a, b, c );
// }

extern int Hash_ForEach (Hash_t *, ST_PFSR, char *);
// static inline int st_foreach (Hash_t * a, ST_PFSR b, char * c) {
//   return Hash_ForEach( a, b, c );
// }

extern int Hash_StrHash (char *, int);
extern int st_strhash (char *, int);
// static inline int st_strhash (char * a, int b) {
//   return Hash_StrHash( a, b );
// }

extern int Hash_NumHash (char *, int);
extern int st_numhash (char *, int);
// static inline int st_numhash (char * a, int b) {
//   return Hash_NumHash( a, b );
// }

extern int Hash_PtrHash (char *, int);
extern int st_ptrhash(char *, int);
// static inline int st_ptrhash (char * a, int b) {
//   return Hash_PtrHash( a, b );
// }

extern int Hash_NumCmp (int, int );
extern int st_numcmp (int, int );
// static inline int st_numcmp  (int a, int b) {
//   return Hash_NumCmp( a, b );
// }

extern int Hash_PtrCmp (char *, char *);
extern int st_ptrcmp (char *, char *);
// static inline int st_ptrcmp (char * a, char * b) {
//   return Hash_PtrCmp( a, b );
// }

extern Hash_Generator_t *Hash_InitGen (Hash_t *);
extern Hash_Generator_t *st_init_gen (Hash_t * a);
// static inline Hash_Generator_t *st_init_gen (Hash_t * a) {
//   return Hash_InitGen( a );
// }

extern int Hash_Gen (Hash_Generator_t *, char **, char **);
extern int st_gen (Hash_Generator_t * a, char ** b, char ** c);
// static inline int st_gen (Hash_Generator_t * a, char ** b, char ** c) {
//   return Hash_Gen( a, b, c );
// }

extern int Hash_GenInt (Hash_Generator_t *, char **, int *);
extern int st_gen_int (Hash_Generator_t * a, char ** b, int * c);
// static inline int st_gen_int (Hash_Generator_t * a, char ** b, int * c) {
//   return Hash_GenInt( a, b, c );
// }

extern void Hash_FreeGen (Hash_Generator_t *);
extern void st_free_gen (Hash_Generator_t * a);
// static inline void st_free_gen (Hash_Generator_t * a) {
//   return Hash_FreeGen( a );
// }

#define HASH_DEFAULT_MAX_DENSITY 5
#define HASH_DEFAULT_INIT_TABLE_SIZE 11
#define HASH_DEFAULT_GROW_FACTOR 2.0
#define HASH_DEFAULT_REORDER_FLAG 0

#define ST_DEFAULT_MAX_DENSITY HASH_DEFAULT_MAX_DENSITY
#define ST_DEFAULT_INIT_TABLE_SIZE HASH_DEFAULT_INIT_TABLE_SIZE
#define ST_DEFAULT_GROW_FACTOR HASH_DEFAULT_GROW_FACTOR
#define ST_DEFAULT_REORDER_FLAG HASH_DEFAULT_REORDER_FLAG 


/** \brief  An iteration macro which loops over all the entries in `table'. 

It sets `key_p' to point to the key and `value_p' to the associated value (if it
is not nil). `gen' is a generator variable used internally. 

Sample usage:
<pre>                                                                                                       char *key, *value;
      st_generator *gen;
                                                                                                           
      st_foreach_item(table, gen, &key, &value) {
           process_item(value);
      }
</pre>
*/

#define Hash_ForEachItem(table, gen, key, value) \
     for(gen=st_init_gen(table); st_gen(gen,key,value) || (st_free_gen(gen),0);)

#define st_foreach_item(table, gen, key, value) \
    Hash_ForEachItem(table, gen, key, value)

#define Hash_ForEachItemNew(table, key, value) \
    for(table->gen=st_init_gen(table); st_gen(table->gen,key,value) || (st_free_gen(table->gen),0);)

#define st_foreach_item_new(table, key, value) \
    Hash_ForEachItemNew(table, key, value)

/** \brief An iteration macro which loops over all the entries in `table'. 

It sets `key_p' to point to the key and `value_p' to the associated value (if it
is not nil). 
`value_p' is assumed to be a pointer to an integer.  `gen'
is a generator variable used internally. 

Sample usage:
<pre>                                                                                                           
        char *key;
        int *value;
        st_generator *gen;
                                                                                                           
        st_foreach_item_int(table, gen, &key, &value) {
            process_item(value);
        }
</pre>

*/

#define st_foreach_item_int(table, gen, key, value) \
    for(gen=st_init_gen(table); st_gen_int(gen,key,value) || (st_free_gen(gen),0);)

#define HASH_OUT_OF_MEM -10000
#define ST_OUT_OF_MEM -10000

/** \brief Returns 1 if there is an entry under `key' in `table', 0 otherwise.  */

static inline int
Hash_IsMember (Hash_t * table, char *key)
{
  return Hash_Lookup( table, key, (char **) 0);
}

static inline int st_is_member( Hash_t *a, char *b ) {
  return Hash_IsMember( a, b );
}


/** \brief Return the number of entries in the table `table'.  */

static inline int
Hash_Count (Hash_t * table)
{
  return ((table)->num_entries);
}

static inline int
st_count( Hash_t *a ) {
  return Hash_Count( a );
}

#ifdef __cplusplus
}
#endif

#endif /* ST_INCLUDED */