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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 59 - (show annotations) (download) (as text)
Sun Oct 30 01:38:20 2005 UTC (18 years, 7 months ago) by jds
File MIME type: text/x-csrc
File size: 6980 byte(s)
- prototype unit test suite based on CUnit added.
- unit tests for base/generic/general and base/generic/utilites added.
- 2nd manual rework of doxygen documentation in general and utilities.
- bug fixes (mostly general & utilities) found during test development.
- added asc_assert prototype to redirect failures to Asc_Panic() and enable decoupling assertions from NDEBUG.
- some modifications of interface & implementation to facilitate testing.
- utilities/ascPrint & utilities/ascMalloc functions now always included in base libs to minimize recompilation when an interface chooses different options.
1 /*
2 * Table Module
3 * by Kirk A. Abbott
4 * Created December 29, 1994.
5 * Version: $Revision: 1.2 $
6 * Version control file: $RCSfile: table.c,v $
7 * Date last modified: $Date: 1998/06/16 15:47:46 $
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 #include "utilities/ascConfig.h"
32 #include "compiler/compiler.h"
33 #include "utilities/ascMalloc.h"
34 #include "utilities/ascPanic.h"
35 #include "general/hashpjw.h"
36 #include "general/table.h"
37
38 struct TableEntry {
39 char *id; /* id string used to hash entry */
40 void *data; /* the actual data */
41 struct TableEntry *next; /* pointer to next entry in linked list */
42 };
43
44
45 struct Table {
46 unsigned long hashsize; /* number of buckets */
47 unsigned long size; /* the current number of entries */
48 struct TableEntry **buckets; /* the actual buckets */
49 struct TableEntry *lastfind; /* a cached pointer into the last thing found */
50 };
51
52
53 struct Table *CreateTable(unsigned long hashsize)
54 {
55 struct Table *result;
56 struct TableEntry **buckets;
57 result = (struct Table *)ascmalloc(sizeof(struct Table));
58 buckets = (struct TableEntry **)asccalloc(hashsize,sizeof(struct TableEntry *));
59 result->buckets = buckets;
60 result->size = 0;
61 result->hashsize = hashsize;
62 result->lastfind = NULL;
63 return result;
64 }
65
66 static void DestroyTableData(void *data, int dispose)
67 {
68 if (dispose)
69 ascfree((char *)data);
70 }
71
72 void DestroyTable(struct Table *table, int dispose)
73 {
74 struct TableEntry *ptr, *next;
75 unsigned long hashsize,c;
76
77 if (table==NULL) return;
78 hashsize = table->hashsize;
79 for (c=0 ; c<hashsize ; c++) {
80 if (table->buckets[c] != NULL) {
81 ptr = table->buckets[c];
82 while(ptr!=NULL) {
83 DestroyTableData(ptr->data, dispose); /* deallocate the data */
84 next = ptr->next;
85 ascfree((char *)ptr->id); /* deallocate the string */
86 ascfree((char *)ptr); /* deallocate the node */
87 table->size--;
88 ptr = next;
89 }
90 table->buckets[c] = NULL;
91 }
92 }
93 ascfree((char *)table->buckets); /* deallocate the table */
94 ascfree((char *)table); /* deallocate the head */
95 }
96
97
98 void AddTableData(struct Table *table, void *data, CONST char *id)
99 {
100 unsigned long c;
101 struct TableEntry *ptr;
102
103 asc_assert((NULL != table) && (NULL != id));
104 c = hashpjw(id,table->hashsize);
105 ptr = table->buckets[c];
106 /* search for name collisions */
107 while (ptr) {
108 if (strcmp(id,ptr->id)==0)
109 return;
110 ptr = ptr->next;
111 }
112 /* add new information node to the head of the list. */
113 ptr = (struct TableEntry *)
114 ascmalloc(sizeof(struct TableEntry));
115 ptr->id = (char *)ascmalloc((strlen(id)+1)*sizeof(char));
116 strcpy(ptr->id,id); /* we will copy the string */
117 ptr->next = table->buckets[c];
118 ptr->data = data;
119 table->buckets[c] = ptr;
120 table->size++;
121 table->lastfind = ptr;
122 }
123
124 void *LookupTableData(struct Table *table, CONST char *id)
125 {
126 unsigned long c;
127 struct TableEntry *ptr;
128
129 asc_assert((NULL != table) && (NULL != id));
130 c = hashpjw(id,table->hashsize);
131 ptr = table->buckets[c];
132 while (ptr) {
133 if (strcmp(id,ptr->id)==0) {
134 table->lastfind = ptr;
135 return ptr->data;
136 }
137 ptr = ptr->next;
138 }
139 table->lastfind = NULL;
140 return NULL; /* id not found */
141 }
142
143 void *RemoveTableData(struct Table *table, char *id)
144 {
145 unsigned long c;
146 struct TableEntry *ptr, **tmp;
147 void *result;
148
149 asc_assert((NULL != table) && (NULL != id));
150 c = hashpjw(id,table->hashsize);
151 tmp = &table->buckets[c];
152 ptr = table->buckets[c];
153 while (ptr) {
154 if (strcmp(id,ptr->id)==0) {
155 *tmp = ptr->next;
156 result = ptr->data;
157 if (table->lastfind==ptr) table->lastfind = NULL;
158 ascfree((char *)ptr->id); /* deallocate the string */
159 ascfree((char *)ptr); /* deallocate the node */
160 table->size--;
161 return result;
162 }
163 tmp = &ptr->next;
164 ptr = ptr->next;
165 }
166 return NULL; /* node id not found */
167 }
168
169 /*
170 * Check our cached pointer first. If we don't find a match,
171 * then do a Lookup. The lookup will reset the cached pointer.
172 */
173 void TableApplyOne(struct Table *table,
174 TableIteratorOne applyfunc,
175 char *id)
176 {
177 void *data;
178
179 asc_assert((NULL != table) && (NULL != applyfunc) && (NULL != id));
180 if (table->lastfind) {
181 if (strcmp(table->lastfind->id,id)==0) {
182 (*applyfunc)(table->lastfind->data);
183 return;
184 }
185 }
186 data = LookupTableData(table,id);
187 if (data)
188 (*applyfunc)(data);
189 return;
190 }
191
192 void TableApplyAll(struct Table *table, TableIteratorOne applyfunc)
193 {
194 unsigned long c,hashsize;
195 struct TableEntry *ptr;
196
197 asc_assert((NULL != table) && (NULL != applyfunc));
198
199 hashsize = table->hashsize;
200 for (c=0;c<hashsize;c++) {
201 ptr = table->buckets[c];
202 while (ptr) {
203 (*applyfunc)(ptr->data);
204 ptr = ptr->next;
205 }
206 }
207 }
208
209 void TableApplyAllTwo(struct Table *table,
210 TableIteratorTwo applyfunc,
211 void *arg2)
212 {
213 unsigned long c,hashsize;
214 struct TableEntry *ptr;
215
216 asc_assert((NULL != table) && (NULL != applyfunc));
217
218 hashsize = table->hashsize;
219 for (c=0;c<hashsize;c++) {
220 ptr = table->buckets[c];
221 while (ptr) {
222 (*applyfunc)(ptr->data,arg2);
223 ptr = ptr->next;
224 }
225 }
226 }
227
228 void PrintTable(FILE *f, struct Table *table)
229 {
230 unsigned long c,hashsize;
231 struct TableEntry *ptr;
232 unsigned long entrynum = 1;
233
234 asc_assert((NULL != table) && (NULL != f));
235
236 hashsize = table->hashsize;
237 for (c=0;c<hashsize;c++) {
238 ptr = table->buckets[c];
239 while (ptr) {
240 FPRINTF(f,"Entry %lu\tBucket %lu\tId %s\n",
241 entrynum++,c,ptr->id);
242 ptr = ptr->next;
243 }
244 }
245 }
246
247 unsigned long TableSize(struct Table *table)
248 {
249 asc_assert(table!=NULL);
250 return table->size;
251 }
252
253 unsigned long TableHashSize(struct Table *table)
254 {
255 asc_assert(table!=NULL);
256 return table->hashsize;
257 }
258
259 void *TableLastFind(struct Table *table)
260 {
261 asc_assert(table!=NULL);
262 return (NULL == table->lastfind) ?
263 NULL : table->lastfind->data;
264 }
265

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