source: libcfa/src/bits/containers.hfa @ 3381ed7

arm-ehjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since 3381ed7 was 3381ed7, checked in by Thierry Delisle <tdelisle@…>, 21 months ago

Added park/unpark primitives thread and removed BlockInternal?.
Converted monitors to use park unpark.
Intrusive Queue now mark next field when thread is inside queue.
Added several asserts to kernel and monitor.
Added a few tests for park and unpark.

  • Property mode set to 100644
File size: 6.4 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 * pop_head( __queue(T) & this ) {
162                        verify(*this.tail == 1p);
163                        T * head = this.head;
164                        if( head != 1p ) {
165                                this.head = get_next( *head );
166                                if( get_next( *head ) == 1p ) {
167                                        this.tail = &this.head;
168                                }
169                                get_next( *head ) = 0p;
170                                verify(*this.tail == 1p);
171                                return head;
172                        }
173                        verify(*this.tail == 1p);
174                        return 0p;
175                }
176
177                T * remove( __queue(T) & this, T ** it ) with( this ) {
178                        T * val = *it;
179                        verify( val );
180
181                        (*it) = get_next( *val );
182
183                        if( tail == &get_next( *val ) ) {
184                                tail = it;
185                        }
186
187                        get_next( *val ) = 0p;
188
189                        verify( (head == 1p) == (&head == tail) );
190                        verify( *tail == 1p );
191                        return val;
192                }
193
194                int ?!=?( const __queue(T) & this, __attribute__((unused)) zero_t zero ) {
195                        return this.head != 0;
196                }
197        }
198#endif
199
200
201//-----------------------------------------------------------------------------
202// Doubly Linked List
203//-----------------------------------------------------------------------------
204#ifdef __cforall
205        forall(dtype TYPE)
206        #define T TYPE
207        #define __getter_t * [T * & next, T * & prev] ( T & )
208#else
209        typedef void (*__generit_c_getter_t)();
210        #define T void
211        #define __getter_t __generit_c_getter_t
212#endif
213struct __dllist {
214        T * head;
215        __getter_t __get;
216};
217#undef T
218#undef __getter_t
219
220#ifdef __cforall
221#define __dllist_t(T) __dllist(T)
222#else
223#define __dllist_t(T) struct __dllist
224#endif
225
226#ifdef __cforall
227        forall(dtype T )
228        static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) {
229                this.head{ 0p };
230                this.__get = __get;
231        }
232
233        #define next 0
234        #define prev 1
235        static inline forall(dtype T) {
236                void push_front( __dllist(T) & this, T & node ) with( this ) {
237                        verify(__get);
238                        if ( head ) {
239                                __get( node ).next = head;
240                                __get( node ).prev = __get( *head ).prev;
241                                // inserted node must be consistent before it is seen
242                                // prevent code movement across barrier
243                                asm( "" : : : "memory" );
244                                __get( *head ).prev = &node;
245                                T & _prev = *__get( node ).prev;
246                                __get( _prev ).next = &node;
247                        } else {
248                                __get( node ).next = &node;
249                                __get( node ).prev = &node;
250                        }
251
252                        // prevent code movement across barrier
253                        asm( "" : : : "memory" );
254                        head = &node;
255                }
256
257                void remove( __dllist(T) & this, T & node ) with( this ) {
258                        verify(__get);
259                        if ( &node == head ) {
260                                if ( __get( *head ).next == head ) {
261                                        head = 0p;
262                                } else {
263                                        head = __get( *head ).next;
264                                }
265                        }
266                        __get( *__get( node ).next ).prev = __get( node ).prev;
267                        __get( *__get( node ).prev ).next = __get( node ).next;
268                        __get( node ).next = 0p;
269                        __get( node ).prev = 0p;
270                }
271
272                int ?!=?( const __dllist(T) & this, __attribute__((unused)) zero_t zero ) {
273                        return this.head != 0;
274                }
275        }
276        #undef next
277        #undef prev
278#endif
279
280//-----------------------------------------------------------------------------
281// Tools
282//-----------------------------------------------------------------------------
283#ifdef __cforall
284
285#endif
286
287// Local Variables: //
288// tab-width: 4 //
289// End: //
Note: See TracBrowser for help on using the repository browser.