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

// 
// 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 : Sun Jun 14 13:25:09 2020
// Update Count     : 64
// 

#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( dtype T | sized(T) | { Link(T) * getNext( 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) {
                        *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
                        } // for
                } // push

                T * pop( StackLF(T) & this ) with(this) {
                        Link(T) t @= stack;                                                     // atomic assignment unnecessary, or use CAA
                        for () {                                                                        // busy wait
                          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
                        } // for
                } // pop
        } // distribution
} // distribution


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