[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 |
---|
| 12 | // Last Modified On : Wed Jun 26 08:52:20 2019 |
---|
| 13 | // Update Count : 4 |
---|
[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 |
---|
| 29 | struct __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 | |
---|
[ea7d2b0] | 66 | //----------------------------------------------------------------------------- |
---|
| 67 | // Node Base |
---|
| 68 | //----------------------------------------------------------------------------- |
---|
| 69 | |
---|
[0cf5b79] | 70 | #ifdef __cforall |
---|
[ea7d2b0] | 71 | trait is_node(dtype T) { |
---|
| 72 | T*& get_next( T& ); |
---|
| 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 |
---|
| 85 | struct __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 ) { |
---|
| 99 | (this.top){ NULL }; |
---|
[ea7d2b0] | 100 | } |
---|
| 101 | |
---|
| 102 | forall(dtype T | is_node(T) | sized(T)) |
---|
[0cf5b79] | 103 | static inline void push( __stack(T) & this, T * val ) { |
---|
[ea7d2b0] | 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)) |
---|
[0cf5b79] | 110 | static inline T * pop( __stack(T) & this ) { |
---|
[ea7d2b0] | 111 | T * top = this.top; |
---|
| 112 | if( top ) { |
---|
| 113 | this.top = get_next( *top ); |
---|
| 114 | get_next( *top ) = NULL; |
---|
| 115 | } |
---|
| 116 | return top; |
---|
| 117 | } |
---|
[2233ad4] | 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 | } |
---|
[ea7d2b0] | 123 | #endif |
---|
| 124 | |
---|
| 125 | //----------------------------------------------------------------------------- |
---|
| 126 | // Queue |
---|
| 127 | //----------------------------------------------------------------------------- |
---|
[0cf5b79] | 128 | #ifdef __cforall |
---|
[3623f9d] | 129 | forall(dtype TYPE) |
---|
[ea7d2b0] | 130 | #define T TYPE |
---|
| 131 | #else |
---|
| 132 | #define T void |
---|
| 133 | #endif |
---|
| 134 | struct __queue { |
---|
| 135 | T * head; |
---|
| 136 | T ** tail; |
---|
| 137 | }; |
---|
[0cf5b79] | 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 |
---|
[ea7d2b0] | 145 | |
---|
[0cf5b79] | 146 | #ifdef __cforall |
---|
[65deb18] | 147 | |
---|
[3623f9d] | 148 | forall(dtype T) |
---|
[65deb18] | 149 | static inline void ?{}( __queue(T) & this ) with( this ) { |
---|
| 150 | head{ NULL }; |
---|
| 151 | tail{ &head }; |
---|
[ea7d2b0] | 152 | } |
---|
| 153 | |
---|
| 154 | forall(dtype T | is_node(T) | sized(T)) |
---|
[65deb18] | 155 | static inline void append( __queue(T) & this, T * val ) with( this ) { |
---|
| 156 | verify(tail != NULL); |
---|
| 157 | *tail = val; |
---|
| 158 | tail = &get_next( *val ); |
---|
[ea7d2b0] | 159 | } |
---|
| 160 | |
---|
| 161 | forall(dtype T | is_node(T) | sized(T)) |
---|
[0cf5b79] | 162 | static inline T * pop_head( __queue(T) & this ) { |
---|
[ea7d2b0] | 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)) |
---|
[65deb18] | 175 | static inline T * remove( __queue(T) & this, T ** it ) with( this ) { |
---|
[ea7d2b0] | 176 | T * val = *it; |
---|
| 177 | verify( val ); |
---|
| 178 | |
---|
| 179 | (*it) = get_next( *val ); |
---|
| 180 | |
---|
[65deb18] | 181 | if( tail == &get_next( *val ) ) { |
---|
| 182 | tail = it; |
---|
[ea7d2b0] | 183 | } |
---|
| 184 | |
---|
| 185 | get_next( *val ) = NULL; |
---|
| 186 | |
---|
[65deb18] | 187 | verify( (head == NULL) == (&head == tail) ); |
---|
| 188 | verify( *tail == NULL ); |
---|
[ea7d2b0] | 189 | return val; |
---|
| 190 | } |
---|
[8ebbfc4] | 191 | |
---|
| 192 | forall(dtype T | is_node(T)) |
---|
[2233ad4] | 193 | static inline int ?!=?( const __queue(T) & this, __attribute__((unused)) zero_t zero ) { |
---|
[0c674e8] | 194 | return this.head != 0; |
---|
[8ebbfc4] | 195 | } |
---|
[ea7d2b0] | 196 | #endif |
---|
[65deb18] | 197 | |
---|
[14a61b5] | 198 | |
---|
| 199 | //----------------------------------------------------------------------------- |
---|
| 200 | // Doubly Linked List |
---|
| 201 | //----------------------------------------------------------------------------- |
---|
| 202 | #ifdef __cforall |
---|
[ffe2fad] | 203 | forall(dtype TYPE) |
---|
[14a61b5] | 204 | #define T TYPE |
---|
[705e612] | 205 | #define __getter_t * [T * & next, T * & prev] ( T & ) |
---|
[14a61b5] | 206 | #else |
---|
[705e612] | 207 | typedef void (*__generit_c_getter_t)(); |
---|
[14a61b5] | 208 | #define T void |
---|
[705e612] | 209 | #define __getter_t __generit_c_getter_t |
---|
[14a61b5] | 210 | #endif |
---|
| 211 | struct __dllist { |
---|
| 212 | T * head; |
---|
[705e612] | 213 | __getter_t __get; |
---|
[14a61b5] | 214 | }; |
---|
| 215 | #undef T |
---|
[705e612] | 216 | #undef __getter_t |
---|
[14a61b5] | 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 | |
---|
[de94a60] | 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 | |
---|
[639991a] | 232 | #define next 0 |
---|
| 233 | #define prev 1 |
---|
[de94a60] | 234 | forall(dtype T | sized(T)) |
---|
| 235 | static inline void push_front( __dllist(T) & this, T & node ) with( this ) { |
---|
[a1a17a74] | 236 | verify(__get); |
---|
[de94a60] | 237 | if ( head ) { |
---|
[639991a] | 238 | __get( node ).next = head; |
---|
| 239 | __get( node ).prev = __get( *head ).prev; |
---|
[de94a60] | 240 | // inserted node must be consistent before it is seen |
---|
| 241 | // prevent code movement across barrier |
---|
| 242 | asm( "" : : : "memory" ); |
---|
[639991a] | 243 | __get( *head ).prev = &node; |
---|
| 244 | T & _prev = *__get( node ).prev; |
---|
| 245 | __get( _prev ).next = &node; |
---|
[de94a60] | 246 | } |
---|
| 247 | else { |
---|
[639991a] | 248 | __get( node ).next = &node; |
---|
| 249 | __get( node ).prev = &node; |
---|
[de94a60] | 250 | } |
---|
| 251 | |
---|
| 252 | // prevent code movement across barrier |
---|
| 253 | asm( "" : : : "memory" ); |
---|
| 254 | head = &node; |
---|
[14a61b5] | 255 | } |
---|
| 256 | |
---|
[de94a60] | 257 | forall(dtype T | sized(T)) |
---|
| 258 | static inline void remove( __dllist(T) & this, T & node ) with( this ) { |
---|
[a1a17a74] | 259 | verify(__get); |
---|
[de94a60] | 260 | if ( &node == head ) { |
---|
[639991a] | 261 | if ( __get( *head ).next == head ) { |
---|
[de94a60] | 262 | head = NULL; |
---|
| 263 | } |
---|
| 264 | else { |
---|
[639991a] | 265 | head = __get( *head ).next; |
---|
[de94a60] | 266 | } |
---|
| 267 | } |
---|
[639991a] | 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; |
---|
[de94a60] | 272 | } |
---|
[0c674e8] | 273 | |
---|
| 274 | forall(dtype T | sized(T)) |
---|
[2233ad4] | 275 | static inline int ?!=?( const __dllist(T) & this, __attribute__((unused)) zero_t zero ) { |
---|
[0c674e8] | 276 | return this.head != 0; |
---|
| 277 | } |
---|
[639991a] | 278 | #undef next |
---|
| 279 | #undef prev |
---|
[14a61b5] | 280 | #endif |
---|
| 281 | |
---|
[65deb18] | 282 | //----------------------------------------------------------------------------- |
---|
| 283 | // Tools |
---|
| 284 | //----------------------------------------------------------------------------- |
---|
| 285 | #ifdef __cforall |
---|
| 286 | |
---|
[2233ad4] | 287 | #endif |
---|