Changes in libcfa/src/containers/stackLockFree.hfa [9019b14:0f89d4f]

File:

• libcfa/src/containers/stackLockFree.hfa (modified) (3 diffs)

libcfa/src/containers/stackLockFree.hfa

@@ -1 @@
-// 
+//
 // Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
 // The contents of this file are covered under the licence agreement in the
 // file "LICENCE" distributed with Cforall.
 //
-// stackLockFree.hfa -- 
-// 
+// stackLockFree.hfa --
+//
 // Author           : Peter A. Buhr
 // Created On       : Wed May 13 20:58:58 2020
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Sun Jun 14 13:25:09 2020
-// Update Count     : 64
-// 
+// Last Modified On : Mon May 18 13:30:08 2020
+// Update Count     : 55
+//
 
 #pragma once
@@ -19 +19 @@
 forall( dtype T )
 union Link {
-        struct {                                                                                        // 32/64-bit x 2
+        struct {                                                                        // 32/64-bit x 2
                 T * volatile top;                                                               // pointer to stack top
-                uintptr_t count;                                                                // count each push
+                uintptr_t count;                                                // count each push
         };
         #if __SIZEOF_INT128__ == 16
-        __int128                                                                                        // gcc, 128-bit integer
+        __int128                                                                        // gcc, 128-bit integer
         #else
-        uint64_t                                                                                        // 64-bit integer
+        uint64_t                                                                        // 64-bit integer
         #endif // __SIZEOF_INT128__ == 16
         atom;
 }; // Link
 
-forall( dtype T | sized(T) | { Link(T) * getNext( T * ); } ) {
-    struct StackLF {
+forall( otype T | { Link(T) * ?`next( T * ); } ) {
+        struct StackLF {
                 Link(T) stack;
         }; // StackLF
@@ -42 +42 @@
 
                 void push( StackLF(T) & this, T & n ) with(this) {
-                        *getNext( &n ) = stack;                                         // atomic assignment unnecessary, or use CAA
                         for () {                                                                        // busy wait
-                          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
+                                *( &n )`next = stack;                                   // atomic assignment unnecessary, or use CAA
+                          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
                         } // for
                 } // push
 
                 T * pop( StackLF(T) & this ) with(this) {
-                        Link(T) t @= stack;                                                     // atomic assignment unnecessary, or use CAA
+                        Link(T) t @= {};
                         for () {                                                                        // busy wait
+                                t = stack;                                                              // atomic assignment unnecessary, or use CAA
                           if ( t.top == 0p ) return 0p;                         // empty stack ?
-                          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
+                          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 node
                         } // for
                 } // pop
+
+                bool unsafe_remove( StackLF(T) & this, T * node ) with(this) {
+                        Link(T) * link = &stack;
+                        for() {
+                                T * next = link->top;
+                                if( next == node ) {
+                                        link->top = ( node )`next->top;
+                                        return true;
+                                }
+                                if( next == 0p ) return false;
+                                link = (next)`next;
+                        }
+                }
         } // distribution
 } // distribution