[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 | |
---|
| 188 | //----------------------------------------------------------------------------- |
---|
| 189 | // Tools |
---|
| 190 | //----------------------------------------------------------------------------- |
---|
| 191 | #ifdef __cforall |
---|
| 192 | |
---|
| 193 | #endif |
---|