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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
/*
* The functions in this file maintain a hash table of strings and manage
* string buffers.
*/
#include "../h/gsupport.h"
/*
* Prototype for static function.
*/
static int streq (int len, char *s1, char *s2);
/*
* Entry in string table.
*/
struct str_entry {
char *s; /* string */
int length; /* length of string */
struct str_entry *next;
};
#define SBufSize 1024 /* initial size of a string buffer */
#define StrTblSz 149 /* size of string hash table */
static struct str_entry **str_tbl = NULL; /* string hash table */
/*
* init_str - initialize string hash table.
*/
void init_str()
{
int h;
if (str_tbl == NULL) {
str_tbl = alloc(StrTblSz * sizeof(struct str_entry *));
for (h = 0; h < StrTblSz; ++h)
str_tbl[h] = NULL;
}
}
/*
* free_stbl - free string table.
*/
void free_stbl()
{
struct str_entry *se, *se1;
int h;
for (h = 0; h < StrTblSz; ++h)
for (se = str_tbl[h]; se != NULL; se = se1) {
se1 = se->next;
free((char *)se);
}
free((char *)str_tbl);
str_tbl = NULL;
}
/*
* init_sbuf - initialize a new sbuf struct, allocating an initial buffer.
*/
void init_sbuf(sbuf)
struct str_buf *sbuf;
{
sbuf->size = SBufSize;
sbuf->frag_lst = alloc(sizeof(struct str_buf_frag) + (SBufSize - 1));
sbuf->frag_lst->next = NULL;
sbuf->strtimage = sbuf->frag_lst->s;
sbuf->endimage = sbuf->strtimage;
sbuf->end = sbuf->strtimage + SBufSize;
}
/*
* clear_sbuf - free string buffer storage.
*/
void clear_sbuf(sbuf)
struct str_buf *sbuf;
{
struct str_buf_frag *sbf, *sbf1;
for (sbf = sbuf->frag_lst; sbf != NULL; sbf = sbf1) {
sbf1 = sbf->next;
free((char *)sbf);
}
sbuf->frag_lst = NULL;
sbuf->strtimage = NULL;
sbuf->endimage = NULL;
sbuf->end = NULL;
}
/*
* new_sbuf - allocate a new buffer for a sbuf struct, copying the partially
* created string from the end of full buffer to the new one.
*/
void new_sbuf(sbuf)
struct str_buf *sbuf;
{
struct str_buf_frag *sbf;
char *s1, *s2;
/*
* The new buffer is larger than the old one to insure that any
* size string can be buffered.
*/
sbuf->size *= 2;
s1 = sbuf->strtimage;
sbf = alloc(sizeof(struct str_buf_frag) + (sbuf->size - 1));
sbf->next = sbuf->frag_lst;
sbuf->frag_lst = sbf;
sbuf->strtimage = sbf->s;
s2 = sbuf->strtimage;
while (s1 < sbuf->endimage)
*s2++ = *s1++;
sbuf->endimage = s2;
sbuf->end = sbuf->strtimage + sbuf->size;
}
/*
* spec_str - install a special string (null terminated) in the string table.
*/
char *spec_str(s)
char *s;
{
struct str_entry *se;
register char *s1;
register int l;
register int h;
h = 0;
l = 1;
for (s1 = s; *s1 != '\0'; ++s1) {
h += *s1 & 0377;
++l;
}
h %= StrTblSz;
for (se = str_tbl[h]; se != NULL; se = se->next)
if (l == se->length && streq(l, s, se->s))
return se->s;
se = NewStruct(str_entry);
se->s = s;
se->length = l;
se->next = str_tbl[h];
str_tbl[h] = se;
return s;
}
/*
* str_install - find out if the string at the end of the buffer is in
* the string table. If not, put it there. Return a pointer to the
* string in the table.
*/
char *str_install(sbuf)
struct str_buf *sbuf;
{
int h;
struct str_entry *se;
register char *s;
register char *e;
int l;
AppChar(*sbuf, '\0'); /* null terminate the buffered copy of the string */
s = sbuf->strtimage;
e = sbuf->endimage;
/*
* Compute hash value.
*/
h = 0;
while (s < e)
h += *s++ & 0377;
h %= StrTblSz;
s = sbuf->strtimage;
l = e - s;
for (se = str_tbl[h]; se != NULL; se = se->next)
if (l == se->length && streq(l, s, se->s)) {
/*
* A copy of the string is already in the table. Delete the copy
* in the buffer.
*/
sbuf->endimage = s;
return se->s;
}
/*
* The string is not in the table. Add the copy from the buffer to the
* table.
*/
se = NewStruct(str_entry);
se->s = s;
se->length = l;
sbuf->strtimage = e;
se->next = str_tbl[h];
str_tbl[h] = se;
return se->s;
}
/*
* streq - compare s1 with s2 for len bytes, and return 1 for equal,
* 0 for not equal.
*/
static int streq(len, s1, s2)
register int len;
register char *s1, *s2;
{
while (len--)
if (*s1++ != *s2++)
return 0;
return 1;
}
|
