Azinix

st.h

Go to the documentation of this file.
00001 #ifndef ST_INCLUDED
00002 #define ST_INCLUDED
00003 
00004 /** \file st.h
00005 
00006 \brief Hash data structures
00007 
00008 */
00009 
00010 #ifdef __cplusplus
00011 extern "C" {
00012 #endif
00013 
00014 
00015 /** \brief Hash table entry
00016 */
00017 
00018 struct Hash_Entry_t
00019 {
00020   char *key;
00021   char *record;
00022   struct Hash_Entry_t *next;
00023 };
00024 
00025 typedef struct Hash_Entry_t Hash_Entry_t;
00026 
00027 typedef Hash_Entry_t st_table_entry;
00028 
00029 // do the typedef here so we can refer to st_table before
00030 // st_table is defined
00031 typedef struct Hash_t Hash_t;
00032 
00033 /** \brief Used for traversing entries in a table */
00034 
00035 struct Hash_Generator_t
00036 {
00037   Hash_t *table;
00038   Hash_Entry_t *entry;
00039   int index;
00040 };
00041 
00042 typedef struct Hash_Generator_t Hash_Generator_t;
00043 
00044 typedef Hash_Generator_t st_generator;
00045 
00046 typedef int (*Hash_GenericFunctionPointer_t)();
00047 
00048 /** \brief Hash table
00049 
00050 The hashtable is based on collision chaining.  The user
00051 is to provide the hash and compare functions.  Pre-defined
00052 functions exists for numbers, pointers, and strings.
00053 */
00054 
00055 struct Hash_t
00056 {
00057   int (*compare) ();
00058   int (*hash) ();
00059   int num_bins;
00060   int num_entries;
00061   int max_density;
00062   int reorder_flag;
00063   double grow_factor;
00064   Hash_Entry_t **bins;
00065   // AA : added this to make the code
00066   // st_foreach_item macro easier to write down
00067   Hash_Generator_t *gen;
00068 };
00069 
00070 typedef Hash_t st_table;
00071 
00072 enum st_retval
00073 { ST_CONTINUE, ST_STOP, ST_DELETE };
00074 
00075 typedef enum st_retval (*ST_PFSR) ();
00076 typedef int (*ST_PFI) ();
00077 
00078 extern void Hash_Test();
00079 
00080 extern Hash_t *Hash_InitTableWithParams (ST_PFI, ST_PFI, int, int, double, int);
00081 // static inline Hash_t *st_init_table_with_params( ST_PFI a, ST_PFI b, int c, int d, double e, int f) { 
00082 //   return Hash_InitTableWithParams (a, b, c, d, e, f ); 
00083 // }
00084 
00085 extern Hash_t *Hash_InitTable(ST_PFI a, ST_PFI b);
00086 // static inline Hash_t *st_init_table (ST_PFI a, ST_PFI b) {
00087 //   return Hash_InitTable( a, b );
00088 // }
00089 
00090 extern void Hash_FreeTable (Hash_t *);
00091 // static inline void st_free_table (Hash_t * a) {
00092 // return Hash_FreeTable( a );
00093 // }
00094 
00095 extern int Hash_Lookup(Hash_t *, char *, char **);
00096 // static inline int st_lookup (Hash_t * a, char * b, char ** c) {
00097 //   return Hash_Lookup( a, b, c );
00098 // }
00099 
00100 extern int Hash_LookupInt (Hash_t *, char *, int *);
00101 // static inline int st_lookup_int (Hash_t * a, char * b, int * c) {
00102 //   return Hash_LookupInt( a, b,c );
00103 // }
00104 
00105 extern int Hash_Insert (Hash_t *, char *, char *);
00106 // static inline int st_insert (Hash_t * a, char * b, char * c) {
00107 //   return Hash_Insert( a, b, c );
00108 // }
00109 
00110 extern int Hash_AddDirect (Hash_t *, char *, char *);
00111 // static inline int st_add_direct (Hash_t * a, char * b, char * c) {
00112 //   return Hash_AddDirect( a, b, c );
00113 // }
00114 
00115 extern int Hash_FindOrAdd (Hash_t *, char *, char ***);
00116 // static inline int st_find_or_add (Hash_t * a, char * b, char *** c){
00117 //   return Hash_FindOrAdd( a, b, c );
00118 // }
00119 
00120 extern int Hash_Find (Hash_t * a, char *b, char *** c);
00121 // static inline int st_find (Hash_t * a, char * b, char *** c) {
00122 //   return Hash_Find( a, b, c );
00123 // }
00124 
00125 extern Hash_t *Hash_Copy (Hash_t *);
00126 // static inline Hash_t *st_copy (Hash_t * a) {
00127 //   return Hash_Copy( a );
00128 // }
00129 
00130 extern int Hash_Delete (Hash_t *, char **, char **);
00131 // static inline int st_delete (Hash_t * a, char ** b, char ** c) {
00132 //   return Hash_Delete( a, b, c );
00133 // }
00134 
00135 extern int Hash_DeleteInt (Hash_t *, int *, char **);
00136 // static inline int st_delete_int (Hash_t * a, int * b, char ** c) {
00137 //   return Hash_DeleteInt( a, b, c );
00138 // }
00139 
00140 extern int Hash_ForEach (Hash_t *, ST_PFSR, char *);
00141 // static inline int st_foreach (Hash_t * a, ST_PFSR b, char * c) {
00142 //   return Hash_ForEach( a, b, c );
00143 // }
00144 
00145 extern int Hash_StrHash (char *, int);
00146 extern int st_strhash (char *, int);
00147 // static inline int st_strhash (char * a, int b) {
00148 //   return Hash_StrHash( a, b );
00149 // }
00150 
00151 extern int Hash_NumHash (char *, int);
00152 extern int st_numhash (char *, int);
00153 // static inline int st_numhash (char * a, int b) {
00154 //   return Hash_NumHash( a, b );
00155 // }
00156 
00157 extern int Hash_PtrHash (char *, int);
00158 extern int st_ptrhash(char *, int);
00159 // static inline int st_ptrhash (char * a, int b) {
00160 //   return Hash_PtrHash( a, b );
00161 // }
00162 
00163 extern int Hash_NumCmp (int, int );
00164 extern int st_numcmp (int, int );
00165 // static inline int st_numcmp  (int a, int b) {
00166 //   return Hash_NumCmp( a, b );
00167 // }
00168 
00169 extern int Hash_PtrCmp (char *, char *);
00170 extern int st_ptrcmp (char *, char *);
00171 // static inline int st_ptrcmp (char * a, char * b) {
00172 //   return Hash_PtrCmp( a, b );
00173 // }
00174 
00175 extern Hash_Generator_t *Hash_InitGen (Hash_t *);
00176 extern Hash_Generator_t *st_init_gen (Hash_t * a);
00177 // static inline Hash_Generator_t *st_init_gen (Hash_t * a) {
00178 //   return Hash_InitGen( a );
00179 // }
00180 
00181 extern int Hash_Gen (Hash_Generator_t *, char **, char **);
00182 extern int st_gen (Hash_Generator_t * a, char ** b, char ** c);
00183 // static inline int st_gen (Hash_Generator_t * a, char ** b, char ** c) {
00184 //   return Hash_Gen( a, b, c );
00185 // }
00186 
00187 extern int Hash_GenInt (Hash_Generator_t *, char **, int *);
00188 extern int st_gen_int (Hash_Generator_t * a, char ** b, int * c);
00189 // static inline int st_gen_int (Hash_Generator_t * a, char ** b, int * c) {
00190 //   return Hash_GenInt( a, b, c );
00191 // }
00192 
00193 extern void Hash_FreeGen (Hash_Generator_t *);
00194 extern void st_free_gen (Hash_Generator_t * a);
00195 // static inline void st_free_gen (Hash_Generator_t * a) {
00196 //   return Hash_FreeGen( a );
00197 // }
00198 
00199 #define HASH_DEFAULT_MAX_DENSITY 5
00200 #define HASH_DEFAULT_INIT_TABLE_SIZE 11
00201 #define HASH_DEFAULT_GROW_FACTOR 2.0
00202 #define HASH_DEFAULT_REORDER_FLAG 0
00203 
00204 #define ST_DEFAULT_MAX_DENSITY HASH_DEFAULT_MAX_DENSITY
00205 #define ST_DEFAULT_INIT_TABLE_SIZE HASH_DEFAULT_INIT_TABLE_SIZE
00206 #define ST_DEFAULT_GROW_FACTOR HASH_DEFAULT_GROW_FACTOR
00207 #define ST_DEFAULT_REORDER_FLAG HASH_DEFAULT_REORDER_FLAG 
00208 
00209 
00210 /** \brief  An iteration macro which loops over all the entries in `table'. 
00211 
00212 It sets `key_p' to point to the key and `value_p' to the associated value (if it
00213 is not nil). `gen' is a generator variable used internally. 
00214 
00215 Sample usage:
00216 <pre>                                                                                                       char *key, *value;
00217       st_generator *gen;
00218                                                                                                            
00219       st_foreach_item(table, gen, &key, &value) {
00220            process_item(value);
00221       }
00222 </pre>
00223 */
00224 
00225 #define Hash_ForEachItem(table, gen, key, value) \
00226      for(gen=st_init_gen(table); st_gen(gen,key,value) || (st_free_gen(gen),0);)
00227 
00228 #define st_foreach_item(table, gen, key, value) \
00229     Hash_ForEachItem(table, gen, key, value)
00230 
00231 #define Hash_ForEachItemNew(table, key, value) \
00232     for(table->gen=st_init_gen(table); st_gen(table->gen,key,value) || (st_free_gen(table->gen),0);)
00233 
00234 #define st_foreach_item_new(table, key, value) \
00235     Hash_ForEachItemNew(table, key, value)
00236 
00237 /** \brief An iteration macro which loops over all the entries in `table'. 
00238 
00239 It sets `key_p' to point to the key and `value_p' to the associated value (if it
00240 is not nil). 
00241 `value_p' is assumed to be a pointer to an integer.  `gen'
00242 is a generator variable used internally. 
00243 
00244 Sample usage:
00245 <pre>                                                                                                           
00246         char *key;
00247         int *value;
00248         st_generator *gen;
00249                                                                                                            
00250         st_foreach_item_int(table, gen, &key, &value) {
00251             process_item(value);
00252         }
00253 </pre>
00254 
00255 */
00256 
00257 #define st_foreach_item_int(table, gen, key, value) \
00258     for(gen=st_init_gen(table); st_gen_int(gen,key,value) || (st_free_gen(gen),0);)
00259 
00260 #define HASH_OUT_OF_MEM -10000
00261 #define ST_OUT_OF_MEM -10000
00262 
00263 /** \brief Returns 1 if there is an entry under `key' in `table', 0 otherwise.  */
00264 
00265 static inline int
00266 Hash_IsMember (Hash_t * table, char *key)
00267 {
00268   return Hash_Lookup( table, key, (char **) 0);
00269 }
00270 
00271 static inline int st_is_member( Hash_t *a, char *b ) {
00272   return Hash_IsMember( a, b );
00273 }
00274 
00275 
00276 /** \brief Return the number of entries in the table `table'.  */
00277 
00278 static inline int
00279 Hash_Count (Hash_t * table)
00280 {
00281   return ((table)->num_entries);
00282 }
00283 
00284 static inline int
00285 st_count( Hash_t *a ) {
00286   return Hash_Count( a );
00287 }
00288 
00289 #ifdef __cplusplus
00290 }
00291 #endif
00292 
00293 #endif /* ST_INCLUDED */
00294