source: libcfa/src/bits/containers.hfa@ 5ccee64

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 5ccee64 was 768bd556, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

start cleanup and update of intrusive data-structures

  • Property mode set to 100644
File size: 6.2 KB
RevLine 
[ea7d2b0]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//
[73abe95]7// bits/containers.hfa -- Intrusive generic containers.hfa
[ea7d2b0]8//
9// Author : Thierry Delisle
10// Created On : Tue Oct 31 16:38:50 2017
[2233ad4]11// Last Modified By : Peter A. Buhr
[768bd556]12// Last Modified On : Wed Jan 15 07:42:35 2020
13// Update Count : 28
[ea7d2b0]14
15#pragma once
16
[73abe95]17#include "bits/align.hfa"
18#include "bits/defs.hfa"
[ea7d2b0]19
[0cf5b79]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))
[768bd556]46 static inline T & ?[?]( __small_array(T) & this, __lock_size_t idx ) {
[0cf5b79]47 return ((typeof(this.data))this.data)[idx];
48 }
49
50 forall(dtype T | sized(T))
[768bd556]51 static inline T & ?[?]( const __small_array(T) & this, __lock_size_t idx ) {
[0cf5b79]52 return ((typeof(this.data))this.data)[idx];
53 }
54
[768bd556]55 forall(dtype T)
56 static inline T * begin( const __small_array(T) & this ) {
[0cf5b79]57 return ((typeof(this.data))this.data);
58 }
59
60 forall(dtype T | sized(T))
[768bd556]61 static inline T * end( const __small_array(T) & this ) {
[0cf5b79]62 return ((typeof(this.data))this.data) + this.size;
63 }
64#endif
65
[ea7d2b0]66//-----------------------------------------------------------------------------
67// Node Base
68//-----------------------------------------------------------------------------
69
[0cf5b79]70#ifdef __cforall
[ea7d2b0]71 trait is_node(dtype T) {
[768bd556]72 T *& get_next( T & );
[ea7d2b0]73 };
74#endif
75
76//-----------------------------------------------------------------------------
77// Stack
78//-----------------------------------------------------------------------------
[0cf5b79]79#ifdef __cforall
[3623f9d]80 forall(dtype TYPE)
[ea7d2b0]81 #define T TYPE
82#else
83 #define T void
84#endif
85struct __stack {
86 T * top;
87};
[0cf5b79]88#undef T
[ea7d2b0]89
[0cf5b79]90#ifdef __cforall
[ea7d2b0]91#define __stack_t(T) __stack(T)
92#else
93#define __stack_t(T) struct __stack
94#endif
95
[0cf5b79]96#ifdef __cforall
[3623f9d]97 forall(dtype T)
[0cf5b79]98 static inline void ?{}( __stack(T) & this ) {
[768bd556]99 (this.top){ 0p };
[ea7d2b0]100 }
101
[768bd556]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 }
[ea7d2b0]108
[768bd556]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;
[ea7d2b0]116 }
[2233ad4]117
[768bd556]118 int ?!=?( const __stack(T) & this, __attribute__((unused)) zero_t zero ) {
119 return this.top != 0;
120 }
[2233ad4]121 }
[ea7d2b0]122#endif
123
124//-----------------------------------------------------------------------------
125// Queue
126//-----------------------------------------------------------------------------
[0cf5b79]127#ifdef __cforall
[3623f9d]128 forall(dtype TYPE)
[ea7d2b0]129 #define T TYPE
130#else
131 #define T void
132#endif
133struct __queue {
134 T * head;
135 T ** tail;
136};
[0cf5b79]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
[ea7d2b0]144
[0cf5b79]145#ifdef __cforall
[768bd556]146 static inline forall( dtype T | is_node(T) ) {
147 void ?{}( __queue(T) & this ) with( this ) {
148 head{ 0p };
149 tail{ &head };
150 }
[65deb18]151
[768bd556]152 void append( __queue(T) & this, T * val ) with( this ) {
153 verify(tail != 0p);
154 *tail = val;
155 tail = &get_next( *val );
156 }
[ea7d2b0]157
[768bd556]158 T * pop_head( __queue(T) & this ) {
159 T * head = this.head;
160 if( head ) {
161 this.head = get_next( *head );
162 if( !get_next( *head ) ) {
163 this.tail = &this.head;
164 }
165 get_next( *head ) = 0p;
[ea7d2b0]166 }
[768bd556]167 return head;
[ea7d2b0]168 }
169
[768bd556]170 T * remove( __queue(T) & this, T ** it ) with( this ) {
171 T * val = *it;
172 verify( val );
[ea7d2b0]173
[768bd556]174 (*it) = get_next( *val );
[ea7d2b0]175
[768bd556]176 if( tail == &get_next( *val ) ) {
177 tail = it;
178 }
[ea7d2b0]179
[768bd556]180 get_next( *val ) = 0p;
[ea7d2b0]181
[768bd556]182 verify( (head == 0p) == (&head == tail) );
183 verify( *tail == 0p );
184 return val;
185 }
[8ebbfc4]186
[768bd556]187 int ?!=?( const __queue(T) & this, __attribute__((unused)) zero_t zero ) {
188 return this.head != 0;
189 }
[8ebbfc4]190 }
[ea7d2b0]191#endif
[65deb18]192
[14a61b5]193
194//-----------------------------------------------------------------------------
195// Doubly Linked List
196//-----------------------------------------------------------------------------
197#ifdef __cforall
[ffe2fad]198 forall(dtype TYPE)
[14a61b5]199 #define T TYPE
[705e612]200 #define __getter_t * [T * & next, T * & prev] ( T & )
[14a61b5]201#else
[705e612]202 typedef void (*__generit_c_getter_t)();
[14a61b5]203 #define T void
[705e612]204 #define __getter_t __generit_c_getter_t
[14a61b5]205#endif
206struct __dllist {
207 T * head;
[705e612]208 __getter_t __get;
[14a61b5]209};
210#undef T
[705e612]211#undef __getter_t
[14a61b5]212
213#ifdef __cforall
214#define __dllist_t(T) __dllist(T)
215#else
216#define __dllist_t(T) struct __dllist
217#endif
218
219#ifdef __cforall
[768bd556]220 forall(dtype T )
[de94a60]221 static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) {
[768bd556]222 this.head{ 0p };
[de94a60]223 this.__get = __get;
224 }
225
[639991a]226 #define next 0
227 #define prev 1
[768bd556]228 static inline forall(dtype T) {
229 void push_front( __dllist(T) & this, T & node ) with( this ) {
230 verify(__get);
231 if ( head ) {
232 __get( node ).next = head;
233 __get( node ).prev = __get( *head ).prev;
234 // inserted node must be consistent before it is seen
235 // prevent code movement across barrier
236 asm( "" : : : "memory" );
237 __get( *head ).prev = &node;
238 T & _prev = *__get( node ).prev;
239 __get( _prev ).next = &node;
240 } else {
241 __get( node ).next = &node;
242 __get( node ).prev = &node;
243 }
244
[de94a60]245 // prevent code movement across barrier
246 asm( "" : : : "memory" );
[768bd556]247 head = &node;
[de94a60]248 }
249
[768bd556]250 void remove( __dllist(T) & this, T & node ) with( this ) {
251 verify(__get);
252 if ( &node == head ) {
253 if ( __get( *head ).next == head ) {
254 head = 0p;
255 } else {
256 head = __get( *head ).next;
257 }
[de94a60]258 }
[768bd556]259 __get( *__get( node ).next ).prev = __get( node ).prev;
260 __get( *__get( node ).prev ).next = __get( node ).next;
261 __get( node ).next = 0p;
262 __get( node ).prev = 0p;
[de94a60]263 }
[0c674e8]264
[768bd556]265 int ?!=?( const __dllist(T) & this, __attribute__((unused)) zero_t zero ) {
266 return this.head != 0;
267 }
[0c674e8]268 }
[639991a]269 #undef next
270 #undef prev
[14a61b5]271#endif
272
[65deb18]273//-----------------------------------------------------------------------------
274// Tools
275//-----------------------------------------------------------------------------
276#ifdef __cforall
277
[2233ad4]278#endif
[768bd556]279
280// Local Variables: //
281// tab-width: 4 //
282// End: //
Note: See TracBrowser for help on using the repository browser.