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 int hexdigit(char c)
 311 {
 312     if((c >= '0') && (c <= '9'))      return(c - '0');
 313     else if((c >= 'a') && (c <= 'f')) return(c - 'a' + 10);
 314     else if((c >= 'A') && (c <= 'F')) return(c - 'A' + 10);
 315     return(-1);
 316 }
 317
 318 static int btheight(struct btree *tree)
 319 {
 320     if(tree == NULL)
 321         return(0);
 322     return(tree->h);
 323 }
 324
 325 static void btsetheight(struct btree *tree)
 326 {
 327     if(tree == NULL)
 328         return;
 329     tree->h = max(btheight(tree->l), btheight(tree->r)) + 1;
 330 }
 331
 332 static void bbtrl(struct btree **tree);
 333
 334 static void bbtrr(struct btree **tree)
 335 {
 336     struct btree *m, *l, *r;
 337
 338     if(btheight((*tree)->l->r) > btheight((*tree)->l->l))
 339         bbtrl(&(*tree)->l);
 340     r = (*tree);
 341     l = r->l;
 342     m = l->r;
 343     r->l = m;
 344     btsetheight(r);
 345     l->r = r;
 346     btsetheight(l);
 347     *tree = l;
 348 }
 349
 350 static void bbtrl(struct btree **tree)
 351 {
 352     struct btree *m, *l, *r;
 353
 354     if(btheight((*tree)->r->l) > btheight((*tree)->r->r))
 355         bbtrr(&(*tree)->r);
 356     l = (*tree);
 357     r = l->r;
 358     m = r->l;
 359     l->r = m;
 360     btsetheight(l);
 361     r->l = l;
 362     btsetheight(r);
 363     *tree = r;
 364 }
 365
 366 static int ptrcmp(void *a, void *b)
 367 {
 368     if(a < b)
 369         return(-1);
 370     else if(a > b)
 371         return(1);
 372     return(0);
 373 }
 374
 375 int bbtreedel(struct btree **tree, void *item, int (*cmp)(void *, void *))
 376 {
 377     int c, r;
 378     struct btree *s, **sp, *o;
 379
 380     if(cmp == NULL)
 381         cmp = ptrcmp;
 382     if(*tree == NULL)
 383         return(0);
 384     if((c = cmp(item, (*tree)->d)) < 0) {
 385         r = bbtreedel(&(*tree)->l, item, cmp);
 386     } else if(c > 0) {
 387         r = bbtreedel(&(*tree)->r, item, cmp);
 388     } else {
 389         r = 1;
 390         o = *tree;
 391         if(((*tree)->r != NULL) && ((*tree)->l != NULL)) {
 392             sp = &(*tree)->r;
 393             s = *sp;
 394             while(s->l != NULL) {
 395                 sp = &(s->l);
 396                 s = *sp;
 397             }
 398             *sp = (*sp)->r;
 399             s->l = (*tree)->l;
 400             s->r = (*tree)->r;
 401             *tree = s;
 402         } else if((*tree)->l != NULL) {
 403             *tree = (*tree)->l;
 404         } else if((*tree)->r != NULL) {
 405             *tree = (*tree)->r;
 406         } else {
 407             *tree = NULL;
 408         }
 409         free(o);
 410     }
 411     if(*tree != NULL) {
 412         btsetheight(*tree);
 413         if(btheight((*tree)->l) > btheight((*tree)->r) + 1)
 414             bbtrr(tree);
 415         if(btheight((*tree)->r) > btheight((*tree)->l) + 1)
 416             bbtrl(tree);
 417     }
 418     return(r);
 419 }
 420
 421 void freebtree(struct btree **tree, void (*ffunc)(void *))
 422 {
 423     if(*tree == NULL)
 424         return;
 425     freebtree(&(*tree)->l, ffunc);
 426     freebtree(&(*tree)->r, ffunc);
 427     if(ffunc != NULL)
 428         ffunc((*tree)->d);
 429     free(*tree);
 430     *tree = NULL;
 431 }
 432
 433 int bbtreeput(struct btree **tree, void *item, int (*cmp)(void *, void *))
 434 {
 435     int c, r;
 436
 437     if(cmp == NULL)
 438         cmp = ptrcmp;
 439     if(*tree == NULL) {
 440         *tree = szmalloc(sizeof(**tree));
 441         (*tree)->d = item;
 442         (*tree)->h = 1;
 443         return(1);
 444     }
 445     if((c = cmp(item, (*tree)->d)) < 0)
 446         r = bbtreeput(&(*tree)->l, item, cmp);
 447     else if(c > 0)
 448         r = bbtreeput(&(*tree)->r, item, cmp);
 449     else
 450         return(0);
 451     btsetheight(*tree);
 452     if(btheight((*tree)->l) > btheight((*tree)->r) + 1)
 453         bbtrr(tree);
 454     if(btheight((*tree)->r) > btheight((*tree)->l) + 1)
 455         bbtrl(tree);
 456     return(r);
 457 }
 458
 459 void *btreeget(struct btree *tree, void *key, int (*cmp)(void *, void *))
 460 {
 461     int c;
 462
 463     if(cmp == NULL)
 464         cmp = ptrcmp;
 465     while(1) {
 466         if(tree == NULL)
 467             return(NULL);
 468         c = cmp(key, tree->d);
 469         if(c < 0)
 470             tree = tree->l;
 471         else if(c > 0)
 472             tree = tree->r;
 473         else
 474             return(tree->d);
 475     }
 476 }