1 #include "all.h" 2 3 #define STRHASH 509 /* prime */ 4 5 static Strnode * stab[STRHASH]; 6 7 static long hashfun(void*); 8 static Strnode* nalloc(int); 9 10 char * 11 strfind(char *a) 12 { 13 Strnode **bin, *x, *xp; 14 15 bin = &stab[hashfun(a) % STRHASH]; 16 for(xp=0, x=*bin; x; xp=x, x=x->next) 17 if(x->str[0] == a[0] && strcmp(x->str, a) == 0) 18 break; 19 if(x == 0) 20 return 0; 21 if(xp){ 22 xp->next = x->next; 23 x->next = *bin; 24 *bin = x; 25 } 26 return x->str; 27 } 28 29 char * 30 strstore(char *a) 31 { 32 Strnode **bin, *x, *xp; 33 int n; 34 35 bin = &stab[hashfun(a) % STRHASH]; 36 for(xp=0, x=*bin; x; xp=x, x=x->next) 37 if(x->str[0] == a[0] && strcmp(x->str, a) == 0) 38 break; 39 if(x == 0){ 40 n = strlen(a)+1; 41 x = nalloc(n); 42 memmove(x->str, a, n); 43 x->next = *bin; 44 *bin = x; 45 }else if(xp){ 46 xp->next = x->next; 47 x->next = *bin; 48 *bin = x; 49 } 50 return x->str; 51 } 52 53 void 54 strprint(int fd) 55 { 56 Strnode **bin, *x; 57 58 for(bin = stab; bin < stab+STRHASH; bin++) 59 for(x=*bin; x; x=x->next) 60 fprint(fd, "%ld %s\n", bin-stab, x->str); 61 } 62 63 static long 64 hashfun(void *v) 65 { 66 ulong a = 0, b; 67 uchar *s = v; 68 69 while(*s){ 70 a = (a << 4) + *s++; 71 if(b = a&0xf0000000){ /* assign = */ 72 a ^= b >> 24; 73 a ^= b; 74 } 75 } 76 return a; 77 } 78 79 #define STRSIZE 1000 80 81 static Strnode * 82 nalloc(int n) /* get permanent storage for Strnode */ 83 { 84 static char *curstp; 85 static int nchleft; 86 int k; 87 char *p; 88 89 if(n < 4) 90 n = 4; 91 else if(k = n&3) /* assign = */ 92 n += 4-k; 93 n += sizeof(Strnode)-4; 94 if(n > nchleft){ 95 nchleft = STRSIZE; 96 while(nchleft < n) 97 nchleft *= 2; 98 if((curstp = malloc(nchleft)) == 0) 99 panic("malloc(%d) failed in nalloc\n", nchleft); 100 } 101 p = curstp; 102 curstp += n; 103 nchleft -= n; 104 return (Strnode*)p; 105 } 106