xref: /inferno-os/appl/lib/tables.b (revision 37da2899f40661e3e9631e497da8dc59b971cbd0) 
1implement Tables;
2include "tables.m";
3
4Table[T].new(nslots: int, nilval: T): ref Table[T]
5{
6	if(nslots == 0)
7		nslots = 13;
8	return ref Table[T](array[nslots] of list of (int, T), nilval);
9}
10
11Table[T].add(t: self ref Table[T], id: int, x: T): int
12{
13	slot := id % len t.items;
14	for(q := t.items[slot]; q != nil; q = tl q)
15		if((hd q).t0 == id)
16			return 0;
17	t.items[slot] = (id, x) :: t.items[slot];
18	return 1;
19}
20
21Table[T].del(t: self ref Table[T], id: int): int
22{
23	slot := id % len t.items;
24
25	p: list of (int, T);
26	r := 0;
27	for(q := t.items[slot]; q != nil; q = tl q){
28		if((hd q).t0 == id){
29			p = joinip(p, tl q);
30			r = 1;
31			break;
32		}
33		p = hd q :: p;
34	}
35	t.items[slot] = p;
36	return r;
37}
38
39Table[T].find(t: self ref Table[T], id: int): T
40{
41	for(p := t.items[id % len t.items]; p != nil; p = tl p)
42		if((hd p).t0 == id)
43			return (hd p).t1;
44	return t.nilval;
45}
46
47Strhash[T].new(nslots: int, nilval: T): ref Strhash[T]
48{
49	if(nslots == 0)
50		nslots = 13;
51	return ref Strhash[T](array[nslots] of list of (string, T), nilval);
52}
53
54Strhash[T].add(t: self ref Strhash, id: string, x: T)
55{
56	slot := hash(id, len t.items);
57	t.items[slot] = (id, x) :: t.items[slot];
58}
59
60Strhash[T].del(t: self ref Strhash, id: string)
61{
62	slot := hash(id, len t.items);
63
64	p: list of (string, T);
65	for(q := t.items[slot]; q != nil; q = tl q)
66		if((hd q).t0 != id)
67			p = hd q :: p;
68	t.items[slot] = p;
69}
70
71Strhash[T].find(t: self ref Strhash, id: string): T
72{
73	for(p := t.items[hash(id, len t.items)]; p != nil; p = tl p)
74		if((hd p).t0 == id)
75			return (hd p).t1;
76	return t.nilval;
77}
78
79hash(s: string, n: int): int
80{
81	h := 0;
82	m := len s;
83	for(i:=0; i<m; i++){
84		h = 65599*h+s[i];
85	}
86	return (h & 16r7fffffff) % n;
87}
88
89rev[T](x: list of T): list of T
90{
91	l: list of T;
92	for(; x != nil; x = tl x)
93		l = hd x :: l;
94	return l;
95}
96
97# join x to y, leaving result in arbitrary order.
98joinip[T](x, y: list of (int, T)): list of (int, T)
99{
100	if(len x > len y)
101		(x, y) = (y, x);
102	for(; x != nil; x = tl x)
103		y = hd x :: y;
104	return y;
105}
106