1 /* 2 * Copyright (C) 2014 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 #ifndef __LINKED_LIST_H 18 #define __LINKED_LIST_H 19 20 #include "private/bionic_macros.h" 21 22 template<typename T> 23 struct LinkedListEntry { 24 LinkedListEntry<T>* next; 25 T* element; 26 }; 27 28 /* 29 * Represents linked list of objects of type T 30 */ 31 template<typename T, typename Allocator> 32 class LinkedList { 33 public: LinkedList()34 LinkedList() : head_(nullptr), tail_(nullptr) {} ~LinkedList()35 ~LinkedList() { 36 clear(); 37 } 38 LinkedList(LinkedList && that)39 LinkedList(LinkedList&& that) { 40 this->head_ = that.head_; 41 this->tail_ = that.tail_; 42 that.head_ = that.tail_ = nullptr; 43 } 44 push_front(T * const element)45 void push_front(T* const element) { 46 LinkedListEntry<T>* new_entry = Allocator::alloc(); 47 new_entry->next = head_; 48 new_entry->element = element; 49 head_ = new_entry; 50 if (tail_ == nullptr) { 51 tail_ = new_entry; 52 } 53 } 54 push_back(T * const element)55 void push_back(T* const element) { 56 LinkedListEntry<T>* new_entry = Allocator::alloc(); 57 new_entry->next = nullptr; 58 new_entry->element = element; 59 if (tail_ == nullptr) { 60 tail_ = head_ = new_entry; 61 } else { 62 tail_->next = new_entry; 63 tail_ = new_entry; 64 } 65 } 66 pop_front()67 T* pop_front() { 68 if (head_ == nullptr) { 69 return nullptr; 70 } 71 72 LinkedListEntry<T>* entry = head_; 73 T* element = entry->element; 74 head_ = entry->next; 75 Allocator::free(entry); 76 77 if (head_ == nullptr) { 78 tail_ = nullptr; 79 } 80 81 return element; 82 } 83 front()84 T* front() const { 85 if (head_ == nullptr) { 86 return nullptr; 87 } 88 89 return head_->element; 90 } 91 clear()92 void clear() { 93 while (head_ != nullptr) { 94 LinkedListEntry<T>* p = head_; 95 head_ = head_->next; 96 Allocator::free(p); 97 } 98 99 tail_ = nullptr; 100 } 101 102 template<typename F> for_each(F action)103 void for_each(F action) const { 104 visit([&] (T* si) { 105 action(si); 106 return true; 107 }); 108 } 109 110 template<typename F> visit(F action)111 bool visit(F action) const { 112 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) { 113 if (!action(e->element)) { 114 return false; 115 } 116 } 117 return true; 118 } 119 120 template<typename F> remove_if(F predicate)121 void remove_if(F predicate) { 122 for (LinkedListEntry<T>* e = head_, *p = nullptr; e != nullptr;) { 123 if (predicate(e->element)) { 124 LinkedListEntry<T>* next = e->next; 125 if (p == nullptr) { 126 head_ = next; 127 } else { 128 p->next = next; 129 } 130 Allocator::free(e); 131 e = next; 132 } else { 133 p = e; 134 e = e->next; 135 } 136 } 137 } 138 139 template<typename F> find_if(F predicate)140 T* find_if(F predicate) const { 141 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) { 142 if (predicate(e->element)) { 143 return e->element; 144 } 145 } 146 147 return nullptr; 148 } 149 copy_to_array(T * array[],size_t array_length)150 size_t copy_to_array(T* array[], size_t array_length) const { 151 size_t sz = 0; 152 for (LinkedListEntry<T>* e = head_; sz < array_length && e != nullptr; e = e->next) { 153 array[sz++] = e->element; 154 } 155 156 return sz; 157 } 158 contains(const T * el)159 bool contains(const T* el) const { 160 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) { 161 if (e->element == el) { 162 return true; 163 } 164 } 165 return false; 166 } 167 make_list(T * const element)168 static LinkedList make_list(T* const element) { 169 LinkedList<T, Allocator> one_element_list; 170 one_element_list.push_back(element); 171 return one_element_list; 172 } 173 174 private: 175 LinkedListEntry<T>* head_; 176 LinkedListEntry<T>* tail_; 177 DISALLOW_COPY_AND_ASSIGN(LinkedList); 178 }; 179 180 #endif // __LINKED_LIST_H 181