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 void push_front(T* const element) {
40 LinkedListEntry<T>* new_entry = Allocator::alloc();
41 new_entry->next = head_;
42 new_entry->element = element;
43 head_ = new_entry;
44 if (tail_ == nullptr) {
45 tail_ = new_entry;
46 }
47 }
49 void push_back(T* const element) {
50 LinkedListEntry<T>* new_entry = Allocator::alloc();
51 new_entry->next = nullptr;
52 new_entry->element = element;
53 if (tail_ == nullptr) {
54 tail_ = head_ = new_entry;
55 } else {
56 tail_->next = new_entry;
57 tail_ = new_entry;
58 }
59 }
61 T* pop_front() {
62 if (head_ == nullptr) {
63 return nullptr;
64 }
66 LinkedListEntry<T>* entry = head_;
67 T* element = entry->element;
68 head_ = entry->next;
69 Allocator::free(entry);
71 if (head_ == nullptr) {
72 tail_ = nullptr;
73 }
75 return element;
76 }
78 void clear() {
79 while (head_ != nullptr) {
80 LinkedListEntry<T>* p = head_;
81 head_ = head_->next;
82 Allocator::free(p);
83 }
85 tail_ = nullptr;
86 }
88 template<typename F>
89 void for_each(F action) const {
90 visit([&] (T* si) {
91 action(si);
92 return true;
93 });
94 }
96 template<typename F>
97 bool visit(F action) const {
98 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
99 if (!action(e->element)) {
100 return false;
101 }
102 }
103 return true;
104 }
106 template<typename F>
107 void remove_if(F predicate) {
108 for (LinkedListEntry<T>* e = head_, *p = nullptr; e != nullptr;) {
109 if (predicate(e->element)) {
110 LinkedListEntry<T>* next = e->next;
111 if (p == nullptr) {
112 head_ = next;
113 } else {
114 p->next = next;
115 }
116 Allocator::free(e);
117 e = next;
118 } else {
119 p = e;
120 e = e->next;
121 }
122 }
123 }
125 size_t copy_to_array(T* array[], size_t array_length) const {
126 size_t sz = 0;
127 for (LinkedListEntry<T>* e = head_; sz < array_length && e != nullptr; e = e->next) {
128 array[sz++] = e->element;
129 }
131 return sz;
132 }
134 bool contains(const T* el) const {
135 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
136 if (e->element == el) {
137 return true;
138 }
139 }
140 return false;
141 }
143 private:
144 LinkedListEntry<T>* head_;
145 LinkedListEntry<T>* tail_;
146 DISALLOW_COPY_AND_ASSIGN(LinkedList);
147 };
149 #endif // __LINKED_LIST_H