source: libcfa/src/bits/containers.hfa@ 28c35e2

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 28c35e2 was 8b73526, checked in by Colby Alexander Parsons <caparsons@…>, 5 years ago

added struct to _anonymous_object and changed containers to reflect change
  • Property mode set to 100644
File size: 6.9 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#include <stdio.h>
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) __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 (this.head){ 1p };
149 (this.tail){ &this.head };
150 verify(*this.tail == 1p);
151 }
152
153 void append( __queue(T) & this, T * val ) with( this ) {
154 verify(this.tail != 0p);
155 verify(*this.tail == 1p);
156 *this.tail = val;
157 this.tail = &get_next( *val );
158 *this.tail = 1p;
159 }
160
161 T * peek( __queue(T) & this ) {
162 verify(*this.tail == 1p);
163 T * front = this.head;
164 if( front != 1p ) {
165 verify(*this.tail == 1p);
166 return front;
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( this.tail == &get_next( *val ) ) {
196 this.tail = it;
197 }
198
199 get_next( *val ) = 0p;
200
201 verify( (this.head == 1p) == (&this.head == this.tail) );
202 verify( *this.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 ( this.head ) {
251 __get( node ).next = this.head;
252 __get( node ).prev = __get( *this.head ).prev;
253 // inserted node must be consistent before it is seen
254 // prevent code movement across barrier
255 asm( "" : : : "memory" );
256 __get( *this.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 this.head = &node;
267 }
268
269 void remove( __dllist(T) & this, T & node ) with( this ) {
270 verify(__get);
271 if ( &node == this.head ) {
272 if ( __get( *this.head ).next == this.head ) {
273 this.head = 0p;
274 } else {
275 this.head = __get( *this.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.