source: libcfa/src/bits/containers.hfa @ ae2c27a

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since ae2c27a was ae2c27a, checked in by Colby Alexander Parsons <caparsons@…>, 14 months ago

Added unified condition variable prototypes

  • Property mode set to 100644
File size: 6.8 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// bits/containers.hfa -- Intrusive generic containers.hfa
8//
9// Author           : Thierry Delisle
10// Created On       : Tue Oct 31 16:38:50 2017
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Wed Jan 15 07:42:35 2020
13// Update Count     : 28
14
15#pragma once
16
17#include "bits/align.hfa"
18#include "bits/defs.hfa"
19
20//-----------------------------------------------------------------------------
21// Array
22//-----------------------------------------------------------------------------
23
24#ifdef __cforall
25        forall(dtype T)
26#else
27        #define T void
28#endif
29struct __small_array {
30        T *           data;
31        __lock_size_t size;
32};
33#undef T
34
35#ifdef __cforall
36        #define __small_array_t(T) __small_array(T)
37#else
38        #define __small_array_t(T) struct __small_array
39#endif
40
41#ifdef __cforall
42        // forall(otype T | sized(T))
43        // static inline void ?{}(__small_array(T) & this) {}
44
45        forall(dtype T | sized(T))
46        static inline T & ?[?]( __small_array(T) & this, __lock_size_t idx ) {
47                return ((typeof(this.data))this.data)[idx];
48        }
49
50        forall(dtype T | sized(T))
51        static inline T & ?[?]( const __small_array(T) & this, __lock_size_t idx ) {
52                return ((typeof(this.data))this.data)[idx];
53        }
54
55        forall(dtype T)
56        static inline T * begin( const __small_array(T) & this ) {
57                return ((typeof(this.data))this.data);
58        }
59
60        forall(dtype T | sized(T))
61        static inline T * end( const __small_array(T) & this ) {
62                return ((typeof(this.data))this.data) + this.size;
63        }
64#endif
65
66//-----------------------------------------------------------------------------
67// Node Base
68//-----------------------------------------------------------------------------
69
70#ifdef __cforall
71        trait is_node(dtype T) {
72                T *& get_next( T & );
73        };
74#endif
75
76//-----------------------------------------------------------------------------
77// Stack
78//-----------------------------------------------------------------------------
79#ifdef __cforall
80        forall(dtype TYPE)
81        #define T TYPE
82#else
83        #define T void
84#endif
85struct __stack {
86        T * top;
87};
88#undef T
89
90#ifdef __cforall
91#define __stack_t(T) __stack(T)
92#else
93#define __stack_t(T) struct __stack
94#endif
95
96#ifdef __cforall
97        forall(dtype T)
98        static inline void ?{}( __stack(T) & this ) {
99                (this.top){ 0p };
100        }
101
102        static inline forall( dtype T | is_node(T) ) {
103                void push( __stack(T) & this, T * val ) {
104                        verify( !get_next( *val ) );
105                        get_next( *val ) = this.top;
106                        this.top = val;
107                }
108
109                T * pop( __stack(T) & this ) {
110                        T * top = this.top;
111                        if( top ) {
112                                this.top = get_next( *top );
113                                get_next( *top ) = 0p;
114                        }
115                        return top;
116                }
117
118                int ?!=?( const __stack(T) & this, __attribute__((unused)) zero_t zero ) {
119                        return this.top != 0;
120                }
121        }
122#endif
123
124//-----------------------------------------------------------------------------
125// Queue
126//-----------------------------------------------------------------------------
127#ifdef __cforall
128        forall(dtype TYPE)
129        #define T TYPE
130#else
131        #define T void
132#endif
133struct __queue {
134        T * head;
135        T ** tail;
136};
137#undef T
138
139#ifdef __cforall
140#define __queue_t(T) __queue(T)
141#else
142#define __queue_t(T) struct __queue
143#endif
144
145#ifdef __cforall
146        static inline forall( dtype T | is_node(T) ) {
147                void ?{}( __queue(T) & this ) with( this ) {
148                        head{ 1p };
149                        tail{ &head };
150                        verify(*tail == 1p);
151                }
152
153                void append( __queue(T) & this, T * val ) with( this ) {
154                        verify(tail != 0p);
155                        verify(*tail == 1p);
156                        *tail = val;
157                        tail = &get_next( *val );
158                        *tail = 1p;
159                }
160
161                T * peek( __queue(T) & this ) {
162                        verify(*this.tail == 1p);
163                        T * head = this.head;
164                        if( head != 1p ) {
165                                verify(*this.tail == 1p);
166                                return head;
167                        }
168                        verify(*this.tail == 1p);
169                        return 0p;
170                }
171
172                T * pop_head( __queue(T) & this ) {
173                        verify(*this.tail == 1p);
174                        T * head = this.head;
175                        if( head != 1p ) {
176                                this.head = get_next( *head );
177                                if( get_next( *head ) == 1p ) {
178                                        this.tail = &this.head;
179                                }
180                                get_next( *head ) = 0p;
181                                verify(*this.tail == 1p);
182                                verify( get_next(*head) == 0p );
183                                return head;
184                        }
185                        verify(*this.tail == 1p);
186                        return 0p;
187                }
188
189                T * remove( __queue(T) & this, T ** it ) with( this ) {
190                        T * val = *it;
191                        verify( val );
192
193                        (*it) = get_next( *val );
194
195                        if( tail == &get_next( *val ) ) {
196                                tail = it;
197                        }
198
199                        get_next( *val ) = 0p;
200
201                        verify( (head == 1p) == (&head == tail) );
202                        verify( *tail == 1p );
203                        return val;
204                }
205
206                int ?!=?( const __queue(T) & this, __attribute__((unused)) zero_t zero ) {
207                        return this.head != 1p;
208                }
209        }
210#endif
211
212
213//-----------------------------------------------------------------------------
214// Doubly Linked List
215//-----------------------------------------------------------------------------
216#ifdef __cforall
217        forall(dtype TYPE)
218        #define T TYPE
219        #define __getter_t * [T * & next, T * & prev] ( T & )
220#else
221        typedef void (*__generit_c_getter_t)();
222        #define T void
223        #define __getter_t __generit_c_getter_t
224#endif
225struct __dllist {
226        T * head;
227        __getter_t __get;
228};
229#undef T
230#undef __getter_t
231
232#ifdef __cforall
233#define __dllist_t(T) __dllist(T)
234#else
235#define __dllist_t(T) struct __dllist
236#endif
237
238#ifdef __cforall
239        forall(dtype T )
240        static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) {
241                this.head{ 0p };
242                this.__get = __get;
243        }
244
245        #define next 0
246        #define prev 1
247        static inline forall(dtype T) {
248                void push_front( __dllist(T) & this, T & node ) with( this ) {
249                        verify(__get);
250                        if ( head ) {
251                                __get( node ).next = head;
252                                __get( node ).prev = __get( *head ).prev;
253                                // inserted node must be consistent before it is seen
254                                // prevent code movement across barrier
255                                asm( "" : : : "memory" );
256                                __get( *head ).prev = &node;
257                                T & _prev = *__get( node ).prev;
258                                __get( _prev ).next = &node;
259                        } else {
260                                __get( node ).next = &node;
261                                __get( node ).prev = &node;
262                        }
263
264                        // prevent code movement across barrier
265                        asm( "" : : : "memory" );
266                        head = &node;
267                }
268
269                void remove( __dllist(T) & this, T & node ) with( this ) {
270                        verify(__get);
271                        if ( &node == head ) {
272                                if ( __get( *head ).next == head ) {
273                                        head = 0p;
274                                } else {
275                                        head = __get( *head ).next;
276                                }
277                        }
278                        __get( *__get( node ).next ).prev = __get( node ).prev;
279                        __get( *__get( node ).prev ).next = __get( node ).next;
280                        __get( node ).next = 0p;
281                        __get( node ).prev = 0p;
282                }
283
284                int ?!=?( const __dllist(T) & this, __attribute__((unused)) zero_t zero ) {
285                        return this.head != 0;
286                }
287
288                void move_to_front( __dllist(T) & src, __dllist(T) & dst, T & node ) {
289                        remove    (src, node);
290                        push_front(dst, node);
291                }
292        }
293        #undef next
294        #undef prev
295#endif
296
297//-----------------------------------------------------------------------------
298// Tools
299//-----------------------------------------------------------------------------
300#ifdef __cforall
301
302#endif
303
304// Local Variables: //
305// tab-width: 4 //
306// End: //
Note: See TracBrowser for help on using the repository browser.