generic/general/table.h

/*  ASCEND modelling environment
    Copyright (C) 2006 Carnegie Mellon University
    Copyright (C) 1994 Kirk Andre Abbott

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2, or (at your option)
    any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.
*//** @file
    Hash Table Module.
    
    Many hash tables are used throughout the implementation of a compiler
    and/or interpreter. This module (in the spirit of the list module)
    attempts to provide a generic table implementation, based on the classic
    *bucket and chains* for resolving collisions. Nothing fancy is done,
    except that we cache a ptr to the last thing found, so that access to
    it if required is fast. We append the new element to the front of the
    chain. The hashpjw algorithm is used.
    
    This module is appropriate for hash tables keyed with arbitrary strings.
    It is not appropriate for use with symbol table entry keys.

    Requires:
    #include "utilities/ascConfig.h"
*//*
    by Kirk A. Abbott
    Created December 29, 1994.
    Last in CVS $Revision: 1.3 $ $Date: 1998/06/16 15:47:47 $ $Author: mthomas $
*/

#ifndef ASC_TABLE_H
#define ASC_TABLE_H

typedef  void (*TableIteratorOne)(void *);
/**<
 * Typedef for casting of 1-parameter functions
 * being passed to TableApply* functions.
 */
typedef  void (*TableIteratorTwo)(void *,void *);
/**<
 * Typedef for casting of 2-parameter functions
 * being passed to TableApply* functions.
 */

ASC_DLLSPEC(struct Table *) CreateTable(unsigned long hashsize);
/**<
 *  Creates a new hash table with the specified hashsize.
 *  This ideally should be a prime number.  A good choice will give
 *  better performance without wasting too much memory.  Some good
 *  prime numbers are: 31, 97, 113, 229, 541, 1023, 3571.
 *  Everything is appropriately initialized.<br><br>
 *
 *  The function returns a pointer to the newly created hash table.
 *  Deallocation of the table is the responsibility of the caller 
 *  using DestroyTable().
 *
 *  @param hashsize The number of buckets in the new hash table.
 *  @return A pointer to the new hash table.
 *  @todo Should general/table:CreateTable have lower limit on hashsize?
 */

ASC_DLLSPEC(void ) DestroyTable(struct Table *table, int dispose);
/**<
 *  Destroys the given table.  If dispose is set to TRUE (nonzero), 
 *  the data items stored in the table will be deallocated as well.  
 *  Do not refer to a table after it has been destroyed.  The 
 *  specified table may be NULL, in which case this function has no
 *  effect.
 *
 *  @param table   Pointer to the hash table to destroy (non-NULL).
 *  @param dispose If non-zero deallocate the stored data also,
 *                 if 0 the data is destroyed as well.
 */

ASC_DLLSPEC(void ) AddTableData(struct Table * table, void *data, CONST char *id);
/**<
 *  Stores *data* in the hash table using id as the lookup key. 
 *  Currently id must be a unique NULL-terminated string.  In the 
 *  future, this may be changed to a generic lookup function 
 *  supplied by the user.  If the id is not unique in the table,
 *  the data is not added.  The *data* can be anything, including 
 *  a NULL pointer.  A pointer to the last item added is cached so 
 *  that subsequent lookup is fairly fast (see TableLastFind()).  
 *  Neither table nor id may be NULL (checked by assertion).
 *
 *  @param table Pointer to the hash table to add to (non-NULL).
 *  @param data  The data to store in the table.
 *  @param id    NULL-terminated string to use for lookup key (non-NULL).
 */

ASC_DLLSPEC(void *) LookupTableData(struct Table *table, CONST char *id);
/**<
 *  Retrieves the data stored in the table under the key *id*.
 *  It will return NULL if id is not found.  A pointer to the last item
 *  looked up is cached so that subsequent lookup is fairly fast
 *  (see TableLastFind()).  The return value will generally need to be
 *  cast to the correct type.  Neither table nor id may be NULL
 *  (checked by assertion).
 *
 *  @param table Pointer to the hash table to query (non-NULL).
 *  @param id    NULL-terminated string to use for lookup key (non-NULL).
 *  @return The data stored under lookup key id, or NULL if not found.
 */

ASC_DLLSPEC(void *) RemoveTableData(struct Table *table, char *id);
/**<
 *  Removes the data stored in the table under the key *id*.
 *  It will return NULL if id is not found.  Otherwise, it will
 *  return the data that was stored under id.  The data is not
 *  deallocated.  The return value will generally need to be
 *  cast to the correct type.  Neither table nor id may be NULL
 *  (checked by assertion).
 *
 *  @param table Pointer to the hash table to query (non-NULL).
 *  @param id    NULL-terminated string to use for lookup key (non-NULL).
 *  @return The data stored under lookup key id, or NULL if not found.
 */

