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 | } |
---|
23 | |
---|
24 | #include <exception.hfa> |
---|
25 | TRIVIAL_EXCEPTION(ht_fill_limit_crossed); |
---|
26 | |
---|
27 | |
---|
28 | #include <containers/list.hfa> |
---|
29 | |
---|
30 | trait has_hash( otype K ) { |
---|
31 | size_t hash(K); |
---|
32 | int ?==?( K, K ); |
---|
33 | }; |
---|
34 | |
---|
35 | trait hkey( otype K, dtype tN | has_hash(K) ) { |
---|
36 | K key(tN &); |
---|
37 | }; |
---|
38 | |
---|
39 | forall( 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 | }; |
---|
50 | |
---|
51 | float fill_frac( hashtable(K, tN, tE) & this ) with(this) { |
---|
52 | 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 | } |
---|
64 | } |
---|
65 | |
---|
66 | size_t bucket_of( hashtable(K, tN, tE) & this, K k ) { |
---|
67 | return hash(k) % this.n_buckets; |
---|
68 | } |
---|
69 | |
---|
70 | tE & get( hashtable(K, tN, tE) & this, K k ) with (this) { |
---|
71 | |
---|
72 | dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ]; |
---|
73 | |
---|
74 | for ( tN * item = & $tempcv_e2n(bucket`first); item != 0p; item = & $tempcv_e2n((*item)`next) ) { |
---|
75 | if ( key(*item) == k ) { |
---|
76 | return *item; |
---|
77 | } |
---|
78 | } |
---|
79 | |
---|
80 | return *0p; |
---|
81 | } |
---|
82 | |
---|
83 | void check_ff_warning( hashtable(K, tN, tE) & this ) with (this) { |
---|
84 | if (fill_frac(this) > ff_next_warn_up) { |
---|
85 | throwResume &(ht_fill_limit_crossed){}; |
---|
86 | ff_next_warn_up *= 2; |
---|
87 | } |
---|
88 | } |
---|
89 | |
---|
90 | void put( hashtable(K, tN, tE) & this, tE & v ) with (this) { |
---|
91 | |
---|
92 | check_ff_warning(this); |
---|
93 | |
---|
94 | K k = key( $tempcv_e2n(v) ); |
---|
95 | dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ]; |
---|
96 | |
---|
97 | for ( tN * item = & $tempcv_e2n(bucket`first); item != 0p; item = & $tempcv_e2n((*item)`next) ) { |
---|
98 | if ( key(*item) == k ) { |
---|
99 | remove(*item); |
---|
100 | break; |
---|
101 | } |
---|
102 | } |
---|
103 | |
---|
104 | insert_first(bucket, v); |
---|
105 | this.item_count ++; |
---|
106 | } |
---|
107 | |
---|
108 | } |
---|
109 | |
---|
110 | |
---|
111 | |
---|
112 | struct request { |
---|
113 | |
---|
114 | unsigned int src_id; |
---|
115 | unsigned int tgt_id; |
---|
116 | |
---|
117 | |
---|
118 | |
---|
119 | DLISTED_MGD_EXPL_IN(request, ht_by_src) |
---|
120 | DLISTED_MGD_EXPL_IN(request, ht_by_tgt) |
---|
121 | }; |
---|
122 | DLISTED_MGD_EXPL_OUT(request, ht_by_src) |
---|
123 | DLISTED_MGD_EXPL_OUT(request, ht_by_tgt) |
---|
124 | |
---|
125 | size_t hash( unsigned int k ) { |
---|
126 | // not really a hash function, not really the point |
---|
127 | return k; |
---|
128 | } |
---|
129 | |
---|
130 | unsigned int key( request_in_ht_by_src & v ) { |
---|
131 | return v.src_id; |
---|
132 | } |
---|
133 | |
---|
134 | |
---|
135 | |
---|
136 | |
---|
137 | int main() { |
---|
138 | |
---|
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 ); |
---|
146 | |
---|
147 | request & wasnt_found = get(h_src, 17); |
---|
148 | assert( &wasnt_found == 0p ); |
---|
149 | |
---|
150 | request r; |
---|
151 | r.src_id = 117; |
---|
152 | r.tgt_id = 998; |
---|
153 | |
---|
154 | put(h_src, r); |
---|
155 | |
---|
156 | request & found = get(h_src, 117); |
---|
157 | assert( &found == &r ); |
---|
158 | |
---|
159 | & wasnt_found = & get(h_src, 998); |
---|
160 | assert( &wasnt_found == 0p ); |
---|
161 | |
---|
162 | printf( "%f\n", fill_frac(h_src) ); |
---|
163 | |
---|
164 | |
---|
165 | request rs[500]; |
---|
166 | try { |
---|
167 | for (i; 500) { |
---|
168 | rs[i].src_id = 8000 * i; |
---|
169 | put(h_src, rs[i]); |
---|
170 | } |
---|
171 | } catchResume(ht_fill_limit_crossed*) { |
---|
172 | printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src)); |
---|
173 | } |
---|
174 | |
---|
175 | assert( & get(h_src, 117 ) ); |
---|
176 | assert( & get(h_src, 8000*25 ) ); |
---|
177 | assert(! & get(h_src, 8000*25+1) ); |
---|
178 | |
---|
179 | free(firstAlloc); |
---|
180 | |
---|
181 | } |
---|