[df733ed] | 1 | |
---|
| 2 | #include <containers/list.hfa> |
---|
| 3 | |
---|
| 4 | typedef unsigned int K; |
---|
| 5 | |
---|
| 6 | // workaround type for trac#185; used here as the ticket's examples use a spontaneous float |
---|
| 7 | typedef struct {} t_unused; |
---|
| 8 | |
---|
| 9 | struct request { |
---|
| 10 | |
---|
| 11 | unsigned int src_id; |
---|
| 12 | unsigned int tgt_id; |
---|
| 13 | |
---|
| 14 | DLISTED_MGD_EXPL_IN(request, ht_by_src) |
---|
| 15 | DLISTED_MGD_EXPL_IN(request, ht_by_tgt) |
---|
| 16 | }; |
---|
| 17 | DLISTED_MGD_EXPL_OUT(request, ht_by_src) |
---|
| 18 | DLISTED_MGD_EXPL_OUT(request, ht_by_tgt) |
---|
| 19 | |
---|
| 20 | size_t hash( unsigned int k ) { |
---|
| 21 | // not really a hash function, not really the point |
---|
| 22 | return k; |
---|
| 23 | } |
---|
| 24 | |
---|
| 25 | unsigned int key( request_in_ht_by_src & v ) { |
---|
| 26 | return v.src_id; |
---|
| 27 | } |
---|
| 28 | |
---|
| 29 | |
---|
| 30 | #include <exception.hfa> |
---|
| 31 | |
---|
[8fc6e92a] | 32 | DATA_EXCEPTION(ht_fill_limit_crossed)( |
---|
| 33 | void * theHashtable; |
---|
| 34 | ); |
---|
[df733ed] | 35 | |
---|
[8fc6e92a] | 36 | void ?{}(ht_fill_limit_crossed & this, void * theHashtable) { |
---|
| 37 | VTABLE_INIT(this, ht_fill_limit_crossed); |
---|
| 38 | this.theHashtable = theHashtable; |
---|
| 39 | } |
---|
[df733ed] | 40 | |
---|
[8fc6e92a] | 41 | const char * ht_fill_limit_crossed_msg(ht_fill_limit_crossed * this) { |
---|
| 42 | return "ht_fill_limit_crossed"; |
---|
[df733ed] | 43 | } |
---|
| 44 | |
---|
[8fc6e92a] | 45 | VTABLE_INSTANCE(ht_fill_limit_crossed)(ht_fill_limit_crossed_msg); |
---|
| 46 | |
---|
| 47 | |
---|
| 48 | |
---|
[df733ed] | 49 | |
---|
| 50 | trait pretendsToMatter( dtype TTT ) { |
---|
| 51 | void actsmart(TTT &); |
---|
| 52 | }; |
---|
| 53 | |
---|
| 54 | forall( dtype TTTx ) |
---|
| 55 | void actsmart(TTTx &) {} |
---|
| 56 | |
---|
| 57 | // probable bug, wrt otype Tt_unused... |
---|
| 58 | // 1. changing to dtype Tt_unused crashes GenPoly |
---|
| 59 | // 2. declaring function check_ff_warning as concrete, i.e. operating on type hashtable_rbs(t_unused) makes cfa-cc generate bad C |
---|
| 60 | // in both cases, it's on the throwResume call |
---|
| 61 | // where it implicitly uses this.defaultResumptionHandler as a throwResume argument |
---|
| 62 | // whereas that, of course, has to be surrounded in a cast |
---|
| 63 | // at GenPoly breakpoint, type of said cast appears as CFA generic struct, even as the "this" parameter appears as C struct; casted type ... |
---|
| 64 | // 1. is hashtable_rbs(Tt_unused); assertion complains you don't need a type arg here |
---|
| 65 | // 2. shows up in -CFA output as hashtable_rbs(), which is bad C; expecting hashtable_rbs* |
---|
| 66 | |
---|
| 67 | forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) { |
---|
| 68 | |
---|
| 69 | // hashtable of request by source |
---|
| 70 | struct hashtable_rbs { |
---|
| 71 | |
---|
| 72 | size_t n_buckets; |
---|
| 73 | dlist(request_in_ht_by_src, request) *buckets; |
---|
| 74 | |
---|
| 75 | size_t item_count; |
---|
| 76 | float ff_next_warn_up; |
---|
| 77 | |
---|
| 78 | void (*defaultResumptionHandler) (ht_fill_limit_crossed &); |
---|
| 79 | }; |
---|
| 80 | |
---|
| 81 | void ?{}( hashtable_rbs(Tt_unused) & this ) = void; |
---|
| 82 | } |
---|
| 83 | |
---|
| 84 | forall( otype Tt_unused | pretendsToMatter(Tt_unused) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) { |
---|
| 85 | |
---|
| 86 | void ?{}( hashtable_rbs(Tt_unused) & this, size_t n_buckets, dlist(request_in_ht_by_src, request) *buckets ) { |
---|
| 87 | |
---|
| 88 | this.n_buckets = n_buckets; |
---|
| 89 | this.buckets = buckets; |
---|
| 90 | |
---|
| 91 | this.item_count = 0; |
---|
| 92 | this.ff_next_warn_up = 0.5; |
---|
| 93 | |
---|
| 94 | this.defaultResumptionHandler = defaultResumptionHandler; |
---|
| 95 | |
---|
| 96 | for ( i; n_buckets ) { |
---|
| 97 | ?{}( this.buckets[i] ); |
---|
| 98 | } |
---|
| 99 | } |
---|
| 100 | } |
---|
| 101 | |
---|
[8fc6e92a] | 102 | |
---|
[df733ed] | 103 | forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) { |
---|
| 104 | |
---|
| 105 | float fill_frac( hashtable_rbs(Tt_unused) & this ) with(this) { |
---|
| 106 | return ((float)item_count) / n_buckets; |
---|
| 107 | } |
---|
| 108 | |
---|
| 109 | size_t bucket_of( hashtable_rbs(Tt_unused) & this, K k ) { |
---|
| 110 | return hash(k) % this.n_buckets; |
---|
| 111 | } |
---|
| 112 | |
---|
| 113 | request & get( hashtable_rbs(Tt_unused) & this, K k ) with (this) { |
---|
| 114 | |
---|
| 115 | dlist(request_in_ht_by_src, request) & bucket = buckets[ bucket_of(this, k) ]; |
---|
| 116 | |
---|
| 117 | for ( request_in_ht_by_src * item = & $tempcv_e2n(bucket`first); item != 0p; item = & $tempcv_e2n((*item)`next) ) { |
---|
| 118 | if ( key(*item) == k ) { |
---|
| 119 | return *item; |
---|
| 120 | } |
---|
| 121 | } |
---|
| 122 | |
---|
| 123 | return *0p; |
---|
| 124 | } |
---|
| 125 | |
---|
| 126 | void check_ff_warning( hashtable_rbs(Tt_unused) & this ) with (this) { |
---|
| 127 | if (fill_frac(this) > ff_next_warn_up) { |
---|
[8fc6e92a] | 128 | throwResume (ht_fill_limit_crossed){ &this }; |
---|
[df733ed] | 129 | } |
---|
| 130 | } |
---|
| 131 | |
---|
| 132 | void put( hashtable_rbs(Tt_unused) & this, request & v ) with (this) { |
---|
| 133 | |
---|
| 134 | check_ff_warning(this); |
---|
| 135 | |
---|
| 136 | K k = key( $tempcv_e2n(v) ); |
---|
| 137 | dlist(request_in_ht_by_src, request) & bucket = buckets[ bucket_of(this, k) ]; |
---|
| 138 | |
---|
| 139 | for ( request_in_ht_by_src * item = & $tempcv_e2n(bucket`first); item != 0p; item = & $tempcv_e2n((*item)`next) ) { |
---|
| 140 | if ( key(*item) == k ) { |
---|
| 141 | remove(*item); |
---|
| 142 | break; |
---|
| 143 | } |
---|
| 144 | } |
---|
| 145 | |
---|
| 146 | insert_first(bucket, v); |
---|
| 147 | this.item_count ++; |
---|
| 148 | } |
---|
| 149 | } |
---|
| 150 | |
---|
[8fc6e92a] | 151 | |
---|
| 152 | |
---|
| 153 | |
---|
[df733ed] | 154 | // tactical usage: |
---|
| 155 | // HASHTABLE_RBS_STATIC(n, ht) |
---|
| 156 | // |
---|
| 157 | // intended equivalent: |
---|
| 158 | // hashtable_rbs_static(Z(n)) ht; |
---|
| 159 | #define HASHTABLE_RBS_STATIC(n_buckets, obj) \ |
---|
| 160 | struct __hashtable_static_ ## obj { \ |
---|
| 161 | inline hashtable_rbs(t_unused); \ |
---|
| 162 | dlist(request_in_ht_by_src, request) $items[n_buckets]; \ |
---|
| 163 | }; \ |
---|
| 164 | void ?{}( __hashtable_static_ ## obj & this ) { \ |
---|
| 165 | ((hashtable_rbs(t_unused) &)this){ n_buckets, this.$items }; \ |
---|
| 166 | } \ |
---|
| 167 | __hashtable_static_ ## obj obj; |
---|
| 168 | |
---|
| 169 | |
---|
| 170 | |
---|
[8fc6e92a] | 171 | void 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 | |
---|
| 177 | void defaultTerminationHandler(ht_fill_limit_crossed &) = void; |
---|
| 178 | |
---|
| 179 | |
---|
| 180 | |
---|
| 181 | |
---|
| 182 | |
---|
[df733ed] | 183 | trait heaped(dtype T) { |
---|
| 184 | T * alloc( size_t ); |
---|
| 185 | void free( void * ); |
---|
| 186 | }; |
---|
| 187 | |
---|
[8fc6e92a] | 188 | void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed &); |
---|
[df733ed] | 189 | |
---|
[8fc6e92a] | 190 | forall( otype Tt_unused ) { |
---|
[df733ed] | 191 | |
---|
| 192 | struct hashtable_rbs_dynamic { |
---|
[8fc6e92a] | 193 | inline hashtable_rbs(Tt_unused); |
---|
| 194 | dlist(request_in_ht_by_src, request) * (*alloc)( size_t ); |
---|
| 195 | void (*free)( void * ); |
---|
[df733ed] | 196 | }; |
---|
[8fc6e92a] | 197 | } |
---|
| 198 | |
---|
| 199 | // will be in list api |
---|
| 200 | void 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 | |
---|
| 209 | forall( otype Tt_unused | heaped( dlist(request_in_ht_by_src, request) ) ) { |
---|
| 210 | |
---|
| 211 | void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, size_t n_buckets ) { |
---|
[df733ed] | 212 | void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler; |
---|
| 213 | dlist(request_in_ht_by_src, request) *buckets = alloc(n_buckets); |
---|
[8fc6e92a] | 214 | ((hashtable_rbs(Tt_unused) &)this){ n_buckets, buckets }; |
---|
| 215 | this.alloc = alloc; |
---|
| 216 | this.free = free; |
---|
[df733ed] | 217 | } |
---|
[8fc6e92a] | 218 | void ^?{}( hashtable_rbs_dynamic(Tt_unused) & this ) { |
---|
[df733ed] | 219 | free(this.buckets); |
---|
| 220 | } |
---|
[8fc6e92a] | 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 | |
---|
| 243 | forall( 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 | |
---|
| 249 | void __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 ); |
---|
[df733ed] | 253 | } |
---|
| 254 | |
---|
| 255 | |
---|
| 256 | |
---|
| 257 | |
---|
| 258 | |
---|
| 259 | |
---|
| 260 | #include <stdlib.hfa> |
---|
| 261 | |
---|
| 262 | int main() { |
---|
| 263 | |
---|
| 264 | |
---|
| 265 | HASHTABLE_RBS_STATIC(67, h_src) |
---|
| 266 | |
---|
| 267 | request & wasnt_found = get(h_src, 17); |
---|
| 268 | assert( &wasnt_found == 0p ); |
---|
| 269 | |
---|
| 270 | request r; |
---|
| 271 | r.src_id = 117; |
---|
| 272 | r.tgt_id = 998; |
---|
| 273 | |
---|
| 274 | put(h_src, r); |
---|
| 275 | |
---|
| 276 | request & found = get(h_src, 117); |
---|
| 277 | assert( &found == &r ); |
---|
| 278 | |
---|
| 279 | & wasnt_found = & get(h_src, 998); |
---|
| 280 | assert( &wasnt_found == 0p ); |
---|
| 281 | |
---|
| 282 | printf( "%f\n", fill_frac(h_src) ); |
---|
| 283 | |
---|
| 284 | |
---|
| 285 | request rs[500]; |
---|
| 286 | try { |
---|
| 287 | for (i; 500) { |
---|
| 288 | rs[i].src_id = 8000 * i; |
---|
| 289 | put(h_src, rs[i]); |
---|
| 290 | } |
---|
| 291 | } catchResume(ht_fill_limit_crossed*) { |
---|
| 292 | printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src)); |
---|
| 293 | throwResume; |
---|
| 294 | } |
---|
| 295 | |
---|
| 296 | assert( & get(h_src, 117 ) ); |
---|
| 297 | assert( & get(h_src, 8000*25 ) ); |
---|
| 298 | assert(! & get(h_src, 8000*25+1) ); |
---|
| 299 | |
---|
| 300 | |
---|
| 301 | |
---|
| 302 | dlist(request_in_ht_by_src, request) * (*old_alloc)( size_t ) = alloc; |
---|
| 303 | dlist(request_in_ht_by_src, request) * alloc( size_t n ) { |
---|
| 304 | dlist(request_in_ht_by_src, request) * ret = old_alloc(n); |
---|
| 305 | printf("alloc'ed at %p\n", ret); |
---|
| 306 | return ret; |
---|
| 307 | } |
---|
| 308 | |
---|
| 309 | void (*old_free)( void * ) = free; |
---|
| 310 | void free( void * o ) { |
---|
| 311 | printf("free'ing at %p\n", o); |
---|
| 312 | old_free(o); |
---|
| 313 | } |
---|
| 314 | |
---|
| 315 | hashtable_rbs_dynamic(t_unused) ht2 = { 113 }; |
---|
| 316 | request rs2[500]; |
---|
| 317 | try { |
---|
| 318 | for (i; 500) { |
---|
| 319 | if (i % 10 == 0) {printf("%d(%f),", i, fill_frac(ht2));} |
---|
| 320 | rs2[i].src_id = 8000 * i; |
---|
| 321 | put(ht2, rs2[i]); |
---|
| 322 | } |
---|
| 323 | } catchResume(ht_fill_limit_crossed*) { |
---|
| 324 | printf("fill limit tripped with ht2 filled at %f\n", fill_frac(ht2)); |
---|
| 325 | throwResume; |
---|
| 326 | } |
---|
| 327 | |
---|
| 328 | |
---|
| 329 | } |
---|