ASC_DLLSPEC(void ) TableApplyOne(struct Table *table,
                          TableIteratorOne applyfunc,
                          char *id);
/**<
 *  Calls the specified function, passing the data stored in the table
 *  under key *id* as argument.  The lookup is fast if the data item was
 *  the last searched for, slower otherwise.  The function applyfunc must
 *  be able to handle NULL pointers gracefully.  Neither table, applyfunc,
 *  nor id may be NULL (checked by assertion).
 *
 *  @param table     Pointer to the hash table to use (non-NULL).
 *  @param applyfunc Pointer to the function to apply (non-NULL).
 *  @param id        NULL-terminated string to use for lookup key (non-NULL).
 */

ASC_DLLSPEC(void ) TableApplyAll(struct Table *table, TableIteratorOne applyfunc);
/**<
 *  Calls the specified function for each data item stored in the table.
 *  The order of operation dependends on internal table structure, so is
 *  not predictable and should not be relied upon.  Using this function
 *  should be a lot faster than fetching each element independently and 
 *  applying applyfunc to it.  The function must be able to handle NULL 
 *  pointers gracefully.  Neither table nor applyfunc may be NULL 
 *  (checked by assertion).
 *
 *  @param table     Pointer to the hash table to use (non-NULL).
 *  @param applyfunc Pointer to the function to apply (non-NULL).
 */

ASC_DLLSPEC(void ) TableApplyAllTwo(struct Table *table,
                             TableIteratorTwo applyfunc,
                             void *arg2);
/**<
 *  Calls the specified function for each data item stored in the table.
 *  This is the same as TableApplyAll(), except that arg2 is passed as a
 *  second argument to applyfunc allowing a closure.  The order of 
 *  operation dependends on internal table structure, so is not 
 *  predictable and should not be relied upon.  Using this function
 *  should be a lot faster than fetching each element independently and
 *  applying applyfunc to it.  The function must be able to handle NULL
 *  pointers gracefully.  Neither table nor applyfunc may be NULL
 *  (checked by assertion).
 *
 *  @param table     Pointer to the hash table to use (non-NULL).
 *  @param applyfunc Pointer to the function to apply (non-NULL).
 *  @param arg2      The 2nd argument to pass to applyfunc.
 */

extern void PrintTable(FILE *file, struct Table *table);
/**<
 *  Prints information about the table to the given file.  This
 *  information currently includes an ordered list of bucket
 *  numbers and id strings for each data item in the table.
 *  The file must be opened and ready for writing.  Neither table
 *  nor file may be NULL (checked by assertion).
 *
 *  @param file  Open, writable file stream to receive the report (non-NULL).
 *  @param table Pointer to the hash table to query (non-NULL).
 */

ASC_DLLSPEC(unsigned long ) TableSize(struct Table *table);
/**<
 *  Returns the current number of entries in the table.  The
 *  specified table may not be NULL (checked by assertion).
 *
 *  @param table Pointer to the hash table to query (non-NULL).
 */

ASC_DLLSPEC(unsigned long ) TableHashSize(struct Table *table);
/**<
 *  Returns the current hashsize of the table.  If internally we 
 *  change the hashing/collision algorithm, this may be useful 
 *  information to someone.  At the moment it is the size 
 *  requested and hence is not very useful.  The specified table 
 *  may not be NULL (checked by assertion).
 *
 *  @param table Pointer to the hash table to query (non-NULL).
 */

ASC_DLLSPEC(void *) TableLastFind(struct Table *table);
/**<
 *  Returns the data item that was last added to or retrieved from the 
 *  table.  Could be useful for those, "do you exist?; now do something 
 *  with you" situations.  Returns NULL if no item was added or retrieved
 *  from the table.  The specified table may not be NULL (checked by
 *  assertion).
 *
 *  @param table Pointer to the hash table to query (non-NULL).
 */

