1 /**********************************************************************
4 * Identifier Processing *
7 **********************************************************************/
12 #include "constants.h"
16 /* partain: special version for strings that may have NULs (etc) in them
33 installHstring(length, s)
41 /* fprintf(stderr, "installHstring: %d, %s\n",length, s); */
43 if (length > 999999) { /* too long */
44 fprintf(stderr,"String length more than six digits\n");
46 } else if (length < 0) { /* too short */
47 fprintf(stderr,"String length < 0 !!\n");
51 /* alloc the struct and store the length */
52 str = (hstring) xmalloc(sizeof(Hstring));
61 /* now store the string */
62 for (i = 0; i < length; i++) {
71 /**********************************************************************
74 * Hashed Identifiers *
77 **********************************************************************/
80 extern BOOLEAN hashIds; /* Whether to use hashed ids. */
82 unsigned hash_table_size = HASH_TABLE_SIZE;
84 static char **hashtab = NULL;
86 static unsigned max_hash_table_entries = 0;
96 /* Create an initialised hash table */
97 hashtab = (char **) calloc( hash_table_size, sizeof(char *) );
100 fprintf(stderr,"Cannot allocate a hash table with %d entries -- insufficient memory\n",hash_table_size);
104 fprintf(stderr,"hashtab = %x\n",hashtab);
107 /* Allow no more than 90% occupancy -- Divide first to avoid overflows with BIG tables! */
108 max_hash_table_entries = (hash_table_size / 10) * 9;
119 printf("%u ",hash_table_size);
121 for(i=0; i < hash_table_size; ++i)
122 if(hashtab[i] != NULL)
123 printf("(%u,%s) ",i,hashtab[i]);
132 return((char **) /* YURGH */ ident - hashtab);
137 The hash function. Returns 0 for Null strings.
140 static unsigned hash_fn(ident)
143 unsigned len = (unsigned) strlen(ident);
149 /* does not work well for hash tables with more than 35K elements */
150 res = (((unsigned)ident[0]*631)+((unsigned)ident[len/2-1]*217)+((unsigned)ident[len-1]*43)+len)
154 fprintf(stderr,"\"%s\" hashes to %d\n",ident,res);
161 Install a literal identifier, such as "+" in hsparser.
162 If we are not using hashing, just return the string.
169 return( hashIds? installid(s): s);
177 return( hashIds? *(char **)sp: (char *)sp );
184 unsigned hash, count;
189 for(hash = hash_fn(s),count=0; count<max_hash_table_entries; ++hash,++count)
191 if (hash >= hash_table_size) hash = 0;
193 if(hashtab[hash] == NULL)
195 hashtab[hash] = xstrdup(s);
197 fprintf(stderr,"New Hash Entry %x\n",(char *)&hashtab[hash]);
199 if ( count >= 100 ) {
200 fprintf(stderr, "installid: %d collisions for %s\n", count, s);
203 return((char *)&hashtab[hash]);
206 if(strcmp(hashtab[hash],s) == 0)
209 fprintf(stderr,"Old Hash Entry %x (%s)\n",(char *)&hashtab[hash],hashtab[hash]);
211 if ( count >= 100 ) {
212 fprintf(stderr, "installid: %d collisions for %s\n", count, s);
215 return((char *)&hashtab[hash]);
218 fprintf(stderr,"Hash Table Contains more than %d entries -- make larger?\n",max_hash_table_entries);
223 /**********************************************************************
226 * Memory Allocation *
229 **********************************************************************/
231 /* Malloc with error checking */
237 char *stuff = malloc(length);
240 fprintf(stderr, "xmalloc failed on a request for %d bytes\n", length);
247 xrealloc(ptr, length)
251 char *stuff = realloc(ptr, length);
254 fprintf(stderr, "xrealloc failed on a request for %d bytes\n", length);
260 /* Strdup with error checking */
266 unsigned len = strlen(s);
267 return xstrndup(s, len);
271 * Strdup for possibly unterminated strings (e.g. substrings of longer strings)
272 * with error checking. Handles NULs as well.
280 char *p = xmalloc(len + 1);