使用风险指针（hazard pointer) 处理无锁栈的 push 与 pop

constexpr size_t maxHazardPointers = 100;
struct HazardPointer
{
    std::atomic<std::thread::id> id;
    std::atomic<void*>           pointer;
};

array<HazardPointer, maxHazardPointers> hazardPointers;

class HazardPointerOwner
{
    HazardPointer* hazardPointer;
public:
    HazardPointerOwner(const HazardPointerOwner&)  = delete;
    HazardPointerOwner& operator=(const HazardPointerOwner&) = delete;
    ~HazardPointerOwner()
    {
        hazardPointer->pointer.store(nullptr);
        hazardPointer->id.store(std::thread::id());
    }
    HazardPointerOwner():
        hazardPointer(nullptr)
    {
        // Get hazard pointer of this thread.
        for(size_t i = 0; i < maxHazardPointers; ++i){
            std:thread::id oldId;
            // If a hazard pointer's id is not be set,
            // replace it with current thread's id.
            if(hazardPointers[i].id.compare_exchange_strong(
                                                            oldId,
                                                            std::this_thread::get_id())){
                // Then get the referrence of this hazard pointer.
                hazardPointer = &hazardPointers[i];
                break;
            }
        }
        if (hazardPointer == nullptr){
            throw std::runtime_error("No hazard pointers available");
        }
    }
    
    std::atomic<void*>& getPointer()
    {
        return hazardPointer->pointer;
    }
};


std::atomic<void*>& getHazardPointerForCurrentThread()
{
    // Every thread have it's own hazard pointer.
    thread_local static HazardPointerOwner hazard;
    return hazard.getPointer();
}

// If other threads have hazard pointer point to p.
bool isOutstandingHazardPointer(void* p)
{
    for (size_t i = 0; i < maxHazardPointers; ++i){
        if (hazardPointers[i].pointer.load() == p) {
            return true;
        }
    }
    return false;
}

template <typename T>
void doDelete(void* p)
{
    delete static_cast<T*>(p);
}

struct DataToReclaim
{
    void* data;
    std::function<void(void*)> deleter;
    DataToReclaim* next;
    
    template<typename T>
    DataToReclaim(T* p):
        data(p),
        deleter(&doDelete<T>),
        next(0)
    {}
    
    ~DataToReclaim()
    {
        deleter(data);
    }
};

std::atomic<DataToReclaim*> nodesToReclaim;

void addToReclaimList(DataToReclaim* node)
{
    node->next = nodesToReclaim.load();
    while(!nodesToReclaim.compare_exchange_weak(node->next, node));
}

template<typename T>
void reclaimLater(T* data)
{
    addToReclaimList(new DataToReclaim(data));
}

void deleteNodesWithoutHazards()
{
    // To make sure that get the head of the reclaim list atomically,
    // use exchange instead of sentence like "auto current = nodesToReclaim;"
    auto currentData = nodesToReclaim.exchange(nullptr);
    while(currentData != nullptr){
        auto const next = currentData->next;
        if (!isOutstandingHazardPointer(currentData->data)) {
            delete currentData;
        }
        else{
            reclaimLater(currentData);
        }
        currentData = next;
    }
}

template<typename T>
class LockFreeStack
{
private:
    struct Node
    {
        std::shared_ptr<T> data;
        Node*              next;
        Node(T const& value):
        data(std::make_shared<T>(value))
        {}
    };
    
    std::atomic<Node*>  head;
    std::atomic<size_t> threadsInPopCount;
    std::atomic<Node*>  toBeDeletedChainHead;
    
    static void deleteNodes(Node* nodes)
    {
        while(nodes != nullptr){
            auto const next = nodes->next;
            delete nodes;
            nodes = next;
        }
    }
    
    void tryReclaim(Node* oldHead)
    {
        // If only this thread invoking pop().
        if (threadsInPopCount == 1) {
            auto toBeDeletedList = toBeDeletedChainHead.exchange(nullptr);
            // Now, if only this thread in the pop.
            if (--threadsInPopCount == 0){
                deleteNodes(toBeDeletedList);
            }
            // If some nodes to be deleted still waiting.
            else if (toBeDeletedList != nullptr){
                pushListToDelChain(toBeDeletedList);
            }
            delete oldHead;
        }
        else{
            // If more than one thread in the pop.
            pushNodeToDelChain(oldHead);
            --threadsInPopCount;
        }
    }
    
    void pushListToDelChain(Node* nodes)
    {
        auto last = nodes;
        while (auto const next = last->next) {
            last = next;
        }
        pushListToDelChain(nodes, last);
    }
    
    void pushListToDelChain(Node* first, Node* last)
    {
        last->next = toBeDeletedChainHead;
        // Put current head of delete chain to the next of the last.
        // Then let the first be the head.
        while(!toBeDeletedChainHead.compare_exchange_weak(last->next, first));
    }
    
    void pushNodeToDelChain(Node* node)
    {
        pushListToDelChain(node, node);
    }
public:
    void push(T const& value)
    {
        auto const newNode = new Node(value);
        newNode->next = head.load();
        while (!head.compare_exchange_weak(newNode->next, newNode));
    }
    
    std::shared_ptr<T> pop()
    {
        auto& hazardPointer = getHazardPointerForCurrentThread();
        auto  oldHead = head.load();
        do{
            Node* tempHead = nullptr;
            do{
                tempHead = oldHead;
                hazardPointer.store(oldHead);
                oldHead = head.load();
            }while(oldHead != tempHead);
        }while(oldHead &&
               !head.compare_exchange_strong(oldHead, oldHead->next)); // 1
        
        // If not set it's hazard pointer nullptr.
        // when sime thread break at '//1' will cause endless loop.
        hazardPointer.store(nullptr);
        
        std::shared_ptr<T> result;
        if (oldHead != nullptr){
            result.swap(oldHead);
            // Shouldn't check itself.
            // So must clear current thread's hazard pointer before.
            if (isOutstandingHazardPointer(oldHead)){
                reclaimLater(oldHead);
            }
            else{
                delete oldHead;
            }
            deleteNodesWithoutHazards();
        }
        
    }
};