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

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since e15683e was 3381ed7, checked in by Thierry Delisle <tdelisle@…>, 6 years 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.