source: doc/theses/thierry_delisle_PhD/code/readyQ_proto/links.hpp @ d035cf7

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since d035cf7 was f9f3775, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Moved phd code for the readQ prototype to it's own folder

  • Property mode set to 100644
File size: 2.9 KB
Line 
1#pragma once
2
3#include "assert.hpp"
4#include "utils.hpp"
5
6template<typename node_t>
7struct _LinksFields_t {
8        node_t * prev = nullptr;
9        node_t * next = nullptr;
10        volatile unsigned long long ts = 0;
11        unsigned hint = (unsigned)-1;
12};
13
14template<typename node_t>
15class __attribute__((aligned(128))) intrusive_queue_t {
16public:
17        typedef spinlock_t lock_t;
18
19        struct stat {
20                ssize_t diff = 0;
21                size_t  push = 0;
22                size_t  pop  = 0;
23        };
24
25private:
26        struct sentinel_t {
27                _LinksFields_t<node_t> _links;
28        };
29
30public:
31        lock_t lock;
32
33private:
34        sentinel_t before;
35        sentinel_t after;
36
37#pragma GCC diagnostic push
38#pragma GCC diagnostic ignored "-Winvalid-offsetof"
39        static constexpr auto fields_offset = offsetof( node_t, _links );
40#pragma GCC diagnostic pop
41public:
42        intrusive_queue_t()
43                : before{{ nullptr, tail() }}
44                , after {{ head(), nullptr }}
45        {
46                /* paranoid */ assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
47                /* paranoid */ assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
48                /* paranoid */ assert(head()->_links.prev == nullptr);
49                /* paranoid */ assert(head()->_links.next == tail() );
50                /* paranoid */ assert(tail()->_links.next == nullptr);
51                /* paranoid */ assert(tail()->_links.prev == head() );
52                /* paranoid */ assert(sizeof(*this) == 128);
53                /* paranoid */ assert((intptr_t(this) % 128) == 0);
54        }
55
56        ~intrusive_queue_t() = default;
57
58        inline node_t * head() const {
59                node_t * rhead = reinterpret_cast<node_t *>(
60                        reinterpret_cast<uintptr_t>( &before ) - fields_offset
61                );
62                assert(rhead);
63                return rhead;
64        }
65
66        inline node_t * tail() const {
67                node_t * rtail = reinterpret_cast<node_t *>(
68                        reinterpret_cast<uintptr_t>( &after ) - fields_offset
69                );
70                assert(rtail);
71                return rtail;
72        }
73
74        inline bool push(node_t * node) {
75                assert(lock);
76                assert(node->_links.ts != 0);
77                node_t * tail = this->tail();
78
79                node_t * prev = tail->_links.prev;
80                // assertf(node->_links.ts >= prev->_links.ts,
81                //      "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
82                node->_links.next = tail;
83                node->_links.prev = prev;
84                prev->_links.next = node;
85                tail->_links.prev = node;
86
87                if(before._links.ts == 0l) {
88                        before._links.ts = node->_links.ts;
89                        assert(node->_links.prev == this->head());
90                        return true;
91                }
92                return false;
93        }
94
95        inline std::pair<node_t *, bool> pop() {
96                assert(lock);
97                node_t * head = this->head();
98                node_t * tail = this->tail();
99
100                node_t * node = head->_links.next;
101                node_t * next = node->_links.next;
102                if(node == tail) return {nullptr, false};
103
104                head->_links.next = next;
105                next->_links.prev = head;
106
107                if(next == tail) {
108                        before._links.ts = 0l;
109                        return {node, true};
110                }
111                else {
112                        assert(next->_links.ts != 0);
113                        before._links.ts = next->_links.ts;
114                        assert(before._links.ts != 0);
115                        return {node, false};
116                }
117        }
118
119        long long ts() const {
120                return before._links.ts;
121        }
122};
Note: See TracBrowser for help on using the repository browser.