[ashd.git] / lib / utils.c

/*
    ashd - A Sane HTTP Daemon
    Copyright (C) 2008  Fredrik Tolf <fredrik@dolda2000.com>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <utils.h>

static char *base64set = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
static int base64rev[] = {
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, -1, -1, -1, 63,
    52, 53, 54, 55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1,
    -1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
    15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
    -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
    41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
};

void _sizebuf(struct buffer *buf, size_t wanted, size_t el)
{
    size_t n;
    
    n = buf->s;
    if(n == 0)
	n = 1;
    while(n < wanted)
	n <<= 1;
    if(n <= buf->s)
	return;
    if(buf->b != NULL)
	buf->b = srealloc(buf->b, n * el);
    else
	buf->b = smalloc(n * el);
    buf->s = n;
}

char *decstr(char **p, size_t *len)
{
    char *p2, *ret;
    
    for(p2 = *p; (p2 - *p) < *len; p2++) {
	if(*p2 == 0)
	    break;
    }
    if((p2 - *p) == *len)
	return(NULL);
    p2++;
    ret = *p;
    *len -= p2 - *p;
    *p = p2;
    return(ret);
}

char *vsprintf2(char *format, va_list al)
{
    int ret;
    char *buf;
    va_list al2;
    
    va_copy(al2, al);
    ret = vsnprintf(NULL, 0, format, al2);
    va_end(al2);
    buf = smalloc(ret + 1);
    va_copy(al2, al);
    vsnprintf(buf, ret + 1, format, al2);
    va_end(al2);
    return(buf);
}

char *sprintf2(char *format, ...)
{
    va_list args;
    char *buf;
    
    va_start(args, format);
    buf = vsprintf2(format, args);
    va_end(args);
    return(buf);
}

char *sprintf3(char *format, ...)
{
    static char *buf = NULL;
    va_list args;
    
    if(buf != NULL)
	free(buf);
    va_start(args, format);
    buf = vsprintf2(format, args);
    va_end(args);
    return(buf);
}

off_t atoo(char *n)
{
    return((off_t)strtoll(n, NULL, 10));
}

char **tokenize(char *src)
{
    char **ret;
    char *p, *p2, *n;
    int s, q, cl;
    
    p = src;
    s = 0;
    ret = NULL;
    while(1) {
	while(isspace(*p))
	    p++;
	if(!*p)
	    break;
	p2 = p;
	q = 0;
	while(1) {
	    if(q) {
		if(*p == '\"')
		    q = 0;
		else if(*p == '\\')
		    p++;
	    } else {
		if(*p == '\"')
		    q = 1;
		else if(isspace(*p) || !*p)
		    break;
		else if(*p == '\\')
		    p++;
	    }
	    p++;
	}
	cl = p - p2;
	n = memcpy(malloc(cl + 1), p2, cl);
	n[cl] = 0;
	for(p2 = n; *p2; cl--) {
	    if(*p2 == '\\') {
		memmove(p2, p2 + 1, cl--);
		p2++;
	    } else if(*p2 == '\"') {
		memmove(p2, p2 + 1, cl);
	    } else {
		p2++;
	    }
	}
	ret = realloc(ret, sizeof(char *) * (++s));
	ret[s - 1] = n;
    }
    ret = realloc(ret, sizeof(char *) * (++s));
    ret[s - 1] = NULL;
    return(ret);
}

void freeca(char **ca)
{
    char **c;
    
    if(ca == NULL)
	return;
    for(c = ca; *c; c++)
	free(*c);
    free(ca);
}

int calen(char **a)
{
    int i;
    
    for(i = 0; *a; a++, i++);
    return(i);
}

void bvprintf(struct charbuf *buf, char *format, va_list al)
{
    va_list al2;
    int ret;
    
    while(1) {
	va_copy(al2, al);
	ret = vsnprintf(buf->b + buf->d, buf->s - buf->d, format, al2);
	va_end(al2);
	if(ret < buf->s - buf->d) {
	    buf->d += ret;
	    return;
	}
	sizebuf(*buf, buf->d + ret + 1);
    }
}

void bprintf(struct charbuf *buf, char *format, ...)
{
    va_list args;
    
    va_start(args, format);
    bvprintf(buf, format, args);
    va_end(args);
}

void replstr(char **p, char *n)
{
    char *tmp;
    
    tmp = *p;
    if(n)
	*p = sstrdup(n);
    else
	*p = NULL;
    if(tmp)
	free(tmp);
}

char *base64encode(char *data, size_t datalen)
{
    struct charbuf buf;
    
    if(datalen == 0)
	return(sstrdup(""));
    bufinit(buf);
    while(datalen >= 3)
    {
	bufadd(buf, base64set[(data[0] & 0xfc) >> 2]);
	bufadd(buf, base64set[((data[0] & 0x03) << 4) | ((data[1] & 0xf0) >> 4)]);
	bufadd(buf, base64set[((data[1] & 0x0f) << 2) | ((data[2] & 0xc0) >> 6)]);
	bufadd(buf, base64set[data[2] & 0x3f]);
	datalen -= 3;
	data += 3;
    }
    if(datalen == 1)
    {
	bufadd(buf, base64set[(data[0] & 0xfc) >> 2]);
	bufadd(buf, base64set[(data[0] & 0x03) << 4]);
	bufcat(buf, "==", 2);
    }
    if(datalen == 2)
    {
	bufadd(buf, base64set[(data[0] & 0xfc) >> 2]);
	bufadd(buf, base64set[((data[0] & 0x03) << 4) | ((data[1] & 0xf0) >> 4)]);
	bufadd(buf, base64set[(data[1] & 0x0f) << 2]);
	bufadd(buf, '=');
    }
    bufadd(buf, 0);
    return(buf.b);
}

char *base64decode(char *data, size_t *datalen)
{
    int b, c;
    char cur;
    struct charbuf buf;
    
    bufinit(buf);
    cur = 0;
    b = 8;
    for(; *data > 0; data++)
    {
	c = (int)(unsigned char)*data;
	if(c == '=')
	    break;
	if(c == '\n')
	    continue;
	if(base64rev[c] == -1)
	{
	    buffree(buf);
	    return(NULL);
	}
	b -= 6;
	if(b <= 0)
	{
	    cur |= base64rev[c] >> -b;
	    bufadd(buf, cur);
	    b += 8;
	    cur = 0;
	}
	cur |= base64rev[c] << b;
    }
    if(datalen != NULL)
	*datalen = buf.d;
    bufadd(buf, 0);
    return(buf.b);
}

int hexdigit(char c)
{
    if((c >= '0') && (c <= '9'))      return(c - '0');
    else if((c >= 'a') && (c <= 'f')) return(c - 'a' + 10);
    else if((c >= 'A') && (c <= 'F')) return(c - 'A' + 10);
    return(-1);
}

static int btheight(struct btree *tree)
{
    if(tree == NULL)
	return(0);
    return(tree->h);
}

static void btsetheight(struct btree *tree)
{
    if(tree == NULL)
	return;
    tree->h = max(btheight(tree->l), btheight(tree->r)) + 1;
}

static void bbtrl(struct btree **tree);

static void bbtrr(struct btree **tree)
{
    struct btree *m, *l, *r;
    
    if(btheight((*tree)->l->r) > btheight((*tree)->l->l))
	bbtrl(&(*tree)->l);
    r = (*tree);
    l = r->l;
    m = l->r;
    r->l = m;
    btsetheight(r);
    l->r = r;
    btsetheight(l);
    *tree = l;
}

static void bbtrl(struct btree **tree)
{
    struct btree *m, *l, *r;
    
    if(btheight((*tree)->r->l) > btheight((*tree)->r->r))
	bbtrr(&(*tree)->r);
    l = (*tree);
    r = l->r;
    m = r->l;
    l->r = m;
    btsetheight(l);
    r->l = l;
    btsetheight(r);
    *tree = r;
}

static int ptrcmp(void *a, void *b)
{
    if(a < b)
	return(-1);
    else if(a > b)
	return(1);
    return(0);
}

int bbtreedel(struct btree **tree, void *item, int (*cmp)(void *, void *))
{
    int c, r;
    struct btree *s, **sp, *o;
    
    if(cmp == NULL)
	cmp = ptrcmp;
    if(*tree == NULL)
	return(0);
    if((c = cmp(item, (*tree)->d)) < 0) {
	r = bbtreedel(&(*tree)->l, item, cmp);
    } else if(c > 0) {
	r = bbtreedel(&(*tree)->r, item, cmp);
    } else {
	r = 1;
	o = *tree;
	if(((*tree)->r != NULL) && ((*tree)->l != NULL)) {
	    sp = &(*tree)->r;
	    s = *sp;
	    while(s->l != NULL) {
		sp = &(s->l);
		s = *sp;
	    }
	    *sp = (*sp)->r;
	    s->l = (*tree)->l;
	    s->r = (*tree)->r;
	    *tree = s;
	} else if((*tree)->l != NULL) {
	    *tree = (*tree)->l;
	} else if((*tree)->r != NULL) {
	    *tree = (*tree)->r;
	} else {
	    *tree = NULL;
	}
	free(o);
    }
    if(*tree != NULL) {
	btsetheight(*tree);
	if(btheight((*tree)->l) > btheight((*tree)->r) + 1)
	    bbtrr(tree);
	if(btheight((*tree)->r) > btheight((*tree)->l) + 1)
	    bbtrl(tree);
    }
    return(r);
}

void freebtree(struct btree **tree, void (*ffunc)(void *))
{
    if(*tree == NULL)
	return;
    freebtree(&(*tree)->l, ffunc);
    freebtree(&(*tree)->r, ffunc);
    if(ffunc != NULL)
	ffunc((*tree)->d);
    free(*tree);
    *tree = NULL;
}

int bbtreeput(struct btree **tree, void *item, int (*cmp)(void *, void *))
{
    int c, r;
    
    if(cmp == NULL)
	cmp = ptrcmp;
    if(*tree == NULL) {
	*tree = szmalloc(sizeof(**tree));
	(*tree)->d = item;
	(*tree)->h = 1;
	return(1);
    }
    if((c = cmp(item, (*tree)->d)) < 0)
	r = bbtreeput(&(*tree)->l, item, cmp);
    else if(c > 0)
	r = bbtreeput(&(*tree)->r, item, cmp);
    else
	return(0);
    btsetheight(*tree);
    if(btheight((*tree)->l) > btheight((*tree)->r) + 1)
	bbtrr(tree);
    if(btheight((*tree)->r) > btheight((*tree)->l) + 1)
	bbtrl(tree);
    return(r);
}

void *btreeget(struct btree *tree, void *key, int (*cmp)(void *, void *))
{
    int c;
    
    if(cmp == NULL)
	cmp = ptrcmp;
    while(1) {
	if(tree == NULL)
	    return(NULL);
	c = cmp(key, tree->d);
	if(c < 0)
	    tree = tree->l;
	else if(c > 0)
	    tree = tree->r;
	else
	    return(tree->d);
    }
}
Commit	Line	Data
f0bbedf7 FT	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>
90f6e953	20	#include <stdio.h>
f2b26d44 FT	21	#include <string.h>
f2b26d44 FT	22	#include <ctype.h>
f0bbedf7	23
ddf99192 FT	24	#ifdef HAVE_CONFIG_H
	25	#include <config.h>
	26	#endif
f0bbedf7 FT	27	#include <utils.h>
f0bbedf7 FT	28
be6e50bf FT	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
f0bbedf7 FT	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
90f6e953 FT	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	}
9aee4cbc FT	123
	124	off_t atoo(char *n)
	125	{
	126	return((off_t)strtoll(n, NULL, 10));
	127	}
f2b26d44 FT	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
06c1a718 FT	186	if(ca == NULL)
06c1a718 FT	187	return;
f2b26d44 FT	188	for(c = ca; *c; c++)
	189	free(*c);
	190	free(ca);
	191	}
d1bd343c FT	192
	193	int calen(char **a)
	194	{
	195	int i;
	196
	197	for(i = 0; *a; a++, i++);
	198	return(i);
	199	}
d422fdfd FT	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	}
5fc1bf9f FT	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	}
be6e50bf FT	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	}
59c94590	309
4dc7f716 FT	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
59c94590 FT	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	}