source: examples/hashtable2.cfa @ 6c4bd02

#include <containers/list.hfa>

typedef unsigned int K;

// workaround type for trac#185; used here as the ticket's examples use a spontaneous float
typedef struct {} t_unused;

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;
}


#include <exception.hfa>

DATA_EXCEPTION(ht_fill_limit_crossed)(
        void * theHashtable;
);

void ?{}(ht_fill_limit_crossed & this, void * theHashtable) {
        VTABLE_INIT(this, ht_fill_limit_crossed);
        this.theHashtable = theHashtable;
}

const char * ht_fill_limit_crossed_msg(ht_fill_limit_crossed * this) {
        return "ht_fill_limit_crossed";
}

VTABLE_INSTANCE(ht_fill_limit_crossed)(ht_fill_limit_crossed_msg);




trait pretendsToMatter( dtype TTT ) {
    void actsmart(TTT &);
};

forall( dtype TTTx )
void actsmart(TTTx &) {}

// probable bug, wrt otype Tt_unused...
//   1. changing to dtype Tt_unused crashes GenPoly
//   2. declaring function check_ff_warning as concrete, i.e. operating on type hashtable_rbs(t_unused) makes cfa-cc generate bad C
// in both cases, it's on the throwResume call
// where it implicitly uses this.defaultResumptionHandler as a throwResume argument
// whereas that, of course, has to be surrounded in a cast
// at GenPoly breakpoint, type of said cast appears as CFA generic struct, even as the "this" parameter appears as C struct; casted type ...
//   1. is hashtable_rbs(Tt_unused); assertion complains you don't need a type arg here
//   2. shows up in -CFA output as hashtable_rbs(), which is bad C; expecting hashtable_rbs*

forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) {

    // hashtable of request by source
    struct hashtable_rbs {

        size_t n_buckets;
        dlist(request_in_ht_by_src, request) *buckets;
        
        size_t item_count;
        float ff_next_warn_up;

        void (*defaultResumptionHandler) (ht_fill_limit_crossed &);
    };

    void ?{}( hashtable_rbs(Tt_unused) & this ) = void;
}

forall( otype Tt_unused | pretendsToMatter(Tt_unused) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) {

    void ?{}( hashtable_rbs(Tt_unused) & this, size_t n_buckets, dlist(request_in_ht_by_src, request) *buckets ) {

        this.n_buckets = n_buckets;
        this.buckets = buckets;

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

        this.defaultResumptionHandler = defaultResumptionHandler;

        for ( i; n_buckets ) {
            ?{}( this.buckets[i] );
        }
    }
}


forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) {

    float fill_frac( hashtable_rbs(Tt_unused) & this ) with(this) {
        return ((float)item_count) / n_buckets;
    }

    size_t bucket_of( hashtable_rbs(Tt_unused) & this, K k ) {
        return hash(k) % this.n_buckets;
    }

    request & get( hashtable_rbs(Tt_unused) & this, K k ) with (this) {

        dlist(request_in_ht_by_src, request) & bucket = buckets[ bucket_of(this, k) ];

        for ( request_in_ht_by_src * 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_rbs(Tt_unused) & this ) with (this) {
        if (fill_frac(this) > ff_next_warn_up) {
            throwResume (ht_fill_limit_crossed){ &this };
        }
    }

    void put( hashtable_rbs(Tt_unused) & this, request & v ) with (this) {

        check_ff_warning(this);

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

        for ( request_in_ht_by_src * 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 ++;
    }
}




// tactical usage:
// HASHTABLE_RBS_STATIC(n, ht)
//
// intended equivalent:
// hashtable_rbs_static(Z(n)) ht;
#define HASHTABLE_RBS_STATIC(n_buckets, obj) \
    struct __hashtable_static_ ## obj { \
        inline hashtable_rbs(t_unused); \
        dlist(request_in_ht_by_src, request) $items[n_buckets]; \
    }; \
    void ?{}( __hashtable_static_ ## obj & this )  { \
        ((hashtable_rbs(t_unused) &)this){ n_buckets, this.$items }; \
    } \
    __hashtable_static_ ## obj obj;



void defaultResumptionHandler(ht_fill_limit_crossed & ex) {
    printf("default resumption ht_fill_limit_crossed\n");
    hashtable_rbs(t_unused) & ht = *(hashtable_rbs(t_unused) *)ex.theHashtable;
    ht.ff_next_warn_up *= 2;
}

void defaultTerminationHandler(ht_fill_limit_crossed &) = void;





trait heaped(dtype T) {
    T * alloc( size_t );
    void free( void * ); 
};

void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed &);

