- File:
-
- 1 edited
-
libcfa/src/containers/stackLockFree.hfa (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/containers/stackLockFree.hfa
r0f89d4f r9019b14 1 // 1 // 2 2 // Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo 3 3 // The contents of this file are covered under the licence agreement in the 4 4 // file "LICENCE" distributed with Cforall. 5 5 // 6 // stackLockFree.hfa -- 7 // 6 // stackLockFree.hfa -- 7 // 8 8 // Author : Peter A. Buhr 9 9 // Created On : Wed May 13 20:58:58 2020 10 10 // Last Modified By : Peter A. Buhr 11 // Last Modified On : Mon May 18 13:30:08202012 // Update Count : 5513 // 11 // Last Modified On : Sun Jun 14 13:25:09 2020 12 // Update Count : 64 13 // 14 14 15 15 #pragma once … … 19 19 forall( dtype T ) 20 20 union Link { 21 struct { // 32/64-bit x 221 struct { // 32/64-bit x 2 22 22 T * volatile top; // pointer to stack top 23 uintptr_t count; // count each push23 uintptr_t count; // count each push 24 24 }; 25 25 #if __SIZEOF_INT128__ == 16 26 __int128 // gcc, 128-bit integer26 __int128 // gcc, 128-bit integer 27 27 #else 28 uint64_t // 64-bit integer28 uint64_t // 64-bit integer 29 29 #endif // __SIZEOF_INT128__ == 16 30 30 atom; 31 31 }; // Link 32 32 33 forall( otype T | { Link(T) * ?`next( T * ); } ) {34 33 forall( dtype T | sized(T) | { Link(T) * getNext( T * ); } ) { 34 struct StackLF { 35 35 Link(T) stack; 36 36 }; // StackLF … … 42 42 43 43 void push( StackLF(T) & this, T & n ) with(this) { 44 *getNext( &n ) = stack; // atomic assignment unnecessary, or use CAA 44 45 for () { // busy wait 45 *( &n )`next = stack; // atomic assignment unnecessary, or use CAA 46 if ( __atomic_compare_exchange_n( &stack.atom, &( &n )`next->atom, (Link(T))@{ {&n, ( &n )`next->count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node 46 if ( __atomic_compare_exchange_n( &stack.atom, &getNext( &n )->atom, (Link(T))@{ {&n, getNext( &n )->count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node 47 47 } // for 48 48 } // push 49 49 50 50 T * pop( StackLF(T) & this ) with(this) { 51 Link(T) t @= {};51 Link(T) t @= stack; // atomic assignment unnecessary, or use CAA 52 52 for () { // busy wait 53 t = stack; // atomic assignment unnecessary, or use CAA54 53 if ( t.top == 0p ) return 0p; // empty stack ? 55 if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ { ( t.top )`next->top, t.count} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.top; // attempt to update top node54 if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ {getNext( t.top )->top, t.count} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.top; // attempt to update top node 56 55 } // for 57 56 } // pop 58 59 bool unsafe_remove( StackLF(T) & this, T * node ) with(this) {60 Link(T) * link = &stack;61 for() {62 T * next = link->top;63 if( next == node ) {64 link->top = ( node )`next->top;65 return true;66 }67 if( next == 0p ) return false;68 link = (next)`next;69 }70 }71 57 } // distribution 72 58 } // distribution
Note:
See TracChangeset
for help on using the changeset viewer.
