source: tests/zombies/hashtable.cfa @ fd54fef

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since fd54fef was fd54fef, checked in by Michael Brooks <mlbrooks@…>, 9 months ago

Converting the project to use the new syntax for otype, dtype and ttytpe.

Changed prelude (gen), libcfa and test suite to use it. Added a simple deprecation rule of the old syntax to the parser; we might wish to support both syntaxes "officially," like with an extra CLI switch, but this measure should serve as a simple reminder for our team to try the new syntax.

  • Property mode set to 100644
File size: 5.9 KB
Line 
1
2#include <containers/list.hfa>
3
4#include <exception.hfa>
5TRIVIAL_EXCEPTION(ht_fill_limit_crossed);
6
7
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
15
16trait has_hash( K ) {
17    size_t hash(K);
18    int ?==?( K, K );
19};
20
21trait hkey( K, tN & | has_hash(K) ) {
22    K key(tN &);
23};
24
25forall( K, tN &, tE & | $dlistable(tN, tE) | hkey(K, tN) ) {
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 (*defaultResumptionHandler) (ht_fill_limit_crossed &);
36    };
37
38    void ?{}( hashtable(K, tN, tE) & this ) = void;
39}
40
41forall( K, tN &, tE & | $dlistable(tN, tE) | hkey(K, tN) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) {
42
43    void ?{}( hashtable(K, tN, tE) & this, size_t n_buckets, dlist(tN, tE) *buckets ) {
44
45        this.n_buckets = n_buckets;
46        this.buckets = buckets;
47
48        this.item_count = 0;
49        this.ff_next_warn_up = 0.5;
50
51        this.defaultResumptionHandler = defaultResumptionHandler;
52
53        for ( i; n_buckets ) {
54            ?{}( this.buckets[i] );
55        }
56    }
57}
58
59forall( K, tN &, tE & | $dlistable(tN, tE) | hkey(K, tN) ) {
60
61    float fill_frac( hashtable(K, tN, tE) & this ) with(this) {
62        return ((float)item_count) / n_buckets;
63    }
64
65    size_t bucket_of( hashtable(K, tN, tE) & this, K k ) {
66        return hash(k) % this.n_buckets;
67    }
68
69    tE & get( hashtable(K, tN, tE) & this, K k ) with (this) {
70
71        dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ];
72
73        for ( tN * item = & $tempcv_e2n(bucket`first);  item != 0p;  item = & $tempcv_e2n((*item)`next) ) {
74            if ( key(*item) == k ) {
75                return *item;
76            }
77        }
78
79        return *0p;
80    }
81
82    void check_ff_warning( hashtable(K, tN, tE) & this ) with (this) {
83        if (fill_frac(this) > ff_next_warn_up) {
84            throwResume (ht_fill_limit_crossed){};
85            ff_next_warn_up *= 2;
86        }
87    }
88
89    void put( hashtable(K, tN, tE) & this, tE & v ) with (this) {
90
91        check_ff_warning(this);
92
93        K k = key( $tempcv_e2n(v) );
94        dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ];
95
96        for ( tN * item = & $tempcv_e2n(bucket`first);  item != 0p;  item = & $tempcv_e2n((*item)`next) ) {
97            if ( key(*item) == k ) {
98                remove(*item);
99                break;
100            }
101        }
102
103        insert_first(bucket, v);
104        this.item_count ++;
105    }
106
107}
108
109// tactical usage:
110// HASHTABLE_STATIC(int, item_by_prority, item, n, ht)
111//
112// intended equivalent:
113// hashtable_static(int, item_by_prority, item, Z(n)) ht;
114#define HASHTABLE_STATIC(K, tN, tE, n_buckets, obj) \
115    struct __hashtable_static_ ## obj { \
116        inline hashtable(K, tN, tE); \
117        dlist(tN, tE) $items[n_buckets]; \
118    }; \
119    void ?{}( __hashtable_static_ ## obj & this )  { \
120        ((hashtable(K, tN, tE) &)this){ n_buckets, this.$items }; \
121    } \
122    __hashtable_static_ ## obj obj;
123
124
125
126trait heaped(T &) {
127    T * alloc( size_t );
128    void free( void * );
129};
130
131void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) {
132    printf("dynamic limit crossed\n");
133}
134
135forall( K, tN &, tE & | $dlistable(tN, tE) | hkey(K, tN) | heaped( dlist(tN, tE) ) ) {
136
137    struct hashtable_dynamic {
138        inline hashtable(K, tN, tE);
139    };
140    void ?{}( hashtable_dynamic(K, tN, tE) & this, size_t n_buckets )  {
141        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler;
142        dlist(tN, tE) *buckets = alloc(n_buckets);
143        ((hashtable(K, tN, tE) &)this){ n_buckets, buckets };
144    }
145    void ^?{}( hashtable_dynamic(K, tN, tE) & this ) {
146        free(this.buckets);
147    }
148}
149
150
151
152
153struct request {
154
155    unsigned int src_id;
156    unsigned int tgt_id;
157
158    DLISTED_MGD_EXPL_IN(request, ht_by_src)
159    DLISTED_MGD_EXPL_IN(request, ht_by_tgt)
160};
161DLISTED_MGD_EXPL_OUT(request, ht_by_src)
162DLISTED_MGD_EXPL_OUT(request, ht_by_tgt)
163
164size_t hash( unsigned int k ) {
165    // not really a hash function, not really the point
166    return k;
167}
168
169unsigned int key( request_in_ht_by_src & v ) {
170    return v.src_id;
171}
172
173
174#include <stdlib.hfa>
175
176int main() {
177
178
179    HASHTABLE_STATIC(unsigned int, request_in_ht_by_src, request, 67, h_src)
180
181    request & wasnt_found = get(h_src, 17);
182    assert( &wasnt_found == 0p );
183
184    request r;
185    r.src_id = 117;
186    r.tgt_id = 998;
187
188    put(h_src, r);
189
190    request & found = get(h_src, 117);
191    assert( &found == &r );
192
193    & wasnt_found = & get(h_src, 998);
194    assert( &wasnt_found == 0p );
195
196    printf( "%f\n", fill_frac(h_src) );
197
198
199    request rs[500];
200    try {
201        for (i; 500) {
202            rs[i].src_id = 8000 * i;
203            put(h_src, rs[i]);
204        }
205    } catchResume(ht_fill_limit_crossed*) {
206        printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src));
207        throwResume;
208    }
209
210    assert(  & get(h_src, 117      ) );
211    assert(  & get(h_src, 8000*25  ) );
212    assert(! & get(h_src, 8000*25+1) );
213
214
215
216    dlist(request_in_ht_by_src, request) * (*old_alloc)( size_t ) = alloc;
217    dlist(request_in_ht_by_src, request) * alloc( size_t n ) {
218        dlist(request_in_ht_by_src, request) * ret = old_alloc(n);
219        printf("alloc'ed at %p\n", ret);
220        return ret;
221    }
222
223    void (*old_free)( void * ) = free;
224    void free( void * o ) {
225        printf("free'ing at %p\n", o);
226        old_free(o);
227    }
228
229    hashtable_dynamic(unsigned int, request_in_ht_by_src, request) ht2 = { 113 };
230    request rs2[500];
231    try {
232        for (i; 500) {
233            if (i % 10 == 0) {printf("%d(%f),", i, fill_frac(ht2));}
234            rs2[i].src_id = 8000 * i;
235            put(ht2, rs2[i]);
236        }
237    } catchResume(ht_fill_limit_crossed*) {
238        printf("fill limit tripped with ht2 filled at %f\n", fill_frac(ht2));
239        throwResume;
240    }
241
242
243}
Note: See TracBrowser for help on using the repository browser.