source: doc/theses/thierry_delisle_PhD/code/links.hpp@ 2aa25cc2

#pragma once

#include "assert.hpp"
#include "utils.hpp"

template<typename node_t>
struct _LinksFields_t {
        node_t * prev = nullptr;
        node_t * next = nullptr;
        volatile unsigned long long ts = 0;
        unsigned hint = (unsigned)-1;
};

template<typename node_t>
class __attribute__((aligned(128))) intrusive_queue_t {
public:
        typedef spinlock_t lock_t;

        struct stat {
                ssize_t diff = 0;
                size_t  push = 0;
                size_t  pop  = 0;
        };

private:
        struct sentinel_t {
                _LinksFields_t<node_t> _links;
        };

public:
        lock_t lock;

private:
        sentinel_t before;
        sentinel_t after;

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Winvalid-offsetof"
        static constexpr auto fields_offset = offsetof( node_t, _links );
#pragma GCC diagnostic pop
public:
        intrusive_queue_t()
                : before{{ nullptr, tail() }}
                , after {{ head(), nullptr }}
        {
                /* paranoid */ assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
                /* paranoid */ assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
                /* paranoid */ assert(head()->_links.prev == nullptr);
                /* paranoid */ assert(head()->_links.next == tail() );
                /* paranoid */ assert(tail()->_links.next == nullptr);
                /* paranoid */ assert(tail()->_links.prev == head() );
                /* paranoid */ assert(sizeof(*this) == 128);
                /* paranoid */ assert((intptr_t(this) % 128) == 0);
        }

        ~intrusive_queue_t() = default;

        inline node_t * head() const {
                node_t * rhead = reinterpret_cast<node_t *>(
                        reinterpret_cast<uintptr_t>( &before ) - fields_offset
                );
                assert(rhead);
                return rhead;
        }

        inline node_t * tail() const {
                node_t * rtail = reinterpret_cast<node_t *>(
                        reinterpret_cast<uintptr_t>( &after ) - fields_offset
                );
                assert(rtail);
                return rtail;
        }

        inline bool push(node_t * node) {
                assert(lock);
                assert(node->_links.ts != 0);
                node_t * tail = this->tail();

                node_t * prev = tail->_links.prev;
                // assertf(node->_links.ts >= prev->_links.ts,
                //      "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
                node->_links.next = tail;
                node->_links.prev = prev;
                prev->_links.next = node;
                tail->_links.prev = node;

                if(before._links.ts == 0l) {
                        before._links.ts = node->_links.ts;
                        assert(node->_links.prev == this->head());
                        return true;
                }
                return false;
        }

        inline std::pair<node_t *, bool> pop() {
                assert(lock);
                node_t * head = this->head();
                node_t * tail = this->tail();

                node_t * node = head->_links.next;
                node_t * next = node->_links.next;
                if(node == tail) return {nullptr, false};

                head->_links.next = next;
                next->_links.prev = head;

                if(next == tail) {
                        before._links.ts = 0l;
                        return {node, true};
                }
                else {
                        assert(next->_links.ts != 0);
                        before._links.ts = next->_links.ts;
                        assert(before._links.ts != 0);
                        return {node, false};
                }
        }

        long long ts() const {
                return before._links.ts;
        }
};