← Back to branch summary

~ubuntu-branches/ubuntu/utopic/cccc/utopic

« back to all changes in this revision

Viewing changes to pccts/antlr/hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson
  • Date: 2003-08-23 04:34:05 UTC
  • Revision ID: james.westby@ubuntu.com-20030823043405-xnzd3mn3hwtvi6dr
Tags: upstream-3.pre81
Import upstream version 3.pre81

Show diffs side-by-side

added added

removed removed

Lines of Context:
pccts/antlr/hash.c
 
1
/*
 
2
 * hash.c
 
3
 *
 
4
 * Manage hash tables.
 
5
 *
 
6
 * The following functions are visible:
 
7
 *
 
8
 *              char    *mystrdup(char *);              Make space and copy string
 
9
 *              Entry   **newHashTable();               Create and return initialized hash table
 
10
 *              Entry   *hash_add(Entry **, char *, Entry *)
 
11
 *              Entry   *hash_get(Entry **, char *)
 
12
 *
 
13
 * SOFTWARE RIGHTS
 
14
 *
 
15
 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
 
16
 * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
 
17
 * company may do whatever they wish with source code distributed with
 
18
 * PCCTS or the code generated by PCCTS, including the incorporation of
 
19
 * PCCTS, or its output, into commerical software.
 
20
 *
 
21
 * We encourage users to develop software with PCCTS.  However, we do ask
 
22
 * that credit is given to us for developing PCCTS.  By "credit",
 
23
 * we mean that if you incorporate our source code into one of your
 
24
 * programs (commercial product, research project, or otherwise) that you
 
25
 * acknowledge this fact somewhere in the documentation, research report,
 
26
 * etc...  If you like PCCTS and have developed a nice tool with the
 
27
 * output, please mention that you developed it using PCCTS.  In
 
28
 * addition, we ask that this header remain intact in our source code.
 
29
 * As long as these guidelines are kept, we expect to continue enhancing
 
30
 * this system and expect to make other tools available as they are
 
31
 * completed.
 
32
 *
 
33
 * ANTLR 1.33
 
34
 * Terence Parr
 
35
 * Parr Research Corporation
 
36
 * with Purdue University and AHPCRC, University of Minnesota
 
37
 * 1989-1998
 
38
 */
 
39
 
 
40
#include <stdio.h>
 
41
#include "pcctscfg.h"
 
42
#include "hash.h"
 
43
 
 
44
#ifdef __USE_PROTOS
 
45
#include <stdlib.h>
 
46
#else
 
47
#ifdef VAXC
 
48
#include <stdlib.h>
 
49
#else
 
50
#include <malloc.h>
 
51
#endif
 
52
#endif
 
53
#include <string.h>
 
54
 
 
55
#define StrSame         0
 
56
 
 
57
#define fatal(err)                                                                                                                      \
 
58
                        {fprintf(stderr, "%s(%d):", __FILE__, __LINE__);                                \
 
59
                        fprintf(stderr, " %s\n", err); exit(PCCTS_EXIT_FAILURE);}
 
60
#define require(expr, err) {if ( !(expr) ) fatal(err);}
 
61
 
 
62
static unsigned size = HashTableSize;
 
63
static char *strings = NULL;
 
64
static char *strp;
 
65
static unsigned strsize = StrTableSize;
 
66
 
 
67
/* create the hash table and string table for terminals (string table only once) */
 
68
Entry **
 
69
#ifdef __USE_PROTOS
 
70
newHashTable( void )
 
71
#else
 
72
newHashTable( )
 
73
#endif
 
74
{
 
75
        Entry **table;
 
76
        
 
77
        table = (Entry **) calloc(size, sizeof(Entry *));
 
78
        require( table != NULL, "cannot allocate hash table");
 
79
        if ( strings == NULL )
 
80
        {
 
81
                strings = (char *) calloc(strsize, sizeof(char));
 
82
                require( strings != NULL, "cannot allocate string table");
 
83
                strp = strings;
 
84
        }
 
85
        return table;
 
86
}
 
87
 
 
88
void
 
89
#ifdef __USE_PROTOS
 
90
killHashTable( Entry **table )
 
91
#else
 
92
killHashTable( table )
 
93
Entry **table;
 
94
#endif
 
95
{
 
96
        /* for now, just free table, forget entries */
 
97
        free( (char *) table );     /* MR10 cast */
 
98
}
 
99
 
 
100
/* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */
 
101
Entry *
 
