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