1 | #pragma once |
---|
2 | |
---|
3 | #include "utils.hpp" |
---|
4 | |
---|
5 | |
---|
6 | class snzi_t { |
---|
7 | class node; |
---|
8 | public: |
---|
9 | const unsigned mask; |
---|
10 | const int root; |
---|
11 | std::unique_ptr<snzi_t::node[]> nodes; |
---|
12 | |
---|
13 | snzi_t(unsigned depth, unsigned base = 2); |
---|
14 | |
---|
15 | void arrive(int idx) { |
---|
16 | idx >>= 2; |
---|
17 | idx %= mask; |
---|
18 | nodes[idx].arrive(); |
---|
19 | } |
---|
20 | |
---|
21 | void depart(int idx) { |
---|
22 | idx >>= 2; |
---|
23 | idx %= mask; |
---|
24 | nodes[idx].depart(); |
---|
25 | } |
---|
26 | |
---|
27 | bool query() const { |
---|
28 | return nodes[root].query(); |
---|
29 | } |
---|
30 | |
---|
31 | |
---|
32 | private: |
---|
33 | class __attribute__((aligned(128))) node { |
---|
34 | friend class snzi_t; |
---|
35 | private: |
---|
36 | |
---|
37 | union val_t { |
---|
38 | static constexpr char Half = -1; |
---|
39 | |
---|
40 | uint64_t _all; |
---|
41 | struct __attribute__((packed)) { |
---|
42 | char cnt; |
---|
43 | uint64_t ver:56; |
---|
44 | }; |
---|
45 | |
---|
46 | bool cas(val_t & exp, char _cnt, uint64_t _ver) volatile { |
---|
47 | val_t t; |
---|
48 | t.ver = _ver; |
---|
49 | t.cnt = _cnt; |
---|
50 | /* paranoid */ assert(t._all == ((_ver << 8) | ((unsigned char)_cnt))); |
---|
51 | return __atomic_compare_exchange_n(&this->_all, &exp._all, t._all, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); |
---|
52 | } |
---|
53 | |
---|
54 | bool cas(val_t & exp, const val_t & tar) volatile { |
---|
55 | return __atomic_compare_exchange_n(&this->_all, &exp._all, tar._all, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); |
---|
56 | } |
---|
57 | |
---|
58 | val_t() : _all(0) {} |
---|
59 | val_t(const volatile val_t & o) : _all(o._all) {} |
---|
60 | }; |
---|
61 | |
---|
62 | //-------------------------------------------------- |
---|
63 | // Hierarchical node |
---|
64 | void arrive_h() { |
---|
65 | int undoArr = 0; |
---|
66 | bool success = false; |
---|
67 | while(!success) { |
---|
68 | auto x{ value }; |
---|
69 | /* paranoid */ assert(x.cnt <= 120); |
---|
70 | if( x.cnt >= 1 ) { |
---|
71 | if( value.cas(x, x.cnt + 1, x.ver ) ) { |
---|
72 | success = true; |
---|
73 | } |
---|
74 | } |
---|
75 | /* paranoid */ assert(x.cnt <= 120); |
---|
76 | if( x.cnt == 0 ) { |
---|
77 | if( value.cas(x, val_t::Half, x.ver + 1) ) { |
---|
78 | success = true; |
---|
79 | x.cnt = val_t::Half; |
---|
80 | x.ver = x.ver + 1; |
---|
81 | } |
---|
82 | } |
---|
83 | /* paranoid */ assert(x.cnt <= 120); |
---|
84 | if( x.cnt == val_t::Half ) { |
---|
85 | /* paranoid */ assert(parent); |
---|
86 | if(undoArr == 2) { |
---|
87 | undoArr--; |
---|
88 | } else { |
---|
89 | parent->arrive(); |
---|
90 | } |
---|
91 | if( !value.cas(x, 1, x.ver) ) { |
---|
92 | undoArr = undoArr + 1; |
---|
93 | } |
---|
94 | } |
---|
95 | } |
---|
96 | |
---|
97 | for(int i = 0; i < undoArr; i++) { |
---|
98 | /* paranoid */ assert(parent); |
---|
99 | parent->depart(); |
---|
100 | } |
---|
101 | } |
---|
102 | |
---|
103 | void depart_h() { |
---|
104 | while(true) { |
---|
105 | auto x = (const val_t)value; |
---|
106 | /* paranoid */ assertf(x.cnt >= 1, "%d", x.cnt); |
---|
107 | if( value.cas( x, x.cnt - 1, x.ver ) ) { |
---|
108 | if( x.cnt == 1 ) { |
---|
109 | /* paranoid */ assert(parent); |
---|
110 | parent->depart(); |
---|
111 | } |
---|
112 | return; |
---|
113 | } |
---|
114 | } |
---|
115 | } |
---|
116 | |
---|
117 | //-------------------------------------------------- |
---|
118 | // Root node |
---|
119 | void arrive_r() { |
---|
120 | __atomic_fetch_add(&value._all, 1, __ATOMIC_SEQ_CST); |
---|
121 | } |
---|
122 | |
---|
123 | void depart_r() { |
---|
124 | __atomic_fetch_sub(&value._all, 1, __ATOMIC_SEQ_CST); |
---|
125 | } |
---|
126 | |
---|
127 | private: |
---|
128 | volatile val_t value; |
---|
129 | class node * parent = nullptr; |
---|
130 | |
---|
131 | bool is_root() { |
---|
132 | return parent == nullptr; |
---|
133 | } |
---|
134 | |
---|
135 | public: |
---|
136 | void arrive() { |
---|
137 | if(is_root()) arrive_r(); |
---|
138 | else arrive_h(); |
---|
139 | } |
---|
140 | |
---|
141 | void depart() { |
---|
142 | if(is_root()) depart_r(); |
---|
143 | else depart_h(); |
---|
144 | } |
---|
145 | |
---|
146 | bool query() { |
---|
147 | /* paranoid */ assert(is_root()); |
---|
148 | return value._all > 0; |
---|
149 | } |
---|
150 | }; |
---|
151 | }; |
---|
152 | |
---|
153 | snzi_t::snzi_t(unsigned depth, unsigned base) |
---|
154 | : mask( std::pow(base, depth) ) |
---|
155 | , root( ((std::pow(base, depth + 1) - 1) / (base -1)) - 1 ) |
---|
156 | , nodes(new node[ root + 1 ]()) |
---|
157 | { |
---|
158 | int width = std::pow(base, depth); |
---|
159 | std::cout << "SNZI: " << depth << "x" << width << "(" << mask - 1 << ")" << std::endl; |
---|
160 | for(int i = 0; i < root; i++) { |
---|
161 | nodes[i].parent = &nodes[(i / base) + width ]; |
---|
162 | } |
---|
163 | } |
---|