source: examples/hashtable.cfa @ d6d1f80

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

Adding an example of lists and exceptions collaborating on a hashtable. On dlist, added existing routines to the dlist trait (public interface).

  • Property mode set to 100644
File size: 4.1 KB
Line 
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)
12forall( ztype(Zn), otype Te )
13struct array {
14  Te items[z(Zn)];
15};
16
17// subscript operator for known-size array
18forall( 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>
25TRIVIAL_EXCEPTION(ht_fill_limit_crossed);
26
27
28#include <containers/list.hfa>
29
30trait has_hash( otype K ) {
31    size_t hash(K);
32    int ?==?( K, K );
33};
34
35trait hkey( otype K, dtype tN | has_hash(K) ) {
36    K key(tN &);
37};
38
39forall( 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
112struct 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};
122DLISTED_MGD_EXPL_OUT(request, ht_by_src)
123DLISTED_MGD_EXPL_OUT(request, ht_by_tgt)
124
125size_t hash( unsigned int k ) {
126    // not really a hash function, not really the point
127    return k;
128}
129
130unsigned int key( request_in_ht_by_src & v ) {
131    return v.src_id;
132}
133
134
135
136
137int 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}
Note: See TracBrowser for help on using the repository browser.