source: doc/theses/thierry_delisle_PhD/code/snzi.hpp @ 3bf812b

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

snzi creator now supports m-ary trees

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