X-Git-Url: http://dolda2000.com/gitweb/?a=blobdiff_plain;f=common%2Futils.c;h=5db9c58922e32d05dbda4e0b57e1b0b9a6fa8889;hb=HEAD;hp=bb297818a036e9fccc73df8dc3ef8512b820eea0;hpb=fe8c6c8e4cb0ce993faa4a972024e30d04977b15;p=doldaconnect.git

diff --git a/common/utils.c b/common/utils.c
index bb29781..5db9c58 100644
--- a/common/utils.c
+++ b/common/utils.c
@@ -1,6 +1,6 @@
 /*
  *  Dolda Connect - Modular multiuser Direct Connect-style client
- *  Copyright (C) 2004 Fredrik Tolf (fredrik@dolda2000.com)
+ *  Copyright (C) 2004 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
@@ -36,6 +36,15 @@
 #include <utils.h>
 #include <log.h>
 
+struct treeiter {
+    struct {
+	struct btree *n;
+	int s;
+    } *st;
+    size_t stsize;
+    int sp;
+};
+
 static char *base64set = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
 static int base64rev[] = {
     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
@@ -408,44 +417,19 @@ double ntime(void)
     return((double)tv.tv_sec + ((double)tv.tv_usec / 1000000.0));
 }
 
-int wcsexists(wchar_t *h, wchar_t *n)
+wchar_t *wcslower(wchar_t *wcs)
 {
-    int i, o, nl, hl;
-    wchar_t *ln, *lh;
+    wchar_t *p;
     
-    ln = alloca(sizeof(*ln) * (nl = wcslen(n)));
-    for(i = 0; i < nl; i++)
-	ln[i] = towlower(n[i]);
-    lh = alloca(sizeof(*lh) * (hl = wcslen(h)));
-    if(nl > hl)
-	return(0);
-    for(i = 0; i < nl; i++)
-	lh[i] = towlower(h[i]);
-    i = 0;
-    while(1)
-    {
-	for(o = 0; o < nl; o++)
-	{
-	    if(lh[i + o] != ln[o])
-		break;
-	}
-	if(o == nl)
-	    return(1);
-	if(i == hl - nl)
-	    return(0);
-	lh[i + nl] = towlower(h[i + nl]);
-	i++;
-    }
+    for(p = wcs; *p != L'\0'; p++)
+	*p = towlower(*p);
+    return(wcs);
 }
 
 #ifndef HAVE_WCSCASECMP
 int wcscasecmp(const wchar_t *s1, const wchar_t *s2)
 {
-    while(towlower(*s1) == towlower(*s2))
-    {
-	if(*s1 == L'\0')
-	    return(0);
-    }
+    for(; (towlower(*s1) == towlower(*s2)) && (*s1 != L'\0'); s1++, s2++);
     return(towlower(*s1) - towlower(*s2));
 }
 #endif
@@ -479,41 +463,39 @@ char *hexencode(char *data, size_t datalen)
 
 char *hexdecode(char *data, size_t *len)
 {
-    char *buf, this;
+    char *buf, this, bit;
     size_t bufsize, bufdata;
     
     buf = NULL;
     bufsize = bufdata = 0;
-    for(; *data; data++)
+    for(bit = 4, this = 0; *data; data++)
     {
 	if((*data >= 'A') && (*data <= 'F'))
 	{
-	    this = (this & 0x0F) | ((*data - 'A' + 10) << 4);
+	    this |= (this & 0x0F) | ((*data - 'A' + 10) << bit);
+	} else if((*data >= 'a') && (*data <= 'f')) {
+	    this |= (this & 0x0F) | ((*data - 'a' + 10) << bit);
 	} else if((*data >= '0') && (*data <= '9')) {
-	    this = (this & 0x0F) | ((*data - '0') << 4);
+	    this |= (this & 0x0F) | ((*data - '0') << bit);
+	} else if(*data == '\n') {
+	    continue;
 	} else {
 	    if(buf != NULL)
 		free(buf);
 	    return(NULL);
 	}
-	data++;
-	if(!*data)
-	{
-	    if(buf != NULL)
-		free(buf);
-	    return(NULL);
-	}
-	if((*data >= 'A') && (*data <= 'F'))
-	{
-	    this = (this & 0xF0) | (*data - 'A' + 10);
-	} else if((*data >= '0') && (*data <= '9')) {
-	    this = (this & 0xF0) | (*data - '0');
+	if(bit == 4) {
+	    bit = 0;
 	} else {
-	    if(buf != NULL)
-		free(buf);
-	    return(NULL);
+	    bit = 4;
+	    addtobuf(buf, this);
+	    this = 0;
 	}
-	addtobuf(buf, this);
+    }
+    if(bit != 4) {
+	if(buf != NULL)
+	    free(buf);
+	return(NULL);
     }
     addtobuf(buf, 0);
     if(len != NULL)
@@ -807,6 +789,51 @@ char *findfile(char *name, char *homedir, int filldef)
     }
 }
 
+struct strpair *newstrpair(char *key, char *val, struct strpair **list)
+{
+    struct strpair *pair;
+    
+    pair = smalloc(sizeof(*pair));
+    memset(pair, 0, sizeof(*pair));
+    if(key != NULL)
+	pair->key = sstrdup(key);
+    if(val != NULL)
+	pair->val = sstrdup(val);
+    if(list != NULL)
+    {
+	pair->next = *list;
+	*list = pair;
+    }
+    return(pair);
+}
+
+void freestrpair(struct strpair *pair, struct strpair **list)
+{
+    struct strpair *cur;
+    
+    for(cur = *list; cur != NULL; list = &(cur->next), cur = cur->next)
+    {
+	if(cur == pair)
+	{
+	    *list = cur->next;
+	    break;
+	}
+    }
+    free(pair->key);
+    free(pair->val);
+    free(pair);
+}
+
+char *spfind(struct strpair *list, char *key)
+{
+    for(; list != NULL; list = list->next)
+    {
+	if(!strcmp(list->key, key))
+	    return(list->val);
+    }
+    return(NULL);
+}
+
 struct wcspair *newwcspair(wchar_t *key, wchar_t *val, struct wcspair **list)
 {
     struct wcspair *pair;
@@ -817,10 +844,8 @@ struct wcspair *newwcspair(wchar_t *key, wchar_t *val, struct wcspair **list)
 	pair->key = swcsdup(key);
     if(val != NULL)
 	pair->val = swcsdup(val);
-    if(list == NULL)
+    if(list != NULL)
     {
-	pair->next = NULL;
-    } else {
 	pair->next = *list;
 	*list = pair;
     }
@@ -853,3 +878,232 @@ wchar_t *wpfind(struct wcspair *list, wchar_t *key)
     }
     return(NULL);
 }
+
+static int btheight(struct btree *tree)
+{
+    if(tree == NULL)
+	return(0);
+    return(tree->h);
+}
+
+static void btsetheight(struct btree *tree)
+{
+    int lh, rh;
+    
+    if(tree == NULL)
+	return;
+    lh = btheight(tree->l);
+    rh = btheight(tree->r);
+    tree->h = ((lh > rh)?lh:rh) + 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;
+}
+
+int bbtreedel(struct btree **tree, void *item, int (*cmp)(void *, void *))
+{
+    int c, r;
+    struct btree *s, **sp, *o;
+
+    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 = NULL;
+	    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);
+}
+
+int bbtreeput(struct btree **tree, void *item, int (*cmp)(void *, void *))
+{
+    int c, r;
+    
+    if(*tree == NULL) {
+	*tree = smalloc(sizeof(**tree));
+	(*tree)->l = (*tree)->r = NULL;
+	(*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;
+    
+    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);
+    }
+}
+
+void btreefree(struct btree *tree)
+{
+    if(tree == NULL)
+	return;
+    btreefree(tree->l);
+    btreefree(tree->r);
+    free(tree);
+}
+
+static void *btreenext(void **iterp)
+{
+    struct treeiter *iter;
+    int s;
+    struct btree *n;
+    
+    if((iter = *iterp) == NULL)
+	return(NULL);
+    while(1) {
+	s = iter->st[iter->sp].s;
+	n = iter->st[iter->sp].n;
+	if(s == 0) {
+	    iter->st[iter->sp].s = 1;
+	    if(n->l != NULL) {
+		iter->sp++;
+		sizebuf2(iter->st, iter->sp + 1, 1);
+		iter->st[iter->sp].s = 0;
+		iter->st[iter->sp].n = n->l;
+	    }
+	} else if(s == 1) {
+	    iter->st[iter->sp].s = 2;
+	    return(iter->st[iter->sp].n->d);
+	} else if(s == 2) {
+	    iter->st[iter->sp].s = 3;
+	    if(n->r != NULL) {
+		iter->sp++;
+		sizebuf2(iter->st, iter->sp + 1, 1);
+		iter->st[iter->sp].s = 0;
+		iter->st[iter->sp].n = n->r;
+	    }
+	} else {
+	    iter->sp--;
+	    if(iter->sp < 0) {
+		free(iter->st);
+		free(iter);
+		*iterp = NULL;
+		return(NULL);
+	    }
+	}
+    }
+}
+
+static void *btreefirst(struct btree *tree, void **iterp)
+{
+    struct treeiter *iter;
+    
+    if(tree == NULL) {
+	*iterp = NULL;
+	return(NULL);
+    }
+    *iterp = iter = memset(smalloc(sizeof(*iter)), 0, sizeof(*iter));
+    sizebuf2(iter->st, 1, 1);
+    iter->st[0].n = tree;
+    iter->st[0].s = 0;
+    return(btreenext(iterp));
+}
+
+static void btreestop(void **iterp)
+{
+    struct treeiter *iter;
+    
+    if((iter = *iterp) == NULL)
+	return;
+    if(iter->st != NULL)
+	free(iter->st);
+    free(iter);
+    *iterp = NULL;
+}
+
+void *btreeiter(struct btree *tree)
+{
+    static void *iter = NULL;
+    
+    if(tree == NULL) {
+	return(btreenext(&iter));
+    } else {
+	if(iter != NULL)
+	    btreestop(&iter);
+	return(btreefirst(tree, &iter));
+    }
+}