1 | |
---|
2 | #include <containers/list.hfa> |
---|
3 | |
---|
4 | #include <exception.hfa> |
---|
5 | TRIVIAL_EXCEPTION(ht_fill_limit_crossed); |
---|
6 | |
---|
7 | |
---|
8 | |
---|
9 | void defaultResumptionHandler(ht_fill_limit_crossed &) { |
---|
10 | printf("default resumption ht_fill_limit_crossed\n"); |
---|
11 | } |
---|
12 | |
---|
13 | void defaultTerminationHandler(ht_fill_limit_crossed &) = void; |
---|
14 | |
---|
15 | |
---|
16 | trait has_hash( K ) { |
---|
17 | size_t hash(K); |
---|
18 | int ?==?( K, K ); |
---|
19 | }; |
---|
20 | |
---|
21 | trait hkey( K, tN & | has_hash(K) ) { |
---|
22 | K key(tN &); |
---|
23 | }; |
---|
24 | |
---|
25 | forall( K, tN &, tE & | $dlistable(tN, tE) | hkey(K, tN) ) { |
---|
26 | |
---|
27 | struct hashtable { |
---|
28 | |
---|
29 | size_t n_buckets; |
---|
30 | dlist(tN, tE) *buckets; |
---|
31 | |
---|
32 | size_t item_count; |
---|
33 | float ff_next_warn_up; |
---|
34 | |
---|
35 | void (*defaultResumptionHandler) (ht_fill_limit_crossed &); |
---|
36 | }; |
---|
37 | |
---|
38 | void ?{}( hashtable(K, tN, tE) & this ) = void; |
---|
39 | } |
---|
40 | |
---|
41 | forall( K, tN &, tE & | $dlistable(tN, tE) | hkey(K, tN) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) { |
---|
42 | |
---|
43 | void ?{}( hashtable(K, tN, tE) & this, size_t n_buckets, dlist(tN, tE) *buckets ) { |
---|
44 | |
---|
45 | this.n_buckets = n_buckets; |
---|
46 | this.buckets = buckets; |
---|
47 | |
---|
48 | this.item_count = 0; |
---|
49 | this.ff_next_warn_up = 0.5; |
---|
50 | |
---|
51 | this.defaultResumptionHandler = defaultResumptionHandler; |
---|
52 | |
---|
53 | for ( i; n_buckets ) { |
---|
54 | ?{}( this.buckets[i] ); |
---|
55 | } |
---|
56 | } |
---|
57 | } |
---|
58 | |
---|
59 | forall( K, tN &, tE & | $dlistable(tN, tE) | hkey(K, tN) ) { |
---|
60 | |
---|
61 | float fill_frac( hashtable(K, tN, tE) & this ) with(this) { |
---|
62 | return ((float)item_count) / n_buckets; |
---|
63 | } |
---|
64 | |
---|
65 | size_t bucket_of( hashtable(K, tN, tE) & this, K k ) { |
---|
66 | return hash(k) % this.n_buckets; |
---|
67 | } |
---|
68 | |
---|
69 | tE & get( hashtable(K, tN, tE) & this, K k ) with (this) { |
---|
70 | |
---|
71 | dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ]; |
---|
72 | |
---|
73 | for ( tN * item = & $tempcv_e2n(bucket`first); item != 0p; item = & $tempcv_e2n((*item)`next) ) { |
---|
74 | if ( key(*item) == k ) { |
---|
75 | return *item; |
---|
76 | } |
---|
77 | } |
---|
78 | |
---|
79 | return *0p; |
---|
80 | } |
---|
81 | |
---|
82 | void check_ff_warning( hashtable(K, tN, tE) & this ) with (this) { |
---|
83 | if (fill_frac(this) > ff_next_warn_up) { |
---|
84 | throwResume (ht_fill_limit_crossed){}; |
---|
85 | ff_next_warn_up *= 2; |
---|
86 | } |
---|
87 | } |
---|
88 | |
---|
89 | void put( hashtable(K, tN, tE) & this, tE & v ) with (this) { |
---|
90 | |
---|
91 | check_ff_warning(this); |
---|
92 | |
---|
93 | K k = key( $tempcv_e2n(v) ); |
---|
94 | dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ]; |
---|
95 | |
---|
96 | for ( tN * item = & $tempcv_e2n(bucket`first); item != 0p; item = & $tempcv_e2n((*item)`next) ) { |
---|
97 | if ( key(*item) == k ) { |
---|
98 | remove(*item); |
---|
99 | break; |
---|
100 | } |
---|
101 | } |
---|
102 | |
---|
103 | insert_first(bucket, v); |
---|
104 | this.item_count ++; |
---|
105 | } |
---|
106 | |
---|
107 | } |
---|
108 | |
---|
109 | // tactical usage: |
---|
110 | // HASHTABLE_STATIC(int, item_by_prority, item, n, ht) |
---|
111 | // |
---|
112 | // intended equivalent: |
---|
113 | // hashtable_static(int, item_by_prority, item, Z(n)) ht; |
---|
114 | #define HASHTABLE_STATIC(K, tN, tE, n_buckets, obj) \ |
---|
115 | struct __hashtable_static_ ## obj { \ |
---|
116 | inline hashtable(K, tN, tE); \ |
---|
117 | dlist(tN, tE) $items[n_buckets]; \ |
---|
118 | }; \ |
---|
119 | void ?{}( __hashtable_static_ ## obj & this ) { \ |
---|
120 | ((hashtable(K, tN, tE) &)this){ n_buckets, this.$items }; \ |
---|
121 | } \ |
---|
122 | __hashtable_static_ ## obj obj; |
---|
123 | |
---|
124 | |
---|
125 | |
---|
126 | trait heaped(T &) { |
---|
127 | T * alloc( size_t ); |
---|
128 | void free( void * ); |
---|
129 | }; |
---|
130 | |
---|
131 | void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) { |
---|
132 | printf("dynamic limit crossed\n"); |
---|
133 | } |
---|
134 | |
---|
135 | forall( K, tN &, tE & | $dlistable(tN, tE) | hkey(K, tN) | heaped( dlist(tN, tE) ) ) { |
---|
136 | |
---|
137 | struct hashtable_dynamic { |
---|
138 | inline hashtable(K, tN, tE); |
---|
139 | }; |
---|
140 | void ?{}( hashtable_dynamic(K, tN, tE) & this, size_t n_buckets ) { |
---|
141 | void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler; |
---|
142 | dlist(tN, tE) *buckets = alloc(n_buckets); |
---|
143 | ((hashtable(K, tN, tE) &)this){ n_buckets, buckets }; |
---|
144 | } |
---|
145 | void ^?{}( hashtable_dynamic(K, tN, tE) & this ) { |
---|
146 | free(this.buckets); |
---|
147 | } |
---|
148 | } |
---|
149 | |
---|
150 | |
---|
151 | |
---|
152 | |
---|
153 | struct request { |
---|
154 | |
---|
155 | unsigned int src_id; |
---|
156 | unsigned int tgt_id; |
---|
157 | |
---|
158 | DLISTED_MGD_EXPL_IN(request, ht_by_src) |
---|
159 | DLISTED_MGD_EXPL_IN(request, ht_by_tgt) |
---|
160 | }; |
---|
161 | DLISTED_MGD_EXPL_OUT(request, ht_by_src) |
---|
162 | DLISTED_MGD_EXPL_OUT(request, ht_by_tgt) |
---|
163 | |
---|
164 | size_t hash( unsigned int k ) { |
---|
165 | // not really a hash function, not really the point |
---|
166 | return k; |
---|
167 | } |
---|
168 | |
---|
169 | unsigned int key( request_in_ht_by_src & v ) { |
---|
170 | return v.src_id; |
---|
171 | } |
---|
172 | |
---|
173 | |
---|
174 | #include <stdlib.hfa> |
---|
175 | |
---|
176 | int main() { |
---|
177 | |
---|
178 | |
---|
179 | HASHTABLE_STATIC(unsigned int, request_in_ht_by_src, request, 67, h_src) |
---|
180 | |
---|
181 | request & wasnt_found = get(h_src, 17); |
---|
182 | assert( &wasnt_found == 0p ); |
---|
183 | |
---|
184 | request r; |
---|
185 | r.src_id = 117; |
---|
186 | r.tgt_id = 998; |
---|
187 | |
---|
188 | put(h_src, r); |
---|
189 | |
---|
190 | request & found = get(h_src, 117); |
---|
191 | assert( &found == &r ); |
---|
192 | |
---|
193 | & wasnt_found = & get(h_src, 998); |
---|
194 | assert( &wasnt_found == 0p ); |
---|
195 | |
---|
196 | printf( "%f\n", fill_frac(h_src) ); |
---|
197 | |
---|
198 | |
---|
199 | request rs[500]; |
---|
200 | try { |
---|
201 | for (i; 500) { |
---|
202 | rs[i].src_id = 8000 * i; |
---|
203 | put(h_src, rs[i]); |
---|
204 | } |
---|
205 | } catchResume(ht_fill_limit_crossed*) { |
---|
206 | printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src)); |
---|
207 | throwResume; |
---|
208 | } |
---|
209 | |
---|
210 | assert( & get(h_src, 117 ) ); |
---|
211 | assert( & get(h_src, 8000*25 ) ); |
---|
212 | assert(! & get(h_src, 8000*25+1) ); |
---|
213 | |
---|
214 | |
---|
215 | |
---|
216 | dlist(request_in_ht_by_src, request) * (*old_alloc)( size_t ) = alloc; |
---|
217 | dlist(request_in_ht_by_src, request) * alloc( size_t n ) { |
---|
218 | dlist(request_in_ht_by_src, request) * ret = old_alloc(n); |
---|
219 | printf("alloc'ed at %p\n", ret); |
---|
220 | return ret; |
---|
221 | } |
---|
222 | |
---|
223 | void (*old_free)( void * ) = free; |
---|
224 | void free( void * o ) { |
---|
225 | printf("free'ing at %p\n", o); |
---|
226 | old_free(o); |
---|
227 | } |
---|
228 | |
---|
229 | hashtable_dynamic(unsigned int, request_in_ht_by_src, request) ht2 = { 113 }; |
---|
230 | request rs2[500]; |
---|
231 | try { |
---|
232 | for (i; 500) { |
---|
233 | if (i % 10 == 0) {printf("%d(%f),", i, fill_frac(ht2));} |
---|
234 | rs2[i].src_id = 8000 * i; |
---|
235 | put(ht2, rs2[i]); |
---|
236 | } |
---|
237 | } catchResume(ht_fill_limit_crossed*) { |
---|
238 | printf("fill limit tripped with ht2 filled at %f\n", fill_frac(ht2)); |
---|
239 | throwResume; |
---|
240 | } |
---|
241 | |
---|
242 | |
---|
243 | } |
---|