102
#ifdef __USE_PROTOS
 
103
hash_add( Entry **table, char *key, Entry *rec )
 
104
#else
 
105
hash_add( table, key, rec )
 
106
Entry **table;
 
107
char *key;
 
108
Entry *rec;
 
109
#endif
 
110
{
 
111
        unsigned h=0;
 
112
        char *p=key;
 
113
        require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition");
 
114
        
 
115
        Hash(p,h,size);
 
116
        rec->next = table[h];                   /* Add to singly-linked list */
 
117
        table[h] = rec;
 
118
        return rec;
 
119
}
 
120
 
 
121
/* Return ptr to 1st entry found in table under key (return NULL if none found) */
 
122
Entry *
 
123
#ifdef __USE_PROTOS
 
124
hash_get( Entry **table, char *key )
 
125
#else
 
126
hash_get( table, key )
 
127
Entry **table;
 
128
char *key;
 
129
#endif
 
130
{
 
131
        unsigned h=0;
 
132
        char *p=key;
 
133
        Entry *q;
 
134
/*      require(table!=NULL && key!=NULL, "get: invalid table and/or key");*/
 
135
        if ( !(table!=NULL && key!=NULL) ) *((char *) 34) = 3;
 
136
        
 
137
        Hash(p,h,size);
 
138
        for (q = table[h]; q != NULL; q = q->next)
 
139
        {
 
140
                if ( strcmp(key, q->str) == StrSame ) return( q );
 
141
        }
 
142
        return( NULL );
 
143
}
 
144
 
 
145
#ifdef DEBUG_HASH
 
146
void
 
147
#ifdef __USE_PROTOS
 
148
hashStat( Entry **table )
 
149
#else
 
150
hashStat( table )
 
151
Entry **table;
 
152
#endif
 
153
{
 
154
        static unsigned short count[20];
 
155
        int i,n=0,low=0, hi=0;
 
156
        Entry **p;
 
157
        float avg=0.0;
 
158
        
 
159
        for (i=0; i<20; i++) count[i] = 0;
 
160
        for (p=table; p<&(table[size]); p++)
 
161
        {
 
162
                Entry *q = *p;
 
163
                int len;
 
164
                
 
165
                if ( q != NULL && low==0 ) low = p-table;
 
166
                len = 0;
 
167
                if ( q != NULL ) fprintf(stderr, "[%d]", p-table);
 
168
                while ( q != NULL )
 
169
                {
 
170
                        len++;
 
171
                        n++;
 
172
                        fprintf(stderr, " %s", q->str);
 
173
                        q = q->next;
 
174
                        if ( q == NULL ) fprintf(stderr, "\n");
 
175
                }
 
176
                count[len]++;
 
177
                if ( *p != NULL ) hi = p-table;
 
178
        }
 
179
 
 
180
        fprintf(stderr, "Storing %d recs used %d hash positions out of %d\n",
 
181
                                        n, size-count[0], size);
 
182
        fprintf(stderr, "%f %% utilization\n",
 
183
                                        ((float)(size-count[0]))/((float)size));
 
184
        for (i=0; i<20; i++)
 
185
        {
 
186
                if ( count[i] != 0 )
 
187
                {
 
188
                        avg += (((float)(i*count[i]))/((float)n)) * i;
 
189
                        fprintf(stderr, "Bucket len %d == %d (%f %% of recs)\n",
 
190
                                                        i, count[i], ((float)(i*count[i]))/((float)n));
 
191
                }
 
192
        }
 
193
        fprintf(stderr, "Avg bucket length %f\n", avg);
 
194
        fprintf(stderr, "Range of hash function: %d..%d\n", low, hi);
 
195
}
 
196
#endif
 
197
 
 
198
/* Add a string to the string table and return a pointer to it.
 
199
 * Bump the pointer into the string table to next avail position.
 
200
 */
 
201
char *
 
202
#ifdef __USE_PROTOS
 
203
mystrdup( char *s )
 
204
#else
 
205
mystrdup( s )
 
206
char *s;
 
207
#endif
 
208
{
 
209
        char *start=strp;
 
210
        require(s!=NULL, "mystrdup: NULL string");
 
211
 
 
212
        while ( *s != '\0' )
 
213
        {
 
214
                require( strp <= &(strings[strsize-2]),
 
215
                                 "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n");
 
216
                *strp++ = *s++;
 
217
        }
 
218
        *strp++ = '\0';
 
219
 
 
220
        return( start );
 
221
}