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