source: libcfa/src/containers/stackLockFree.hfa @ b232745

//
// 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 --
//
// Author           : Peter A. Buhr
// Created On       : Wed May 13 20:58:58 2020
// Last Modified By : Peter A. Buhr
// Last Modified On : Mon May 18 13:30:08 2020
// Update Count     : 55
//

#pragma once

#include <stdint.h>

forall( dtype T )
union Link {
        struct {                                                                        // 32/64-bit x 2
                T * volatile top;                                                               // pointer to stack top
                uintptr_t count;                                                // count each push
        };
        #if __SIZEOF_INT128__ == 16
        __int128                                                                        // gcc, 128-bit integer
        #else
        uint64_t                                                                        // 64-bit integer
        #endif // __SIZEOF_INT128__ == 16
        atom;
}; // Link

forall( otype T | { Link(T) * ?`next( T * ); } ) {
        struct StackLF {
                Link(T) stack;
        }; // StackLF

        static inline {
                void ?{}( StackLF(T) & this ) with(this) { stack.atom = 0; }

                T * top( StackLF(T) & this ) with(this) { return stack.top; }

                void push( StackLF(T) & this, T & n ) with(this) {
                        for () {                                                                        // busy wait
                                *( &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 @= {};
                        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))@{ {( 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


// Local Variables: //
// tab-width: 4 //
// End: //