source: libcfa/src/containers/stackLockFree.hfa @ 64a7146

arm-ehjacob/cs343-translationnew-astnew-ast-unique-expr
Last change on this file since 64a7146 was 64a7146, checked in by Thierry Delisle <tdelisle@…>, 18 months ago

Fixed idle sleep to no-longer use a spinlock, broke registration and gdbtools in the process

  • Property mode set to 100644
File size: 2.2 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
3// The contents of this file are covered under the licence agreement in the
4// file "LICENCE" distributed with Cforall.
5//
6// stackLockFree.hfa --
7//
8// Author           : Peter A. Buhr
9// Created On       : Wed May 13 20:58:58 2020
10// Last Modified By : Peter A. Buhr
11// Last Modified On : Mon May 18 13:30:08 2020
12// Update Count     : 55
13//
14
15#pragma once
16
17#include <stdint.h>
18
19forall( dtype T )
20union Link {
21        struct {                                                                        // 32/64-bit x 2
22                T * volatile top;                                                               // pointer to stack top
23                uintptr_t count;                                                // count each push
24        };
25        #if __SIZEOF_INT128__ == 16
26        __int128                                                                        // gcc, 128-bit integer
27        #else
28        uint64_t                                                                        // 64-bit integer
29        #endif // __SIZEOF_INT128__ == 16
30        atom;
31}; // Link
32
33forall( otype T | { Link(T) * getNext( T * ); } ) {
34        struct StackLF {
35                Link(T) stack;
36        }; // StackLF
37
38        static inline {
39                void ?{}( StackLF(T) & this ) with(this) { stack.atom = 0; }
40
41                T * top( StackLF(T) & this ) with(this) { return stack.top; }
42
43                void push( StackLF(T) & this, T & n ) with(this) {
44                        for () {                                                                        // busy wait
45                                *getNext( &n ) = stack;                                 // atomic assignment unnecessary, or use CAA
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                        } // for
48                } // push
49
50                T * pop( StackLF(T) & this ) with(this) {
51                        Link(T) t @= {};
52                        for () {                                                                        // busy wait
53                                t = stack;                                                              // atomic assignment unnecessary, or use CAA
54                          if ( t.top == 0p ) return 0p;                         // empty stack ?
55                          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                        } // for
57                } // 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 = getNext( node )->top;
65                                        return true;
66                                }
67                                if( next == 0p ) return false;
68                                link = getNext(next);
69                        }
70                }
71        } // distribution
72} // distribution
73
74
75// Local Variables: //
76// tab-width: 4 //
77// End: //
Note: See TracBrowser for help on using the repository browser.