Changeset b8e3941


Ignore:
Timestamp:
Jun 18, 2020, 7:05:21 PM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
109c916, ab652e7
Parents:
6026628 (diff), fb19194 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • examples/hashtable.cfa

    r6026628 rb8e3941  
    1 // a type whose size is n
    2 #define Z(n) char[n]
    3 
    4 // the inverse of Z(-)
    5 #define z(Zn) sizeof(Zn)
    6 
    7 // if you're expecting a Z(n), say so, by asking for a ztype, instead of dtype or otype
    8 #define ztype(Zn) dtype Zn | sized(Zn)
    9 
    10 // a "known-size" array
    11 // an array of length n, whose elements are of Te, letting n be such that Zn is Z(n)
    12 forall( ztype(Zn), otype Te )
    13 struct array {
    14   Te items[z(Zn)];
    15 };
    16 
    17 // subscript operator for known-size array
    18 forall( ztype(Zn), otype Te ) {
    19   Te & ?[?]( array(Zn, Te) &this, size_t idx ) with(this) {
    20     return items[idx];
    21   }
    22 }
     1
     2#include <containers/list.hfa>
    233
    244#include <exception.hfa>
     
    266
    277
    28 #include <containers/list.hfa>
     8
     9void defaultResumptionHandler(ht_fill_limit_crossed &) {
     10    printf("default resumption ht_fill_limit_crossed\n");
     11}
     12
     13void defaultTerminationHandler(ht_fill_limit_crossed &) = void;
     14
    2915
    3016trait has_hash( otype K ) {
     
    3723};
    3824
     25forall( otype K, dtype tN, dtype tE | $dlistable(tN, tE) | hkey(K, tN) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) {
     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 (*__stashed_defaultResumptionHandler) (ht_fill_limit_crossed &);
     36    };
     37
     38    void ?{}( hashtable(K, tN, tE) & this ) = void;
     39//    void ?{}( hashtable(K, tN, tE) & this, size_t, dlist(tN, tE)* ) = void;
     40
     41    void ?{}( hashtable(K, tN, tE) & this, size_t n_buckets, dlist(tN, tE) *buckets ) {
     42
     43        this.n_buckets = n_buckets;
     44        this.buckets = buckets;
     45
     46        this.item_count = 0;
     47        this.ff_next_warn_up = 0.5;
     48
     49        this.__stashed_defaultResumptionHandler = defaultResumptionHandler;
     50
     51        for ( i; n_buckets ) {
     52            ?{}( this.buckets[i] );
     53        }
     54    }
     55}
     56
    3957forall( otype K, dtype tN, dtype tE | $dlistable(tN, tE) | hkey(K, tN) ) {
    40 
    41     struct hashtable {
    42 
    43         size_t item_count;
    44         size_t n_buckets;
    45 
    46         float ff_next_warn_up;
    47 
    48         dlist(tN, tE) buckets[ 0 ];
    49     };
    5058
    5159    float fill_frac( hashtable(K, tN, tE) & this ) with(this) {
    5260        return ((float)item_count) / n_buckets;
    53     }
    54 
    55     void ?{}( hashtable(K, tN, tE) & this, int n_buckets ) {
    56 
    57         this.item_count = 0;
    58         this.n_buckets = n_buckets;
    59         this.ff_next_warn_up = 0.5;
    60 
    61         for ( int i = 0; i < n_buckets; i++ ) {
    62             ?{}( this.buckets[i] );
    63         }
    6461    }
    6562
     
    8279
    8380    void check_ff_warning( hashtable(K, tN, tE) & this ) with (this) {
     81        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __stashed_defaultResumptionHandler;
    8482        if (fill_frac(this) > ff_next_warn_up) {
    85             throwResume &(ht_fill_limit_crossed){};
     83            throwResume (ht_fill_limit_crossed){};
    8684            ff_next_warn_up *= 2;
    8785        }
     
    108106}
    109107
     108// tactical usage:
     109// HASHTABLE_STATIC(int, item_by_prority, item, n, ht)
     110//
     111// intended equivalent:
     112// hashtable_static(int, item_by_prority, item, Z(n)) ht;
     113#define HASHTABLE_STATIC(K, tN, tE, n_buckets, obj) \
     114    struct __hashtable_static_ ## obj { \
     115        inline hashtable(K, tN, tE); \
     116        dlist(tN, tE) $items[n_buckets]; \
     117    }; \
     118    void ?{}( __hashtable_static_ ## obj & this )  { \
     119        ((hashtable(K, tN, tE) &)this){ n_buckets, this.$items }; \
     120    } \
     121    __hashtable_static_ ## obj obj;
     122
     123
     124
     125trait heaped(dtype T) {
     126    T * alloc( size_t );
     127    void free( void * );
     128};
     129
     130void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) {
     131    printf("dynamic limit crossed\n");
     132}
     133
     134forall( otype K, dtype tN, dtype tE | $dlistable(tN, tE) | hkey(K, tN) | heaped( dlist(tN, tE) ) ) {
     135
     136    struct hashtable_dynamic {
     137        inline hashtable(K, tN, tE);
     138    };
     139    void ?{}( hashtable_dynamic(K, tN, tE) & this, size_t n_buckets )  {
     140        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler;
     141        dlist(tN, tE) *buckets = alloc(n_buckets);
     142        ((hashtable(K, tN, tE) &)this){ n_buckets, buckets };
     143    }
     144    void ^?{}( hashtable_dynamic(K, tN, tE) & this ) {
     145        free(this.buckets);
     146    }
     147}
     148
     149
    110150
    111151
     
    114154    unsigned int src_id;
    115155    unsigned int tgt_id;
    116 
    117 
    118156
    119157    DLISTED_MGD_EXPL_IN(request, ht_by_src)
     
    133171
    134172
    135 
     173#include <stdlib.hfa>
    136174
    137175int main() {
    138176
    139     void *firstAlloc = malloc( sizeof( hashtable(unsigned int, request_in_ht_by_src, request))
    140                              + sizeof( dlist(request_in_ht_by_src, request) [67] )
    141                              );
    142     hashtable(unsigned int, request_in_ht_by_src, request) & h_src =
    143         * (hashtable(unsigned int, request_in_ht_by_src, request) *) firstAlloc;
    144    
    145     ?{}( h_src, 67 );
     177
     178    HASHTABLE_STATIC(unsigned int, request_in_ht_by_src, request, 67, h_src)
    146179
    147180    request & wasnt_found = get(h_src, 17);
     
    171204    } catchResume(ht_fill_limit_crossed*) {
    172205        printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src));
     206        throwResume;
    173207    }
    174208
     
    177211    assert(! & get(h_src, 8000*25+1) );
    178212
    179     free(firstAlloc);
    180 
    181 }
     213
     214
     215    dlist(request_in_ht_by_src, request) * (*old_alloc)( size_t ) = alloc;
     216    dlist(request_in_ht_by_src, request) * alloc( size_t n ) {
     217        dlist(request_in_ht_by_src, request) * ret = old_alloc(n);
     218        printf("alloc'ed at %p\n", ret);
     219        return ret;
     220    }
     221
     222    void (*old_free)( void * ) = free;
     223    void free( void * o ) {
     224        printf("free'ing at %p\n", o);
     225        old_free(o);
     226    }
     227
     228    hashtable_dynamic(unsigned int, request_in_ht_by_src, request) ht2 = { 113 };
     229    request rs2[500];
     230    try {
     231        for (i; 500) {
     232            if (i % 10 == 0) {printf("%d(%f),", i, fill_frac(ht2));}
     233            rs2[i].src_id = 8000 * i;
     234            put(ht2, rs2[i]);
     235        }
     236    } catchResume(ht_fill_limit_crossed*) {
     237        printf("fill limit tripped with ht2 filled at %f\n", fill_frac(ht2));
     238        throwResume;
     239    }
     240
     241
     242}
Note: See TracChangeset for help on using the changeset viewer.