python: Added PDM support in scgi-wsgi{,3}.
[ashd.git] / lib / utils.c
1 /*
2     ashd - A Sane HTTP Daemon
3     Copyright (C) 2008  Fredrik Tolf <fredrik@dolda2000.com>
4
5     This program is free software: you can redistribute it and/or modify
6     it under the terms of the GNU General Public License as published by
7     the Free Software Foundation, either version 3 of the License, or
8     (at your option) any later version.
9
10     This program is distributed in the hope that it will be useful,
11     but WITHOUT ANY WARRANTY; without even the implied warranty of
12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13     GNU General Public License for more details.
14
15     You should have received a copy of the GNU General Public License
16     along with this program.  If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <stdlib.h>
20 #include <stdio.h>
21 #include <string.h>
22 #include <ctype.h>
23
24 #ifdef HAVE_CONFIG_H
25 #include <config.h>
26 #endif
27 #include <utils.h>
28
29 static char *base64set = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
30 static int base64rev[] = {
31     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
32     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
33     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, -1, -1, -1, 63,
34     52, 53, 54, 55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1,
35     -1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
36     15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
37     -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
38     41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1,
39     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
40     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
41     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
42     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
43     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
44     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
45     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
46     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
47 };
48
49 void _sizebuf(struct buffer *buf, size_t wanted, size_t el)
50 {
51     size_t n;
52     
53     n = buf->s;
54     if(n == 0)
55         n = 1;
56     while(n < wanted)
57         n <<= 1;
58     if(n <= buf->s)
59         return;
60     if(buf->b != NULL)
61         buf->b = srealloc(buf->b, n * el);
62     else
63         buf->b = smalloc(n * el);
64     buf->s = n;
65 }
66
67 char *decstr(char **p, size_t *len)
68 {
69     char *p2, *ret;
70     
71     for(p2 = *p; (p2 - *p) < *len; p2++) {
72         if(*p2 == 0)
73             break;
74     }
75     if((p2 - *p) == *len)
76         return(NULL);
77     p2++;
78     ret = *p;
79     *len -= p2 - *p;
80     *p = p2;
81     return(ret);
82 }
83
84 char *vsprintf2(char *format, va_list al)
85 {
86     int ret;
87     char *buf;
88     va_list al2;
89     
90     va_copy(al2, al);
91     ret = vsnprintf(NULL, 0, format, al2);
92     va_end(al2);
93     buf = smalloc(ret + 1);
94     va_copy(al2, al);
95     vsnprintf(buf, ret + 1, format, al2);
96     va_end(al2);
97     return(buf);
98 }
99
100 char *sprintf2(char *format, ...)
101 {
102     va_list args;
103     char *buf;
104     
105     va_start(args, format);
106     buf = vsprintf2(format, args);
107     va_end(args);
108     return(buf);
109 }
110
111 char *sprintf3(char *format, ...)
112 {
113     static char *buf = NULL;
114     va_list args;
115     
116     if(buf != NULL)
117         free(buf);
118     va_start(args, format);
119     buf = vsprintf2(format, args);
120     va_end(args);
121     return(buf);
122 }
123
124 off_t atoo(char *n)
125 {
126     return((off_t)strtoll(n, NULL, 10));
127 }
128
129 char **tokenize(char *src)
130 {
131     char **ret;
132     char *p, *p2, *n;
133     int s, q, cl;
134     
135     p = src;
136     s = 0;
137     ret = NULL;
138     while(1) {
139         while(isspace(*p))
140             p++;
141         if(!*p)
142             break;
143         p2 = p;
144         q = 0;
145         while(1) {
146             if(q) {
147                 if(*p == '\"')
148                     q = 0;
149                 else if(*p == '\\')
150                     p++;
151             } else {
152                 if(*p == '\"')
153                     q = 1;
154                 else if(isspace(*p) || !*p)
155                     break;
156                 else if(*p == '\\')
157                     p++;
158             }
159             p++;
160         }
161         cl = p - p2;
162         n = memcpy(malloc(cl + 1), p2, cl);
163         n[cl] = 0;
164         for(p2 = n; *p2; cl--) {
165             if(*p2 == '\\') {
166                 memmove(p2, p2 + 1, cl--);
167                 p2++;
168             } else if(*p2 == '\"') {
169                 memmove(p2, p2 + 1, cl);
170             } else {
171                 p2++;
172             }
173         }
174         ret = realloc(ret, sizeof(char *) * (++s));
175         ret[s - 1] = n;
176     }
177     ret = realloc(ret, sizeof(char *) * (++s));
178     ret[s - 1] = NULL;
179     return(ret);
180 }
181
182 void freeca(char **ca)
183 {
184     char **c;
185     
186     if(ca == NULL)
187         return;
188     for(c = ca; *c; c++)
189         free(*c);
190     free(ca);
191 }
192
193 int calen(char **a)
194 {
195     int i;
196     
197     for(i = 0; *a; a++, i++);
198     return(i);
199 }
200
201 void bvprintf(struct charbuf *buf, char *format, va_list al)
202 {
203     va_list al2;
204     int ret;
205     
206     while(1) {
207         va_copy(al2, al);
208         ret = vsnprintf(buf->b + buf->d, buf->s - buf->d, format, al2);
209         va_end(al2);
210         if(ret < buf->s - buf->d) {
211             buf->d += ret;
212             return;
213         }
214         sizebuf(*buf, buf->d + ret + 1);
215     }
216 }
217
218 void bprintf(struct charbuf *buf, char *format, ...)
219 {
220     va_list args;
221     
222     va_start(args, format);
223     bvprintf(buf, format, args);
224     va_end(args);
225 }
226
227 void replstr(char **p, char *n)
228 {
229     char *tmp;
230     
231     tmp = *p;
232     if(n)
233         *p = sstrdup(n);
234     else
235         *p = NULL;
236     if(tmp)
237         free(tmp);
238 }
239
240 char *base64encode(char *data, size_t datalen)
241 {
242     struct charbuf buf;
243     
244     if(datalen == 0)
245         return(sstrdup(""));
246     bufinit(buf);
247     while(datalen >= 3)
248     {
249         bufadd(buf, base64set[(data[0] & 0xfc) >> 2]);
250         bufadd(buf, base64set[((data[0] & 0x03) << 4) | ((data[1] & 0xf0) >> 4)]);
251         bufadd(buf, base64set[((data[1] & 0x0f) << 2) | ((data[2] & 0xc0) >> 6)]);
252         bufadd(buf, base64set[data[2] & 0x3f]);
253         datalen -= 3;
254         data += 3;
255     }
256     if(datalen == 1)
257     {
258         bufadd(buf, base64set[(data[0] & 0xfc) >> 2]);
259         bufadd(buf, base64set[(data[0] & 0x03) << 4]);
260         bufcat(buf, "==", 2);
261     }
262     if(datalen == 2)
263     {
264         bufadd(buf, base64set[(data[0] & 0xfc) >> 2]);
265         bufadd(buf, base64set[((data[0] & 0x03) << 4) | ((data[1] & 0xf0) >> 4)]);
266         bufadd(buf, base64set[(data[1] & 0x0f) << 2]);
267         bufadd(buf, '=');
268     }
269     bufadd(buf, 0);
270     return(buf.b);
271 }
272
273 char *base64decode(char *data, size_t *datalen)
274 {
275     int b, c;
276     char cur;
277     struct charbuf buf;
278     
279     bufinit(buf);
280     cur = 0;
281     b = 8;
282     for(; *data > 0; data++)
283     {
284         c = (int)(unsigned char)*data;
285         if(c == '=')
286             break;
287         if(c == '\n')
288             continue;
289         if(base64rev[c] == -1)
290         {
291             buffree(buf);
292             return(NULL);
293         }
294         b -= 6;
295         if(b <= 0)
296         {
297             cur |= base64rev[c] >> -b;
298             bufadd(buf, cur);
299             b += 8;
300             cur = 0;
301         }
302         cur |= base64rev[c] << b;
303     }
304     if(datalen != NULL)
305         *datalen = buf.d;
306     bufadd(buf, 0);
307     return(buf.b);
308 }
309
310 static int btheight(struct btree *tree)
311 {
312     if(tree == NULL)
313         return(0);
314     return(tree->h);
315 }
316
317 static void btsetheight(struct btree *tree)
318 {
319     if(tree == NULL)
320         return;
321     tree->h = max(btheight(tree->l), btheight(tree->r)) + 1;
322 }
323
324 static void bbtrl(struct btree **tree);
325
326 static void bbtrr(struct btree **tree)
327 {
328     struct btree *m, *l, *r;
329     
330     if(btheight((*tree)->l->r) > btheight((*tree)->l->l))
331         bbtrl(&(*tree)->l);
332     r = (*tree);
333     l = r->l;
334     m = l->r;
335     r->l = m;
336     btsetheight(r);
337     l->r = r;
338     btsetheight(l);
339     *tree = l;
340 }
341
342 static void bbtrl(struct btree **tree)
343 {
344     struct btree *m, *l, *r;
345     
346     if(btheight((*tree)->r->l) > btheight((*tree)->r->r))
347         bbtrr(&(*tree)->r);
348     l = (*tree);
349     r = l->r;
350     m = r->l;
351     l->r = m;
352     btsetheight(l);
353     r->l = l;
354     btsetheight(r);
355     *tree = r;
356 }
357
358 static int ptrcmp(void *a, void *b)
359 {
360     if(a < b)
361         return(-1);
362     else if(a > b)
363         return(1);
364     return(0);
365 }
366
367 int bbtreedel(struct btree **tree, void *item, int (*cmp)(void *, void *))
368 {
369     int c, r;
370     struct btree *s, **sp, *o;
371     
372     if(cmp == NULL)
373         cmp = ptrcmp;
374     if(*tree == NULL)
375         return(0);
376     if((c = cmp(item, (*tree)->d)) < 0) {
377         r = bbtreedel(&(*tree)->l, item, cmp);
378     } else if(c > 0) {
379         r = bbtreedel(&(*tree)->r, item, cmp);
380     } else {
381         r = 1;
382         o = *tree;
383         if(((*tree)->r != NULL) && ((*tree)->l != NULL)) {
384             sp = &(*tree)->r;
385             s = *sp;
386             while(s->l != NULL) {
387                 sp = &(s->l);
388                 s = *sp;
389             }
390             *sp = (*sp)->r;
391             s->l = (*tree)->l;
392             s->r = (*tree)->r;
393             *tree = s;
394         } else if((*tree)->l != NULL) {
395             *tree = (*tree)->l;
396         } else if((*tree)->r != NULL) {
397             *tree = (*tree)->r;
398         } else {
399             *tree = NULL;
400         }
401         free(o);
402     }
403     if(*tree != NULL) {
404         btsetheight(*tree);
405         if(btheight((*tree)->l) > btheight((*tree)->r) + 1)
406             bbtrr(tree);
407         if(btheight((*tree)->r) > btheight((*tree)->l) + 1)
408             bbtrl(tree);
409     }
410     return(r);
411 }
412
413 void freebtree(struct btree **tree, void (*ffunc)(void *))
414 {
415     if(*tree == NULL)
416         return;
417     freebtree(&(*tree)->l, ffunc);
418     freebtree(&(*tree)->r, ffunc);
419     if(ffunc != NULL)
420         ffunc((*tree)->d);
421     free(*tree);
422     *tree = NULL;
423 }
424
425 int bbtreeput(struct btree **tree, void *item, int (*cmp)(void *, void *))
426 {
427     int c, r;
428     
429     if(cmp == NULL)
430         cmp = ptrcmp;
431     if(*tree == NULL) {
432         *tree = szmalloc(sizeof(**tree));
433         (*tree)->d = item;
434         (*tree)->h = 1;
435         return(1);
436     }
437     if((c = cmp(item, (*tree)->d)) < 0)
438         r = bbtreeput(&(*tree)->l, item, cmp);
439     else if(c > 0)
440         r = bbtreeput(&(*tree)->r, item, cmp);
441     else
442         return(0);
443     btsetheight(*tree);
444     if(btheight((*tree)->l) > btheight((*tree)->r) + 1)
445         bbtrr(tree);
446     if(btheight((*tree)->r) > btheight((*tree)->l) + 1)
447         bbtrl(tree);
448     return(r);
449 }
450
451 void *btreeget(struct btree *tree, void *key, int (*cmp)(void *, void *))
452 {
453     int c;
454     
455     if(cmp == NULL)
456         cmp = ptrcmp;
457     while(1) {
458         if(tree == NULL)
459             return(NULL);
460         c = cmp(key, tree->d);
461         if(c < 0)
462             tree = tree->l;
463         else if(c > 0)
464             tree = tree->r;
465         else
466             return(tree->d);
467     }
468 }