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

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since c2051e10 was 2233ad4, checked in by Peter A. Buhr <pabuhr@…>, 5 years ago

change queue/deque != 0 to return int instead of bool, add != 0 to stack
  • Property mode set to 100644
File size: 6.5 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 Jun 26 08:52:20 2019
13// Update Count     : 4
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 | 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)
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){ 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
119        forall(dtype T | is_node(T))
120        static inline int ?!=?( const __stack(T) & this, __attribute__((unused)) zero_t zero ) {
121                return this.top != 0;
122        }
123#endif
124
125//-----------------------------------------------------------------------------
126// Queue
127//-----------------------------------------------------------------------------
128#ifdef __cforall
129        forall(dtype TYPE)
130        #define T TYPE
131#else
132        #define T void
133#endif
134struct __queue {
135        T * head;
136        T ** tail;
137};
138#undef 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
148        forall(dtype T)
149        static inline void ?{}( __queue(T) & this ) with( this ) {
150                head{ NULL };
151                tail{ &head };
152        }
153
154        forall(dtype T | is_node(T) | sized(T))
155        static inline void append( __queue(T) & this, T * val ) with( this ) {
156                verify(tail != NULL);
157                *tail = val;
158                tail = &get_next( *val );
159        }
160
161        forall(dtype T | is_node(T) | sized(T))
162        static inline T * pop_head( __queue(T) & this ) {
163                T * head = this.head;
164                if( head ) {
165                        this.head = get_next( *head );
166                        if( !get_next( *head ) ) {
167                                this.tail = &this.head;
168                        }
169                        get_next( *head ) = NULL;
170                }
171                return head;
172        }
173
174        forall(dtype T | is_node(T) | sized(T))
175        static inline T * remove( __queue(T) & this, T ** it ) with( this ) {
176                T * val = *it;
177                verify( val );
178
179                (*it) = get_next( *val );
180
181                if( tail == &get_next( *val ) ) {
182                        tail = it;
183                }
184
185                get_next( *val ) = NULL;
186
187                verify( (head == NULL) == (&head == tail) );
188                verify( *tail == NULL );
189                return val;
190        }
191
192        forall(dtype T | is_node(T))
193        static inline int ?!=?( const __queue(T) & this, __attribute__((unused)) zero_t zero ) {
194                return this.head != 0;
195        }
196#endif
197
198
199//-----------------------------------------------------------------------------
200// Doubly Linked List
201//-----------------------------------------------------------------------------
202#ifdef __cforall
203        forall(dtype TYPE)
204        #define T TYPE
205        #define __getter_t * [T * & next, T * & prev] ( T & )
206#else
207        typedef void (*__generit_c_getter_t)();
208        #define T void
209        #define __getter_t __generit_c_getter_t
210#endif
211struct __dllist {
212        T * head;
213        __getter_t __get;
214};
215#undef T
216#undef __getter_t
217
218#ifdef __cforall
219#define __dllist_t(T) __dllist(T)
220#else
221#define __dllist_t(T) struct __dllist
222#endif
223
224#ifdef __cforall
225
226        forall(dtype T | sized(T))
227        static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) {
228                this.head{ NULL };
229                this.__get = __get;
230        }
231
232        #define next 0
233        #define prev 1
234        forall(dtype T | sized(T))
235        static inline void push_front( __dllist(T) & this, T & node ) with( this ) {
236                verify(__get);
237                if ( head ) {
238                        __get( node ).next = head;
239                        __get( node ).prev = __get( *head ).prev;
240                        // inserted node must be consistent before it is seen
241                        // prevent code movement across barrier
242                        asm( "" : : : "memory" );
243                        __get( *head ).prev = &node;
244                        T & _prev = *__get( node ).prev;
245                        __get( _prev ).next = &node;
246                }
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        forall(dtype T | sized(T))
258        static inline void remove( __dllist(T) & this, T & node ) with( this ) {
259                verify(__get);
260                if ( &node == head ) {
261                        if ( __get( *head ).next == head ) {
262                                head = NULL;
263                        }
264                        else {
265                                head = __get( *head ).next;
266                        }
267                }
268                __get( *__get( node ).next ).prev = __get( node ).prev;
269                __get( *__get( node ).prev ).next = __get( node ).next;
270                __get( node ).next = NULL;
271                __get( node ).prev = NULL;
272        }
273
274        forall(dtype T | sized(T))
275        static inline int ?!=?( const __dllist(T) & this, __attribute__((unused)) zero_t zero ) {
276                return this.head != 0;
277        }
278        #undef next
279        #undef prev
280#endif
281
282//-----------------------------------------------------------------------------
283// Tools
284//-----------------------------------------------------------------------------
285#ifdef __cforall
286
287#endif
Note: See TracBrowser for help on using the repository browser.