Changeset d95969a for libcfa/src/bits
- Timestamp:
- Jan 25, 2021, 3:45:42 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum, stuck-waitfor-destruct
- Children:
- c292244
- Parents:
- b6a8b31 (diff), 7158202 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - Location:
- libcfa/src/bits
- Files:
-
- 2 added
- 8 edited
-
algorithm.hfa (modified) (7 diffs)
-
collection.hfa (modified) (5 diffs)
-
containers.hfa (modified) (10 diffs)
-
defs.hfa (modified) (2 diffs)
-
locks.hfa (modified) (3 diffs)
-
queue.hfa (modified) (2 diffs)
-
sequence.hfa (modified) (9 diffs)
-
stack.hfa (modified) (2 diffs)
-
weakso_locks.cfa (added)
-
weakso_locks.hfa (added)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/algorithm.hfa
rb6a8b31 rd95969a 17 17 18 18 #ifdef SAFE_SORT 19 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort2( T * arr );20 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort3( T * arr );21 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort4( T * arr );22 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort5( T * arr );23 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort6( T * arr );24 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim );19 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort2( T * arr ); 20 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort3( T * arr ); 21 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort4( T * arr ); 22 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort5( T * arr ); 23 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort6( T * arr ); 24 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim ); 25 25 26 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )26 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 27 27 static inline void __libcfa_small_sort( T * arr, size_t dim ) { 28 28 switch( dim ) { … … 41 41 #define SWAP(x,y) { T a = min(arr[x], arr[y]); T b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;} 42 42 43 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )43 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 44 44 static inline void __libcfa_small_sort2( T * arr ) { 45 45 SWAP(0, 1); 46 46 } 47 47 48 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )48 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 49 49 static inline void __libcfa_small_sort3( T * arr ) { 50 50 SWAP(1, 2); … … 53 53 } 54 54 55 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )55 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 56 56 static inline void __libcfa_small_sort4( T * arr ) { 57 57 SWAP(0, 1); … … 62 62 } 63 63 64 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )64 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 65 65 static inline void __libcfa_small_sort5( T * arr ) { 66 66 SWAP(0, 1); … … 75 75 } 76 76 77 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )77 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 78 78 static inline void __libcfa_small_sort6( T * arr ) { 79 79 SWAP(1, 2); … … 91 91 } 92 92 93 forall( otypeT | { int ?<?( T, T ); int ?>?( T, T ); } )93 forall( T | { int ?<?( T, T ); int ?>?( T, T ); } ) 94 94 static inline void __libcfa_small_sortN( T * arr, size_t dim ) { 95 95 int i, j; … … 112 112 static inline void __libcfa_small_sortN( void* * arr, size_t dim ); 113 113 114 forall( dtype T)114 forall( T & ) 115 115 static inline void __libcfa_small_sort( T* * arr, size_t dim ) { 116 116 switch( dim ) { -
libcfa/src/bits/collection.hfa
rb6a8b31 rd95969a 1 // 2 // Cforall Version 1.0.0 Copyright (C) 2021 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/collection.hfa -- PUBLIC 8 // Intrusive singly-linked list 9 // 10 // Author : Colby Alexander Parsons & Peter A. Buhr 11 // Created On : Thu Jan 21 19:46:50 2021 12 // Last Modified By : 13 // Last Modified On : 14 // Update Count : 15 // 16 1 17 #pragma once 2 #include <stdio.h> // REMOVE THIS AFTER DEBUGGING3 4 18 5 19 struct Colable { 6 struct Colable * next;// next node in the list20 // next node in the list 7 21 // invariant: (next != 0) <=> listed() 22 struct Colable * next; 8 23 }; 9 24 #ifdef __cforall … … 31 46 32 47 // // wrappers to make Collection have T 33 // forall( dtype T) {48 // forall( T & ) { 34 49 // T *& Next( T * n ) { 35 50 // return (T *)Next( (Colable *)n ); … … 38 53 } // distribution 39 54 40 forall( dtype T| { T *& Next ( T * ); } ) {55 static inline forall( T & | { T *& Next ( T * ); } ) { 41 56 bool listed( T * n ) { 42 57 return Next( n ) != 0p; … … 53 68 Collection & ?=?( const Collection & ) = void; // no assignment 54 69 55 void ?{}( Collection & collection ) with( collection ) { 70 void ?{}( Collection & collection ) with( collection ) { 56 71 root = 0p; 57 72 } // post: empty() … … 76 91 } // post: elts = null 77 92 78 forall( dtype T) {93 forall( T & ) { 79 94 T * Curr( ColIter & ci ) with( ci ) { 80 95 return (T *)curr; -
libcfa/src/bits/containers.hfa
rb6a8b31 rd95969a 23 23 24 24 #ifdef __cforall 25 forall( dtype T)25 forall(T &) 26 26 #else 27 27 #define T void … … 40 40 41 41 #ifdef __cforall 42 // forall( otypeT | sized(T))42 // forall(T | sized(T)) 43 43 // static inline void ?{}(__small_array(T) & this) {} 44 44 45 forall( dtype T| sized(T))45 forall(T & | sized(T)) 46 46 static inline T & ?[?]( __small_array(T) & this, __lock_size_t idx ) { 47 47 return ((typeof(this.data))this.data)[idx]; 48 48 } 49 49 50 forall( dtype T| sized(T))50 forall(T & | sized(T)) 51 51 static inline T & ?[?]( const __small_array(T) & this, __lock_size_t idx ) { 52 52 return ((typeof(this.data))this.data)[idx]; 53 53 } 54 54 55 forall( dtype T)55 forall(T &) 56 56 static inline T * begin( const __small_array(T) & this ) { 57 57 return ((typeof(this.data))this.data); 58 58 } 59 59 60 forall( dtype T| sized(T))60 forall(T & | sized(T)) 61 61 static inline T * end( const __small_array(T) & this ) { 62 62 return ((typeof(this.data))this.data) + this.size; … … 69 69 70 70 #ifdef __cforall 71 trait is_node( dtype T) {71 trait is_node(T &) { 72 72 T *& get_next( T & ); 73 73 }; … … 78 78 //----------------------------------------------------------------------------- 79 79 #ifdef __cforall 80 forall( dtype TYPE)80 forall(TYPE &) 81 81 #define T TYPE 82 82 #else … … 95 95 96 96 #ifdef __cforall 97 forall( dtype T)97 forall(T &) 98 98 static inline void ?{}( __stack(T) & this ) { 99 99 (this.top){ 0p }; 100 100 } 101 101 102 static inline forall( dtype T| is_node(T) ) {102 static inline forall( T & | is_node(T) ) { 103 103 void push( __stack(T) & this, T * val ) { 104 104 verify( !get_next( *val ) ); … … 126 126 //----------------------------------------------------------------------------- 127 127 #ifdef __cforall 128 forall( dtype TYPE)128 forall(TYPE &) 129 129 #define T TYPE 130 130 #else … … 144 144 145 145 #ifdef __cforall 146 static inline forall( dtype T| is_node(T) ) {146 static inline forall( T & | is_node(T) ) { 147 147 void ?{}( __queue(T) & this ) with( this ) { 148 148 (this.head){ 1p }; … … 215 215 //----------------------------------------------------------------------------- 216 216 #ifdef __cforall 217 forall( dtype TYPE)217 forall(TYPE &) 218 218 #define T TYPE 219 219 #define __getter_t * [T * & next, T * & prev] ( T & ) … … 237 237 238 238 #ifdef __cforall 239 forall( dtype T)239 forall(T & ) 240 240 static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) { 241 241 (this.head){ 0p }; … … 245 245 #define next 0 246 246 #define prev 1 247 static inline forall( dtype T) {247 static inline forall(T &) { 248 248 void push_front( __dllist(T) & this, T & node ) with( this ) { 249 249 verify(__get); -
libcfa/src/bits/defs.hfa
rb6a8b31 rd95969a 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // defs.hfa -- 7 // defs.hfa -- Commen macros, functions and typedefs 8 // Most files depend on them and they are always useful to have. 9 // 10 // *** Must not contain code specific to libcfathread *** 8 11 // 9 12 // Author : Thierry Delisle … … 62 65 #endif 63 66 } 67 68 // pause to prevent excess processor bus usage 69 #if defined( __i386 ) || defined( __x86_64 ) 70 #define Pause() __asm__ __volatile__ ( "pause" : : : ) 71 #elif defined( __ARM_ARCH ) 72 #define Pause() __asm__ __volatile__ ( "YIELD" : : : ) 73 #else 74 #error unsupported architecture 75 #endif -
libcfa/src/bits/locks.hfa
rb6a8b31 rd95969a 5 5 // file "LICENCE" distributed with Cforall. 6 6 // 7 // bits/locks.hfa -- Fast internal locks. 7 // bits/locks.hfa -- Basic spinlocks that are reused in the system. 8 // Used for locks that aren't specific to cforall threads and can be used anywhere 9 // 10 // *** Must not contain code specific to libcfathread *** 8 11 // 9 12 // Author : Thierry Delisle … … 19 22 #include "bits/defs.hfa" 20 23 #include <assert.h> 21 22 #ifdef __cforall23 extern "C" {24 #include <pthread.h>25 }26 #endif27 28 // pause to prevent excess processor bus usage29 #if defined( __i386 ) || defined( __x86_64 )30 #define Pause() __asm__ __volatile__ ( "pause" : : : )31 #elif defined( __ARM_ARCH )32 #define Pause() __asm__ __volatile__ ( "YIELD" : : : )33 #else34 #error unsupported architecture35 #endif36 24 37 25 struct __spinlock_t { … … 104 92 enable_interrupts_noPoll(); 105 93 } 106 107 108 #ifdef __CFA_WITH_VERIFY__109 extern bool __cfaabi_dbg_in_kernel();110 #endif111 112 extern "C" {113 char * strerror(int);114 }115 #define CHECKED(x) { int err = x; if( err != 0 ) abort("KERNEL ERROR: Operation \"" #x "\" return error %d - %s\n", err, strerror(err)); }116 117 struct __bin_sem_t {118 pthread_mutex_t lock;119 pthread_cond_t cond;120 int val;121 };122 123 static inline void ?{}(__bin_sem_t & this) with( this ) {124 // Create the mutex with error checking125 pthread_mutexattr_t mattr;126 pthread_mutexattr_init( &mattr );127 pthread_mutexattr_settype( &mattr, PTHREAD_MUTEX_ERRORCHECK_NP);128 pthread_mutex_init(&lock, &mattr);129 130 pthread_cond_init (&cond, (const pthread_condattr_t *)0p); // workaround trac#208: cast should not be required131 val = 0;132 }133 134 static inline void ^?{}(__bin_sem_t & this) with( this ) {135 CHECKED( pthread_mutex_destroy(&lock) );136 CHECKED( pthread_cond_destroy (&cond) );137 }138 139 static inline void wait(__bin_sem_t & this) with( this ) {140 verify(__cfaabi_dbg_in_kernel());141 CHECKED( pthread_mutex_lock(&lock) );142 while(val < 1) {143 pthread_cond_wait(&cond, &lock);144 }145 val -= 1;146 CHECKED( pthread_mutex_unlock(&lock) );147 }148 149 static inline bool post(__bin_sem_t & this) with( this ) {150 bool needs_signal = false;151 152 CHECKED( pthread_mutex_lock(&lock) );153 if(val < 1) {154 val += 1;155 pthread_cond_signal(&cond);156 needs_signal = true;157 }158 CHECKED( pthread_mutex_unlock(&lock) );159 160 return needs_signal;161 }162 163 #undef CHECKED164 165 struct $thread;166 extern void park( void );167 extern void unpark( struct $thread * this );168 static inline struct $thread * active_thread ();169 170 // Semaphore which only supports a single thread171 struct single_sem {172 struct $thread * volatile ptr;173 };174 175 static inline {176 void ?{}(single_sem & this) {177 this.ptr = 0p;178 }179 180 void ^?{}(single_sem &) {}181 182 bool wait(single_sem & this) {183 for() {184 struct $thread * expected = this.ptr;185 if(expected == 1p) {186 if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {187 return false;188 }189 }190 else {191 /* paranoid */ verify( expected == 0p );192 if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {193 park();194 return true;195 }196 }197 198 }199 }200 201 bool post(single_sem & this) {202 for() {203 struct $thread * expected = this.ptr;204 if(expected == 1p) return false;205 if(expected == 0p) {206 if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {207 return false;208 }209 }210 else {211 if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {212 unpark( expected );213 return true;214 }215 }216 }217 }218 }219 220 // Synchronozation primitive which only supports a single thread and one post221 // Similar to a binary semaphore with a 'one shot' semantic222 // is expected to be discarded after each party call their side223 struct oneshot {224 // Internal state :225 // 0p : is initial state (wait will block)226 // 1p : fulfilled (wait won't block)227 // any thread : a thread is currently waiting228 struct $thread * volatile ptr;229 };230 231 static inline {232 void ?{}(oneshot & this) {233 this.ptr = 0p;234 }235 236 void ^?{}(oneshot &) {}237 238 // Wait for the post, return immidiately if it already happened.239 // return true if the thread was parked240 bool wait(oneshot & this) {241 for() {242 struct $thread * expected = this.ptr;243 if(expected == 1p) return false;244 /* paranoid */ verify( expected == 0p );245 if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {246 park();247 /* paranoid */ verify( this.ptr == 1p );248 return true;249 }250 }251 }252 253 // Mark as fulfilled, wake thread if needed254 // return true if a thread was unparked255 bool post(oneshot & this) {256 struct $thread * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);257 if( got == 0p ) return false;258 unpark( got );259 return true;260 }261 }262 263 // base types for future to build upon264 // It is based on the 'oneshot' type to allow multiple futures265 // to block on the same instance, permitting users to block a single266 // thread on "any of" [a given set of] futures.267 // does not support multiple threads waiting on the same future268 struct future_t {269 // Internal state :270 // 0p : is initial state (wait will block)271 // 1p : fulfilled (wait won't block)272 // 2p : in progress ()273 // 3p : abandoned, server should delete274 // any oneshot : a context has been setup to wait, a thread could wait on it275 struct oneshot * volatile ptr;276 };277 278 static inline {279 void ?{}(future_t & this) {280 this.ptr = 0p;281 }282 283 void ^?{}(future_t &) {}284 285 void reset(future_t & this) {286 // needs to be in 0p or 1p287 __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);288 }289 290 // check if the future is available291 bool available( future_t & this ) {292 return this.ptr == 1p;293 }294 295 // Prepare the future to be waited on296 // intented to be use by wait, wait_any, waitfor, etc. rather than used directly297 bool setup( future_t & this, oneshot & wait_ctx ) {298 /* paranoid */ verify( wait_ctx.ptr == 0p );299 // The future needs to set the wait context300 for() {301 struct oneshot * expected = this.ptr;302 // Is the future already fulfilled?303 if(expected == 1p) return false; // Yes, just return false (didn't block)304 305 // The future is not fulfilled, try to setup the wait context306 /* paranoid */ verify( expected == 0p );307 if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {308 return true;309 }310 }311 }312 313 // Stop waiting on a future314 // When multiple futures are waited for together in "any of" pattern315 // futures that weren't fulfilled before the thread woke up316 // should retract the wait ctx317 // intented to be use by wait, wait_any, waitfor, etc. rather than used directly318 void retract( future_t & this, oneshot & wait_ctx ) {319 // Remove the wait context320 struct oneshot * got = __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);321 322 // got == 0p: future was never actually setup, just return323 if( got == 0p ) return;324 325 // got == wait_ctx: since fulfil does an atomic_swap,326 // if we got back the original then no one else saw context327 // It is safe to delete (which could happen after the return)328 if( got == &wait_ctx ) return;329 330 // got == 1p: the future is ready and the context was fully consumed331 // the server won't use the pointer again332 // It is safe to delete (which could happen after the return)333 if( got == 1p ) return;334 335 // got == 2p: the future is ready but the context hasn't fully been consumed336 // spin until it is safe to move on337 if( got == 2p ) {338 while( this.ptr != 1p ) Pause();339 return;340 }341 342 // got == any thing else, something wen't wrong here, abort343 abort("Future in unexpected state");344 }345 346 // Mark the future as abandoned, meaning it will be deleted by the server347 bool abandon( future_t & this ) {348 /* paranoid */ verify( this.ptr != 3p );349 350 // Mark the future as abandonned351 struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);352 353 // If the future isn't already fulfilled, let the server delete it354 if( got == 0p ) return false;355 356 // got == 2p: the future is ready but the context hasn't fully been consumed357 // spin until it is safe to move on358 if( got == 2p ) {359 while( this.ptr != 1p ) Pause();360 got = 1p;361 }362 363 // The future is completed delete it now364 /* paranoid */ verify( this.ptr != 1p );365 free( &this );366 return true;367 }368 369 // from the server side, mark the future as fulfilled370 // delete it if needed371 bool fulfil( future_t & this ) {372 for() {373 struct oneshot * expected = this.ptr;374 // was this abandoned?375 #if defined(__GNUC__) && __GNUC__ >= 7376 #pragma GCC diagnostic push377 #pragma GCC diagnostic ignored "-Wfree-nonheap-object"378 #endif379 if( expected == 3p ) { free( &this ); return false; }380 #if defined(__GNUC__) && __GNUC__ >= 7381 #pragma GCC diagnostic pop382 #endif383 384 /* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen385 /* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.386 387 // If there is a wait context, we need to consume it and mark it as consumed after388 // If there is no context then we can skip the in progress phase389 struct oneshot * want = expected == 0p ? 1p : 2p;390 if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {391 if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return false; }392 bool ret = post( *expected );393 __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);394 return ret;395 }396 }397 398 }399 400 // Wait for the future to be fulfilled401 bool wait( future_t & this ) {402 oneshot temp;403 if( !setup(this, temp) ) return false;404 405 // Wait context is setup, just wait on it406 bool ret = wait( temp );407 408 // Wait for the future to tru409 while( this.ptr == 2p ) Pause();410 // Make sure the state makes sense411 // Should be fulfilled, could be in progress but it's out of date if so412 // since if that is the case, the oneshot was fulfilled (unparking this thread)413 // and the oneshot should not be needed any more414 __attribute__((unused)) struct oneshot * was = this.ptr;415 /* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was );416 417 // Mark the future as fulfilled, to be consistent418 // with potential calls to avail419 // this.ptr = 1p;420 return ret;421 }422 }423 94 #endif -
libcfa/src/bits/queue.hfa
rb6a8b31 rd95969a 9 9 // instead of being null. 10 10 11 forall( dtype T| { T *& Next ( T * ); } ) {11 forall( T & | { T *& Next ( T * ); } ) { 12 12 struct Queue { 13 13 inline Collection; // Plan 9 inheritance … … 151 151 } // distribution 152 152 153 forall( dtype T| { T *& Next ( T * ); } ) {153 forall( T & | { T *& Next ( T * ); } ) { 154 154 struct QueueIter { 155 155 inline ColIter; // Plan 9 inheritance -
libcfa/src/bits/sequence.hfa
rb6a8b31 rd95969a 1 // 2 // Cforall Version 1.0.0 Copyright (C) 2021 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/sequence.hfa -- PUBLIC 8 // Intrusive doubly-linked list 9 // 10 // Author : Colby Alexander Parsons & Peter A. Buhr 11 // Created On : Thu Jan 21 19:46:50 2021 12 // Last Modified By : 13 // Last Modified On : 14 // Update Count : 15 // 16 1 17 #pragma once 2 18 … … 6 22 struct Seqable { 7 23 __cfa_anonymous_object(Colable); 8 struct Seqable * back; // pointer to previous node in the list 24 // pointer to previous node in the list 25 struct Seqable * back; 9 26 }; 10 27 … … 27 44 return sq->back; 28 45 } 29 30 // // wrappers to make Collection have T31 // forall( dtype T ) {32 // T *& Back( T * n ) {33 // return (T *)Back( (Seqable *)n );34 // }35 // } // distribution36 46 } // distribution 37 47 … … 43 53 // and the back field of the last node points at the first node (circular). 44 54 45 forall( dtype T | { T *& Back ( T * ); T *& Next ( T * ); }) {55 forall( T & ) { 46 56 struct Sequence { 47 inline Collection; // Plan 9 inheritance 57 // Plan 9 inheritance 58 inline Collection; 48 59 }; 49 60 50 61 static inline { 62 void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy 63 Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment 64 65 void ?{}( Sequence(T) & s ) with( s ) { 66 ((Collection &)s){}; 67 } // post: isEmpty() 68 } 69 70 static inline forall(| { T *& Back ( T * ); T *& Next ( T * ); }) { 51 71 // wrappers to make Collection have T 52 72 T & head( Sequence(T) & s ) with( s ) { 53 73 return *(T *)head( (Collection &)s ); 54 74 } // post: empty() & head() == 0 | !empty() & head() in *s 55 56 void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy57 Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment58 59 void ?{}( Sequence(T) & s ) with( s ) {60 ((Collection &)s){};61 } // post: isEmpty()62 75 63 76 // Return a pointer to the last sequence element, without removing it. … … 145 158 return n; 146 159 } // post: n->listed() & *n in *s & succ(n) == bef 147 160 148 161 // pre: n->listed() & *n in *s 149 162 T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1) … … 231 244 } // distribution 232 245 233 forall( dtype T| { T *& Back ( T * ); T *& Next ( T * ); } ) {246 forall( T & | { T *& Back ( T * ); T *& Next ( T * ); } ) { 234 247 // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order. 235 248 struct SeqIter { … … 285 298 286 299 static inline { 287 void ?{}( SeqIterRev(T) & si ) with( si ) { 300 void ?{}( SeqIterRev(T) & si ) with( si ) { 288 301 ((ColIter &)si){}; 289 302 seq = 0p; … … 291 304 292 305 // Create a iterator active in sequence s. 293 void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 306 void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 294 307 ((ColIter &)si){}; 295 308 seq = &s; … … 297 310 } // post: elts = null 298 311 299 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) { 312 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) { 300 313 ((ColIter &)si){}; 301 314 seq = &s; -
libcfa/src/bits/stack.hfa
rb6a8b31 rd95969a 9 9 // instead of being null. 10 10 11 forall( dtype T| { T *& Next ( T * ); } ) {11 forall( T & | { T *& Next ( T * ); } ) { 12 12 struct Stack { 13 13 inline Collection; // Plan 9 inheritance … … 67 67 // order returned by drop(). 68 68 69 forall( dtype T| { T *& Next ( T * ); } ) {69 forall( T & | { T *& Next ( T * ); } ) { 70 70 struct StackIter { 71 71 inline ColIter; // Plan 9 inheritance
Note:
See TracChangeset
for help on using the changeset viewer.
