1 /*
2  * Copyright (C) 2017 The Android Open Source Project
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 
17 #pragma once
18 
19 #include "common.h"
20 
21 #include <assert.h>
22 
23 namespace slicer {
24 
25 // A minimal intrusive linked list with a STL-style container interface
26 // (It works for any type T which has T* next, prev fields)
27 //
28 template <class T>
29 class IntrusiveList {
30  public:
31   struct Iterator {
IteratorIterator32     explicit Iterator(T* p) : p_(p) {}
33 
34     bool operator==(Iterator other) const { return p_ == other.p_; }
35     bool operator!=(Iterator other) const { return p_ != other.p_; }
36 
37     T* operator*() const {
38       assert(p_ != nullptr);
39       return p_;
40     }
41 
42     Iterator operator++() {
43       assert(p_ != nullptr);
44       p_ = p_->next;
45       return *this;
46     }
47 
48     Iterator operator++(int) {
49       auto tmp(*this);
50       operator++();
51       return tmp;
52     }
53 
54     Iterator operator--() {
55       assert(p_ != nullptr);
56       p_ = p_->prev;
57       return *this;
58     }
59 
60     Iterator operator--(int) {
61       auto tmp(*this);
62       operator--();
63       return tmp;
64     }
65 
66    private:
67     T* p_;
68   };
69 
70  public:
71   IntrusiveList() = default;
72   ~IntrusiveList() = default;
73 
74   IntrusiveList(const IntrusiveList&) = delete;
75   IntrusiveList& operator=(const IntrusiveList&) = delete;
76 
push_back(T * p)77   void push_back(T* p) {
78     insert(end(), p);
79   }
80 
insert(Iterator it,T * p)81   Iterator insert(Iterator it, T* p) {
82     return InsertBefore(*it, p);
83   }
84 
InsertBefore(T * pos,T * p)85   Iterator InsertBefore(T* pos, T* p) {
86     assert(p != nullptr);
87     assert(p->next == nullptr);
88     assert(p->prev == nullptr);
89     assert(pos != nullptr);
90     p->prev = pos->prev;
91     if (pos == begin_) {
92       assert(pos->prev == nullptr);
93       begin_ = p;
94     } else {
95       assert(pos->prev != nullptr);
96       p->prev->next = p;
97     }
98     p->next = pos;
99     pos->prev = p;
100     return Iterator(p);
101   }
102 
InsertAfter(T * pos,T * p)103   Iterator InsertAfter(T* pos, T* p) {
104     assert(p != nullptr);
105     assert(p->next == nullptr);
106     assert(p->prev == nullptr);
107     assert(pos != nullptr);
108     assert(pos != &end_sentinel_);
109     p->next = pos->next;
110     p->next->prev = p;
111     p->prev = pos;
112     pos->next = p;
113     return Iterator(p);
114   }
115 
Remove(T * pos)116   void Remove(T* pos) {
117     SLICER_CHECK(pos != end_);
118     if (pos->prev != nullptr) {
119       assert(pos != begin_);
120       pos->prev->next = pos->next;
121     } else {
122       assert(pos == begin_);
123       begin_ = pos->next;
124     }
125     assert(pos->next != nullptr);
126     pos->next->prev = pos->prev;
127     pos->prev = nullptr;
128     pos->next = nullptr;
129   }
130 
empty()131   bool empty() const { return begin_ == end_; }
132 
begin()133   Iterator begin() const { return Iterator(begin_); }
end()134   Iterator end() const { return Iterator(end_); }
135 
136  private:
137   T* begin_ = &end_sentinel_;
138   T* const end_ = &end_sentinel_;
139   T end_sentinel_;
140 };
141 
142 }  // namespace slicer
143