folly/experimental/hazptr/example/LockFreeLIFO.h

   1 /*
   2  * Copyright 2016 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_owner<Node> hptr;
  58     Node* pnode;
  59     while (true) {
  60       if ((pnode = head_.load()) == nullptr) return false;
  61       if (!hptr.protect(pnode, head_)) continue;
  62       auto next = pnode->next_;
  63       if (head_.compare_exchange_weak(pnode, next)) break;
  64     }
  65     hptr.clear();
  66     val = pnode->value_;
  67     pnode->retire();
  68     return true;
  69   }
  70
  71  private:
  72   std::atomic<Node*> head_ = {nullptr};
  73 };
  74
  75 } // namespace folly {
  76 } // namespace hazptr {