[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 |
---|
| 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)) |
---|
[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 |
---|
| 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 ) { |
---|
[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 |
---|
| 133 | struct __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 |
---|
| 206 | struct __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: // |
---|