]>
git.proxmox.com Git - mirror_edk2.git/blob - Tools/CodeTools/Source/Pccts/support/sym/sym.c
2 * Simple symbol table manager using coalesced chaining to resolve collisions
4 * Doubly-linked lists are used for fast removal of entries.
6 * 'sym.h' must have a definition for typedef "Sym". Sym must include at
7 * minimum the following fields:
11 * struct ... *next, *prev, **head, *scope;
15 * 'template.h' can be used as a template to create a 'sym.h'.
17 * 'head' is &(table[hash(itself)]).
18 * The hash table is not resizable at run-time.
19 * The scope field is used to link all symbols of a current scope together.
20 * Scope() sets the current scope (linked list) to add symbols to.
21 * Any number of scopes can be handled. The user passes the address of
22 * a pointer to a symbol table
23 * entry (INITIALIZED TO NULL first time).
25 * Available Functions:
27 * zzs_init(s1,s2) -- Create hash table with size s1, string table size s2.
28 * zzs_done() -- Free hash and string table created with zzs_init().
29 * zzs_add(key,rec)-- Add 'rec' with key 'key' to the symbol table.
30 * zzs_newadd(key) -- create entry; add using 'key' to the symbol table.
31 * zzs_get(key) -- Return pointer to last record entered under 'key'
33 * zzs_del(p) -- Unlink the entry associated with p. This does
34 * NOT free 'p' and DOES NOT remove it from a scope
35 * list. If it was a part of your intermediate code
36 * tree or another structure. It will still be there.
37 * It is only removed from further consideration
38 * by the symbol table.
39 * zzs_keydel(s) -- Unlink the entry associated with key s.
40 * Calls zzs_del(p) to unlink.
41 * zzs_scope(sc) -- Specifies that everything added to the symbol
42 * table with zzs_add() is added to the list (scope)
43 * 'sc'. 'sc' is of 'Sym **sc' type and must be
44 * initialized to NULL before trying to add anything
45 * to it (passing it to zzs_scope()). Scopes can be
46 * switched at any time and merely links a set of
47 * symbol table entries. If a NULL pointer is
48 * passed, the current scope is returned.
49 * zzs_rmscope(sc) -- Remove (zzs_del()) all elements of scope 'sc'
50 * from the symbol table. The entries are NOT
51 * free()'d. A pointer to the first
52 * element in the "scope" is returned. The user
53 * can then manipulate the list as he/she chooses
54 * (such as freeing them all). NOTE that this
55 * function sets your scope pointer to NULL,
56 * but returns a pointer to the list for you to use.
57 * zzs_stat() -- Print out the symbol table and some relevant stats.
58 * zzs_new(key) -- Create a new record with calloc() of type Sym.
59 * Add 'key' to the string table and make the new
60 * records 'symbol' pointer point to it.
61 * zzs_strdup(s) -- Add s to the string table and return a pointer
62 * to it. Very fast allocation routine
63 * and does not require strlen() nor calloc().
72 * Sym *scope1=NULL, *scope2=NULL, *a, *p;
76 * a = zzs_new("Apple"); zzs_add(a->symbol, a); -- No scope
77 * zzs_scope( &scope1 ); -- enter scope 1
78 * a = zzs_new("Plum"); zzs_add(a->symbol, a);
79 * zzs_scope( &scope2 ); -- enter scope 2
80 * a = zzs_new("Truck"); zzs_add(a->symbol, a);
82 * p = zzs_get("Plum");
83 * if ( p == NULL ) fprintf(stderr, "Hmmm...Can't find 'Plum'\n");
85 * p = zzs_rmscope(&scope1)
86 * for (; p!=NULL; p=p->scope) {printf("Scope1: %s\n", p->symbol);}
87 * p = zzs_rmscope(&scope2)
88 * for (; p!=NULL; p=p->scope) {printf("Scope2: %s\n", p->symbol);}
99 * Renamed functions to be consistent with ANTLR
103 * Fixed up zzs_stat()
106 * Made symbol table entry save its hash code for fast comparison
107 * during searching etc...
111 #if defined(__STDC__) || defined(__USE_PROTOS)
121 static Sym
**CurScope
= NULL
;
122 static unsigned size
= 0;
123 static Sym
**table
=NULL
;
124 static char *strings
;
126 static int strsize
= 0;
129 void zzs_init(int sz
,int strs
)
131 void zzs_init(sz
, strs
)
135 if ( sz
<= 0 || strs
<= 0 ) return;
136 table
= (Sym
**) calloc(sz
, sizeof(Sym
*));
139 fprintf(stderr
, "Cannot allocate table of size %d\n", sz
);
142 strings
= (char *) calloc(strs
, sizeof(char));
143 if ( strings
== NULL
)
145 fprintf(stderr
, "Cannot allocate string table of size %d\n", strs
);
159 if ( table
!= NULL
) free( table
);
160 if ( strings
!= NULL
) free( strings
);
164 void zzs_add(char *key
,Sym rec
)
166 void zzs_add(key
, rec
)
171 register unsigned int h
=0;
172 register char *p
=key
;
175 rec
->hash
= h
; /* save hash code for fast comp later */
178 if ( CurScope
!= NULL
) {rec
->scope
= *CurScope
; *CurScope
= rec
;}
179 rec
->next
= table
[h
]; /* Add to doubly-linked list */
181 if ( rec
->next
!= NULL
) (rec
->next
)->prev
= rec
;
183 rec
->head
= &(table
[h
]);
187 Sym
* zzs_get(char *key
)
193 register unsigned int h
=0;
194 register char *p
=key
;
199 for (q
= table
[h
%size
]; q
!= NULL
; q
= q
->next
)
201 if ( q
->hash
== h
) /* do we even have a chance of matching? */
202 if ( strcmp(key
, q
->symbol
) == StrSame
) return( q
);
208 * Unlink p from the symbol table. Hopefully, it's actually in the
211 * If p is not part of a bucket chain of the symbol table, bad things
214 * Will do nothing if all list pointers are NULL
223 if ( p
== NULL
) {fprintf(stderr
, "zzs_del(NULL)\n"); exit(1);}
224 if ( p
->prev
== NULL
) /* Head of list */
226 register Sym
**t
= p
->head
;
228 if ( t
== NULL
) return; /* not part of symbol table */
230 if ( (*t
) != NULL
) (*t
)->prev
= NULL
;
234 (p
->prev
)->next
= p
->next
;
235 if ( p
->next
!= NULL
) (p
->next
)->prev
= p
->prev
;
237 p
->next
= p
->prev
= NULL
; /* not part of symbol table anymore */
242 void zzs_keydel(char *key
)
248 Sym
*p
= zzs_get(key
);
250 if ( p
!= NULL
) zzs_del( p
);
253 /* S c o p e S t u f f */
255 /* Set current scope to 'scope'; return current scope if 'scope' == NULL */
258 Sym
** zzs_scope(Sym
**scope
)
260 Sym
** zzs_scope(scope
)
264 if ( scope
== NULL
) return( CurScope
);
269 /* Remove a scope described by 'scope'. Return pointer to 1st element in scope */
272 Sym
* zzs_rmscope(Sym
**scope
)
274 Sym
* zzs_rmscope(scope
)
275 register Sym
**scope
;
281 if ( scope
== NULL
) return(NULL
);
283 for (; p
!= NULL
; p
=p
->scope
) { zzs_del( p
); }
294 static unsigned short count
[20];
295 unsigned int i
,n
=0,low
=0, hi
=0;
299 for (i
=0; i
<20; i
++) count
[i
] = 0;
300 for (p
=table
; p
<&(table
[size
]); p
++)
302 register Sym
*q
= *p
;
305 if ( q
!= NULL
&& low
==0 ) low
= p
-table
;
307 if ( q
!= NULL
) printf("[%d]", p
-table
);
312 printf(" %s", q
->symbol
);
314 if ( q
== NULL
) printf("\n");
316 if ( len
>=20 ) printf("zzs_stat: count table too small\n");
318 if ( *p
!= NULL
) hi
= p
-table
;
321 printf("Storing %d recs used %d hash positions out of %d\n",
322 n
, size
-count
[0], size
);
323 printf("%f %% utilization\n",
324 ((float)(size
-count
[0]))/((float)size
));
329 avg
+= (((float)(i
*count
[i
]))/((float)n
)) * i
;
330 printf("Buckets of len %d == %d (%f %% of recs)\n",
331 i
, count
[i
], 100.0*((float)(i
*count
[i
]))/((float)n
));
334 printf("Avg bucket length %f\n", avg
);
335 printf("Range of hash function: %d..%d\n", low
, hi
);
339 * Given a string, this function allocates and returns a pointer to a
340 * symbol table record whose "symbol" pointer is reset to a position
341 * in the string table.
345 Sym
* zzs_new(char *text
)
353 if ( (p
= (Sym
*) calloc(1,sizeof(Sym
))) == 0 )
355 fprintf(stderr
,"Out of memory\n");
358 p
->symbol
= zzs_strdup(text
);
363 /* create a new symbol table entry and add it to the symbol table */
366 Sym
* zzs_newadd(char *text
)
368 Sym
* zzs_newadd(text
)
372 Sym
*p
= zzs_new(text
);
373 if ( p
!= NULL
) zzs_add(text
, p
);
377 /* Add a string to the string table and return a pointer to it.
378 * Bump the pointer into the string table to next avail position.
382 char * zzs_strdup(char *s
)
388 register char *start
=strp
;
392 if ( strp
>= &(strings
[strsize
-2]) )
394 fprintf(stderr
, "sym: string table overflow (%d chars)\n", strsize
);