source: doc/theses/aaron_moss_PhD/phd/generic-bench.tex @ 8a5530c

\chapter{Generic Stack Benchmarks} \label{generic-bench-app}

This appendix includes the generic stack code for all four language variants discussed in Section~\ref{generic-performance-sec}. Throughout, !/***/! designates a counted redundant type annotation; these include !sizeof! on a known type, repetition of a type name in initialization or return statements, and type-specific helper functions.
The code is reformatted slightly for brevity.

\section{C}

\begin{cfa}
typedef struct node {
        void * value;
        struct node * next;
} node;
typedef struct stack {
        struct node * head;
} stack;
void copy_stack( stack * s, const stack * t, void * (*copy)( const void * ) ) {
        node ** cr = &s->head;
        for (node * nx = t->head; nx; nx = nx->next) {
                *cr = malloc( sizeof(node) ); /***/
                (*cr)->value = copy( nx->value );
                cr = &(*cr)->next;
        }
        *cr = NULL;
}
void clear_stack( stack * s, void (* free_el)( void * ) ) {
        for ( node * nx = s->head; nx; ) {
                node * cr = nx;
                nx = cr->next;
                free_el( cr->value );
                free( cr );
        }
        s->head = NULL;
}
stack new_stack() {
        return (stack){ NULL }; /***/
}
stack * assign_stack( stack * s, const stack * t, void * (*copy_el)( const void * ),
                                void (*free_el)( void * ) ) {
        if ( s->head == t->head ) return s;
        clear_stack( s, free_el ); /***/
        copy_stack( s, t, copy_el ); /***/
        return s;
}
_Bool stack_empty( const stack * s ) {
        return s->head == NULL;
}
void push_stack( stack * s, void * v ) {
        node * n = malloc( sizeof(node) ); /***/
        *n = (node){ v, s->head }; /***/
        s->head = n;
}
void * pop_stack( stack * s ) {
        node * n = s->head;
        s->head = n->next;
        void * v = n->value;
        free( n );
        return v;
}
\end{cfa}

\section{\CFA{}}

\begin{cfa}
forall( otype T ) {
        struct node {
                T value;
                node(T) * next;
        };
        struct stack { node(T) * head; };
        void ?{}( stack(T) & s, stack(T) t ) { // copy
                node(T) ** cr = &s.head;
                for ( node(T) * nx = t.head; nx; nx = nx->next ) {
                        *cr = alloc();
                        ((*cr)->value){ nx->value };
                        cr = &(*cr)->next;
                }
                *cr = 0;
        }
        void clear( stack(T) & s ) with( s ) {
                for ( node(T) * nx = head; nx; ) {
                        node(T) * cr = nx;
                        nx = cr->next;
                        ^(*cr){};
                        free( cr );
                }
                head = 0;
        }
        void ?{}( stack(T) & s ) { (s.head){ 0 }; }
        void ^?{}( stack(T) & s) { clear( s ); }
        stack(T) ?=?( stack(T) & s, stack(T) t ) {
                if ( s.head == t.head ) return s;
                clear( s );
                s{ t };
                return s;
        }
        _Bool empty( const stack(T) & s ) {
                return s.head == 0;
        }
        void push( stack(T) & s, T value ) with( s ) {
                node(T) * n = alloc();
                (*n){ value, head };
                head = n;
        }
        T pop( stack(T) & s ) with( s ) {
                node(T) * n = head;
                head = n->next;
                T v = n->value;
                ^(*n){};
                free( n );
                return v;
        }
}
\end{cfa}

\section{\CC{}}

\begin{cfa}
template<typename T> struct stack {
        struct node {
                T value;
                node * next;
                node( const T & v, node * n = nullptr ) :
                        value( v ), next( n ) {}
        };
        node * head;
        void copy( const stack<T> & o ) {
                node ** cr = &head;
                for ( node * nx = o.head; nx; nx = nx->next ) {
                        *cr = new node{ nx->value }; /***/
                        cr = &(*cr)->next;
                }
                *cr = nullptr;
        }
        void clear() {
                for ( node * nx = head; nx; ) {
                        node * cr = nx;
                        nx = cr->next;
                        delete cr;
                }
                head = nullptr;
        }
        stack() : head( nullptr ) {}
        stack( const stack<T> & o ) { copy( o ); }
        ~stack() { clear(); }
        stack & operator=( const stack<T> & o ) {
                if ( this == &o ) return *this;
                clear();
                copy( o );
                return *this;
        }
        bool empty() const {
                return head == nullptr;
        }
        void push( const T & value ) {
                head = new node{ value, head };  /***/
        }
        T pop() {
                node * n = head;
                head = n->next;
                T v = std::move( n->value );
                delete n;
                return v;
        }
};
\end{cfa}

\section{\CCV{}}

\begin{cfa}
struct stack {
        struct node {
                ptr<object> value;
                node * next;
                node( const object & v, node * n = nullptr ) :
                                value( v.new_copy() ), next( n ) {}
        };
        node * head;
        void copy( const stack & o ) {
                node ** cr = &head;
                for ( node * nx = o.head; nx; nx = nx->next ) {
                        *cr = new node{ *nx->value }; /***/
                        cr = &(*cr)->next;
                }
                *cr = nullptr;
        }
        void clear() {
                for ( node * nx = head; nx; ) {
                        node * cr = nx;
                        nx = cr->next;
                        delete cr;
                }
                head = nullptr;
        }
        stack() : head( nullptr ) {}
        stack( const stack & o ) { copy( o ); }
        ~stack() { clear(); }
        stack & operator=( const stack & o ) {
                if ( this == &o ) return *this;
                clear();
                copy( o );
                return *this;
        }
        bool empty() const {
                return head == nullptr;
        }
        void push( const object & value ) {
                head = new node{ value, head }; /***/
        }
        ptr<object> pop() {
                node * n = head;
                head = n->next;
                ptr<object> v = std::move( n->value );
                delete n;
                return v;
        }
};
\end{cfa}