1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
# Copyright(c) 1986 Association of Universities for Research in Astronomy Inc.
include "symtab.h"
# STFIND -- Search the symbol table for the named key and return a pointer to
# the symstruct or NULL. This is the main table lookup procedure. If the
# thread is empty NULL is returned after only a hash function call. If there
# is only one element on a thread (common for well conditioned symbol tables)
# the expense is essentialy two traversals of the key string plus procedure
# overhead (pointer calculations, etc.).
pointer procedure stfind (stp, key)
pointer stp # symbol table descriptor
char key[ARB] # symbol name
long sum
char first_char
int head, ip, thread
pointer el, cp, stab, sbuf
begin
# When a symbol is entered in the table a flag is set in the ST_ASCII
# array to flag that the symbol table contains at least one key
# beginning with that character. If the flag is not set we can thus
# determine very quickly that the symbol is not present. This is
# important for applications such as mapping identifiers for macro
# expansion, where most macros have upper case keys but most program
# identifiers have lower case keys. (Subtle note: since the first
# element of ST_ASCII is for ascii value 0=EOS, the following also
# serves to detect null keys).
if (ST_ASCII(stp,key[1]) == 0)
return (NULL)
# Hash the key onto a thread in the index.
sum = 0
do ip = 1, MAX_HASHCHARS {
if (key[ip] == EOS)
break
sum = sum + (sum + key[ip])
}
thread = mod (sum, ST_INDEXLEN(stp))
head = Memi[ST_INDEX(stp)+thread]
# If thread is not empty search down it for the named key and return
# the symbol pointer if found. Note that the value of the E_NEXTHASH
# pointer is given as an integer offset to facilitate reallocation
# upon overflow.
if (head != NULL) {
first_char = key[1]
sbuf = ST_SBUFP(stp)
stab = ST_STABP(stp)
for (el=stab+head; el > stab; el=stab+E_NEXTHASH(el)) {
cp = sbuf + E_KEY(el)
if (Memc[cp] != first_char)
next
# Compare target key to symbol key.
do ip = 1, MAX_SZKEY {
if (key[ip] != Memc[cp])
break
if (key[ip] == EOS)
return (E_USERFIELDS(el)) # found key
cp = cp + 1
}
}
}
return (NULL)
end
|
