library/cpp/threading/queue/mpsc_intrusive_unordered.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#pragma once

/*
  Simple almost-wait-free unordered queue for low contention operations.

  It's wait-free for producers.
  Hanging producer can hide some items from consumer.
 */

#include <util/system/types.h>

namespace NThreading {
    struct TIntrusiveNode {
        TIntrusiveNode* Next;
    };

    class TMPSCIntrusiveUnordered {
    public:
        static constexpr ui32 NUMBER_OF_TRIES_FOR_CAS = 3;

        void Push(TIntrusiveNode* node) noexcept;
        TIntrusiveNode* PopMany() noexcept;
        TIntrusiveNode* Pop() noexcept;

        void Push(void* node) noexcept {
            Push(reinterpret_cast<TIntrusiveNode*>(node));
        }
 
    private:
        TIntrusiveNode* HeadForCaS = nullptr;
        TIntrusiveNode* HeadForSwap = nullptr;
        TIntrusiveNode* NotReadyChain = nullptr;
        TIntrusiveNode* PopOneQueue = nullptr;
    };
}