/[ascend]/trunk/base/generic/general/table.h
ViewVC logotype

Contents of /trunk/base/generic/general/table.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 593 - (show annotations) (download) (as text)
Fri May 12 10:03:59 2006 UTC (16 years, 3 months ago) by johnpye
File MIME type: text/x-chdr
File size: 9628 byte(s)
Bumped version to 0.9.5.91.
Changed WITH_CUNIT_TESTS to WITH_CUNIT.
Added GCOV scons option.
Fixed up 'test' target for SCons.
Added lots of export symbols to libascend.so.

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

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22