source: examples/hashtable2.cfa @ 8fc6e92a

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 8fc6e92a was 8fc6e92a, checked in by Michael Brooks <mlbrooks@…>, 3 years ago

Hashtable demo (non-generic version) does dynamic resizing via exception.

  • Property mode set to 100644
File size: 9.0 KB
Line 
1
2#include <containers/list.hfa>
3
4typedef unsigned int K;
5
6// workaround type for trac#185; used here as the ticket's examples use a spontaneous float
7typedef struct {} t_unused;
8
9struct 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};
17DLISTED_MGD_EXPL_OUT(request, ht_by_src)
18DLISTED_MGD_EXPL_OUT(request, ht_by_tgt)
19
20size_t hash( unsigned int k ) {
21    // not really a hash function, not really the point
22    return k;
23}
24
25unsigned int key( request_in_ht_by_src & v ) {
26    return v.src_id;
27}
28
29
30#include <exception.hfa>
31
32DATA_EXCEPTION(ht_fill_limit_crossed)(
33        void * theHashtable;
34);
35
36void ?{}(ht_fill_limit_crossed & this, void * theHashtable) {
37        VTABLE_INIT(this, ht_fill_limit_crossed);
38        this.theHashtable = theHashtable;
39}
40
41const char * ht_fill_limit_crossed_msg(ht_fill_limit_crossed * this) {
42        return "ht_fill_limit_crossed";
43}
44
45VTABLE_INSTANCE(ht_fill_limit_crossed)(ht_fill_limit_crossed_msg);
46
47
48
49
50trait pretendsToMatter( dtype TTT ) {
51    void actsmart(TTT &);
52};
53
54forall( dtype TTTx )
55void 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
67forall( 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
84forall( 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
103forall( 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
171void 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
177void defaultTerminationHandler(ht_fill_limit_crossed &) = void;
178
179
180
181
182
183trait heaped(dtype T) {
184    T * alloc( size_t );
185    void free( void * );
186};
187
188void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed &);
189
190forall( 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
200void 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
209forall( 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
243forall( 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
249void __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
262int 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}
Note: See TracBrowser for help on using the repository browser.