Changeset 8b58bae for examples/hashtable.cfa

Timestamp:

Jun 24, 2020, 5:00:59 PM (4 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

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

Children:

c953163

Parents:

9791ab5 (diff), 7f9968a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' into relaxed_ready

File:

• examples/hashtable.cfa (modified) (9 diffs)

examples/hashtable.cfa

@@ -1 @@
-// 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 <containers/list.hfa>
 
 #include <exception.hfa>
@@ -26 +6 @@
 
 
-#include <containers/list.hfa>
+
+void defaultResumptionHandler(ht_fill_limit_crossed &) {
+    printf("default resumption ht_fill_limit_crossed\n");
+}
+
+void defaultTerminationHandler(ht_fill_limit_crossed &) = void;
+
 
 trait has_hash( otype K ) {
@@ -41 +27 @@
     struct hashtable {
 
+        size_t n_buckets;
+        dlist(tN, tE) *buckets;
+        
         size_t item_count;
-        size_t n_buckets;
-
         float ff_next_warn_up;
 
-        dlist(tN, tE) buckets[ 0 ];
+        void (*defaultResumptionHandler) (ht_fill_limit_crossed &);
     };
+
+    void ?{}( hashtable(K, tN, tE) & this ) = void;
+}
+
+forall( otype K, dtype tN, dtype tE | $dlistable(tN, tE) | hkey(K, tN) | { void defaultResumptionHandler(ht_fill_limit_crossed &); } ) {
+
+    void ?{}( hashtable(K, tN, tE) & this, size_t n_buckets, dlist(tN, tE) *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 K, dtype tN, dtype tE | $dlistable(tN, tE) | hkey(K, tN) ) {
 
     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] );
-        }
     }
 
@@ -83 +82 @@
     void check_ff_warning( hashtable(K, tN, tE) & this ) with (this) {
         if (fill_frac(this) > ff_next_warn_up) {
-            throwResume &(ht_fill_limit_crossed){};
+            throwResume (ht_fill_limit_crossed){};
             ff_next_warn_up *= 2;
         }
@@ -108 +107 @@
 }
 
+// tactical usage:
+// HASHTABLE_STATIC(int, item_by_prority, item, n, ht)
+//
+// intended equivalent:
+// hashtable_static(int, item_by_prority, item, Z(n)) ht;
+#define HASHTABLE_STATIC(K, tN, tE, n_buckets, obj) \
+    struct __hashtable_static_ ## obj { \
+        inline hashtable(K, tN, tE); \
+        dlist(tN, tE) $items[n_buckets]; \
+    }; \
+    void ?{}( __hashtable_static_ ## obj & this )  { \
+        ((hashtable(K, tN, tE) &)this){ n_buckets, this.$items }; \
+    } \
+    __hashtable_static_ ## obj obj;
+
+
+
+trait heaped(dtype T) {
+    T * alloc( size_t );
+    void free( void * ); 
+};
+
+void __dynamic_defaultResumptionHandler(ht_fill_limit_crossed & ex) {
+    printf("dynamic limit crossed\n");
+}
+
+forall( otype K, dtype tN, dtype tE | $dlistable(tN, tE) | hkey(K, tN) | heaped( dlist(tN, tE) ) ) {
+
+    struct hashtable_dynamic { 
+        inline hashtable(K, tN, tE); 
+    };
+    void ?{}( hashtable_dynamic(K, tN, tE) & this, size_t n_buckets )  {
+        void (*defaultResumptionHandler) (ht_fill_limit_crossed &) = __dynamic_defaultResumptionHandler;
+        dlist(tN, tE) *buckets = alloc(n_buckets);
+        ((hashtable(K, tN, tE) &)this){ n_buckets, buckets };
+    }
+    void ^?{}( hashtable_dynamic(K, tN, tE) & this ) {
+        free(this.buckets);
+    }
+}
+
+
 
 
@@ -114 +155 @@
     unsigned int src_id;
     unsigned int tgt_id;
-
-
 
     DLISTED_MGD_EXPL_IN(request, ht_by_src)
@@ -133 +172 @@
 
 
-
+#include <stdlib.hfa>
 
 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 );
+
+    HASHTABLE_STATIC(unsigned int, request_in_ht_by_src, request, 67, h_src)
 
     request & wasnt_found = get(h_src, 17);
@@ -171 +205 @@
     } catchResume(ht_fill_limit_crossed*) {
         printf("fill limit tripped with h_src filled at %f\n", fill_frac(h_src));
+        throwResume;
     }
 
@@ -177 +212 @@
     assert(! & get(h_src, 8000*25+1) );
 
-    free(firstAlloc);
-
-}
+
+
+    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_dynamic(unsigned int, request_in_ht_by_src, request) 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;
+    }
+
+
+}