forall( otype Tt_unused ) {

    struct hashtable_rbs_dynamic { 
        inline hashtable_rbs(Tt_unused);
        dlist(request_in_ht_by_src, request) * (*alloc)( size_t );
        void (*free)( void * ); 
    };
}

// will be in list api
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 ) {

    // will re-implement as an actual splice
    while ( & src_to_empty`first != 0p ) {
        insert_last( snk_to_fill_at_last, pop_first( src_to_empty ) );
    }
}


forall( otype Tt_unused | heaped( dlist(request_in_ht_by_src, request) ) ) {

    void ?{}( hashtable_rbs_dynamic(Tt_unused) & this, size_t n_buckets )  {
        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler;
        dlist(request_in_ht_by_src, request) *buckets = alloc(n_buckets);
        ((hashtable_rbs(Tt_unused) &)this){ n_buckets, buckets };
        this.alloc = alloc;
        this.free = free;
    }
    void ^?{}( hashtable_rbs_dynamic(Tt_unused) & this ) {
        free(this.buckets);
    }
    void rehashToLarger( hashtable_rbs_dynamic(Tt_unused) & this, size_t new_n_buckets ) with(this) {
        printf("resizing from %ld to %ld, old buckets at %p\n", n_buckets, new_n_buckets, buckets);

        // collect hash items from old buckets
        dlist(request_in_ht_by_src, request) items;
        for (i; n_buckets) {
            splice_all_to_last( buckets[i], items );
        }

        // make empty hash table of new size
        dlist(request_in_ht_by_src, request) *oldBuckets = buckets;
        ^?{}( (hashtable_rbs(Tt_unused) &)this );
        free( oldBuckets );
        ?{}( (hashtable_rbs(Tt_unused) &)this, new_n_buckets, alloc(new_n_buckets) );

        // fill new table with old items
        while ( & items`first != 0p ) {
            put( this, pop_first( items ) );
        }
    }
}

forall( otype Tt_unused ) {
    void rehashToLarger_STEP( hashtable_rbs_dynamic(Tt_unused) & this, size_t new_n_buckets ) with (this) {
        rehashToLarger( this, new_n_buckets );
    }
}

void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) {
    hashtable_rbs_dynamic(t_unused) & ht = *(hashtable_rbs_dynamic(t_unused) *)ex.theHashtable;
    printf("dynamic limit crossed with fill_frac = %f and buckets at %p\n", fill_frac(ht), ht.buckets);
    rehashToLarger_STEP( ht, 2 * ht.n_buckets );
}






#include <stdlib.hfa>

int main() {


    HASHTABLE_RBS_STATIC(67, h_src)

    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));
        throwResume;
    }

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



    dlist(request_in_ht_by_src, request) * (*old_alloc)( size_t ) = alloc;
    dlist(request_in_ht_by_src, request) * alloc( size_t n ) {
        dlist(request_in_ht_by_src, request) * ret = old_alloc(n);
        printf("alloc'ed at %p\n", ret);
        return ret;
    }

    void (*old_free)( void * ) = free;
    void free( void * o ) {
        printf("free'ing at %p\n", o);
        old_free(o);
    }

    hashtable_rbs_dynamic(t_unused) ht2 = { 113 };
    request rs2[500];
    try {
        for (i; 500) {
            if (i % 10 == 0) {printf("%d(%f),", i, fill_frac(ht2));}
            rs2[i].src_id = 8000 * i;
            put(ht2, rs2[i]);
        }
    } catchResume(ht_fill_limit_crossed*) {
        printf("fill limit tripped with ht2 filled at %f\n", fill_frac(ht2));
        throwResume;
    }


}