source: examples/hashtable.cfa @ fb19194

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

Hashtable demo grows to include static v dynamic allocation and a throwResume size-limit-exceeded exception that goes to different default handlers in those cases.

  • Property mode set to 100644
File size: 6.1 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( otype K ) {
17    size_t hash(K);
18    int ?==?( K, K );
19};
20
21trait hkey( otype K, dtype tN | has_hash(K) ) {
22    K key(tN &);
23};
24
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
57forall( otype K, dtype tN, dtype tE | $dlistable(tN, tE) | hkey(K, tN) ) {
58
59    float fill_frac( hashtable(K, tN, tE) & this ) with(this) {
60        return ((float)item_count) / n_buckets;
61    }
62
63    size_t bucket_of( hashtable(K, tN, tE) & this, K k ) {
64        return hash(k) % this.n_buckets;
65    }
66
67    tE & get( hashtable(K, tN, tE) & this, K k ) with (this) {
68
69        dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ];
70
71        for ( tN * item = & $tempcv_e2n(bucket`first);  item != 0p;  item = & $tempcv_e2n((*item)`next) ) {
72            if ( key(*item) == k ) {
73                return *item;
74            }
75        }
76
77        return *0p;
78    }
79
80    void check_ff_warning( hashtable(K, tN, tE) & this ) with (this) {
81        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __stashed_defaultResumptionHandler;
82        if (fill_frac(this) > ff_next_warn_up) {
83            throwResume (ht_fill_limit_crossed){};
84            ff_next_warn_up *= 2;
85        }
86    }
87
88    void put( hashtable(K, tN, tE) & this, tE & v ) with (this) {
89
90        check_ff_warning(this);
91
92        K k = key( $tempcv_e2n(v) );
93        dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ];
94
95        for ( tN * item = & $tempcv_e2n(bucket`first);  item != 0p;  item = & $tempcv_e2n((*item)`next) ) {
96            if ( key(*item) == k ) {
97                remove(*item);
98                break;
99            }
100        }
101
102        insert_first(bucket, v);
103        this.item_count ++;
104    }
105
106}
107
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
150
151
152struct request {
153
154    unsigned int src_id;
155    unsigned int tgt_id;
156
157    DLISTED_MGD_EXPL_IN(request, ht_by_src)
158    DLISTED_MGD_EXPL_IN(request, ht_by_tgt)
159};
160DLISTED_MGD_EXPL_OUT(request, ht_by_src)
161DLISTED_MGD_EXPL_OUT(request, ht_by_tgt)
162
163size_t hash( unsigned int k ) {
164    // not really a hash function, not really the point
165    return k;
166}
167
168unsigned int key( request_in_ht_by_src & v ) {
169    return v.src_id;
170}
171
172
173#include <stdlib.hfa>
174
175int main() {
176
177
178    HASHTABLE_STATIC(unsigned int, request_in_ht_by_src, request, 67, h_src)
179
180    request & wasnt_found = get(h_src, 17);
181    assert( &wasnt_found == 0p );
182
183    request r;
184    r.src_id = 117;
185    r.tgt_id = 998;
186
187    put(h_src, r);
188
189    request & found = get(h_src, 117);
190    assert( &found == &r );
191
192    & wasnt_found = & get(h_src, 998);
193    assert( &wasnt_found == 0p );
194
195    printf( "%f\n", fill_frac(h_src) );
196
197
198    request rs[500];
199    try {
200        for (i; 500) {
201            rs[i].src_id = 8000 * i;
202            put(h_src, rs[i]);
203        }
204    } catchResume(ht_fill_limit_crossed*) {
205        printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src));
206        throwResume;
207    }
208
209    assert(  & get(h_src, 117      ) );
210    assert(  & get(h_src, 8000*25  ) );
211    assert(! & get(h_src, 8000*25+1) );
212
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 TracBrowser for help on using the repository browser.