Changeset 8fc6e92a


Ignore:
Timestamp:
Jun 18, 2020, 10:03:20 PM (4 years ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
1d2314f
Parents:
df733ed
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • examples/hashtable2.cfa

    rdf733ed r8fc6e92a  
    2929
    3030#include <exception.hfa>
    31 TRIVIAL_EXCEPTION(ht_fill_limit_crossed);
    32 
    33 
    34 
    35 void defaultResumptionHandler(ht_fill_limit_crossed &) {
    36     printf("default resumption ht_fill_limit_crossed\n");
    37 }
    38 
    39 void defaultTerminationHandler(ht_fill_limit_crossed &) = void;
     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
    4049
    4150trait pretendsToMatter( dtype TTT ) {
     
    91100}
    92101
     102
    93103forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) {
    94104
     
    116126    void check_ff_warning( hashtable_rbs(Tt_unused) & this ) with (this) {
    117127        if (fill_frac(this) > ff_next_warn_up) {
    118             throwResume (ht_fill_limit_crossed){};
    119             ff_next_warn_up *= 2;
     128            throwResume (ht_fill_limit_crossed){ &this };
    120129        }
    121130    }
     
    139148    }
    140149}
     150
     151
     152
    141153
    142154// tactical usage:
     
    157169
    158170
     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
    159183trait heaped(dtype T) {
    160184    T * alloc( size_t );
     
    162186};
    163187
    164 void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) {
    165     printf("dynamic limit crossed\n");
    166 }
    167 
    168 forall( | heaped( dlist(request_in_ht_by_src, request) ) ) {
     188void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed &);
     189
     190forall( otype Tt_unused ) {
    169191
    170192    struct hashtable_rbs_dynamic {
    171         inline hashtable_rbs(t_unused);
     193        inline hashtable_rbs(Tt_unused);
     194        dlist(request_in_ht_by_src, request) * (*alloc)( size_t );
     195        void (*free)( void * );
    172196    };
    173     void ?{}( hashtable_rbs_dynamic(t_unused) & this, size_t n_buckets )  {
     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 )  {
    174212        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler;
    175213        dlist(request_in_ht_by_src, request) *buckets = alloc(n_buckets);
    176         ((hashtable_rbs(t_unused) &)this){ n_buckets, buckets };
    177     }
    178     void ^?{}( hashtable_rbs_dynamic(t_unused) & this ) {
     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 ) {
    179219        free(this.buckets);
    180220    }
     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 );
    181253}
    182254
Note: See TracChangeset for help on using the changeset viewer.