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 
11 namespace td {
12 
13 struct ListNode {
14   ListNode *next;
15   ListNode *prev;
ListNodeListNode16   ListNode() {
17     clear();
18   }
19 
~ListNodeListNode20   ~ListNode() {
21     remove();
22   }
23 
24   ListNode(const ListNode &) = delete;
25   ListNode &operator=(const ListNode &) = delete;
26 
ListNodeListNode27   ListNode(ListNode &&other) noexcept {
28     if (other.empty()) {
29       clear();
30     } else {
31       init_from(std::move(other));
32     }
33   }
34 
35   ListNode &operator=(ListNode &&other) noexcept {
36     if (this == &other) {
37       return *this;
38     }
39 
40     this->remove();
41 
42     if (!other.empty()) {
43       init_from(std::move(other));
44     }
45 
46     return *this;
47   }
48 
connectListNode49   void connect(ListNode *to) {
50     CHECK(to != nullptr);
51     next = to;
52     to->prev = this;
53   }
54 
removeListNode55   void remove() {
56     prev->connect(next);
57     clear();
58   }
59 
putListNode60   void put(ListNode *other) {
61     DCHECK(other->empty());
62     put_unsafe(other);
63   }
64 
put_backListNode65   void put_back(ListNode *other) {
66     DCHECK(other->empty());
67     prev->connect(other);
68     other->connect(this);
69   }
70 
getListNode71   ListNode *get() {
72     ListNode *result = prev;
73     if (result == this) {
74       return nullptr;
75     }
76     result->prev->connect(this);
77     result->clear();
78     // this->connect(result->next);
79     return result;
80   }
81 
emptyListNode82   bool empty() const {
83     return next == this;
84   }
85 
beginListNode86   ListNode *begin() {
87     return next;
88   }
endListNode89   ListNode *end() {
90     return this;
91   }
get_nextListNode92   ListNode *get_next() {
93     return next;
94   }
get_prevListNode95   ListNode *get_prev() {
96     return prev;
97   }
98 
99  protected:
clearListNode100   void clear() {
101     next = this;
102     prev = this;
103   }
104 
init_fromListNode105   void init_from(ListNode &&other) {
106     ListNode *head = other.prev;
107     other.remove();
108     head->put_unsafe(this);
109   }
110 
put_unsafeListNode111   void put_unsafe(ListNode *other) {
112     other->connect(next);
113     this->connect(other);
114   }
115 };
116 
117 }  // namespace td
118