[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 | // |
---|
| 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 | |
---|
[c2b9f21] | 17 | #include "bits/align.h" |
---|
[0cf5b79] | 18 | #include "bits/defs.h" |
---|
[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 |
---|
[ea7d2b0] | 80 | forall(dtype TYPE | is_node(TYPE)) |
---|
| 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 |
---|
[ea7d2b0] | 97 | forall(dtype T | is_node(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 | } |
---|
| 118 | #endif |
---|
| 119 | |
---|
| 120 | //----------------------------------------------------------------------------- |
---|
| 121 | // Queue |
---|
| 122 | //----------------------------------------------------------------------------- |
---|
[0cf5b79] | 123 | #ifdef __cforall |
---|
| 124 | forall(dtype TYPE | is_node(TYPE)) |
---|
[ea7d2b0] | 125 | #define T TYPE |
---|
| 126 | #else |
---|
| 127 | #define T void |
---|
| 128 | #endif |
---|
| 129 | struct __queue { |
---|
| 130 | T * head; |
---|
| 131 | T ** tail; |
---|
| 132 | }; |
---|
[0cf5b79] | 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 |
---|
[ea7d2b0] | 140 | |
---|
[0cf5b79] | 141 | #ifdef __cforall |
---|
[65deb18] | 142 | |
---|
[ea7d2b0] | 143 | forall(dtype T | is_node(T)) |
---|
[65deb18] | 144 | static inline void ?{}( __queue(T) & this ) with( this ) { |
---|
| 145 | head{ NULL }; |
---|
| 146 | tail{ &head }; |
---|
[ea7d2b0] | 147 | } |
---|
| 148 | |
---|
| 149 | forall(dtype T | is_node(T) | sized(T)) |
---|
[65deb18] | 150 | static inline void append( __queue(T) & this, T * val ) with( this ) { |
---|
| 151 | verify(tail != NULL); |
---|
| 152 | *tail = val; |
---|
| 153 | tail = &get_next( *val ); |
---|
[ea7d2b0] | 154 | } |
---|
| 155 | |
---|
| 156 | forall(dtype T | is_node(T) | sized(T)) |
---|
[0cf5b79] | 157 | static inline T * pop_head( __queue(T) & this ) { |
---|
[ea7d2b0] | 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)) |
---|
[65deb18] | 170 | static inline T * remove( __queue(T) & this, T ** it ) with( this ) { |
---|
[ea7d2b0] | 171 | T * val = *it; |
---|
| 172 | verify( val ); |
---|
| 173 | |
---|
| 174 | (*it) = get_next( *val ); |
---|
| 175 | |
---|
[65deb18] | 176 | if( tail == &get_next( *val ) ) { |
---|
| 177 | tail = it; |
---|
[ea7d2b0] | 178 | } |
---|
| 179 | |
---|
| 180 | get_next( *val ) = NULL; |
---|
| 181 | |
---|
[65deb18] | 182 | verify( (head == NULL) == (&head == tail) ); |
---|
| 183 | verify( *tail == NULL ); |
---|
[ea7d2b0] | 184 | return val; |
---|
| 185 | } |
---|
| 186 | #endif |
---|
[65deb18] | 187 | |
---|
[14a61b5] | 188 | |
---|
| 189 | //----------------------------------------------------------------------------- |
---|
| 190 | // Doubly Linked List |
---|
| 191 | //----------------------------------------------------------------------------- |
---|
| 192 | #ifdef __cforall |
---|
[de94a60] | 193 | forall(dtype TYPE | sized(TYPE)) |
---|
[14a61b5] | 194 | #define T TYPE |
---|
[705e612] | 195 | #define __getter_t * [T * & next, T * & prev] ( T & ) |
---|
[14a61b5] | 196 | #else |
---|
[705e612] | 197 | typedef void (*__generit_c_getter_t)(); |
---|
[14a61b5] | 198 | #define T void |
---|
[705e612] | 199 | #define __getter_t __generit_c_getter_t |
---|
[14a61b5] | 200 | #endif |
---|
| 201 | struct __dllist { |
---|
| 202 | T * head; |
---|
[705e612] | 203 | __getter_t __get; |
---|
[14a61b5] | 204 | }; |
---|
| 205 | #undef T |
---|
[705e612] | 206 | #undef __getter_t |
---|
[14a61b5] | 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 | |
---|
[de94a60] | 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; |
---|
[14a61b5] | 244 | } |
---|
| 245 | |
---|
[de94a60] | 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 |
---|
[14a61b5] | 263 | #endif |
---|
| 264 | |
---|
[65deb18] | 265 | //----------------------------------------------------------------------------- |
---|
| 266 | // Tools |
---|
| 267 | //----------------------------------------------------------------------------- |
---|
| 268 | #ifdef __cforall |
---|
| 269 | |
---|
| 270 | #endif |
---|