Subversion Repositories planix.SVN

#include <u.h>
#include <libc.h>
#include <bio.h>
#include "hash.h"

/***
 * String hash tables.
 */

Stringtab *tfree;

Stringtab*
taballoc(void)
{
        static Stringtab *t;
        static uint nt;

        if(tfree){
                Stringtab *tt = tfree;
                tfree = tt->link;
                return tt;
        }

        if(nt == 0){
                t = malloc(64000*sizeof(Stringtab));
                if(t == 0)
                        sysfatal("out of memory");
                nt = 64000;
        }
        nt--;
        return t++;
}

void
tabfree(Stringtab *tt)
{
        tt->link = tfree;
        tfree = tt;
}

char*
xstrdup(char *s, int len)
{
        char *r;
        static char *t;
        static int nt;

        if(nt < len){
                t = malloc(512*1024+len);
                if(t == 0)
                        sysfatal("out of memory");
                nt = 512*1024;
        }
        r = t;
        t += len;
        nt -= len;
        memmove(r, s, len);
        return r;
}

static uint
hash(char *s, int n)
{
        uint h;
        uchar *p, *ep;
        h = 0;
        for(p=(uchar*)s, ep=p+n; p<ep; p++)
                h = h*37 + *p;
        return h;
}

static void
rehash(Hash *hh)
{
        int h;
        Stringtab *s;

        if(hh->nstab == 0)
                hh->nstab = 1024;
        else
                hh->nstab = hh->ntab*2;

        free(hh->stab);
        hh->stab = mallocz(hh->nstab*sizeof(Stringtab*), 1);
        if(hh->stab == nil)
                sysfatal("out of memory");

        for(s=hh->all; s; s=s->link){
                h = hash(s->str, s->n) % hh->nstab;
                s->hash = hh->stab[h];
                hh->stab[h] = s;
        }
}

Stringtab*
findstab(Hash *hh, char *str, int n, int create)
{
        uint h;
        Stringtab *tab, **l;

        if(hh->nstab == 0)
                rehash(hh);

        h = hash(str, n) % hh->nstab;
        for(tab=hh->stab[h], l=&hh->stab[h]; tab; l=&tab->hash, tab=tab->hash)
                if(n==tab->n && memcmp(str, tab->str, n) == 0){
                        *l = tab->hash;
                        tab->hash = hh->stab[h];
                        hh->stab[h] = tab;
                        return tab;
                }

        if(!create)
                return nil;

        hh->sorted = 0;
        tab = taballoc();
        tab->str = xstrdup(str, n);
        tab->hash = hh->stab[h];
        tab->link = hh->all;
        hh->all = tab;
        tab->n = n;
        tab->count = 0;
        tab->date = 0;
        hh->stab[h] = tab;

        hh->ntab++;
        if(hh->ntab > 2*hh->nstab && !(hh->ntab&(hh->ntab-1)))
                rehash(hh);
        return tab;
}

int
scmp(Stringtab *a, Stringtab *b)
{
        int n, x;

        if(a == 0)
                return 1;
        if(b == 0)
                return -1;
        n = a->n;
        if(n > b->n)
                n = b->n;
        x = memcmp(a->str, b->str, n);
        if(x != 0)
                return x;
        if(a->n < b->n)
                return -1;
        if(a->n > b->n)
                return 1;
        return 0;       /* shouldn't happen */
}

Stringtab*
merge(Stringtab *a, Stringtab *b)
{
        Stringtab *s, **l;

        l = &s;
        while(a || b){
                if(scmp(a, b) < 0){
                        *l = a;
                        l = &a->link;
                        a = a->link;
                }else{
                        *l = b;
                        l = &b->link;
                        b = b->link;
                }
        }
        *l = 0;
        return s;
}

Stringtab*
mergesort(Stringtab *s)
{
        Stringtab *a, *b;
        int delay;

        if(s == nil)
                return nil;
        if(s->link == nil)
                return s;

        a = b = s;
        delay = 1;
        while(a && b){
                if(delay)       /* easy way to handle 2-element list */
                        delay = 0;
                else
                        a = a->link;
                if(b = b->link)
                        b = b->link;
        }

        b = a->link;
        a->link = nil;

        a = mergesort(s);
        b = mergesort(b);

        return merge(a, b);
}

Stringtab*
sortstab(Hash *hh)
{
        if(!hh->sorted){
                hh->all = mergesort(hh->all);
                hh->sorted = 1;
        }
        return hh->all;
}

int
Bwritehash(Biobuf *b, Hash *hh)
{
        Stringtab *s;
        int now;

        now = time(0);
        s = sortstab(hh);
        Bprint(b, "# hash table\n");
        for(; s; s=s->link){
                if(s->count <= 0)
                        continue;
                /*
                 * Entries that haven't been updated in thirty days get tossed.
                 */
                if(s->date+30*86400 < now)
                        continue;
                Bwrite(b, s->str, s->n);
                Bprint(b, "\t%d %d\n", s->count, s->date);
        }
        if(Bflush(b) == Beof)
                return -1;
        return 0;
}

void
Breadhash(Biobuf *b, Hash *hh, int scale)
{
        char *s;
        char *t;
        int n;
        int date;
        Stringtab *st;

        s = Brdstr(b, '\n', 1);
        if(s == nil)
                return;
        if(strcmp(s, "# hash table") != 0)
                sysfatal("bad hash table format");

        while(s = Brdline(b, '\n')){
                s[Blinelen(b)-1] = 0;
                t = strrchr(s, '\t');
                if(t == nil)
                        sysfatal("bad hash table format");
                *t++ = '\0';
                if(*t < '0' || *t > '9')
                        sysfatal("bad hash table format");
                n = strtol(t, &t, 10);
                date = time(0);
                if(*t != 0){
                        if(*t == ' '){
                                t++;
                                date = strtol(t, &t, 10);
                        }
                        if(*t != 0)
                                sysfatal("bad hash table format");
                }
                st = findstab(hh, s, strlen(s), 1);
                if(date > st->date)
                        st->date = date;
                st->count += n*scale;
        }
}

void
freehash(Hash *h)
{
        Stringtab *s, *next;

        for(s=h->all; s; s=next){
                next = s->link;
                tabfree(s);
        }
        free(h->stab);
        free(h);
}

Biobuf*
Bopenlock(char *file, int mode)
{
        int i;
        Biobuf *b;
        char err[ERRMAX];

        b = nil;
        for(i=0; i<120; i++){
                if((b = Bopen(file, mode)) != nil)
                        break;
                rerrstr(err, sizeof err);
                if(strstr(err, "file is locked")==nil && strstr(err, "exclusive lock")==nil)
                        break;
                sleep(1000);
        }
        return b;
}