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   }
  56
  57   bool pop(T& val) {
  58     DEBUG_PRINT(this);
  59     hazptr_holder hptr;
  60     Node* pnode = head_.load();
  61     do {
  62       if (pnode == nullptr) {
  63         return false;
  64       }
  65       if (!hptr.try_protect(pnode, head_)) {
  66         continue;
  67       }
  68       auto next = pnode->next_;
  69       if (head_.compare_exchange_weak(pnode, next)) {
  70         break;
  71       }
  72     } while (true);
  73     hptr.reset();
  74     val = pnode->value_;
  75     pnode->retire();
  76     return true;
  77   }
  78
  79  private:
  80   std::atomic<Node*> head_ = {nullptr};
  81 };
  82
  83 } // namespace folly
  84 } // namespace hazptr