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

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

thesis: Add appendix with generic benchmark code

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