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 */
17 #ifndef __LINKED_LIST_H
18 #define __LINKED_LIST_H
20 #include "private/bionic_macros.h"
22 template<typename T>
23 struct LinkedListEntry {
24 LinkedListEntry<T>* next;
25 T* element;
26 };
28 /*
29 * Represents linked list of objects of type T
30 */
31 template<typename T, typename Allocator>
32 class LinkedList {
33 public:
34 LinkedList() : head_(nullptr), tail_(nullptr) {}
35 ~LinkedList() {
36 clear();
37 }
39 LinkedList(LinkedList&& that) {
40 this->head_ = that.head_;
41 this->tail_ = that.tail_;
42 that.head_ = that.tail_ = nullptr;
43 }
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 }
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 }
67 T* pop_front() {
68 if (head_ == nullptr) {
69 return nullptr;
70 }
72 LinkedListEntry<T>* entry = head_;
73 T* element = entry->element;
74 head_ = entry->next;
75 Allocator::free(entry);
77 if (head_ == nullptr) {
78 tail_ = nullptr;
79 }
81 return element;
82 }
84 T* front() const {
85 if (head_ == nullptr) {
86 return nullptr;
87 }
89 return head_->element;
90 }
92 void clear() {
93 while (head_ != nullptr) {
94 LinkedListEntry<T>* p = head_;
95 head_ = head_->next;
96 Allocator::free(p);
97 }
99 tail_ = nullptr;
100 }
102 template<typename F>
103 void for_each(F action) const {
104 visit([&] (T* si) {
105 action(si);
106 return true;
107 });
108 }
110 template<typename F>
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 }
120 template<typename F>
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 }
139 size_t copy_to_array(T* array[], size_t array_length) const {
140 size_t sz = 0;
141 for (LinkedListEntry<T>* e = head_; sz < array_length && e != nullptr; e = e->next) {
142 array[sz++] = e->element;
143 }
145 return sz;
146 }
148 bool contains(const T* el) const {
149 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
150 if (e->element == el) {
151 return true;
152 }
153 }
154 return false;
155 }
157 static LinkedList make_list(T* const element) {
158 LinkedList<T, Allocator> one_element_list;
159 one_element_list.push_back(element);
160 return one_element_list;
161 }
163 private:
164 LinkedListEntry<T>* head_;
165 LinkedListEntry<T>* tail_;
166 DISALLOW_COPY_AND_ASSIGN(LinkedList);
167 };
169 #endif // __LINKED_LIST_H