source: examples/hashtable.cfa @ d6d1f80

// a type whose size is n
#define Z(n) char[n]

// the inverse of Z(-)
#define z(Zn) sizeof(Zn)

// if you're expecting a Z(n), say so, by asking for a ztype, instead of dtype or otype
#define ztype(Zn) dtype Zn | sized(Zn)

// a "known-size" array
// an array of length n, whose elements are of Te, letting n be such that Zn is Z(n)
forall( ztype(Zn), otype Te )
struct array {
  Te items[z(Zn)];
};

// subscript operator for known-size array
forall( ztype(Zn), otype Te ) {
  Te & ?[?]( array(Zn, Te) &this, size_t idx ) with(this) {
    return items[idx];
  }
}

#include <exception.hfa>
TRIVIAL_EXCEPTION(ht_fill_limit_crossed);


#include <containers/list.hfa>

trait has_hash( otype K ) {
    size_t hash(K);
    int ?==?( K, K );
};

trait hkey( otype K, dtype tN | has_hash(K) ) {
    K key(tN &);
};

forall( otype K, dtype tN, dtype tE | $dlistable(tN, tE) | hkey(K, tN) ) {

    struct hashtable {

        size_t item_count;
        size_t n_buckets;

        float ff_next_warn_up;

        dlist(tN, tE) buckets[ 0 ];
    };

    float fill_frac( hashtable(K, tN, tE) & this ) with(this) {
        return ((float)item_count) / n_buckets;
    }

    void ?{}( hashtable(K, tN, tE) & this, int n_buckets ) {

        this.item_count = 0;
        this.n_buckets = n_buckets;
        this.ff_next_warn_up = 0.5;

        for ( int i = 0; i < n_buckets; i++ ) {
            ?{}( this.buckets[i] );
        }
    }

    size_t bucket_of( hashtable(K, tN, tE) & this, K k ) {
        return hash(k) % this.n_buckets;
    }

    tE & get( hashtable(K, tN, tE) & this, K k ) with (this) {

        dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ];

        for ( tN * item = & $tempcv_e2n(bucket`first);  item != 0p;  item = & $tempcv_e2n((*item)`next) ) {
            if ( key(*item) == k ) {
                return *item;
            }
        }

        return *0p;
    }

    void check_ff_warning( hashtable(K, tN, tE) & this ) with (this) {
        if (fill_frac(this) > ff_next_warn_up) {
            throwResume &(ht_fill_limit_crossed){};
            ff_next_warn_up *= 2;
        }
    }

    void put( hashtable(K, tN, tE) & this, tE & v ) with (this) {

        check_ff_warning(this);

        K k = key( $tempcv_e2n(v) );
        dlist(tN, tE) & bucket = buckets[ bucket_of(this, k) ];

        for ( tN * item = & $tempcv_e2n(bucket`first);  item != 0p;  item = & $tempcv_e2n((*item)`next) ) {
            if ( key(*item) == k ) {
                remove(*item);
                break;
            }
        }

        insert_first(bucket, v);
        this.item_count ++;
    }

}



struct request {

    unsigned int src_id;
    unsigned int tgt_id;



    DLISTED_MGD_EXPL_IN(request, ht_by_src)
    DLISTED_MGD_EXPL_IN(request, ht_by_tgt)
};
DLISTED_MGD_EXPL_OUT(request, ht_by_src)
DLISTED_MGD_EXPL_OUT(request, ht_by_tgt)

size_t hash( unsigned int k ) {
    // not really a hash function, not really the point
    return k;
}

unsigned int key( request_in_ht_by_src & v ) {
    return v.src_id;
}




int main() {

    void *firstAlloc = malloc( sizeof( hashtable(unsigned int, request_in_ht_by_src, request))
                             + sizeof( dlist(request_in_ht_by_src, request) [67] )
                             );
    hashtable(unsigned int, request_in_ht_by_src, request) & h_src =
        * (hashtable(unsigned int, request_in_ht_by_src, request) *) firstAlloc;
    
    ?{}( h_src, 67 );

    request & wasnt_found = get(h_src, 17);
    assert( &wasnt_found == 0p );

    request r;
    r.src_id = 117;
    r.tgt_id = 998;

    put(h_src, r);

    request & found = get(h_src, 117);
    assert( &found == &r );

    & wasnt_found = & get(h_src, 998);
    assert( &wasnt_found == 0p );

    printf( "%f\n", fill_frac(h_src) );


    request rs[500];
    try {
        for (i; 500) {
            rs[i].src_id = 8000 * i;
            put(h_src, rs[i]);
        }
    } catchResume(ht_fill_limit_crossed*) {
        printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src));
    }

    assert(  & get(h_src, 117      ) );
    assert(  & get(h_src, 8000*25  ) );
    assert(! & get(h_src, 8000*25+1) );

    free(firstAlloc);

}