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