source: src/libcfa/bits/containers.h @ 705e612

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerwith_gc
Last change on this file since 705e612 was 705e612, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

fixed containers for C compilation

  • 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                if ( head ) {
227                        __get( node )_next = head;
228                        __get( node )_prev = __get( *head )_prev;
229                        // inserted node must be consistent before it is seen
230                        // prevent code movement across barrier
231                        asm( "" : : : "memory" );
232                        __get( *head )_prev = &node;
233                        T & prev = *__get( node )_prev;
234                        __get( prev )_next = &node;
235                }
236                else {
237                        __get( node )_next = &node;
238                        __get( node )_prev = &node;
239                }
240
241                // prevent code movement across barrier
242                asm( "" : : : "memory" );
243                head = &node;
244        }
245
246        forall(dtype T | sized(T))
247        static inline void remove( __dllist(T) & this, T & node ) with( this ) {
248                if ( &node == head ) {
249                        if ( __get( *head )_next == head ) {
250                                head = NULL;
251                        }
252                        else {
253                                head = __get( *head )_next;
254                        }
255                }
256                __get( *__get( node )_next )_prev = __get( node )_prev;
257                __get( *__get( node )_prev )_next = __get( node )_next;
258                __get( node )_next = NULL;
259                __get( node )_prev = NULL;
260        }
261        #undef _next
262        #undef _prev
263#endif
264
265//-----------------------------------------------------------------------------
266// Tools
267//-----------------------------------------------------------------------------
268#ifdef __cforall
269
270#endif
Note: See TracBrowser for help on using the repository browser.