Changes in / [f674479:da1c772]


Ignore:
Location:
doc/generic_types
Files:
4 added
12 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/evaluation/Makefile

    rf674479 rda1c772  
    2525        $(COMPILE.cfa) $(OUTPUT_OPTION) -c $<
    2626
    27 COBJS = c-stack.o
     27COBJS = c-stack.o c-pair.o
    2828CPPOBJS =
    2929CPPVOBJS = cpp-vstack.o
    30 CFAOBJS = cfa-stack.o
     30CFAOBJS = cfa-stack.o cfa-pair.o
    3131
    3232c-bench: c-bench.c c-bench.d $(COBJS)
  • doc/generic_types/evaluation/bench.h

    rf674479 rda1c772  
    44#include <time.h>
    55
    6 #define N 100000000
     6#define N 50000000
    77
    88long ms_between(clock_t start, clock_t end) {
  • doc/generic_types/evaluation/bench.hpp

    rf674479 rda1c772  
    55#include <time.h>
    66
    7 static const int N = 100000000;
     7static const int N = 50000000;
    88
    99long ms_between(clock_t start, clock_t end) {
  • doc/generic_types/evaluation/c-bench.c

    rf674479 rda1c772  
    11#include <stdlib.h>
    22#include "bench.h"
     3#include "c-pair.h"
    34#include "c-stack.h"
    45
    5 void* copy_int( void* p ) {
     6_Bool* new_bool( _Bool b ) {
     7        _Bool* q = malloc(sizeof(_Bool));
     8        *q = b;
     9        return q;
     10}
     11
     12char* new_char( char c ) {
     13        char* q = malloc(sizeof(char));
     14        *q = c;
     15        return q;
     16}
     17
     18int* new_int( int i ) {
    619        int* q = malloc(sizeof(int));
    7         *q = *(int*)p;
     20        *q = i;
    821        return q;
     22}
     23
     24void* copy_bool( const void* p ) { return new_bool( *(const _Bool*)p ); }
     25
     26void* copy_char( const void* p ) { return new_char( *(const char*)p ); }
     27
     28void* copy_int( const void* p ) { return new_int( *(const int*)p ); }
     29
     30void* copy_pair_bool_char( const void* p ) { return copy_pair( p, copy_bool, copy_char ); }
     31
     32void free_pair_bool_char( void* p ) { free_pair( p, free, free ); }
     33
     34int cmp_bool( const void* a, const void* b ) {
     35        return *(const _Bool*)a == *(const _Bool*)b ? 0 : *(const _Bool*)a < *(const _Bool*)b ? -1 : 1;
     36}
     37
     38int cmp_char( const void* a, const void* b ) {
     39        return *(const char*)a == *(const char*)b ? 0 : *(const char*)a < *(const char*)b ? -1 : 1;
    940}
    1041
     
    1445        struct stack s = new_stack();
    1546        REPEAT_TIMED( "push_int",
    16                 int* x = malloc(sizeof(int));
    17                 *x = rand();
    18                 push_stack(&s, x);
     47                push_stack(&s, new_int( rand() ));
    1948        )
    2049
     
    2554
    2655        TIMED( "clear_int",
    27                 clear_stack(&s);
     56                clear_stack(&s, free);
    2857        )
    2958
    30         int sum;
     59        int max = 0;
    3160        REPEAT_TIMED( "pop_int",
    3261                int* x = pop_stack(&t);
    33                 sum += *x;
     62                if ( *x > max ) { max = *x; }
    3463                free(x);
    3564        )
     65
     66        struct stack s2 = new_stack();
     67        REPEAT_TIMED( "push_bool_char",
     68                push_stack(&s2, new_pair( new_bool( rand() & 0x1 ), new_char( rand() & 0x7F ) ));
     69        )
     70
     71        struct stack t2;
     72        TIMED( "copy_bool_char",
     73                copy_stack(&t2, &s2, copy_pair_bool_char);
     74        )
     75
     76        TIMED( "clear_bool_char",
     77                clear_stack(&s2, free_pair_bool_char);
     78        )
     79
     80        struct pair* max2 = new_pair( new_bool(0), new_char('\0') );
     81        REPEAT_TIMED( "pop_bool_char",
     82                struct pair* x = pop_stack(&t2);
     83                if ( cmp_pair( x, max2, cmp_bool, cmp_char ) > 0 ) {
     84                        free_pair_bool_char( max2 );
     85                        max2 = x;
     86                } else {
     87                        free_pair_bool_char( x );
     88                }
     89        )
     90        free_pair_bool_char( max2 );
    3691}
  • doc/generic_types/evaluation/c-stack.c

    rf674479 rda1c772  
    1111}
    1212
    13 void copy_stack(struct stack* s, struct stack* t, void* (*copy)(void*)) {
     13void copy_stack(struct stack* s, const struct stack* t, void* (*copy)(const void*)) {
    1414        struct stack_node** crnt = &s->head;
    1515        struct stack_node* next = t->head;
     
    2323}
    2424
    25 void clear_stack(struct stack* s) {
     25void clear_stack(struct stack* s, void (*free_el)(void*)) {
    2626        struct stack_node* next = s->head;
    2727        while ( next ) {
    2828                struct stack_node* crnt = next;
    2929                next = crnt->next;
    30                 free(crnt->value);
     30                free_el(crnt->value);
    3131                free(crnt);
    3232        }
  • doc/generic_types/evaluation/c-stack.h

    rf674479 rda1c772  
    99struct stack new_stack();
    1010
    11 void copy_stack(struct stack* dst, struct stack* src, void* (*copy)(void*));
     11void copy_stack(struct stack* dst, const struct stack* src, void* (*copy)(const void*));
    1212
    13 void clear_stack(struct stack* s);
     13void clear_stack(struct stack* s, void (*free_el)(void*));
    1414
    1515_Bool stack_empty(const struct stack* s);
  • doc/generic_types/evaluation/cfa-bench.c

    rf674479 rda1c772  
     1#include <stdlib>
    12#include <stdlib.h>
     3#include "pair"
    24#include "bench.h"
    35#include "cfa-stack.h"
     
    2022        )
    2123
    22         int sum;
     24        int max = 0;
    2325        REPEAT_TIMED( "pop_int",
    24                 sum += pop( &t );
     26                max = max( max, pop( &t ) );
     27        )
     28
     29        stack(pair(_Bool, unsigned char)) s2;
     30        REPEAT_TIMED( "push_bool_char",
     31                push( &s2, (pair(_Bool, unsigned char)){ rand() & 0x1, rand() & 0x7F } );
     32        )
     33
     34        stack(pair(_Bool, unsigned char)) t2;
     35        TIMED( "copy_bool_char",
     36                t2 = s2;
     37        )
     38
     39        TIMED( "clear_bool_char",
     40                clear( &s2 );
     41        )
     42
     43        pair(_Bool, unsigned char) max2 = { (_Bool)0, '\0' };
     44        REPEAT_TIMED( "pop_bool_char",
     45                max2 = max( max2, pop( &t2 ) );
    2546        )
    2647}
  • doc/generic_types/evaluation/cfa-stack.c

    rf674479 rda1c772  
    1 #include <assert>
    21#include <stdlib>
    32#include "cfa-stack.h"
  • doc/generic_types/evaluation/cpp-bench.cpp

    rf674479 rda1c772  
     1#include <algorithm>
    12#include <stdlib.h>
     3#include <utility>
    24#include "bench.hpp"
    35#include "cpp-stack.hpp"
     
    2022        )
    2123
    22         int sum;
     24        int max = 0;
    2325        REPEAT_TIMED( "pop_int",
    24                 sum += t.pop();
     26                max = std::max( max, t.pop() );
     27        )
     28
     29        stack<std::pair<bool, char>> s2;
     30        REPEAT_TIMED( "push_bool_char",
     31                s2.push( std::pair<bool, char>{ rand() & 0x1, rand() & 0x7F } );
     32        )
     33
     34        stack<std::pair<bool,char>> t2;
     35        TIMED( "copy_bool_char",
     36                t2 = s2;
     37        )
     38
     39        TIMED( "clear_bool_char",
     40                s2.clear();
     41        )
     42
     43        std::pair<bool, char> max2 = { false, '\0' };
     44        REPEAT_TIMED( "pop_bool_char",
     45                max2 = std::max( max2, t2.pop() );
    2546        )
    2647}
  • doc/generic_types/evaluation/cpp-vbench.cpp

    rf674479 rda1c772  
     1#include <algorithm>
    12#include <stdlib.h>
    23#include "bench.hpp"
    34#include "cpp-vstack.hpp"
     5#include "object.hpp"
    46
    57int main(int argc, char** argv) {
     
    2022        )
    2123
    22         integer sum;
     24        integer max;
    2325        REPEAT_TIMED( "pop_int",
    24                 sum += t.pop()->as<integer>();
     26                max = std::max( max, t.pop()->as<integer>() );
     27        )
     28
     29        stack s2;
     30        REPEAT_TIMED( "push_bool_char",
     31                s2.push( std::make_unique<pair>( std::make_unique<boolean>( rand() & 0x1 ),
     32                        std::make_unique<character>( rand() & 0x7F ) ) );
     33        )
     34
     35        stack t2;
     36        TIMED( "copy_bool_char",
     37                t2 = s2;
     38        )
     39
     40        TIMED( "clear_bool_char",
     41                s2.clear();
     42        )
     43
     44        pair max2 = { std::make_unique<boolean>(false), std::make_unique<character>('\0') };
     45        REPEAT_TIMED( "pop_bool_char",
     46                max2 = std::max( max2, t2.pop()->as<pair>() );
    2547        )
    2648}
  • doc/generic_types/evaluation/object.hpp

    rf674479 rda1c772  
    1919};
    2020
     21template<typename T>
     22std::type_index class_of() { return { typeid(T) }; }
     23
    2124class object {
    2225public:
     
    2528        template<typename T>
    2629        T& as() {
    27                 std::type_index from = get_class(), to = { typeid(T) };
     30                std::type_index from = get_class(), to = class_of<T>();
    2831                if ( from != to ) throw bad_cast{ from, to };
    2932                return reinterpret_cast<T&>(*this);
     
    3235        template<typename T>
    3336        const T& as() const {
    34                 std::type_index from = get_class(), to = { typeid(T) };
     37                std::type_index from = get_class(), to = class_of<T>();
    3538                if ( from != to ) throw bad_cast{ from, to };
    3639                return reinterpret_cast<const T&>(*this);
     
    4649};
    4750
    48 class integer : public object {
     51template<typename T>
     52T* as_subclass_of( object* o ) {
     53        T* r = dynamic_cast<T*>( o );
     54        if ( r == nullptr ) throw bad_cast{ o->get_class(), class_of<T>() };
     55        return r;
     56}
     57
     58template<typename T>
     59const T* as_subclass_of( const object* o ) {
     60        const T* r = dynamic_cast<const T*>( o );
     61        if ( r == nullptr ) throw bad_cast{ o->get_class(), class_of<T>() };
     62        return r;
     63}
     64
     65class ordered : public object {
     66public:
     67        virtual int cmp(const ordered&) const = 0;
     68
     69        bool operator< (const ordered& that) const { return cmp(that) < 0; }
     70
     71        bool operator<= ( const ordered& that ) const { return cmp(that) <= 0; }
     72
     73        bool operator== ( const ordered& that ) const { return cmp(that) == 0; }
     74
     75        bool operator!= ( const ordered& that ) const { return cmp(that) != 0; }
     76
     77        bool operator> ( const ordered& that ) const { return cmp(that) > 0; }
     78
     79        bool operator>= ( const ordered& that ) const { return cmp(that) >= 0; }
     80};
     81
     82class boolean : public ordered {
     83private:
     84        bool x;
     85
     86public:
     87        boolean() = default;
     88
     89        boolean(bool x) : x(x) {}
     90
     91        std::unique_ptr<object> new_inst() const override { return std::make_unique<boolean>(); }
     92       
     93        std::unique_ptr<object> new_copy() const override { return std::make_unique<boolean>(*this); }
     94
     95        boolean& operator= (const boolean& that) {
     96                x = that.x;
     97                return *this;   
     98        }
     99
     100        object& operator= (const object& that) override {
     101                std::type_index from = that.get_class(), to = get_class();
     102                if ( from != to ) throw bad_cast{ from, to };
     103                return *this = static_cast<const boolean&>(that);
     104        }
     105
     106        ~boolean() override = default;
     107
     108        int cmp(const boolean& that) const { return x == that.x ? 0 : x == false ? -1 : 1; }
     109
     110        // bool operator< (const boolean& that) const { return x < that.x; }
     111
     112        // bool operator== (const boolean& that) const { return x == that.x; }
     113
     114        int cmp(const ordered& that) const override {
     115                std::type_index from = that.get_class(), to = get_class();
     116                if ( from != to ) throw bad_cast{ from, to };
     117                return cmp( static_cast<const boolean&>(that) );
     118        }
     119};
     120
     121class character : public ordered {
     122private:
     123        char x;
     124
     125public:
     126        character() = default;
     127
     128        character(char x) : x(x) {}
     129
     130        std::unique_ptr<object> new_inst() const override { return std::make_unique<character>(); }
     131       
     132        std::unique_ptr<object> new_copy() const override { return std::make_unique<character>(*this); }
     133
     134        character& operator= (const character& that) {
     135                x = that.x;
     136                return *this;   
     137        }
     138
     139        object& operator= (const object& that) override {
     140                std::type_index from = that.get_class(), to = get_class();
     141                if ( from != to ) throw bad_cast{ from, to };
     142                return *this = static_cast<const character&>(that);
     143        }
     144
     145        ~character() override = default;
     146
     147        int cmp(const character& that) const { return x == that.x ? 0 : x < that.x ? -1 : 1; }
     148
     149        // bool operator< (const character& that) const { return x < that.x; }
     150
     151        // bool operator== (const character& that) const { return x == that.x; }
     152
     153        int cmp(const ordered& that) const override {
     154                std::type_index from = that.get_class(), to = get_class();
     155                if ( from != to ) throw bad_cast{ from, to };
     156                return cmp( static_cast<const character&>(that) );
     157        }
     158};
     159
     160class integer : public ordered {
    49161private:
    50162        int x;
     
    67179                std::type_index from = that.get_class(), to = get_class();
    68180                if ( from != to ) throw bad_cast{ from, to };
    69                 return *this = reinterpret_cast<const integer&>(that);
     181                return *this = static_cast<const integer&>(that);
    70182        }
    71183
    72184        ~integer() override = default;
    73185
    74         integer& operator+= (const integer& that) {
    75                 x += that.x;
     186        int cmp(const integer& that) const { return x == that.x ? 0 : x < that.x ? -1 : 1; }
     187
     188        // bool operator< (const integer& that) const { return x < that.x; }
     189
     190        // bool operator== (const integer& that) const { return x == that.x; }
     191
     192        int cmp(const ordered& that) const override {
     193                std::type_index from = that.get_class(), to = get_class();
     194                if ( from != to ) throw bad_cast{ from, to };
     195                return cmp( static_cast<const integer&>(that) );
     196        }
     197};
     198
     199class pair : public ordered {
     200private:
     201        std::unique_ptr<object> x;
     202        std::unique_ptr<object> y;
     203
     204public:
     205        pair() = default;
     206
     207        pair(std::unique_ptr<object>&& x, std::unique_ptr<object>&& y)
     208                : x(std::move(x)), y(std::move(y)) {}
     209       
     210        std::unique_ptr<object> new_inst() const override { return std::make_unique<pair>(); }
     211
     212        std::unique_ptr<object> new_copy() const override {
     213                return std::make_unique<pair>(x->new_copy(), y->new_copy());
     214        }
     215
     216        pair& operator= (const pair& that) {
     217                x = that.x->new_copy();
     218                y = that.y->new_copy();
    76219                return *this;
    77220        }
    78 };
     221
     222        object& operator= (const object& that) override {
     223                std::type_index from = that.get_class(), to = get_class();
     224                if ( from != to ) throw bad_cast{ from, to };
     225                return *this = static_cast<const pair&>(that);
     226        }
     227
     228        ~pair() override = default;
     229
     230        int cmp(const pair& that) const {
     231                const ordered* a = as_subclass_of<ordered>( x.get() );
     232                const ordered* b = as_subclass_of<ordered>( that.x.get() );
     233                int c = a->cmp( *b );
     234                if ( c != 0 ) return c;
     235                a = as_subclass_of<ordered>( y.get() );
     236                b = as_subclass_of<ordered>( that.y.get() );
     237                return a->cmp( *b );
     238        }
     239
     240        // bool operator< (const pair& that) const { return cmp(that) < 0; }
     241
     242        // bool operator== ( const pair& that) const { return cmp(that) == 0; }
     243
     244        int cmp(const ordered& that) const override {
     245                std::type_index from = that.get_class(), to = get_class();
     246                if ( from != to ) throw bad_cast{ from, to };
     247                return cmp( static_cast<const pair&>(that) );
     248        }
     249};
  • doc/generic_types/generic_types.tex

    rf674479 rda1c772  
    11% take off review (for line numbers) and anonymous (for anonymization) on submission
    2 % \documentclass[format=acmlarge, anonymous, review]{acmart}
    3 \documentclass[format=acmlarge,review]{acmart}
     2\documentclass[format=acmlarge,anonymous,review]{acmart}
     3% \documentclass[format=acmlarge,review]{acmart}
    44
    55\usepackage{xspace,calc,comment}
     
    760760It is also possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions. For example, it is possible to write @new@ as a library function:
    761761\begin{lstlisting}
    762 struct Pair(otype R, otype S);
     762struct pair(otype R, otype S);
    763763forall(otype R, otype S)
    764 void ?{}(Pair(R, S) *, R, S);  // (1)
     764void ?{}(pair(R, S) *, R, S);  // (1)
    765765
    766766forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
     
    769769}
    770770
    771 Pair(int, char) * x = new(42, '!');
     771pair(int, char) * x = new(42, '!');
    772772\end{lstlisting}
    773773The @new@ function provides the combination of type-safe @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically allocated objects. This function provides the type-safety of @new@ in \CC, without the need to specify the allocated type again, thanks to return-type inference.
    774774
    775 In the call to @new@, @Pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. The constructor (1) may be specialized to  satisfy the assertion for a constructor with an interface compatible with @void ?{}(Pair(int, char) *, int, char)@.
    776 
    777 \TODO{Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).}
     775In the call to @new@, @pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. The constructor (1) may be specialized to  satisfy the assertion for a constructor with an interface compatible with @void ?{}(pair(int, char) *, int, char)@.
    778776
    779777\subsection{Implementation}
Note: See TracChangeset for help on using the changeset viewer.