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