|
|
1 # include "dgd.h"
2 # include "hash.h"
3 # include "str.h"
4 # include "array.h"
5 # include "object.h"
6 # include "data.h"
7
8 # define STR_CHUNK 128
9
10 typedef struct _strh_ {
11 hte chain; /* hash table chain */
12 string *str; /* string entry */
13 Uint index; /* building index */
14 struct _strh_ **link; /* next in list */
15 } strh;
16
17 typedef struct _strhchunk_ {
18 struct _strhchunk_ *next; /* next in list */
19 strh sh[STR_CHUNK]; /* chunk of strh entries */
20 } strhchunk;
21
22 static hashtab *ht; /* string merge table */
23 static strh **slink; /* linked list of merged strings */
24 static strhchunk *shlist; /* list of all strh chunks */
25 static int strhchunksz; /* size of current strh chunk */
26
27 /*
28 * NAME: string->init()
29 * DESCRIPTION: initialize string handling
30 */
31 void str_init()
32 {
33 ht = ht_new(STRMERGETABSZ, STRMERGEHASHSZ);
34 strhchunksz = STR_CHUNK;
35 }
36
37 /*
38 * NAME: string->alloc()
39 * DESCRIPTION: Create a new string. The text can be a NULL pointer, in which
40 * case it must be filled in later.
41 */
42 string *str_alloc(text, len)
43 char *text;
44 register long len;
45 {
46 register string *s;
47 string dummy;
48
49 /* allocate string struct & text in one block */
50 s = (string *) ALLOC(char, dummy.text - (char *) &dummy + 1 + len);
51 if (text != (char *) NULL && len > 0) {
52 memcpy(s->text, text, (unsigned int) len);
53 }
54 s->text[s->len = len] = '\0';
55 s->ref = 0;
56 s->primary = (strref *) NULL;
57
58 return s;
59 }
60
61 /*
62 * NAME: string->new()
63 * DESCRIPTION: create a new string with size check
64 */
65 string *str_new(text, len)
66 char *text;
67 long len;
68 {
69 if (len > (unsigned long) MAX_STRLEN) {
70 error("String too long");
71 }
72 return str_alloc(text, len);
73 }
74
75 /*
76 * NAME: string->del()
77 * DESCRIPTION: remove a reference from a string. If there are none left, the
78 * string is removed.
79 */
80 void str_del(s)
81 register string *s;
82 {
83 if (--(s->ref) == 0) {
84 FREE(s);
85 }
86 }
87
88 /*
89 * NAME: string->put()
90 * DESCRIPTION: put a string in the string merge table
91 */
92 Uint str_put(str, n)
93 register string *str;
94 register Uint n;
95 {
96 register strh **h;
97
98 h = (strh **) ht_lookup(ht, str->text, FALSE);
99 for (;;) {
100 /*
101 * The hasher doesn't handle \0 in strings, and so may not have
102 * found the proper string. Follow the hash table chain until
103 * the end is reached, or until a match is found using str_cmp().
104 */
105 if (*h == (strh *) NULL) {
106 register strh *s;
107
108 /*
109 * Not in the hash table. Make a new entry.
110 */
111 if (strhchunksz == STR_CHUNK) {
112 register strhchunk *l;
113
114 l = ALLOC(strhchunk, 1);
115 l->next = shlist;
116 shlist = l;
117 strhchunksz = 0;
118 }
119 s = *h = &shlist->sh[strhchunksz++];
120 s->chain.next = (hte *) NULL;
121 s->chain.name = str->text;
122 s->str = str;
123 s->index = n;
124 s->link = slink;
125 slink = h;
126
127 return n;
128 } else if (str_cmp(str, (*h)->str) == 0) {
129 /* already in the hash table */
130 return (*h)->index;
131 }
132 h = (strh **) &(*h)->chain.next;
133 }
134 }
135
136 /*
137 * NAME: string->clear()
138 * DESCRIPTION: clear the string merge table. All entries are in a separate
139 * linked list so this is simple. Note that this routine makes
140 * assumptions about how the hash table is constructed.
141 */
142 void str_clear()
143 {
144 register strh **h;
145 register strhchunk *l;
146
147 for (h = slink; h != (strh **) NULL; ) {
148 register strh *f;
149
150 f = *h;
151 *h = (strh *) NULL;
152 h = f->link;
153 }
154 slink = (strh **) NULL;
155
156 for (l = shlist; l != (strhchunk *) NULL; ) {
157 register strhchunk *f;
158
159 f = l;
160 l = l->next;
161 FREE(f);
162 }
163 shlist = (strhchunk *) NULL;
164 strhchunksz = STR_CHUNK;
165 }
166
167
168 /*
169 * NAME: string->cmp()
170 * DESCRIPTION: compare two strings
171 */
172 int str_cmp(s1, s2)
173 string *s1, *s2;
174 {
175 if (s1 == s2) {
176 return 0;
177 } else {
178 register ssizet len;
179 register char *p, *q;
180 long cmplen;
181 int cmp;
182
183 cmplen = (long) s1->len - s2->len;
184 if (cmplen > 0) {
185 /* s1 longer */
186 cmplen = 1;
187 len = s2->len;
188 } else {
189 /* s2 longer or equally long */
190 if (cmplen < 0) {
191 cmplen = -1;
192 }
193 len = s1->len;
194 }
195 for (p = s1->text, q = s2->text; len > 0 && *p == *q; p++, q++, --len) ;
196 cmp = UCHAR(*p) - UCHAR(*q);
197 return (cmp != 0) ? cmp : cmplen;
198 }
199 }
200
201 /*
202 * NAME: string->add()
203 * DESCRIPTION: add two strings
204 */
205 string *str_add(s1, s2)
206 register string *s1, *s2;
207 {
208 register string *s;
209
210 s = str_new((char *) NULL, (long) s1->len + s2->len);
211 memcpy(s->text, s1->text, s1->len);
212 memcpy(s->text + s1->len, s2->text, s2->len);
213
214 return s;
215 }
216
217 /*
218 * NAME: string->index()
219 * DESCRIPTION: index a string
220 */
221 ssizet str_index(s, l)
222 string *s;
223 register long l;
224 {
225 if (l < 0 || l >= (long) s->len) {
226 error("String index out of range");
227 }
228
229 return l;
230 }
231
232 /*
233 * NAME: string->ckrange()
234 * DESCRIPTION: check a string subrange
235 */
236 void str_ckrange(s, l1, l2)
237 string *s;
238 register long l1, l2;
239 {
240 if (l1 < 0 || l1 > l2 + 1 || l2 >= (long) s->len) {
241 error("Invalid string range");
242 }
243 }
244
245 /*
246 * NAME: string->range()
247 * DESCRIPTION: return a subrange of a string
248 */
249 string *str_range(s, l1, l2)
250 register string *s;
251 register long l1, l2;
252 {
253 if (l1 < 0 || l1 > l2 + 1 || l2 >= (long) s->len) {
254 error("Invalid string range");
255 }
256
257 return str_new(s->text + l1, l2 - l1 + 1);
258 }
259
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.