1 saw 1.1 /*-----------------------------------------------------------------------------
2 * Copyright (c) 1991,1992 Southeastern Universities Research Association,
3 * Continuous Electron Beam Accelerator Facility
4 *
5 * This software was developed under a United States Government license
6 * described in the NOTICE file included as part of this distribution.
7 *
8 * CEBAF Data Acquisition Group, 12000 Jefferson Ave., Newport News, VA 23606
9 * Email: coda@cebaf.gov Tel: (804) 249-7101 Fax: (804) 249-7363
10 *-----------------------------------------------------------------------------
11 *
12 * Description:
13 * CODA readout language symbol hashtable related routines
14 *
15 * Author: Jie Chen, CEBAF Data Acquisition Group
16 *
17 * Revision History:
18 * $Log: daVarHashLib.c,v $
19 * Revision 1.1 1996/07/31 20:33:15 saw
20 * Initial revision
21 *
22 saw 1.1 * $Log: daVarHashLib.c,v $
23 * Revision 1.1 1996/07/31 20:33:15 saw
24 * Initial revision
25 *
26 * Revision 1.1 94/03/15 12:53:11 12:53:11 heyes (Graham Heyes)
27 * Initial revision
28 *
29 *
30 */
31 #define CASE_INSENSITIVE
32
33 #include <stdio.h>
|
35 saw 1.1 #include "daVarHash.h"
36 #include "daVar.h"
37
38 /* hash table size, change to a different prime number if necessary */
39 /* Some primes: 97 257 1031 2053 4099 */
40
41 /*static symbolEntry *hash_table_head[TABLE_SIZE];*/
42 static void crlSymbol_copy();
43 static void crlSymbol_delete();
44 static int hashFunction();
45
46 #ifdef CASE_INSENSITIVE
47 #define STRCMP daVarComp
48 #define TOLOWER tolower
49 #else
50 #define STRCMP strcmp
51 #define TOLOWER
52 #endif
53
54 #ifdef _NO_STRDUP
55 char *strdup (s)
56 saw 1.1 char *s;
57 {
58 char *p = (char *)malloc ((strlen(s) + 1)*sizeof(char));
59 if (p == 0) {
60 fprintf (stderr, "Cannot allocate memory for strdup\n");
61 exit (1);
62 }
63 strcpy (p, s);
64 return p;
65 }
66 #endif
67
68 /****************************************************************
69 * void crlHashCreate() *
70 * Hash table creation routine. Hash table is organized in *
71 * such a way to eliminate the collision *
72 ***************************************************************/
73 void crlHashCreate(symbolEntry **hash_table_head)
74 {
75 register int i;
76
77 saw 1.1 for (i = 0; i < TABLE_SIZE; i++){
78 hash_table_head[i]=(symbolEntry *)malloc(sizeof(symbolEntry));
79 if(hash_table_head[i] == NULL){
80 fprintf(stderr,"Cannot allocate memory for crl hash table\n");
81 exit(1);
82 }
83 else{
84 hash_table_head[i]->crlSymbol = 0;
85 hash_table_head[i]->next=(symbolEntry *)0;
86 }
87 }
88 }
89
90 /*************************************************************
91 * int crlHashAdd() *
92 * Add an item to the hashTable, return 1 on success *
93 * return 0 on failure *
94 ************************************************************/
95 int crlHashAdd (CrlSymbol symbol,symbolEntry **hash_table_head)
96 {
97 int hashvalue,i;
98 saw 1.1 symbolEntry *ptr,*txt;
99
100 hashvalue = hashFunction(symbol, TABLE_SIZE);
101 /* printf ("Hash value for is %d\n",hashvalue);*/
102 for(ptr = hash_table_head[hashvalue]->next; ptr != NULL; ptr = ptr->next){
103 if((STRCMP(ptr->crlSymbol,symbol)) == 0)
104 break;
105 else
106 ;
107 }
108 if(ptr !=NULL)
109 return 0;
110 else{
111 txt=(symbolEntry *)malloc(sizeof(symbolEntry));
112 if(txt == NULL){
113 fprintf(stderr,"Cannot allocate memory for this cns entry.\n");
114 exit(1);
115 }
116 /* crlSymbol_copy(&txt->crlSymbol,symbol);*/
117 txt->crlSymbol = symbol;
118 txt->next = hash_table_head[hashvalue]->next;
119 saw 1.1 hash_table_head[hashvalue]->next=txt;
120 return 1;
121 }
122 }
123
124 /************************************************************
125 * int crlHashDelete() *
126 * delete a single item from the Hash Table *
127 * return 0 on success, return 1 on failure *
128 ***********************************************************/
129 int crlHashDelete(CrlSymbol symbol,symbolEntry **hash_table_head)
130 {
131 int hashvalue;
132 symbolEntry *ptr,*qtr;
133
134 hashvalue=hashFunction (symbol, TABLE_SIZE);
135 qtr = hash_table_head [hashvalue];
136 for(ptr = hash_table_head[hashvalue]->next; ptr!=NULL; ptr=ptr->next){
137 if((STRCMP(ptr->crlSymbol, symbol)) == 0)
138 break;
139 else
140 saw 1.1 qtr=qtr->next;
141 }
142
143 if(ptr !=NULL){
144 qtr->next=ptr->next;
145 ptr->next=NULL;
146 /* free memory */
147 /* crlSymbol_delete (&(ptr->crlSymbol));*/
148 free (ptr);
149 return 0;
150 }
151 else
152 return 1;
153 }
154
155 /**************************************************************
156 * int crlHashFind() *
157 * Find out whether a particular item which has key 'key' *
158 * existed in the hash Tabel, return item *
159 * return 0 for failure *
160 *************************************************************/
161 saw 1.1 CrlSymbol *crlHashFind(CrlSymbol symbol,symbolEntry **hash_table_head)
162 {
163 int hashvalue;
164 symbolEntry *ptr;
165
166 hashvalue = hashFunction (symbol, TABLE_SIZE);
167 /* printf ("Hash value inside find for is %d\n", hashvalue);*/
168 for(ptr = hash_table_head[hashvalue]->next; ptr != NULL; ptr = ptr->next){
169 if((STRCMP(ptr->crlSymbol, symbol)) == 0)
170 break;
171 else
172 ;
173 }
174 if(ptr != NULL){
175 return(&(ptr->crlSymbol));
176 }
177 else
178 return 0;
179 }
180
181 /**********************************************************
182 saw 1.1 * int crlHashDestroy() *
183 * Destroy hashTable and free memory *
184 * return 0 on success, return 1 on failure *
185 *********************************************************/
186 #if 0
187 int crlHashDestroy()
188 {
189 int i;
190 symbolEntry *ptr,*qtr;
191
192 for(i=0;i < TABLE_SIZE; i++){
193 ptr = hash_table_head[i];
194 while(ptr != NULL){
195 qtr = ptr->next;
196 /* free all memory */
197 crlSymbol_delete (&(ptr->crlSymbol));
198 free(ptr);
199 /* update pointer information */
200 ptr = qtr;
201 }
202 }
203 saw 1.1 return 0;
204 }
205 #endif
206
207
208 /**********************************************************
209 * int hashFunction() *
210 * return hash value according to the char key *
211 * case sensitive *
212 *********************************************************/
213 static int hashFunction(s,slot_num)
214 daVarStruct *s;
215 int slot_num;
216 {
217 char *p;
218 unsigned h=0,g;
219
220 /* printf("H(%s)=",s->name);*/
221 for(p = s->name; *p !='\0'; p++) {
222 h= (h<<4) + (TOLOWER(*p));
223 if(g = h & 0xf0000000) {
224 saw 1.1 h=h^(g>>24);
225 h=h^g;
226 }
227 }
228 /* printf("%d\n",h%slot_num);*/
229 return h%slot_num;
230 }
231 extern void crlHashWalk(symbolEntry **hash_table_head,void (*action)())
232 {
233 int i;
234 symbolEntry *ptr;
235
236 for(i=0;i < TABLE_SIZE; i++){
237 ptr = hash_table_head[i]->next;
238 while(ptr != NULL){
239 (*action) (ptr->crlSymbol);
240 ptr = ptr->next;
241 }
242 }
243 }
244
245 saw 1.1 /**********************************************************
246 * void crlSymbol_copy() *
247 * locally used structure copy routine *
248 * copy expid struct from id1 to id2 *
249 * id2 memory must be allocated before use this routine *
250 **********************************************************/
251 /*static void crlSymbol_copy(id2,id1)
252 CrlSymbol *id2,*id1;
253 {
254 id2->var_name = strdup(id1->var_name);
255 id2->var_type = id1->var_type;
256 }*/
257
258 /**********************************************************
259 * void crlSymbol_delete() *
260 * locally used structure delete routine *
261 * free memory pointed by id *
262 **********************************************************/
263 #if 0
264 static void crlSymbol_delete(id)
265 CrlSymbol *id;
266 saw 1.1 {
267 free (id->var_name);
268 }
269 #endif
270 /*********************************************************
271 * void crlAddSymbols() *
272 * Description: *
273 * add list of var names to symbol hashtable *
274 ********************************************************/
275 #if 0
276 void crlAddSymbols(var_list,type)
277 char *var_list;
278 int type;
279 {
280 char *p, *q,temp[80];
281 int status;
282 CrlSymbol crlSymbol;
283
284 if(strchr(var_list,',') == NULL){ /* single var name */
285 crlSymbol.var_name = strdup(var_list);
286 crlSymbol.var_type = type;
287 saw 1.1 status = crlHashAdd(crlSymbol.var_name, &crlSymbol);
288 }
289 else{
290 p = var_list;
291 q = temp;
292 while(*p != '\n' && *p != '\0'){
293 if(*p == ','){
294 *q = '\0';
295 p++;
296 crlSymbol.var_name = strdup(temp);
297 crlSymbol.var_type = type;
298 status = crlHashAdd(crlSymbol.var_name,&crlSymbol);
299 q = temp;
300 }
301 else{
302 *q = *p;
303 q++; p++;
304 }
305 }
306 }
307 }
308 saw 1.1 #endif
309 /*****************************************************************
310 * void isSymbolFound() *
311 * Description: *
312 * Check to see whether a var name existed in the hashTable *
313 ****************************************************************/
314 #if 0
315 void isSymbolFound(symbol)
316 char *symbol;
317 {
318 int status = 0;
319
320 status = crlHashFind(symbol);
321 if(status != 0){
322 fprintf(stderr,"Error: Undefined symbol \"%s\"\n", symbol);
323 fprintf(stderr,"Cannot continue, Quit.\n");
324 exit(1);
325 }
326 }
327 #endif
|