cbcf88e0dbeee64fba5ad5ae046523b7415a1997
[folly.git] / 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 {