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

aaron-thesisarm-ehcleanup-dtorsjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since cf01d0b was cf01d0b, checked in by Aaron Moss <a3moss@…>, 3 years ago

thesis: typo-fixing revisions from Werner, Ondrej

  • Property mode set to 100644
File size: 4.6 KB
Line 
1\chapter{Generic Stack Benchmarks} \label{generic-bench-app}
2
3This 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.
4The code is reformatted slightly for brevity.
5
6\section{C}
7
8\begin{cfa}
9typedef struct node {
10        void * value;
11        struct node * next;
12} node;
13typedef struct stack {
14        struct node * head;
15} stack;
16void copy_stack( stack * s, const stack * t, void * (*copy)( const void * ) ) {
17        node ** cr = &s->head;
18        for (node * nx = t->head; nx; nx = nx->next) {
19                *cr = malloc( sizeof(node) ); /***/
20                (*cr)->value = copy( nx->value );
21                cr = &(*cr)->next;
22        }
23        *cr = NULL;
24}
25void clear_stack( stack * s, void (* free_el)( void * ) ) {
26        for ( node * nx = s->head; nx; ) {
27                node * cr = nx;
28                nx = cr->next;
29                free_el( cr->value );
30                free( cr );
31        }
32        s->head = NULL;
33}
34stack new_stack() {
35        return (stack){ NULL }; /***/
36}
37stack * assign_stack( stack * s, const stack * t, void * (*copy_el)( const void * ),
38                                void (*free_el)( void * ) ) {
39        if ( s->head == t->head ) return s;
40        clear_stack( s, free_el ); /***/
41        copy_stack( s, t, copy_el ); /***/
42        return s;
43}
44_Bool stack_empty( const stack * s ) {
45        return s->head == NULL;
46}
47void push_stack( stack * s, void * v ) {
48        node * n = malloc( sizeof(node) ); /***/
49        *n = (node){ v, s->head }; /***/
50        s->head = n;
51}
52void * pop_stack( stack * s ) {
53        node * n = s->head;
54        s->head = n->next;
55        void * v = n->value;
56        free( n );
57        return v;
58}
59\end{cfa}
60
61\section{\CFA{}}
62
63\begin{cfa}
64forall( otype T ) {
65        struct node {
66                T value;
67                node(T) * next;
68        };
69        struct stack { node(T) * head; };
70        void ?{}( stack(T) & s, stack(T) t ) { // copy
71                node(T) ** cr = &s.head;
72                for ( node(T) * nx = t.head; nx; nx = nx->next ) {
73                        *cr = alloc();
74                        ((*cr)->value){ nx->value };
75                        cr = &(*cr)->next;
76                }
77                *cr = 0;
78        }
79        void clear( stack(T) & s ) with( s ) {
80                for ( node(T) * nx = head; nx; ) {
81                        node(T) * cr = nx;
82                        nx = cr->next;
83                        ^(*cr){};
84                        free( cr );
85                }
86                head = 0;
87        }
88        void ?{}( stack(T) & s ) { (s.head){ 0 }; }
89        void ^?{}( stack(T) & s) { clear( s ); }
90        stack(T) ?=?( stack(T) & s, stack(T) t ) {
91                if ( s.head == t.head ) return s;
92                clear( s );
93                s{ t };
94                return s;
95        }
96        _Bool empty( const stack(T) & s ) {
97                return s.head == 0;
98        }
99        void push( stack(T) & s, T value ) with( s ) {
100                node(T) * n = alloc();
101                (*n){ value, head };
102                head = n;
103        }
104        T pop( stack(T) & s ) with( s ) {
105                node(T) * n = head;
106                head = n->next;
107                T v = n->value;
108                ^(*n){};
109                free( n );
110                return v;
111        }
112}
113\end{cfa}
114
115\section{\CC{}}
116
117\begin{cfa}
118template<typename T> struct stack {
119        struct node {
120                T value;
121                node * next;
122                node( const T & v, node * n = nullptr ) :
123                        value( v ), next( n ) {}
124        };
125        node * head;
126        void copy( const stack<T> & o ) {
127                node ** cr = &head;
128                for ( node * nx = o.head; nx; nx = nx->next ) {
129                        *cr = new node{ nx->value }; /***/
130                        cr = &(*cr)->next;
131                }
132                *cr = nullptr;
133        }
134        void clear() {
135                for ( node * nx = head; nx; ) {
136                        node * cr = nx;
137                        nx = cr->next;
138                        delete cr;
139                }
140                head = nullptr;
141        }
142        stack() : head( nullptr ) {}
143        stack( const stack<T> & o ) { copy( o ); }
144        ~stack() { clear(); }
145        stack & operator=( const stack<T> & o ) {
146                if ( this == &o ) return *this;
147                clear();
148                copy( o );
149                return *this;
150        }
151        bool empty() const {
152                return head == nullptr;
153        }
154        void push( const T & value ) {
155                head = new node{ value, head };  /***/
156        }
157        T pop() {
158                node * n = head;
159                head = n->next;
160                T v = std::move( n->value );
161                delete n;
162                return v;
163        }
164};
165\end{cfa}
166
167\section{\CCV{}}
168
169\begin{cfa}
170struct stack {
171        struct node {
172                ptr<object> value;
173                node * next;
174                node( const object & v, node * n = nullptr ) :
175                                value( v.new_copy() ), next( n ) {}
176        };
177        node * head;
178        void copy( const stack & o ) {
179                node ** cr = &head;
180                for ( node * nx = o.head; nx; nx = nx->next ) {
181                        *cr = new node{ *nx->value }; /***/
182                        cr = &(*cr)->next;
183                }
184                *cr = nullptr;
185        }
186        void clear() {
187                for ( node * nx = head; nx; ) {
188                        node * cr = nx;
189                        nx = cr->next;
190                        delete cr;
191                }
192                head = nullptr;
193        }
194        stack() : head( nullptr ) {}
195        stack( const stack & o ) { copy( o ); }
196        ~stack() { clear(); }
197        stack & operator=( const stack & o ) {
198                if ( this == &o ) return *this;
199                clear();
200                copy( o );
201                return *this;
202        }
203        bool empty() const {
204                return head == nullptr;
205        }
206        void push( const object & value ) {
207                head = new node{ value, head }; /***/
208        }
209        ptr<object> pop() {
210                node * n = head;
211                head = n->next;
212                ptr<object> v = std::move( n->value );
213                delete n;
214                return v;
215        }
216};
217\end{cfa}
Note: See TracBrowser for help on using the repository browser.