1# ehg@research.bell-labs.com 14Dec1996 2implement Hash; 3 4include "hash.m"; 5 6# from Aho Hopcroft Ullman 7fun1(s:string, n:int):int 8{ 9 h := 0; 10 m := len s; 11 for(i:=0; i<m; i++){ 12 h = 65599*h+s[i]; 13 } 14 return (h & 16r7fffffff) % n; 15} 16 17# from Limbo compiler 18fun2(s:string, n:int):int 19{ 20 h := 0; 21 m := len s; 22 for(i := 0; i < m; i++){ 23 c := s[i]; 24 d := c; 25 c ^= c << 6; 26 h += (c << 11) ^ (c >> 1); 27 h ^= (d << 14) + (d << 7) + (d << 4) + d; 28 } 29 return (h & 16r7fffffff) % n; 30} 31 32new(size: int):ref HashTable 33{ 34 return ref HashTable(array[size] of list of HashNode); 35} 36 37HashTable.find(h: self ref HashTable, key: string): ref HashVal 38{ 39 j := fun1(key,len h.a); 40 for(q := h.a[j]; q!=nil; q = tl q){ 41 if((hd q).key==key) 42 return (hd q).val; 43 } 44 return nil; 45} 46 47HashTable.insert(h: self ref HashTable, key: string, val: HashVal) 48{ 49 j := fun1(key,len h.a); 50 for(q := h.a[j]; q!=nil; q = tl q){ 51 if((hd q).key==key){ 52 p := (hd q).val; 53 p.i = val.i; 54 p.r = val.r; 55 p.s = val.s; 56 return; 57 } 58 } 59 h.a[j] = HashNode(key,ref HashVal(val.i,val.r,val.s)) :: h.a[j]; 60} 61 62HashTable.delete(h:self ref HashTable, key:string) 63{ 64 j := fun1(key,len h.a); 65 dl:list of HashNode; dl = nil; 66 for(q := h.a[j]; q!=nil; q = tl q){ 67 if((hd q).key!=key) 68 dl = (hd q) :: dl; 69 } 70 h.a[j] = dl; 71} 72 73HashTable.all(h:self ref HashTable): list of HashNode 74{ 75 dl:list of HashNode; dl = nil; 76 for(j:=0; j<len h.a; j++) 77 for(q:=h.a[j]; q!=nil; q = tl q) 78 dl = (hd q) :: dl; 79 return dl; 80} 81