source: examples/hashtable2.cfa @ 585d910

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 585d910 was 9f7fff4, checked in by Michael Brooks <mlbrooks@…>, 4 years ago

Hashtable demo includes the essential features from the WHJIL.

  • Property mode set to 100644
File size: 14.3 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    bool want_throwResume_ht_auto_resize_pending;
35    size_t size_for_ht_auto_resize_pending;
36);
37
38void ?{}(ht_fill_limit_crossed & this, void * theHashtable) {
39        VTABLE_INIT(this, ht_fill_limit_crossed);
40        this.theHashtable = theHashtable;
41    this.want_throwResume_ht_auto_resize_pending = false;
42    this.size_for_ht_auto_resize_pending = 0;
43}
44
45const char * ht_fill_limit_crossed_msg(ht_fill_limit_crossed * this) {
46        return "ht_fill_limit_crossed";
47}
48
49VTABLE_INSTANCE(ht_fill_limit_crossed)(ht_fill_limit_crossed_msg);
50
51
52DATA_EXCEPTION(ht_auto_resize_pending)(
53        void * theHashtable;
54    size_t new_size;
55);
56
57void ?{}(ht_auto_resize_pending & this, void * theHashtable, size_t new_size) {
58        VTABLE_INIT(this, ht_auto_resize_pending);
59        this.theHashtable = theHashtable;
60    this.new_size = new_size;
61}
62
63const char * ht_auto_resize_pending_msg(ht_auto_resize_pending * this) {
64        return "ht_auto_resize_pending";
65}
66
67VTABLE_INSTANCE(ht_auto_resize_pending)(ht_auto_resize_pending_msg);
68
69
70
71trait pretendsToMatter( dtype TTT ) {
72    void actsmart(TTT &);
73};
74
75forall( dtype TTTx )
76void actsmart(TTTx &) {}
77
78// probable bug, wrt otype Tt_unused...
79//   1. changing to dtype Tt_unused crashes GenPoly
80//   2. declaring function check_ff_warning as concrete, i.e. operating on type hashtable_rbs(t_unused) makes cfa-cc generate bad C
81// in both cases, it's on the throwResume call
82// where it implicitly uses this.defaultResumptionHandler as a throwResume argument
83// whereas that, of course, has to be surrounded in a cast
84// at GenPoly breakpoint, type of said cast appears as CFA generic struct, even as the "this" parameter appears as C struct; casted type ...
85//   1. is hashtable_rbs(Tt_unused); assertion complains you don't need a type arg here
86//   2. shows up in -CFA output as hashtable_rbs(), which is bad C; expecting hashtable_rbs*
87
88forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) {
89
90    // hashtable of request by source
91    struct hashtable_rbs {
92
93        size_t n_buckets;
94        dlist(request_in_ht_by_src, request) *buckets;
95       
96        size_t item_count;
97        float ff_next_warn_up;
98        float ff_warn_step_factor;
99
100        void (*defaultResumptionHandler) (ht_fill_limit_crossed &);
101    };
102
103    void ?{}( hashtable_rbs(Tt_unused) & this ) = void;
104}
105
106forall( otype Tt_unused | pretendsToMatter(Tt_unused) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) {
107
108    void ?{}( hashtable_rbs(Tt_unused) & this, size_t n_buckets, dlist(request_in_ht_by_src, request) *buckets,
109        float ff_next_warn_up, float ff_warn_step_factor ) {
110
111        printf( "base hashtable ctor with %ld buckets at %p\n", n_buckets, buckets);
112
113        this.n_buckets = n_buckets;
114        this.buckets = buckets;
115
116        this.item_count = 0;
117        this.ff_next_warn_up = ff_next_warn_up;
118        this.ff_warn_step_factor = ff_warn_step_factor;
119
120        this.defaultResumptionHandler = defaultResumptionHandler;
121
122        for ( i; n_buckets ) {
123            ?{}( this.buckets[i] );
124        }
125    }
126
127    void ?{}( hashtable_rbs(Tt_unused) & this, size_t n_buckets, dlist(request_in_ht_by_src, request) *buckets ) {
128        printf( "base hashtable ctor with default warning steps\n" );
129        ( this ) { n_buckets, buckets, 0.5, 2 };
130    }
131
132}
133
134// this fwd declaration is artifact of workaround trac#192
135void defaultResumptionHandler( ht_auto_resize_pending & ex );
136
137forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) {
138
139    float fill_frac( hashtable_rbs(Tt_unused) & this ) with(this) {
140        return ((float)item_count) / n_buckets;
141    }
142
143    size_t bucket_of( hashtable_rbs(Tt_unused) & this, K k ) {
144        return hash(k) % this.n_buckets;
145    }
146
147    request & get( hashtable_rbs(Tt_unused) & this, K k ) with (this) {
148
149        dlist(request_in_ht_by_src, request) & bucket = buckets[ bucket_of(this, k) ];
150
151        for ( request_in_ht_by_src * item = & $tempcv_e2n(bucket`first);  item != 0p;  item = & $tempcv_e2n((*item)`next) ) {
152            if ( key(*item) == k ) {
153                return *item;
154            }
155        }
156
157        return *0p;
158    }
159
160    void check_ff_warning( hashtable_rbs(Tt_unused) & this ) with (this) {
161        if (fill_frac(this) > ff_next_warn_up) {
162            ht_fill_limit_crossed ex1 = { &this };
163            throwResume ex1;
164            // workaround trac#192: want the second throwResume to be in __dynamic_defaultResumptionHandler
165            // ... want base hashtable decoupled from resize
166            if ( ex1.want_throwResume_ht_auto_resize_pending ) {
167                throwResume( (ht_auto_resize_pending) { & this, ex1.size_for_ht_auto_resize_pending } );
168            }
169        }
170    }
171
172    void put( hashtable_rbs(Tt_unused) & this, request & v ) with (this) {
173
174        check_ff_warning(this);
175
176        K k = key( $tempcv_e2n(v) );
177        dlist(request_in_ht_by_src, request) & bucket = buckets[ bucket_of(this, k) ];
178
179        for ( request_in_ht_by_src * item = & $tempcv_e2n(bucket`first);  item != 0p;  item = & $tempcv_e2n((*item)`next) ) {
180            if ( key(*item) == k ) {
181                remove(*item);
182                break;
183            }
184        }
185
186        insert_first(bucket, v);
187        this.item_count ++;
188    }
189}
190
191
192
193
194// tactical usage:
195// HASHTABLE_RBS_STATIC(n, ht)
196//
197// intended equivalent:
198// hashtable_rbs_static(Z(n)) ht;
199#define HASHTABLE_RBS_STATIC(n_buckets, obj) \
200    struct __hashtable_static_ ## obj { \
201        inline hashtable_rbs(t_unused); \
202        dlist(request_in_ht_by_src, request) $items[n_buckets]; \
203    }; \
204    void ?{}( __hashtable_static_ ## obj & this )  { \
205        ((hashtable_rbs(t_unused) &)this){ n_buckets, this.$items }; \
206    } \
207    __hashtable_static_ ## obj obj;
208
209
210
211void defaultResumptionHandler(ht_fill_limit_crossed & ex) {
212    hashtable_rbs(t_unused) & ht = *(hashtable_rbs(t_unused) *)ex.theHashtable;
213    printf("base default resumption handler ht_fill_limit_crossed with ht filled at %f\n", fill_frac(ht));
214    ht.ff_next_warn_up *= ht.ff_warn_step_factor;
215}
216
217void defaultTerminationHandler(ht_fill_limit_crossed &) = void;
218
219
220
221
222
223trait heaped(dtype T) {
224    T * alloc( size_t );
225    void free( void * );
226};
227
228void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed &);
229
230forall( otype Tt_unused ) {
231
232    struct hashtable_rbs_dynamic {
233        inline hashtable_rbs(Tt_unused);
234
235        struct resize_policy {
236            // When fill factor exceeds grow limit, grow big enough for
237            // resulting fill factor to be lower than grow_target.  Vice versa.
238            // Using different grow and shrink limits prevents noisy current
239            // size from triggering grow-shrink oscillation.  OK to use same
240            // grow and shrink targets.
241            float grow_limit, shrink_limit, grow_target, shrink_target;
242
243            // warn with exception but do nothing, this many -1 times, then actually resize
244            unsigned short int warns_per_grow, warns_per_shrink;
245
246            // Don't shrink below.
247            size_t nbuckets_floor;
248        } policy;
249
250        dlist(request_in_ht_by_src, request) * (*alloc)( size_t );
251        void (*free)( void * );
252    };
253}
254
255// will be in list api
256void 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 ) {
257
258    // will re-implement as an actual splice
259    while ( & src_to_empty`first != 0p ) {
260        insert_last( snk_to_fill_at_last, pop_first( src_to_empty ) );
261    }
262}
263
264
265forall( otype Tt_unused | heaped( dlist(request_in_ht_by_src, request) ) ) {
266
267    void ?{}( hashtable_rbs_dynamic(Tt_unused).resize_policy & this, size_t nbuckets_floor ) {
268        printf("default dynamic policy ctor\n");
269
270        (this.grow_limit)      {2.0};
271        (this.shrink_limit)    {0.5};
272        (this.grow_target)     {1.0};
273        (this.shrink_target)   {1.0};
274        (this.warns_per_grow)  {4};
275        (this.warns_per_shrink){4};
276        (this.nbuckets_floor)  {nbuckets_floor};
277    }
278
279    void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, size_t n_buckets, hashtable_rbs_dynamic(Tt_unused).resize_policy rp )  {
280        printf("ctor hashtable_rbs_dynamic{ size_t, resize_policy }\n");
281
282        float first_first_warn_up = rp.grow_target;
283        float ff_warn_step_factor = (rp.grow_limit / rp.grow_target) \ ( 1. / rp.warns_per_grow );
284
285        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler;
286        dlist(request_in_ht_by_src, request) *buckets = alloc(n_buckets);
287        ( ( hashtable_rbs( Tt_unused ) & ) this ){ n_buckets, buckets, first_first_warn_up, ff_warn_step_factor };
288        ( this.policy ){ rp };
289        this.alloc = alloc;
290        this.free = free;
291    }
292    void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, hashtable_rbs_dynamic(Tt_unused).resize_policy rp )  {
293        printf("ctor hashtable_rbs_dynamic{ resize_policy }\n");
294        ( this ) { rp.nbuckets_floor, rp };
295    }
296    void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, size_t n_buckets )  {
297        printf("ctor hashtable_rbs_dynamic{ size_t }\n");
298        ( this ) { n_buckets, (hashtable_rbs_dynamic(Tt_unused).resize_policy){ n_buckets } };
299    }
300    void ^?{}( hashtable_rbs_dynamic(Tt_unused) & this ) {
301        free(this.buckets);
302    }
303    void rehashToLarger( hashtable_rbs_dynamic(Tt_unused) & this, size_t new_n_buckets ) with(this) {
304        printf("resizing from %ld to %ld, old buckets at %p\n", n_buckets, new_n_buckets, buckets);
305
306        // collect hash items from old buckets
307        dlist(request_in_ht_by_src, request) items;
308        for (i; n_buckets) {
309            splice_all_to_last( buckets[i], items );
310        }
311
312        // make empty hash table of new size
313        dlist(request_in_ht_by_src, request) *oldBuckets = buckets;
314        float oldFfWarnStepFactor = ff_warn_step_factor;
315        float newFfNextWarnUp = ((float)item_count) / ((float) new_n_buckets);
316        ^?{}( (hashtable_rbs(Tt_unused) &)this );
317        free( oldBuckets );
318        ?{}( (hashtable_rbs(Tt_unused) &)this, new_n_buckets, alloc(new_n_buckets), newFfNextWarnUp, oldFfWarnStepFactor );
319
320        // fill new table with old items
321        while ( & items`first != 0p ) {
322            put( this, pop_first( items ) );
323        }
324    }
325}
326
327forall( otype Tt_unused ) {
328    void rehashToLarger_STEP( hashtable_rbs_dynamic(Tt_unused) & this, size_t new_n_buckets ) with (this) {
329        rehashToLarger( this, new_n_buckets );
330    }
331}
332
333void defaultResumptionHandler( ht_auto_resize_pending & ex ) {
334    hashtable_rbs_dynamic(t_unused) & ht = *(hashtable_rbs_dynamic(t_unused) *)ex.theHashtable;
335    printf("auto-resize unhandled: proceeding with resize\n");
336    rehashToLarger_STEP( ht, ex.new_size );
337}
338
339void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) {
340    hashtable_rbs_dynamic(t_unused) & ht = *(hashtable_rbs_dynamic(t_unused) *)ex.theHashtable;
341    printf("dynamic warning received with fill_frac = %f and buckets at %p\n", fill_frac(ht), ht.buckets);
342    if ( fill_frac( ht ) >= ht.policy.grow_limit ) {
343        float grow_amount =  ht.policy.grow_limit / ht.policy.grow_target;
344        ex.want_throwResume_ht_auto_resize_pending = true;
345        ex.size_for_ht_auto_resize_pending = ( size_t )( grow_amount * ht.n_buckets );
346    } else {
347        // base handler, not specialized for dynamic
348        defaultResumptionHandler( ex );
349    }
350}
351
352
353
354
355
356
357#include <stdlib.hfa>
358
359void basicFillingTestHelper( hashtable_rbs(t_unused) & ht, size_t n_elems ) {
360
361    request & wasnt_found = get(ht, 17);
362    assert( &wasnt_found == 0p );
363
364    request r;
365    r.src_id = 117;
366    r.tgt_id = 998;
367
368    put(ht, r);
369
370    request & found = get(ht, 117);
371    assert( &found == &r );
372
373    & wasnt_found = & get(ht, 998);
374    assert( &wasnt_found == 0p );
375
376    request rs[n_elems];
377    for (i; n_elems) {
378        rs[i].src_id = 8000 * i;
379        put(ht, rs[i]);
380    }
381
382    assert(  & get(ht, 117      ) );
383    assert(  & get(ht, 8000*25  ) );
384    assert(! & get(ht, 8000*25+1) );
385}
386
387void basicFillingTest_static() {
388
389    printf("---start basic fill test static ----\n");
390
391    HASHTABLE_RBS_STATIC(67, ht)
392
393    basicFillingTestHelper(ht, 500);
394}
395
396void basicFillingTest_dynamic() {
397
398    dlist(request_in_ht_by_src, request) * (*old_alloc)( size_t ) = alloc;
399    dlist(request_in_ht_by_src, request) * alloc( size_t n ) {
400        dlist(request_in_ht_by_src, request) * ret = old_alloc(n);
401        printf("alloc'ed at %p\n", ret);
402        return ret;
403    }
404
405    void (*old_free)( void * ) = free;
406    void free( void * o ) {
407        printf("free'ing at %p\n", o);
408        old_free(o);
409    }
410
411    printf("---start basic fill test dynamic ----\n");
412
413    hashtable_rbs_dynamic(t_unused) ht = { 113 };
414
415    basicFillingTestHelper(ht, 500);
416}
417
418// Demonstrates user-provided instrumentation monitoring a fixed-size hash table
419void logTest() {
420
421    printf("---start log test ----\n");
422
423    HASHTABLE_RBS_STATIC(67, ht)
424
425    try {
426        basicFillingTestHelper(ht, 500);
427    } catchResume( ht_fill_limit_crossed * ) {
428        printf("log test instrumentation runs\n");
429        throwResume;
430    }
431}
432
433// Demonstrates "snoozing" a growing hash table's auto-resize event,
434// in that that next call to put will get the resize exception instead.
435void snoozeTest() {
436
437    printf("---start snooze test ----\n");
438
439    hashtable_rbs_dynamic(t_unused) ht = { 113 };
440
441    bool lastResizeSnoozed = false;
442
443    try {
444        basicFillingTestHelper(ht, 500);
445    } catchResume( ht_auto_resize_pending * ) {
446
447        if ( lastResizeSnoozed == false ) {
448            lastResizeSnoozed = true;
449            printf("snooze test intervention decides to snooze this time\n");
450        } else {
451            lastResizeSnoozed = false;
452            printf("snooze test intervention decides to allow the resize\n");
453            throwResume;
454        }
455
456    }
457}
458
459int main() {
460
461    basicFillingTest_static();
462    basicFillingTest_dynamic();
463
464    logTest();
465    snoozeTest();
466}
Note: See TracBrowser for help on using the repository browser.