1 /*
2 Copyright (c) 2003-2006 by Juliusz Chroboczek
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 THE SOFTWARE.
21 */
22
23 #include "polipo.h"
24
25 /* Atoms are interned, read-only reference-counted strings.
26
27 Interned means that equality of atoms is equivalent to structural
28 equality -- you don't need to strcmp, you just compare the AtomPtrs.
29 This property is used throughout Polipo, e.g. to speed up the HTTP
30 parser.
31
32 Polipo's atoms may contain NUL bytes -- you can use internAtomN to
33 store any random binary data within an atom. However, Polipo always
34 terminates your data, so if you store textual data in an atom, you
35 may use the result of atomString as though it were a (read-only)
36 C string.
37
38 */
39
40 static AtomPtr *atomHashTable;
41 int used_atoms;
42
43 void
initAtoms()44 initAtoms()
45 {
46 atomHashTable = calloc((1 << LOG2_ATOM_HASH_TABLE_SIZE),
47 sizeof(AtomPtr));
48
49 if(atomHashTable == NULL) {
50 do_log(L_ERROR, "Couldn't allocate atom hash table.\n");
51 exit(1);
52 }
53 used_atoms = 0;
54 }
55
56 AtomPtr
internAtomN(const char * string,int n)57 internAtomN(const char *string, int n)
58 {
59 AtomPtr atom;
60 int h;
61
62 if(n < 0 || n >= (1 << (8 * sizeof(unsigned short))))
63 return NULL;
64
65 h = hash(0, string, n, LOG2_ATOM_HASH_TABLE_SIZE);
66 atom = atomHashTable[h];
67 while(atom) {
68 if(atom->length == n &&
69 (n == 0 || memcmp(atom->string, string, n) == 0))
70 break;
71 atom = atom->next;
72 }
73
74 if(!atom) {
75 atom = malloc(sizeof(AtomRec) - 1 + n + 1);
76 if(atom == NULL) {
77 return NULL;
78 }
79 atom->refcount = 0;
80 atom->length = n;
81 /* Atoms are used both for binary data and strings. To make
82 their use as strings more convenient, atoms are always
83 NUL-terminated. */
84 memcpy(atom->string, string, n);
85 atom->string[n] = '\0';
86 atom->next = atomHashTable[h];
87 atomHashTable[h] = atom;
88 used_atoms++;
89 }
90 do_log(D_ATOM_REFCOUNT, "A 0x%lx %d++\n",
91 (unsigned long)atom, atom->refcount);
92 atom->refcount++;
93 return atom;
94 }
95
96 AtomPtr
internAtom(const char * string)97 internAtom(const char *string)
98 {
99 return internAtomN(string, strlen(string));
100 }
101
102 AtomPtr
atomCat(AtomPtr atom,const char * string)103 atomCat(AtomPtr atom, const char *string)
104 {
105 char buf[128];
106 char *s = buf;
107 AtomPtr newAtom;
108 int n = strlen(string);
109 if(atom->length + n > 128) {
110 s = malloc(atom->length + n + 1);
111 if(s == NULL)
112 return NULL;
113 }
114 memcpy(s, atom->string, atom->length);
115 memcpy(s + atom->length, string, n);
116 newAtom = internAtomN(s, atom->length + n);
117 if(s != buf) free(s);
118 return newAtom;
119 }
120
121 int
atomSplit(AtomPtr atom,char c,AtomPtr * return1,AtomPtr * return2)122 atomSplit(AtomPtr atom, char c, AtomPtr *return1, AtomPtr *return2)
123 {
124 char *p;
125 AtomPtr atom1, atom2;
126 p = memchr(atom->string, c, atom->length);
127 if(p == NULL)
128 return 0;
129 atom1 = internAtomN(atom->string, p - atom->string);
130 if(atom1 == NULL)
131 return -ENOMEM;
132 atom2 = internAtomN(p + 1, atom->length - (p + 1 - atom->string));
133 if(atom2 == NULL) {
134 releaseAtom(atom1);
135 return -ENOMEM;
136 }
137 *return1 = atom1;
138 *return2 = atom2;
139 return 1;
140 }
141
142 AtomPtr
internAtomLowerN(const char * string,int n)143 internAtomLowerN(const char *string, int n)
144 {
145 char *s;
146 char buf[100];
147 AtomPtr atom;
148
149 if(n < 0 || n >= 50000)
150 return NULL;
151
152 if(n < 100) {
153 s = buf;
154 } else {
155 s = malloc(n);
156 if(s == NULL)
157 return NULL;
158 }
159
160 lwrcpy(s, string, n);
161 atom = internAtomN(s, n);
162 if(s != buf) free(s);
163 return atom;
164 }
165
166 AtomPtr
retainAtom(AtomPtr atom)167 retainAtom(AtomPtr atom)
168 {
169 if(atom == NULL)
170 return NULL;
171
172 do_log(D_ATOM_REFCOUNT, "A 0x%lx %d++\n",
173 (unsigned long)atom, atom->refcount);
174 assert(atom->refcount >= 1 && atom->refcount < LARGE_ATOM_REFCOUNT);
175 atom->refcount++;
176 return atom;
177 }
178
179 void
releaseAtom(AtomPtr atom)180 releaseAtom(AtomPtr atom)
181 {
182 if(atom == NULL)
183 return;
184
185 do_log(D_ATOM_REFCOUNT, "A 0x%lx %d--\n",
186 (unsigned long)atom, atom->refcount);
187 assert(atom->refcount >= 1 && atom->refcount < LARGE_ATOM_REFCOUNT);
188
189 atom->refcount--;
190
191 if(atom->refcount == 0) {
192 int h = hash(0, atom->string, atom->length, LOG2_ATOM_HASH_TABLE_SIZE);
193 assert(atomHashTable[h] != NULL);
194
195 if(atom == atomHashTable[h]) {
196 atomHashTable[h] = atom->next;
197 free(atom);
198 } else {
199 AtomPtr previous = atomHashTable[h];
200 while(previous->next) {
201 if(previous->next == atom)
202 break;
203 previous = previous->next;
204 }
205 assert(previous->next != NULL);
206 previous->next = atom->next;
207 free(atom);
208 }
209 used_atoms--;
210 }
211 }
212
213 AtomPtr
internAtomF(const char * format,...)214 internAtomF(const char *format, ...)
215 {
216 char *s;
217 char buf[150];
218 int n;
219 va_list args;
220 AtomPtr atom = NULL;
221
222 va_start(args, format);
223 n = vsnprintf(buf, 150, format, args);
224 va_end(args);
225 if(n >= 0 && n < 150) {
226 atom = internAtomN(buf, n);
227 } else {
228 va_start(args, format);
229 s = vsprintf_a(format, args);
230 va_end(args);
231 if(s != NULL) {
232 atom = internAtom(s);
233 free(s);
234 }
235 }
236 return atom;
237 }
238
239 static AtomPtr
internAtomErrorV(int e,const char * f,va_list args)240 internAtomErrorV(int e, const char *f, va_list args)
241 {
242
243 char *es = pstrerror(e);
244 AtomPtr atom;
245 char *s1, *s2;
246 int n, rc;
247 va_list args_copy;
248
249 if(f) {
250 va_copy(args_copy, args);
251 s1 = vsprintf_a(f, args_copy);
252 va_end(args_copy);
253 if(s1 == NULL)
254 return NULL;
255 n = strlen(s1);
256 } else {
257 s1 = NULL;
258 n = 0;
259 }
260
261 s2 = malloc(n + 70);
262 if(s2 == NULL) {
263 free(s1);
264 return NULL;
265 }
266 if(s1) {
267 strcpy(s2, s1);
268 free(s1);
269 }
270
271 rc = snprintf(s2 + n, 69, f ? ": %s" : "%s", es);
272 if(rc < 0 || rc >= 69) {
273 free(s2);
274 return NULL;
275 }
276
277 atom = internAtomN(s2, n + rc);
278 free(s2);
279 return atom;
280 }
281
282 AtomPtr
internAtomError(int e,const char * f,...)283 internAtomError(int e, const char *f, ...)
284 {
285 AtomPtr atom;
286 va_list args;
287 va_start(args, f);
288 atom = internAtomErrorV(e, f, args);
289 va_end(args);
290 return atom;
291 }
292
293 char *
atomString(AtomPtr atom)294 atomString(AtomPtr atom)
295 {
296 if(atom)
297 return atom->string;
298 else
299 return "(null)";
300 }
301
302 AtomListPtr
makeAtomList(AtomPtr * atoms,int n)303 makeAtomList(AtomPtr *atoms, int n)
304 {
305 AtomListPtr list;
306 list = malloc(sizeof(AtomListRec));
307 if(list == NULL) return NULL;
308 list->length = 0;
309 list->size = 0;
310 list->list = NULL;
311 if(n > 0) {
312 int i;
313 list->list = malloc(n * sizeof(AtomPtr));
314 if(list->list == NULL) {
315 free(list);
316 return NULL;
317 }
318 list->size = n;
319 for(i = 0; i < n; i++)
320 list->list[i] = atoms[i];
321 list->length = n;
322 }
323 return list;
324 }
325
326 void
destroyAtomList(AtomListPtr list)327 destroyAtomList(AtomListPtr list)
328 {
329 int i;
330 if(list->list) {
331 for(i = 0; i < list->length; i++)
332 releaseAtom(list->list[i]);
333 list->length = 0;
334 free(list->list);
335 list->list = NULL;
336 list->size = 0;
337 }
338 assert(list->size == 0);
339 free(list);
340 }
341
342 int
atomListMember(AtomPtr atom,AtomListPtr list)343 atomListMember(AtomPtr atom, AtomListPtr list)
344 {
345 int i;
346 for(i = 0; i < list->length; i++) {
347 if(atom == list->list[i])
348 return 1;
349 }
350 return 0;
351 }
352
353 void
atomListCons(AtomPtr atom,AtomListPtr list)354 atomListCons(AtomPtr atom, AtomListPtr list)
355 {
356 if(list->list == NULL) {
357 assert(list->size == 0);
358 list->list = malloc(5 * sizeof(AtomPtr));
359 if(list->list == NULL) {
360 do_log(L_ERROR, "Couldn't allocate AtomList\n");
361 return;
362 }
363 list->size = 5;
364 }
365 if(list->size <= list->length) {
366 AtomPtr *new_list;
367 int n = (2 * list->length + 1);
368 new_list = realloc(list->list, n * sizeof(AtomPtr));
369 if(new_list == NULL) {
370 do_log(L_ERROR, "Couldn't realloc AtomList\n");
371 return;
372 }
373 list->list = new_list;
374 list->size = n;
375 }
376 list->list[list->length] = atom;
377 list->length++;
378 }
379
380