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 *
strfind(char * a)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 *
strstore(char * a)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
strprint(int fd)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
hashfun(void * v)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 *
nalloc(int n)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