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