source: libcfa/src/bits/collections.hfa@ 77bc259

Last change on this file since 77bc259 was acafba4, checked in by Michael Brooks <mlbrooks@…>, 2 years ago

Rename internal macro away from TYPE, which is a cs343 name collision.
  • Property mode set to 100644
File size: 7.0 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/collections.hfa -- Intrusive generic collections
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 Aug 30 21:26:39 2023
13// Update Count : 30
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(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(T | sized(T))
43 // static inline void ?{}(__small_array(T) & this) {}
44
45 forall(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(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(T &)
56 static inline T * begin( const __small_array(T) & this ) {
57 return ((typeof(this.data))this.data);
58 }
59
60 forall(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 forall( T & )
72 trait is_node {
73 T *& get_next( T & );
74 };
75#endif
76
77//-----------------------------------------------------------------------------
78// Stack
79//-----------------------------------------------------------------------------
80#ifdef __cforall
81 forall(T &)
82 #define __elem_t T
83#else
84 #define __elem_t void
85#endif
86struct __stack {
87 __elem_t * top;
88};
89#undef __elem_t
90
91#ifdef __cforall
92#define __stack_t(T) __stack(T)
93#else
94#define __stack_t(T) struct __stack
95#endif
96
97#ifdef __cforall
98 forall(T &)
99 static inline void ?{}( __stack(T) & this ) {
100 (this.top){ 0p };
101 }
102
103 static inline forall( T & | is_node(T) ) {
104 void push( __stack(T) & this, T * val ) {
105 verify( !get_next( *val ) );
106 get_next( *val ) = this.top;
107 this.top = val;
108 }
109
110 T * pop( __stack(T) & this ) {
111 T * top = this.top;
112 if( top ) {
113 this.top = get_next( *top );
114 get_next( *top ) = 0p;
115 }
116 return top;
117 }
118
119 int ?!=?( const __stack(T) & this, __attribute__((unused)) zero_t zero ) {
120 return this.top != 0;
121 }
122 }
123#endif
124
125//-----------------------------------------------------------------------------
126// Queue
127//-----------------------------------------------------------------------------
128#ifdef __cforall
129 forall(T &)
130 #define __elem_t T
131#else
132 #define __elem_t void
133#endif
134struct __queue {
135 __elem_t * head;
136 __elem_t ** tail;
137};
138#undef __elem_t
139
140#ifdef __cforall
141#define __queue_t(T) __queue(T)
142#else
143#define __queue_t(T) struct __queue
144#endif
145
146#ifdef __cforall
147 static inline forall( T & | is_node(T) ) {
148 void ?{}( __queue(T) & this ) with( this ) {
149 (this.head){ 1p };
150 (this.tail){ &this.head };
151 verify(*this.tail == 1p);
152 }
153
154 void append( __queue(T) & this, T * val ) with(this) {
155 verify(get_next( *val ) == 0p);
156 verify(this.tail != 0p);
157 verify(*this.tail == 1p);
158 *this.tail = val;
159 this.tail = &get_next( *val );
160 *this.tail = 1p;
161 }
162
163 T * peek( __queue(T) & this ) {
164 verify(*this.tail == 1p);
165 T * frontnode = this.head;
166 if( frontnode != 1p ) {
167 verify(*this.tail == 1p);
168 return frontnode;
169 }
170 verify(*this.tail == 1p);
171 return 0p;
172 }
173
174 T * pop_head( __queue(T) & this ) {
175 verify(*this.tail == 1p);
176 T * _head = this.head;
177 if( _head != 1p ) {
178 this.head = get_next( *_head );
179 if( get_next( *_head ) == 1p ) {
180 this.tail = &this.head;
181 }
182 get_next( *_head ) = 0p;
183 verify(*this.tail == 1p);
184 verify( get_next(*_head) == 0p );
185 return _head;
186 }
187 verify(*this.tail == 1p);
188 return 0p;
189 }
190
191 T * remove( __queue(T) & this, T ** it ) with( this ) {
192 T * val = *it;
193 verify( val );
194
195 (*it) = get_next( *val );
196
197 if( this.tail == &get_next( *val ) ) {
198 this.tail = it;
199 }
200
201 get_next( *val ) = 0p;
202
203 verify( (this.head == 1p) == (&this.head == this.tail) );
204 verify( *this.tail == 1p );
205 return val;
206 }
207
208 int ?!=?( const __queue(T) & this, __attribute__((unused)) zero_t zero ) {
209 return this.head != 1p;
210 }
211 }
212#endif
213
214
215//-----------------------------------------------------------------------------
216// Doubly Linked List
217//-----------------------------------------------------------------------------
218#ifdef __cforall
219 forall(T &)
220 #define __elem_t T
221 #define __getter_t * [__elem_t * & next, __elem_t * & prev] ( __elem_t & )
222#else
223 typedef void (*__generit_c_getter_t)();
224 #define __elem_t void
225 #define __getter_t __generit_c_getter_t
226#endif
227struct __dllist {
228 __elem_t * head;
229 __getter_t __get;
230};
231#undef __elem_t
232#undef __getter_t
233
234#ifdef __cforall
235#define __dllist_t(T) __dllist(T)
236#else
237#define __dllist_t(T) struct __dllist
238#endif
239
240#ifdef __cforall
241 forall(T & )
242 static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) {
243 (this.head){ 0p };
244 this.__get = __get;
245 }
246
247 #define next 0
248 #define prev 1
249 static inline forall(T &) {
250 void push_front( __dllist(T) & this, T & node ) with( this ) {
251 verify(__get);
252 if ( this.head ) {
253 __get( node ).next = this.head;
254 __get( node ).prev = __get( *this.head ).prev;
255 // inserted node must be consistent before it is seen
256 // prevent code movement across barrier
257 asm( "" : : : "memory" );
258 __get( *this.head ).prev = &node;
259 T & _prev = *__get( node ).prev;
260 __get( _prev ).next = &node;
261 } else {
262 __get( node ).next = &node;
263 __get( node ).prev = &node;
264 }
265
266 // prevent code movement across barrier
267 asm( "" : : : "memory" );
268 this.head = &node;
269 }
270
271 void remove( __dllist(T) & this, T & node ) with( this ) {
272 verify(__get);
273 if ( &node == this.head ) {
274 if ( __get( *this.head ).next == this.head ) {
275 this.head = 0p;
276 } else {
277 this.head = __get( *this.head ).next;
278 }
279 }
280 __get( *__get( node ).next ).prev = __get( node ).prev;
281 __get( *__get( node ).prev ).next = __get( node ).next;
282 __get( node ).next = 0p;
283 __get( node ).prev = 0p;
284 }
285
286 int ?!=?( const __dllist(T) & this, __attribute__((unused)) zero_t zero ) {
287 return this.head != 0;
288 }
289
290 void move_to_front( __dllist(T) & src, __dllist(T) & dst, T & node ) {
291 remove (src, node);
292 push_front(dst, node);
293 }
294 }
295 #undef next
296 #undef prev
297#endif
298
299//-----------------------------------------------------------------------------
300// Tools
301//-----------------------------------------------------------------------------
302#ifdef __cforall
303
304#endif
305
306// Local Variables: //
307// tab-width: 4 //
308// End: //
Note: See TracBrowser for help on using the repository browser.