folly/experimental/hazptr/example/LockFreeLIFO.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #pragma once
  17
  18 #include <folly/experimental/hazptr/debug.h>
  19 #include <folly/experimental/hazptr/hazptr.h>
  20
  21 namespace folly {
  22 namespace hazptr {
  23
  24 template <typename T>
  25 class LockFreeLIFO {
  26   class Node : public hazptr_obj_base<Node> {
  27     friend LockFreeLIFO;
  28    public:
  29     ~Node() {
  30       DEBUG_PRINT(this);
  31     }
  32    private:
  33     Node(T v, Node* n) : value_(v), next_(n) {
  34       DEBUG_PRINT(this);
  35     }
  36     T value_;
  37     Node* next_;
  38   };
  39
  40  public:
  41   LockFreeLIFO() {
  42     DEBUG_PRINT(this);
  43   }
  44
  45   ~LockFreeLIFO() {
  46     DEBUG_PRINT(this);
  47   }
  48
  49   void push(T val) {
  50     DEBUG_PRINT(this);
  51     auto pnode = new Node(val, head_.load());
  52     while (!head_.compare_exchange_weak(pnode->next_, pnode));
  53   }
  54
  55   bool pop(T& val) {
  56     DEBUG_PRINT(this);
  57     hazptr_holder hptr;
  58     Node* pnode = head_.load();
  59     do {
  60       if (pnode == nullptr)
  61         return false;
  62       if (!hptr.try_protect(pnode, head_))
  63         continue;
  64       auto next = pnode->next_;
  65       if (head_.compare_exchange_weak(pnode, next)) break;
  66     } while (true);
  67     hptr.reset();
  68     val = pnode->value_;
  69     pnode->retire();
  70     return true;
  71   }
  72
  73  private:
  74   std::atomic<Node*> head_ = {nullptr};
  75 };
  76
  77 } // namespace folly {
  78 } // namespace hazptr {