source: examples/hashtable.cfa@ b8e3941

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since b8e3941 was fb19194, checked in by Michael Brooks <mlbrooks@…>, 5 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.