source: src/libcfa/bits/containers.h@ 17238fd

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum with_gc
Last change on this file since 17238fd was a1a17a74, checked in by Thierry Delisle <tdelisle@…>, 7 years ago

Moved thread list to cluster, all concurrency object should be accessible through gdb
  • Property mode set to 100644
File size: 6.1 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.h -- Intrusive generic containers.h
8//
9// Author : Thierry Delisle
10// Created On : Tue Oct 31 16:38:50 2017
11// Last Modified By : --
12// Last Modified On : --
13// Update Count : 0
14
15#pragma once
16
17#include "bits/align.h"
18#include "bits/defs.h"
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 | sized(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 | is_node(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 | is_node(T))
98 static inline void ?{}( __stack(T) & this ) {
99 (this.top){ NULL };
100 }
101
102 forall(dtype T | is_node(T) | sized(T))
103 static inline 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 forall(dtype T | is_node(T) | sized(T))
110 static inline T * pop( __stack(T) & this ) {
111 T * top = this.top;
112 if( top ) {
113 this.top = get_next( *top );
114 get_next( *top ) = NULL;
115 }
116 return top;
117 }
118#endif
119
120//-----------------------------------------------------------------------------
121// Queue
122//-----------------------------------------------------------------------------
123#ifdef __cforall
124 forall(dtype TYPE | is_node(TYPE))
125 #define T TYPE
126#else
127 #define T void
128#endif
129struct __queue {
130 T * head;
131 T ** tail;
132};
133#undef T
134
135#ifdef __cforall
136#define __queue_t(T) __queue(T)
137#else
138#define __queue_t(T) struct __queue
139#endif
140
141#ifdef __cforall
142
143 forall(dtype T | is_node(T))
144 static inline void ?{}( __queue(T) & this ) with( this ) {
145 head{ NULL };
146 tail{ &head };
147 }
148
149 forall(dtype T | is_node(T) | sized(T))
150 static inline void append( __queue(T) & this, T * val ) with( this ) {
151 verify(tail != NULL);
152 *tail = val;
153 tail = &get_next( *val );
154 }
155
156 forall(dtype T | is_node(T) | sized(T))
157 static inline T * pop_head( __queue(T) & this ) {
158 T * head = this.head;
159 if( head ) {
160 this.head = get_next( *head );
161 if( !get_next( *head ) ) {
162 this.tail = &this.head;
163 }
164 get_next( *head ) = NULL;
165 }
166 return head;
167 }
168
169 forall(dtype T | is_node(T) | sized(T))
170 static inline T * remove( __queue(T) & this, T ** it ) with( this ) {
171 T * val = *it;
172 verify( val );
173
174 (*it) = get_next( *val );
175
176 if( tail == &get_next( *val ) ) {
177 tail = it;
178 }
179
180 get_next( *val ) = NULL;
181
182 verify( (head == NULL) == (&head == tail) );
183 verify( *tail == NULL );
184 return val;
185 }
186#endif
187
188
189//-----------------------------------------------------------------------------
190// Doubly Linked List
191//-----------------------------------------------------------------------------
192#ifdef __cforall
193 forall(dtype TYPE | sized(TYPE))
194 #define T TYPE
195 #define __getter_t * [T * & next, T * & prev] ( T & )
196#else
197 typedef void (*__generit_c_getter_t)();
198 #define T void
199 #define __getter_t __generit_c_getter_t
200#endif
201struct __dllist {
202 T * head;
203 __getter_t __get;
204};
205#undef T
206#undef __getter_t
207
208#ifdef __cforall
209#define __dllist_t(T) __dllist(T)
210#else
211#define __dllist_t(T) struct __dllist
212#endif
213
214#ifdef __cforall
215
216 forall(dtype T | sized(T))
217 static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) {
218 this.head{ NULL };
219 this.__get = __get;
220 }
221
222 #define next 0
223 #define prev 1
224 forall(dtype T | sized(T))
225 static inline void push_front( __dllist(T) & this, T & node ) with( this ) {
226 verify(__get);
227 if ( head ) {
228 __get( node ).next = head;
229 __get( node ).prev = __get( *head ).prev;
230 // inserted node must be consistent before it is seen
231 // prevent code movement across barrier
232 asm( "" : : : "memory" );
233 __get( *head ).prev = &node;
234 T & _prev = *__get( node ).prev;
235 __get( _prev ).next = &node;
236 }
237 else {
238 __get( node ).next = &node;
239 __get( node ).prev = &node;
240 }
241
242 // prevent code movement across barrier
243 asm( "" : : : "memory" );
244 head = &node;
245 }
246
247 forall(dtype T | sized(T))
248 static inline void remove( __dllist(T) & this, T & node ) with( this ) {
249 verify(__get);
250 if ( &node == head ) {
251 if ( __get( *head ).next == head ) {
252 head = NULL;
253 }
254 else {
255 head = __get( *head ).next;
256 }
257 }
258 __get( *__get( node ).next ).prev = __get( node ).prev;
259 __get( *__get( node ).prev ).next = __get( node ).next;
260 __get( node ).next = NULL;
261 __get( node ).prev = NULL;
262 }
263 #undef next
264 #undef prev
265#endif
266
267//-----------------------------------------------------------------------------
268// Tools
269//-----------------------------------------------------------------------------
270#ifdef __cforall
271
272#endif
Note: See TracBrowser for help on using the repository browser.