1 | |
---|
2 | #include <containers/list.hfa> |
---|
3 | |
---|
4 | typedef unsigned int K; |
---|
5 | |
---|
6 | // workaround type for trac#185; used here as the ticket's examples use a spontaneous float |
---|
7 | typedef struct {} t_unused; |
---|
8 | |
---|
9 | struct request { |
---|
10 | |
---|
11 | unsigned int src_id; |
---|
12 | unsigned int tgt_id; |
---|
13 | |
---|
14 | DLISTED_MGD_EXPL_IN(request, ht_by_src) |
---|
15 | DLISTED_MGD_EXPL_IN(request, ht_by_tgt) |
---|
16 | }; |
---|
17 | DLISTED_MGD_EXPL_OUT(request, ht_by_src) |
---|
18 | DLISTED_MGD_EXPL_OUT(request, ht_by_tgt) |
---|
19 | |
---|
20 | size_t hash( unsigned int k ) { |
---|
21 | // not really a hash function, not really the point |
---|
22 | return k; |
---|
23 | } |
---|
24 | |
---|
25 | unsigned int key( request_in_ht_by_src & v ) { |
---|
26 | return v.src_id; |
---|
27 | } |
---|
28 | |
---|
29 | |
---|
30 | #include <exception.hfa> |
---|
31 | |
---|
32 | DATA_EXCEPTION(ht_fill_limit_crossed)( |
---|
33 | void * theHashtable; |
---|
34 | ); |
---|
35 | |
---|
36 | void ?{}(ht_fill_limit_crossed & this, void * theHashtable) { |
---|
37 | VTABLE_INIT(this, ht_fill_limit_crossed); |
---|
38 | this.theHashtable = theHashtable; |
---|
39 | } |
---|
40 | |
---|
41 | const char * ht_fill_limit_crossed_msg(ht_fill_limit_crossed * this) { |
---|
42 | return "ht_fill_limit_crossed"; |
---|
43 | } |
---|
44 | |
---|
45 | VTABLE_INSTANCE(ht_fill_limit_crossed)(ht_fill_limit_crossed_msg); |
---|
46 | |
---|
47 | |
---|
48 | |
---|
49 | |
---|
50 | trait pretendsToMatter( dtype TTT ) { |
---|
51 | void actsmart(TTT &); |
---|
52 | }; |
---|
53 | |
---|
54 | forall( dtype TTTx ) |
---|
55 | void actsmart(TTTx &) {} |
---|
56 | |
---|
57 | // probable bug, wrt otype Tt_unused... |
---|
58 | // 1. changing to dtype Tt_unused crashes GenPoly |
---|
59 | // 2. declaring function check_ff_warning as concrete, i.e. operating on type hashtable_rbs(t_unused) makes cfa-cc generate bad C |
---|
60 | // in both cases, it's on the throwResume call |
---|
61 | // where it implicitly uses this.defaultResumptionHandler as a throwResume argument |
---|
62 | // whereas that, of course, has to be surrounded in a cast |
---|
63 | // at GenPoly breakpoint, type of said cast appears as CFA generic struct, even as the "this" parameter appears as C struct; casted type ... |
---|
64 | // 1. is hashtable_rbs(Tt_unused); assertion complains you don't need a type arg here |
---|
65 | // 2. shows up in -CFA output as hashtable_rbs(), which is bad C; expecting hashtable_rbs* |
---|
66 | |
---|
67 | forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) { |
---|
68 | |
---|
69 | // hashtable of request by source |
---|
70 | struct hashtable_rbs { |
---|
71 | |
---|
72 | size_t n_buckets; |
---|
73 | dlist(request_in_ht_by_src, request) *buckets; |
---|
74 | |
---|
75 | size_t item_count; |
---|
76 | float ff_next_warn_up; |
---|
77 | |
---|
78 | void (*defaultResumptionHandler) (ht_fill_limit_crossed &); |
---|
79 | }; |
---|
80 | |
---|
81 | void ?{}( hashtable_rbs(Tt_unused) & this ) = void; |
---|
82 | } |
---|
83 | |
---|
84 | forall( otype Tt_unused | pretendsToMatter(Tt_unused) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) { |
---|
85 | |
---|
86 | void ?{}( hashtable_rbs(Tt_unused) & this, size_t n_buckets, dlist(request_in_ht_by_src, request) *buckets ) { |
---|
87 | |
---|
88 | this.n_buckets = n_buckets; |
---|
89 | this.buckets = buckets; |
---|
90 | |
---|
91 | this.item_count = 0; |
---|
92 | this.ff_next_warn_up = 0.5; |
---|
93 | |
---|
94 | this.defaultResumptionHandler = defaultResumptionHandler; |
---|
95 | |
---|
96 | for ( i; n_buckets ) { |
---|
97 | ?{}( this.buckets[i] ); |
---|
98 | } |
---|
99 | } |
---|
100 | } |
---|
101 | |
---|
102 | |
---|
103 | forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) { |
---|
104 | |
---|
105 | float fill_frac( hashtable_rbs(Tt_unused) & this ) with(this) { |
---|
106 | return ((float)item_count) / n_buckets; |
---|
107 | } |
---|
108 | |
---|
109 | size_t bucket_of( hashtable_rbs(Tt_unused) & this, K k ) { |
---|
110 | return hash(k) % this.n_buckets; |
---|
111 | } |
---|
112 | |
---|
113 | request & get( hashtable_rbs(Tt_unused) & this, K k ) with (this) { |
---|
114 | |
---|
115 | dlist(request_in_ht_by_src, request) & bucket = buckets[ bucket_of(this, k) ]; |
---|
116 | |
---|
117 | for ( request_in_ht_by_src * item = & $tempcv_e2n(bucket`first); item != 0p; item = & $tempcv_e2n((*item)`next) ) { |
---|
118 | if ( key(*item) == k ) { |
---|
119 | return *item; |
---|
120 | } |
---|
121 | } |
---|
122 | |
---|
123 | return *0p; |
---|
124 | } |
---|
125 | |
---|
126 | void check_ff_warning( hashtable_rbs(Tt_unused) & this ) with (this) { |
---|
127 | if (fill_frac(this) > ff_next_warn_up) { |
---|
128 | throwResume (ht_fill_limit_crossed){ &this }; |
---|
129 | } |
---|
130 | } |
---|
131 | |
---|
132 | void put( hashtable_rbs(Tt_unused) & this, request & v ) with (this) { |
---|
133 | |
---|
134 | check_ff_warning(this); |
---|
135 | |
---|
136 | K k = key( $tempcv_e2n(v) ); |
---|
137 | dlist(request_in_ht_by_src, request) & bucket = buckets[ bucket_of(this, k) ]; |
---|
138 | |
---|
139 | for ( request_in_ht_by_src * item = & $tempcv_e2n(bucket`first); item != 0p; item = & $tempcv_e2n((*item)`next) ) { |
---|
140 | if ( key(*item) == k ) { |
---|
141 | remove(*item); |
---|
142 | break; |
---|
143 | } |
---|
144 | } |
---|
145 | |
---|
146 | insert_first(bucket, v); |
---|
147 | this.item_count ++; |
---|
148 | } |
---|
149 | } |
---|
150 | |
---|
151 | |
---|
152 | |
---|
153 | |
---|
154 | // tactical usage: |
---|
155 | // HASHTABLE_RBS_STATIC(n, ht) |
---|
156 | // |
---|
157 | // intended equivalent: |
---|
158 | // hashtable_rbs_static(Z(n)) ht; |
---|
159 | #define HASHTABLE_RBS_STATIC(n_buckets, obj) \ |
---|
160 | struct __hashtable_static_ ## obj { \ |
---|
161 | inline hashtable_rbs(t_unused); \ |
---|
162 | dlist(request_in_ht_by_src, request) $items[n_buckets]; \ |
---|
163 | }; \ |
---|
164 | void ?{}( __hashtable_static_ ## obj & this ) { \ |
---|
165 | ((hashtable_rbs(t_unused) &)this){ n_buckets, this.$items }; \ |
---|
166 | } \ |
---|
167 | __hashtable_static_ ## obj obj; |
---|
168 | |
---|
169 | |
---|
170 | |
---|
171 | void defaultResumptionHandler(ht_fill_limit_crossed & ex) { |
---|
172 | printf("default resumption ht_fill_limit_crossed\n"); |
---|
173 | hashtable_rbs(t_unused) & ht = *(hashtable_rbs(t_unused) *)ex.theHashtable; |
---|
174 | ht.ff_next_warn_up *= 2; |
---|
175 | } |
---|
176 | |
---|
177 | void defaultTerminationHandler(ht_fill_limit_crossed &) = void; |
---|
178 | |
---|
179 | |
---|
180 | |
---|
181 | |
---|
182 | |
---|
183 | trait heaped(dtype T) { |
---|
184 | T * alloc( size_t ); |
---|
185 | void free( void * ); |
---|
186 | }; |
---|
187 | |
---|
188 | void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed &); |
---|
189 | |
---|
190 | forall( otype Tt_unused ) { |
---|
191 | |
---|
192 | struct hashtable_rbs_dynamic { |
---|
193 | inline hashtable_rbs(Tt_unused); |
---|
194 | dlist(request_in_ht_by_src, request) * (*alloc)( size_t ); |
---|
195 | void (*free)( void * ); |
---|
196 | }; |
---|
197 | } |
---|
198 | |
---|
199 | // will be in list api |
---|
200 | void splice_all_to_last( dlist(request_in_ht_by_src, request) & src_to_empty, dlist(request_in_ht_by_src, request) & snk_to_fill_at_last ) { |
---|
201 | |
---|
202 | // will re-implement as an actual splice |
---|
203 | while ( & src_to_empty`first != 0p ) { |
---|
204 | insert_last( snk_to_fill_at_last, pop_first( src_to_empty ) ); |
---|
205 | } |
---|
206 | } |
---|
207 | |
---|
208 | |
---|
209 | forall( otype Tt_unused | heaped( dlist(request_in_ht_by_src, request) ) ) { |
---|
210 | |
---|
211 | void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, size_t n_buckets ) { |
---|
212 | void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler; |
---|
213 | dlist(request_in_ht_by_src, request) *buckets = alloc(n_buckets); |
---|
214 | ((hashtable_rbs(Tt_unused) &)this){ n_buckets, buckets }; |
---|
215 | this.alloc = alloc; |
---|
216 | this.free = free; |
---|
217 | } |
---|
218 | void ^?{}( hashtable_rbs_dynamic(Tt_unused) & this ) { |
---|
219 | free(this.buckets); |
---|
220 | } |
---|
221 | void rehashToLarger( hashtable_rbs_dynamic(Tt_unused) & this, size_t new_n_buckets ) with(this) { |
---|
222 | printf("resizing from %ld to %ld, old buckets at %p\n", n_buckets, new_n_buckets, buckets); |
---|
223 | |
---|
224 | // collect hash items from old buckets |
---|
225 | dlist(request_in_ht_by_src, request) items; |
---|
226 | for (i; n_buckets) { |
---|
227 | splice_all_to_last( buckets[i], items ); |
---|
228 | } |
---|
229 | |
---|
230 | // make empty hash table of new size |
---|
231 | dlist(request_in_ht_by_src, request) *oldBuckets = buckets; |
---|
232 | ^?{}( (hashtable_rbs(Tt_unused) &)this ); |
---|
233 | free( oldBuckets ); |
---|
234 | ?{}( (hashtable_rbs(Tt_unused) &)this, new_n_buckets, alloc(new_n_buckets) ); |
---|
235 | |
---|
236 | // fill new table with old items |
---|
237 | while ( & items`first != 0p ) { |
---|
238 | put( this, pop_first( items ) ); |
---|
239 | } |
---|
240 | } |
---|
241 | } |
---|
242 | |
---|
243 | forall( otype Tt_unused ) { |
---|
244 | void rehashToLarger_STEP( hashtable_rbs_dynamic(Tt_unused) & this, size_t new_n_buckets ) with (this) { |
---|
245 | rehashToLarger( this, new_n_buckets ); |
---|
246 | } |
---|
247 | } |
---|
248 | |
---|
249 | void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) { |
---|
250 | hashtable_rbs_dynamic(t_unused) & ht = *(hashtable_rbs_dynamic(t_unused) *)ex.theHashtable; |
---|
251 | printf("dynamic limit crossed with fill_frac = %f and buckets at %p\n", fill_frac(ht), ht.buckets); |
---|
252 | rehashToLarger_STEP( ht, 2 * ht.n_buckets ); |
---|
253 | } |
---|
254 | |
---|
255 | |
---|
256 | |
---|
257 | |
---|
258 | |
---|
259 | |
---|
260 | #include <stdlib.hfa> |
---|
261 | |
---|
262 | int main() { |
---|
263 | |
---|
264 | |
---|
265 | HASHTABLE_RBS_STATIC(67, h_src) |
---|
266 | |
---|
267 | request & wasnt_found = get(h_src, 17); |
---|
268 | assert( &wasnt_found == 0p ); |
---|
269 | |
---|
270 | request r; |
---|
271 | r.src_id = 117; |
---|
272 | r.tgt_id = 998; |
---|
273 | |
---|
274 | put(h_src, r); |
---|
275 | |
---|
276 | request & found = get(h_src, 117); |
---|
277 | assert( &found == &r ); |
---|
278 | |
---|
279 | & wasnt_found = & get(h_src, 998); |
---|
280 | assert( &wasnt_found == 0p ); |
---|
281 | |
---|
282 | printf( "%f\n", fill_frac(h_src) ); |
---|
283 | |
---|
284 | |
---|
285 | request rs[500]; |
---|
286 | try { |
---|
287 | for (i; 500) { |
---|
288 | rs[i].src_id = 8000 * i; |
---|
289 | put(h_src, rs[i]); |
---|
290 | } |
---|
291 | } catchResume(ht_fill_limit_crossed*) { |
---|
292 | printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src)); |
---|
293 | throwResume; |
---|
294 | } |
---|
295 | |
---|
296 | assert( & get(h_src, 117 ) ); |
---|
297 | assert( & get(h_src, 8000*25 ) ); |
---|
298 | assert(! & get(h_src, 8000*25+1) ); |
---|
299 | |
---|
300 | |
---|
301 | |
---|
302 | dlist(request_in_ht_by_src, request) * (*old_alloc)( size_t ) = alloc; |
---|
303 | dlist(request_in_ht_by_src, request) * alloc( size_t n ) { |
---|
304 | dlist(request_in_ht_by_src, request) * ret = old_alloc(n); |
---|
305 | printf("alloc'ed at %p\n", ret); |
---|
306 | return ret; |
---|
307 | } |
---|
308 | |
---|
309 | void (*old_free)( void * ) = free; |
---|
310 | void free( void * o ) { |
---|
311 | printf("free'ing at %p\n", o); |
---|
312 | old_free(o); |
---|
313 | } |
---|
314 | |
---|
315 | hashtable_rbs_dynamic(t_unused) ht2 = { 113 }; |
---|
316 | request rs2[500]; |
---|
317 | try { |
---|
318 | for (i; 500) { |
---|
319 | if (i % 10 == 0) {printf("%d(%f),", i, fill_frac(ht2));} |
---|
320 | rs2[i].src_id = 8000 * i; |
---|
321 | put(ht2, rs2[i]); |
---|
322 | } |
---|
323 | } catchResume(ht_fill_limit_crossed*) { |
---|
324 | printf("fill limit tripped with ht2 filled at %f\n", fill_frac(ht2)); |
---|
325 | throwResume; |
---|
326 | } |
---|
327 | |
---|
328 | |
---|
329 | } |
---|