[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: //
|
---|