{"id":599,"date":"2019-10-27T20:51:39","date_gmt":"2019-10-27T12:51:39","guid":{"rendered":"http:\/\/blog.coolcoding.cn\/?p=599"},"modified":"2020-09-27T17:02:37","modified_gmt":"2020-09-27T09:02:37","slug":"%e8%bd%ac%e8%bd%bd%e6%97%a0%e9%94%81%e9%98%9f%e5%88%97","status":"publish","type":"post","link":"https:\/\/blog.coolcoding.cn\/?p=599","title":{"rendered":"[\u8f6c\u8f7d]C++\u65e0\u9501\u961f\u5217"},"content":{"rendered":"\n<p>\u539f\u6587\u94fe\u63a5\uff1a <a href=\"http:\/\/chenshungen.cn\/lock_free_queue\/\">http:\/\/chenshungen.cn\/lock_free_queue\/<\/a> <\/p>\n\n\n\n<p>\u5173\u4e8e\u65e0\u9501\u961f\u5217\u7684\u8bf4\u660e\u8bf7\u53c2\u8003\u9648\u7693\u7684\u535a\u5ba2\u4e0a\u7684\u4e00\u7bc7\u5173\u4e8e\u65e0\u9501\u961f\u5217\u7684\u5b9e\u73b0\u7684\u7406\u8bba\u8bf4\u660e\uff08<a rel=\"noreferrer noopener\" href=\"https:\/\/coolshell.cn\/articles\/8239.html\" target=\"_blank\">coolshell<\/a>\uff09\u5206\u4eab\u4f7f\u7528\u73af\u5f62\u6570\u7ec4\u5b9e\u73b0\u7684\u65e0\u9501\u961f\u5217\u7684c++\u5b9e\u73b0\u4ee3\u7801\u3002\u5355\u751f\u4ea7\u8005-\u5355\u6d88\u8d39\u8005<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#ifndef WATER_BASE_LOCK_FREE_CIRCULAR_QUEUE_SS_HPP\n#define WATER_BASE_LOCK_FREE_CIRCULAR_QUEUE_SS_HPP\n#include \"class_helper.h\"\n#include &lt;vector>\n#include &lt;atomic>\nnamespace water{\nnamespace componet{\ntemplate &lt;typename T>\nclass LockFreeCircularQueueSPSC final \/\/\u4e0d\u53ef\u4f5c\u4e3a\u57fa\u7c7b\n{\n    struct Cell\n    {\n        enum class Status : uint_fast32_t \n        {\n            empty, \n            full, \n        };\n        Cell()\n        : status(Status::empty), t()\n        {\n        }\n        std::atomic&lt;Status> status;\n        T t;\n    };\npublic:\n    TYPEDEF_PTR(LockFreeCircularQueueSPSC);\n    explicit LockFreeCircularQueueSPSC(uint32_t powArg = 10) \/\/\u961f\u5217\u957f\u5ea6\u4e3a 2^powArg\n    : m_begin(0), m_end(0), m_maxSize(1u &lt;&lt; (powArg &lt; 24 ? powArg : 24)), m_data(m_maxSize)\n    {\n    }\n    ~LockFreeCircularQueueSPSC() = default;\n    \/\/noncopyable\n    LockFreeCircularQueueSPSC(const LockFreeCircularQueueSPSC&amp;) = delete;\n    LockFreeCircularQueueSPSC&amp; operator=(const LockFreeCircularQueueSPSC&amp;) = delete;\n    bool isLockFree() const\n    {\n        return m_data[0].status.is_lock_free();\n    }\n    bool push(const T&amp; item)\n    {\n        const uint_fast32_t pos = realPos(m_end);\n        int i = 0;\n        while(true)\n        {\n            if(++i == 3) \/\/\u6700\u591a\u5c1d\u8bd53\u6b21\u6570\u4f9d\u7136\u961f\u5217\u6ee1\uff0c\u8fd4\u56de\u5931\u8d25\uff0c\u65e0\u6cd5\u653e\u5165\n                return false;\n            \/\/\u5c3e\u90e8\u4e3a\u7a7a\uff0c\u5373\u961f\u5217\u975e\u6ee1\uff0c\u53ef\u4ee5push\n            if(m_data[pos].status.load(std::memory_order_acquire) == Cell::Status::empty)\n                break;\n        };\n        \/\/\u961f\u5c3e\u540e\u79fb\n        m_end++;\n        \/\/\u5411\u8282\u70b9\u586b\u5165\u6570\u636e\n        m_data[pos].t = item;\n        \/\/\u6807\u8bb0\u4e3a\u5df2\u653e\u5165\u5e76\u5c06\u63d0\u4ea4\u5185\u5b58\u4fee\u6539\uff0c\u4ee4\u6240\u6709\u7ebf\u7a0b\u53ef\u89c1\n        m_data[pos].status.store(Cell::Status::full, std::memory_order_release);\n        return true;\n    }\n    bool pop(T* t)\n    {\n        const uint_fast32_t pos = realPos(m_begin);\n        int i = 0;\n        while(true)\n        {\n            if(i++ == 3) \/\/\u6700\u591a\u5c1d\u8bd53\u6b21\u6570\u4f9d\u7136\u961f\u5217\u7a7a\uff0c\u8fd4\u56de\u5931\u8d25\uff0c\u65e0\u6cd5\u53d6\u51fa\n                return false;\n             \/\/pos\uff08\u5934\u90e8\uff09\u4f4d\u7f6e\u975e\u7a7a\uff0c\u5373\u961f\u5217\u975e\u7a7a\uff0c\u53ef\u4ee5pop\n            if(m_data[pos].status.load(std::memory_order_acquire) == Cell::Status::full)\n                break;\n        }\n        \/\/\u961f\u9996\u540e\u79fb\n        m_begin++;\n        \/\/\u53d6\u51fa\u8282\u70b9\u5185\u7684\u6570\u636e\n        *t = m_data[pos].t;\n        m_data[pos].t = T();\n        \/\/\u6807\u8bb0\u4e3a\u5df2\u53d6\u51fa\u5e76\u5c06\u63d0\u4ea4\u5185\u5b58\u4fee\u6539\uff0c\u4ee4\u6240\u6709\u7ebf\u7a0b\u53ef\u89c1\n        m_data[pos].status.store(Cell::Status::empty, std::memory_order_release);\n        return true;\n    }\n    bool empty() const\n    {\n        return m_data[realPos(m_begin)].status.load(std::memory_order_relaxed) == Cell::Status::empty;\n    }\n    bool full() const\n    {\n        return m_data[realPos(m_end)].status.load(std::memory_order_relaxed) == Cell::Status::full;\n    }\n    uint64_t maxSize() const\n    {\n        return static_cast&lt;uint64_t>(m_data.size());\n    }\nprivate: \n    uint64_t realPos(uint64_t pos) const\n    {\n        return pos &amp; (maxSize() - 1);\n    }\nprivate: \n    uint_fast32_t m_begin;\n    uint_fast32_t m_end;\n    const uint_fast32_t m_maxSize;\n    std::vector&lt;Cell> m_data;\n};\n}}\n#endif \/\/#ifndef WATER_BASE_CIRCULAR_QUEUE_HPP<\/code><\/pre>\n\n\n\n<p> \u591a\u751f\u4ea7\u8005\u591a\u6d88\u8d39\u8005 <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#ifndef WATER_BASE_M_LOCK_FREE_CIRCULAR_QUEUE_MM_HPP\n#define WATER_BASE_M_LOCK_FREE_CIRCULAR_QUEUE_MM_HPP\n \n#include &lt;vector>\n#include &lt;atomic>\n \n#include &lt;iostream>\nusing std::cerr;\nusing std::endl;\n \nnamespace water{\nnamespace componet{\n \ntemplate &lt;typename T>\nclass LockFreeCircularQueueMPMC final \/\/\u4e0d\u53ef\u4f5c\u4e3a\u57fa\u7c7b\n{\n    struct Cell\n    {\n        enum class Status : uint8_t\n        {\n            writing,\n            reading,\n            empty,\n            full,\n        };\n \n        Cell()\n        : status(Status::empty) ,t()\n        {\n        }\n \n        std::atomic&lt;Status> status;\n        T t;\n    };\n \npublic:\n    explicit LockFreeCircularQueueMPMC(uint64_t powArg = 16)\n    : m_begin(0), m_end(0), m_maxSize(1u &lt;&lt; (powArg &lt; 24 ? powArg : 24)), m_data(m_maxSize)\n    {\n    }\n    ~LockFreeCircularQueueMPMC() = default;\n \n    \/\/noncopyable\n    LockFreeCircularQueueMPMC(const LockFreeCircularQueueMPMC&amp;) = delete;\n    LockFreeCircularQueueMPMC&amp; operator=(const LockFreeCircularQueueMPMC&amp;) = delete;\n \n    bool isLockFree() const\n    {\n        return m_data[0].status.is_lock_free();\n    }\n \n    bool push(const T&amp; item)\n    {\n        int i = 0;\n        while(true) \/\/\u5c1d\u8bd5\u9501\u5b9a\u961f\u5c3e\u4e3a\u53ef\u5199\n        {\n            if(i++ == 5) \/\/\u6700\u5927\u5c1d\u8bd5\u6b21\u6570\n                return false;\n \n            uint32_t oldEnd = m_end.load(std::memory_order_acquire);\/\/\u961f\u5c3e\n            uint32_t index = realIndex(oldEnd);\n \n            typename Cell::Status oldStatus = m_data[index].status.load(std::memory_order_acquire);\n            if(oldStatus != Cell::Status::empty)\n                continue;\n \n            if(!m_data[index].status.compare_exchange_weak(oldStatus, Cell::Status::writing))\n                continue;\n \n            \/\/\u961f\u5c3e\u540e\u79fb\n            if(!m_end.compare_exchange_weak(oldEnd, oldEnd + 1))\n            {\n                m_data[index].status.store(Cell::Status::empty, std::memory_order_relaxed);\n                continue;\n            }\n \n            \/\/\u6570\u636e\u653e\u5165\u961f\u5217\n            m_data[index].t = item;\n            m_data[index].status.store(Cell::Status::full, std::memory_order_release);\n            break;\n        }\n        return true;\n    }\n \n    bool pop(T* t)\n    {\n        int i = 1;\n        while(true) \/\/\u5c1d\u8bd5\u9501\u5b9a\u961f\u9996\u4e3a\u53ef\u8bfb\n        {\n            if(i++ == 5) \/\/\u6700\u5927\u5c1d\u8bd5\u6b21\u6570\n                return false;\n \n            uint32_t oldBegin = m_begin.load(std::memory_order_acquire);\/\/\u961f\u9996\n            uint_fast32_t index = realIndex(oldBegin);\n \n            typename Cell::Status oldStatus = m_data[index].status.load(std::memory_order_acquire);\n            if(oldStatus != Cell::Status::full)\n                continue;\n \n            if(!m_data[index].status.compare_exchange_weak(oldStatus, Cell::Status::reading))\n                continue;\n \n            \/\/\u961f\u9996\u540e\u79fb\n            if(!m_begin.compare_exchange_weak(oldBegin, oldBegin + 1))\n            {\n                m_data[index].status.store(Cell::Status::full, std::memory_order_relaxed);\n                continue;\n            }\n \n            \/\/\u53d6\u51fa\u8282\u7ed3\u70b9\u5185\u7684\u6570\u636e\n            *t = m_data[index].t;\n            m_data[index].t = T();\n            m_data[index].status.store(Cell::Status::empty, std::memory_order_release);\n            break;\n        }\n        return true;\n    }\n \n    bool empty() const\n    {\n        return m_data[realIndex(m_begin.load(std::memory_order_relaxed))].status.load(std::memory_order_relaxed) == Cell::Status::empty;\n    }\n \n    bool full() const\n    {\n        return m_data[realIndex(m_end.load(std::memory_order_relaxed))].status.load(std::memory_order_relaxed) == Cell::Status::full;\n    }\n \n    inline uint32_t maxSize() const\n    {\n        return m_maxSize;\n    }\n \nprivate:\n    inline uint32_t realIndex(uint64_t index) const\n    {\n        return index &amp; (maxSize() - 1);\n    }\n \nprivate:\n    std::atomic&lt;uint32_t> m_begin;\n    std::atomic&lt;uint32_t> m_end;\n    const uint_fast32_t m_maxSize;\n    std::vector&lt;Cell> m_data;\n};\n \n}}\n \n#endif \/\/#ifndef WATER_BASE_CIRCULAR_QUEUE_HPP<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u539f\u6587\u94fe\u63a5\uff1a http:\/\/chenshungen.cn\/lock_free_queue\/ \u5173\u4e8e\u65e0\u9501\u961f\u5217\u7684\u8bf4\u660e\u8bf7 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[20],"_links":{"self":[{"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/posts\/599"}],"collection":[{"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=599"}],"version-history":[{"count":2,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/posts\/599\/revisions"}],"predecessor-version":[{"id":601,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=\/wp\/v2\/posts\/599\/revisions\/601"}],"wp:attachment":[{"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=599"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=599"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.coolcoding.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=599"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}