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) {} 35 push_front(T * const element)36 void push_front(T* const element) { 37 LinkedListEntry<T>* new_entry = Allocator::alloc(); 38 new_entry->next = head_; 39 new_entry->element = element; 40 head_ = new_entry; 41 if (tail_ == nullptr) { 42 tail_ = new_entry; 43 } 44 } 45 push_back(T * const element)46 void push_back(T* const element) { 47 LinkedListEntry<T>* new_entry = Allocator::alloc(); 48 new_entry->next = nullptr; 49 new_entry->element = element; 50 if (tail_ == nullptr) { 51 tail_ = head_ = new_entry; 52 } else { 53 tail_->next = new_entry; 54 tail_ = new_entry; 55 } 56 } 57 pop_front()58 T* pop_front() { 59 if (head_ == nullptr) { 60 return nullptr; 61 } 62 63 LinkedListEntry<T>* entry = head_; 64 T* element = entry->element; 65 head_ = entry->next; 66 Allocator::free(entry); 67 68 if (head_ == nullptr) { 69 tail_ = nullptr; 70 } 71 72 return element; 73 } 74 clear()75 void clear() { 76 while (head_ != nullptr) { 77 LinkedListEntry<T>* p = head_; 78 head_ = head_->next; 79 Allocator::free(p); 80 } 81 82 tail_ = nullptr; 83 } 84 85 template<typename F> for_each(F && action)86 void for_each(F&& action) { 87 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) { 88 if (e->element != nullptr) { 89 action(e->element); 90 } 91 } 92 } 93 94 template<typename F> remove_if(F && predicate)95 void remove_if(F&& predicate) { 96 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) { 97 if (e->element != nullptr && predicate(e->element)) { 98 e->element = nullptr; 99 } 100 } 101 } 102 contains(const T * el)103 bool contains(const T* el) { 104 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) { 105 if (e->element != nullptr && e->element == el) { 106 return true; 107 } 108 } 109 return false; 110 } 111 112 private: 113 LinkedListEntry<T>* head_; 114 LinkedListEntry<T>* tail_; 115 DISALLOW_COPY_AND_ASSIGN(LinkedList); 116 }; 117 118 #endif // __LINKED_LIST_H 119