123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105 |
- #include "all.h"
- #define STRHASH 509 /* prime */
- static Strnode * stab[STRHASH];
- static long hashfun(void*);
- static Strnode* nalloc(int);
- char *
- strfind(char *a)
- {
- Strnode **bin, *x, *xp;
- bin = &stab[hashfun(a) % STRHASH];
- for(xp=0, x=*bin; x; xp=x, x=x->next)
- if(x->str[0] == a[0] && strcmp(x->str, a) == 0)
- break;
- if(x == 0)
- return 0;
- if(xp){
- xp->next = x->next;
- x->next = *bin;
- *bin = x;
- }
- return x->str;
- }
- char *
- strstore(char *a)
- {
- Strnode **bin, *x, *xp;
- int n;
- bin = &stab[hashfun(a) % STRHASH];
- for(xp=0, x=*bin; x; xp=x, x=x->next)
- if(x->str[0] == a[0] && strcmp(x->str, a) == 0)
- break;
- if(x == 0){
- n = strlen(a)+1;
- x = nalloc(n);
- memmove(x->str, a, n);
- x->next = *bin;
- *bin = x;
- }else if(xp){
- xp->next = x->next;
- x->next = *bin;
- *bin = x;
- }
- return x->str;
- }
- void
- strprint(int fd)
- {
- Strnode **bin, *x;
- for(bin = stab; bin < stab+STRHASH; bin++)
- for(x=*bin; x; x=x->next)
- fprint(fd, "%ld %s\n", bin-stab, x->str);
- }
- static long
- hashfun(void *v)
- {
- ulong a = 0, b;
- uchar *s = v;
- while(*s){
- a = (a << 4) + *s++;
- if(b = a&0xf0000000){ /* assign = */
- a ^= b >> 24;
- a ^= b;
- }
- }
- return a;
- }
- #define STRSIZE 1000
- static Strnode *
- nalloc(int n) /* get permanent storage for Strnode */
- {
- static char *curstp;
- static int nchleft;
- int k;
- char *p;
- if(n < 4)
- n = 4;
- else if(k = n&3) /* assign = */
- n += 4-k;
- n += sizeof(Strnode)-4;
- if(n > nchleft){
- nchleft = STRSIZE;
- while(nchleft < n)
- nchleft *= 2;
- if((curstp = malloc(nchleft)) == 0)
- panic("malloc(%d) failed in nalloc\n", nchleft);
- }
- p = curstp;
- curstp += n;
- nchleft -= n;
- return (Strnode*)p;
- }
|