Changeset 8fc6e92a for examples/hashtable2.cfa

Timestamp:

Jun 18, 2020, 10:03:20 PM (4 years ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

1d2314f

Parents:

df733ed

Message:

Hashtable demo (non-generic version) does dynamic resizing via exception.

File:

• examples/hashtable2.cfa (modified) (6 diffs)

examples/hashtable2.cfa

@@ -29 +29 @@
 
 #include <exception.hfa>
-TRIVIAL_EXCEPTION(ht_fill_limit_crossed);
-
-
-
-void defaultResumptionHandler(ht_fill_limit_crossed &) {
-    printf("default resumption ht_fill_limit_crossed\n");
-}
-
-void defaultTerminationHandler(ht_fill_limit_crossed &) = void;
+
+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 ) {
@@ -91 +100 @@
 }
 
+
 forall( otype Tt_unused | pretendsToMatter(Tt_unused) ) {
 
@@ -116 +126 @@
     void check_ff_warning( hashtable_rbs(Tt_unused) & this ) with (this) {
         if (fill_frac(this) > ff_next_warn_up) {
-            throwResume (ht_fill_limit_crossed){};
-            ff_next_warn_up *= 2;
+            throwResume (ht_fill_limit_crossed){ &this };
         }
     }
@@ -139 +148 @@
     }
 }
+
+
+
 
 // tactical usage:
@@ -157 +169 @@
 
 
+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 );
@@ -162 +186 @@
 };
 
-void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) {
-    printf("dynamic limit crossed\n");
-}
-
-forall( | heaped( dlist(request_in_ht_by_src, request) ) ) {
+void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed &);
+
+forall( otype Tt_unused ) {
 
     struct hashtable_rbs_dynamic { 
-        inline hashtable_rbs(t_unused); 
+        inline hashtable_rbs(Tt_unused);
+        dlist(request_in_ht_by_src, request) * (*alloc)( size_t );
+        void (*free)( void * ); 
     };
-    void ?{}( hashtable_rbs_dynamic(t_unused) & this, size_t n_buckets )  {
+}
+
+// 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(t_unused) &)this){ n_buckets, buckets };
-    }
-    void ^?{}( hashtable_rbs_dynamic(t_unused) & this ) {
+        ((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 );
 }