#endif /* ASC_TABLE_H */
1	/* ASCEND modelling environment
2	Copyright (C) 2006 Carnegie Mellon University
3	Copyright (C) 1994 Kirk Andre Abbott
4
5	This program is free software; you can redistribute it and/or modify
6	it under the terms of the GNU General Public License as published by
7	the Free Software Foundation; either version 2, or (at your option)
8	any later version.
9
10	This program is distributed in the hope that it will be useful,
11	but WITHOUT ANY WARRANTY; without even the implied warranty of
12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13	GNU General Public License for more details.
14
15	You should have received a copy of the GNU General Public License
16	along with this program; if not, write to the Free Software
17	Foundation, Inc., 59 Temple Place - Suite 330,
18	Boston, MA 02111-1307, USA.
19	//* @file
20	Hash Table Module.
21
22	Many hash tables are used throughout the implementation of a compiler
23	and/or interpreter. This module (in the spirit of the list module)
24	attempts to provide a generic table implementation, based on the classic
25	bucket and chains for resolving collisions. Nothing fancy is done,
26	except that we cache a ptr to the last thing found, so that access to
27	it if required is fast. We append the new element to the front of the
28	chain. The hashpjw algorithm is used.
29
30	This module is appropriate for hash tables keyed with arbitrary strings.
31	It is not appropriate for use with symbol table entry keys.
32
33	Requires:
34	#include "utilities/ascConfig.h"
35	//
36	by Kirk A. Abbott
37	Created December 29, 1994.
38	Last in CVS $Revision: 1.3 $ $Date: 1998/06/16 15:47:47 $ $Author: mthomas $
39	*/
40
41	#ifndef ASC_TABLE_H
42	#define ASC_TABLE_H
43
44	typedef void (TableIteratorOne)(void );
45	/**<
46	* Typedef for casting of 1-parameter functions
47	* being passed to TableApply* functions.
48	*/
49	typedef void (TableIteratorTwo)(void ,void *);
50	/**<
51	* Typedef for casting of 2-parameter functions
52	* being passed to TableApply* functions.
53	*/
54
55	ASC_DLLSPEC(struct Table *) CreateTable(unsigned long hashsize);
56	/**<
57	* Creates a new hash table with the specified hashsize.
58	* This ideally should be a prime number. A good choice will give
59	* better performance without wasting too much memory. Some good
60	* prime numbers are: 31, 97, 113, 229, 541, 1023, 3571.
61	* Everything is appropriately initialized.<br><br>
62	*
63	* The function returns a pointer to the newly created hash table.
64	* Deallocation of the table is the responsibility of the caller
65	* using DestroyTable().
66	*
67	* @param hashsize The number of buckets in the new hash table.
68	* @return A pointer to the new hash table.
69	* @todo Should general/table:CreateTable have lower limit on hashsize?
70	*/
71
72	ASC_DLLSPEC(void ) DestroyTable(struct Table *table, int dispose);
73	/**<
74	* Destroys the given table. If dispose is set to TRUE (nonzero),
75	* the data items stored in the table will be deallocated as well.
76	* Do not refer to a table after it has been destroyed. The
77	* specified table may be NULL, in which case this function has no
78	* effect.
79	*
80	* @param table Pointer to the hash table to destroy (non-NULL).
81	* @param dispose If non-zero deallocate the stored data also,
82	* if 0 the data is destroyed as well.
83	*/
84
85	ASC_DLLSPEC(void ) AddTableData(struct Table * table, void data, CONST char id);
86	/**<
87	* Stores data in the hash table using id as the lookup key.
88	* Currently id must be a unique NULL-terminated string. In the
89	* future, this may be changed to a generic lookup function
90	* supplied by the user. If the id is not unique in the table,
91	* the data is not added. The data can be anything, including
92	* a NULL pointer. A pointer to the last item added is cached so
93	* that subsequent lookup is fairly fast (see TableLastFind()).
94	* Neither table nor id may be NULL (checked by assertion).
95	*
96	* @param table Pointer to the hash table to add to (non-NULL).
97	* @param data The data to store in the table.
98	* @param id NULL-terminated string to use for lookup key (non-NULL).
99	*/
100
101	ASC_DLLSPEC(void ) LookupTableData(struct Table table, CONST char *id);
102	/**<
103	* Retrieves the data stored in the table under the key id.
104	* It will return NULL if id is not found. A pointer to the last item
105	* looked up is cached so that subsequent lookup is fairly fast
106	* (see TableLastFind()). The return value will generally need to be
107	* cast to the correct type. Neither table nor id may be NULL
108	* (checked by assertion).
109	*
110	* @param table Pointer to the hash table to query (non-NULL).
111	* @param id NULL-terminated string to use for lookup key (non-NULL).
112	* @return The data stored under lookup key id, or NULL if not found.
113	*/
114
115	ASC_DLLSPEC(void ) RemoveTableData(struct Table table, char *id);
116	/**<
117	* Removes the data stored in the table under the key id.
118	* It will return NULL if id is not found. Otherwise, it will
119	* return the data that was stored under id. The data is not
120	* deallocated. The return value will generally need to be
121	* cast to the correct type. Neither table nor id may be NULL
122	* (checked by assertion).
123	*
124	* @param table Pointer to the hash table to query (non-NULL).
125	* @param id NULL-terminated string to use for lookup key (non-NULL).
126	* @return The data stored under lookup key id, or NULL if not found.
127	*/
128
129	ASC_DLLSPEC(void ) TableApplyOne(struct Table *table,
130	TableIteratorOne applyfunc,
131	char *id);
132	/**<
133	* Calls the specified function, passing the data stored in the table
134	* under key id as argument. The lookup is fast if the data item was
135	* the last searched for, slower otherwise. The function applyfunc must
136	* be able to handle NULL pointers gracefully. Neither table, applyfunc,
137	* nor id may be NULL (checked by assertion).
138	*
139	* @param table Pointer to the hash table to use (non-NULL).
140	* @param applyfunc Pointer to the function to apply (non-NULL).
141	* @param id NULL-terminated string to use for lookup key (non-NULL).
142	*/
143
144	ASC_DLLSPEC(void ) TableApplyAll(struct Table *table, TableIteratorOne applyfunc);
145	/**<
146	* Calls the specified function for each data item stored in the table.
147	* The order of operation dependends on internal table structure, so is
148	* not predictable and should not be relied upon. Using this function
149	* should be a lot faster than fetching each element independently and
150	* applying applyfunc to it. The function must be able to handle NULL
151	* pointers gracefully. Neither table nor applyfunc may be NULL
152	* (checked by assertion).
153	*
154	* @param table Pointer to the hash table to use (non-NULL).
155	* @param applyfunc Pointer to the function to apply (non-NULL).
156	*/
157
158	ASC_DLLSPEC(void ) TableApplyAllTwo(struct Table *table,
159	TableIteratorTwo applyfunc,
160	void *arg2);
161	/**<
162	* Calls the specified function for each data item stored in the table.
163	* This is the same as TableApplyAll(), except that arg2 is passed as a
164	* second argument to applyfunc allowing a closure. The order of
165	* operation dependends on internal table structure, so is not
166	* predictable and should not be relied upon. Using this function
167	* should be a lot faster than fetching each element independently and
168	* applying applyfunc to it. The function must be able to handle NULL
169	* pointers gracefully. Neither table nor applyfunc may be NULL
170	* (checked by assertion).
171	*
172	* @param table Pointer to the hash table to use (non-NULL).
173	* @param applyfunc Pointer to the function to apply (non-NULL).
174	* @param arg2 The 2nd argument to pass to applyfunc.
175	*/
176
177	extern void PrintTable(FILE file, struct Table table);
178	/**<
179	* Prints information about the table to the given file. This
180	* information currently includes an ordered list of bucket
181	* numbers and id strings for each data item in the table.
182	* The file must be opened and ready for writing. Neither table
183	* nor file may be NULL (checked by assertion).
184	*
185	* @param file Open, writable file stream to receive the report (non-NULL).
186	* @param table Pointer to the hash table to query (non-NULL).
187	*/
188
189	ASC_DLLSPEC(unsigned long ) TableSize(struct Table *table);
190	/**<
191	* Returns the current number of entries in the table. The
192	* specified table may not be NULL (checked by assertion).
193	*
194	* @param table Pointer to the hash table to query (non-NULL).
195	*/
196
197	ASC_DLLSPEC(unsigned long ) TableHashSize(struct Table *table);
198	/**<
199	* Returns the current hashsize of the table. If internally we
200	* change the hashing/collision algorithm, this may be useful
201	* information to someone. At the moment it is the size
202	* requested and hence is not very useful. The specified table
203	* may not be NULL (checked by assertion).
204	*
205	* @param table Pointer to the hash table to query (non-NULL).
206	*/
207
208	ASC_DLLSPEC(void ) TableLastFind(struct Table table);
209	/**<
210	* Returns the data item that was last added to or retrieved from the
211	* table. Could be useful for those, "do you exist?; now do something
212	* with you" situations. Returns NULL if no item was added or retrieved
213	* from the table. The specified table may not be NULL (checked by
214	* assertion).
215	*
216	* @param table Pointer to the hash table to query (non-NULL).
217	*/
218
219	#endif /* ASC_TABLE_H */