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

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

thesis: add changebars

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