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 }