1 //
2 // Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2021
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 #pragma once
8 
9 #include "td/utils/common.h"
10 #include "td/utils/List.h"
11 
12 #include <mutex>
13 
14 namespace td {
15 
16 template <class DataT>
17 class TsList;
18 
19 template <class DataT>
20 class TsListNode : protected ListNode {
21  public:
TsListNode()22   TsListNode() {
23     clear();
24   }
TsListNode(DataT && data)25   explicit TsListNode(DataT &&data) : data_(std::move(data)) {
26     clear();
27   }
28 
~TsListNode()29   ~TsListNode() {
30     remove();
31   }
32 
33   std::unique_lock<std::mutex> lock() TD_WARN_UNUSED_RESULT;
34 
35   TsListNode(const TsListNode &) = delete;
36   TsListNode &operator=(const TsListNode &) = delete;
37 
TsListNode(TsListNode && other)38   TsListNode(TsListNode &&other) noexcept {
39     other.validate();
40     if (other.empty()) {
41       data_ = std::move(other.data_);
42       clear();
43     } else {
44       auto guard = other.lock();
45       init_from(std::move(other));
46     }
47     validate();
48     other.validate();
49   }
50 
51   TsListNode &operator=(TsListNode &&other) noexcept {
52     validate();
53     if (this == &other) {
54       return *this;
55     }
56     other.validate();
57     remove();
58 
59     if (other.empty()) {
60       data_ = std::move(other.data_);
61     } else {
62       auto guard = other.lock();
63       init_from(std::move(other));
64     }
65 
66     validate();
67     other.validate();
68     return *this;
69   }
70 
validate()71   void validate() {
72     if (empty()) {
73       CHECK(ListNode::empty());
74     } else {
75       auto guard = lock();
76       CHECK(!ListNode::empty() || is_root);
77     }
78   }
79 
remove()80   void remove() {
81     validate();
82     if (is_root) {
83       CHECK(ListNode::empty());
84       return;
85     }
86     if (empty()) {
87       CHECK(ListNode::empty());
88       return;
89     }
90     {
91       auto guard = lock();
92       ListNode::remove();
93       if (!is_root) {
94         parent = nullptr;
95       }
96     }
97     validate();
98   }
99 
put(TsListNode * other)100   void put(TsListNode *other) {
101     validate();
102     other->validate();
103     DCHECK(other->empty());
104     DCHECK(!empty());
105     DCHECK(!other->is_root);
106     {
107       auto guard = lock();
108       ListNode::put(other);
109       other->parent = parent;
110     }
111     validate();
112     other->validate();
113   }
114 
put_back(TsListNode * other)115   void put_back(TsListNode *other) {
116     DCHECK(other->empty());
117     DCHECK(!empty());
118     DCHECK(!other->is_root);
119     auto guard = lock();
120     ListNode::put_back(other);
121     other->parent = parent;
122   }
123 
empty()124   bool empty() const {
125     return parent == nullptr;
126   }
127 
get_next()128   TsListNode *get_next() {
129     return static_cast<TsListNode *>(next);
130   }
get_prev()131   TsListNode *get_prev() {
132     return static_cast<TsListNode *>(prev);
133   }
134 
get_data_unsafe()135   DataT &get_data_unsafe() {
136     return data_;
137   }
138 
139  private:
140   TsList<DataT> *parent;
141   bool is_root{false};
142   DataT data_;
143 
144   friend class TsList<DataT>;
145 
clear()146   void clear() {
147     ListNode::clear();
148     if (!is_root) {
149       parent = nullptr;
150     }
151   }
152 
init_from(TsListNode && other)153   void init_from(TsListNode &&other) {
154     ListNode::init_from(std::move(other));
155     parent = other.parent;
156     other.parent = nullptr;
157     data_ = std::move(other.data_);
158   }
159 };
160 
161 template <class DataT>
162 class TsList final : public TsListNode<DataT> {
163  public:
TsList()164   TsList() {
165     this->parent = this;
166     this->is_root = true;
167   }
168   TsList(const TsList &) = delete;
169   TsList &operator=(const TsList &) = delete;
170   TsList(TsList &&) = delete;
171   TsList &operator=(TsList &&) = delete;
~TsList()172   ~TsList() {
173     auto guard = lock();
174     while (true) {
175       auto res = static_cast<TsListNode<DataT> *>(ListNode::get());
176       if (!res) {
177         break;
178       }
179       res->parent = nullptr;
180     }
181     this->parent = nullptr;
182   }
lock()183   std::unique_lock<std::mutex> lock() TD_WARN_UNUSED_RESULT {
184     return std::unique_lock<std::mutex>(mutex_);
185   }
begin()186   TsListNode<DataT> *begin() {
187     return this->get_next();
188   }
end()189   TsListNode<DataT> *end() {
190     return this;
191   }
get()192   TsListNode<DataT> *get() {
193     auto guard = lock();
194     auto res = static_cast<TsListNode<DataT> *>(ListNode::get());
195     if (res) {
196       res->parent = nullptr;
197     }
198     return res;
199   }
200 
201  private:
202   std::mutex mutex_;
203 };
204 
205 template <class DataT>
lock()206 std::unique_lock<std::mutex> TsListNode<DataT>::lock() {
207   if (parent == nullptr) {
208     return {};
209   }
210   CHECK(parent != nullptr);
211   return parent->lock();
212 }
213 
214 }  // namespace td
215