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 // ForwardInputIterator
29 template<typename T>
30 class LinkedListIterator {
31  public:
LinkedListIterator()32   LinkedListIterator() : entry_(nullptr) {}
LinkedListIterator(const LinkedListIterator<T> & that)33   LinkedListIterator(const LinkedListIterator<T>& that) : entry_(that.entry_) {}
LinkedListIterator(LinkedListEntry<T> * entry)34   explicit LinkedListIterator(LinkedListEntry<T>* entry) : entry_(entry) {}
35 
36   LinkedListIterator<T>& operator=(const LinkedListIterator<T>& that) {
37     entry_ = that.entry_;
38     return *this;
39   }
40 
41   LinkedListIterator<T>& operator++() {
42     entry_ = entry_->next;
43     return *this;
44   }
45 
46   T* const operator*() {
47     return entry_->element;
48   }
49 
50   bool operator==(const LinkedListIterator<T>& that) const {
51     return entry_ == that.entry_;
52   }
53 
54   bool operator!=(const LinkedListIterator<T>& that) const {
55     return entry_ != that.entry_;
56   }
57 
58  private:
59   LinkedListEntry<T> *entry_;
60 };
61 
62 /*
63  * Represents linked list of objects of type T
64  */
65 template<typename T, typename Allocator>
66 class LinkedList {
67  public:
68   typedef LinkedListIterator<T> iterator;
69   typedef T* value_type;
70 
LinkedList()71   LinkedList() : head_(nullptr), tail_(nullptr) {}
~LinkedList()72   ~LinkedList() {
73     clear();
74   }
75 
LinkedList(LinkedList && that)76   LinkedList(LinkedList&& that) {
77     this->head_ = that.head_;
78     this->tail_ = that.tail_;
79     that.head_ = that.tail_ = nullptr;
80   }
81 
push_front(T * const element)82   void push_front(T* const element) {
83     LinkedListEntry<T>* new_entry = Allocator::alloc();
84     new_entry->next = head_;
85     new_entry->element = element;
86     head_ = new_entry;
87     if (tail_ == nullptr) {
88       tail_ = new_entry;
89     }
90   }
91 
push_back(T * const element)92   void push_back(T* const element) {
93     LinkedListEntry<T>* new_entry = Allocator::alloc();
94     new_entry->next = nullptr;
95     new_entry->element = element;
96     if (tail_ == nullptr) {
97       tail_ = head_ = new_entry;
98     } else {
99       tail_->next = new_entry;
100       tail_ = new_entry;
101     }
102   }
103 
pop_front()104   T* pop_front() {
105     if (head_ == nullptr) {
106       return nullptr;
107     }
108 
109     LinkedListEntry<T>* entry = head_;
110     T* element = entry->element;
111     head_ = entry->next;
112     Allocator::free(entry);
113 
114     if (head_ == nullptr) {
115       tail_ = nullptr;
116     }
117 
118     return element;
119   }
120 
front()121   T* front() const {
122     if (head_ == nullptr) {
123       return nullptr;
124     }
125 
126     return head_->element;
127   }
128 
clear()129   void clear() {
130     while (head_ != nullptr) {
131       LinkedListEntry<T>* p = head_;
132       head_ = head_->next;
133       Allocator::free(p);
134     }
135 
136     tail_ = nullptr;
137   }
138 
139   template<typename F>
for_each(F action)140   void for_each(F action) const {
141     visit([&] (T* si) {
142       action(si);
143       return true;
144     });
145   }
146 
147   template<typename F>
visit(F action)148   bool visit(F action) const {
149     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
150       if (!action(e->element)) {
151         return false;
152       }
153     }
154     return true;
155   }
156 
157   template<typename F>
remove_if(F predicate)158   void remove_if(F predicate) {
159     for (LinkedListEntry<T>* e = head_, *p = nullptr; e != nullptr;) {
160       if (predicate(e->element)) {
161         LinkedListEntry<T>* next = e->next;
162         if (p == nullptr) {
163           head_ = next;
164         } else {
165           p->next = next;
166         }
167 
168         if (tail_ == e) {
169           tail_ = p;
170         }
171 
172         Allocator::free(e);
173 
174         e = next;
175       } else {
176         p = e;
177         e = e->next;
178       }
179     }
180   }
181 
182   template<typename F>
find_if(F predicate)183   T* find_if(F predicate) const {
184     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
185       if (predicate(e->element)) {
186         return e->element;
187       }
188     }
189 
190     return nullptr;
191   }
192 
begin()193   iterator begin() const {
194     return iterator(head_);
195   }
196 
end()197   iterator end() const {
198     return iterator(nullptr);
199   }
200 
find(T * value)201   iterator find(T* value) const {
202     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
203       if (e->element == value) {
204         return iterator(e);
205       }
206     }
207 
208     return end();
209   }
210 
copy_to_array(T * array[],size_t array_length)211   size_t copy_to_array(T* array[], size_t array_length) const {
212     size_t sz = 0;
213     for (LinkedListEntry<T>* e = head_; sz < array_length && e != nullptr; e = e->next) {
214       array[sz++] = e->element;
215     }
216 
217     return sz;
218   }
219 
contains(const T * el)220   bool contains(const T* el) const {
221     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
222       if (e->element == el) {
223         return true;
224       }
225     }
226     return false;
227   }
228 
make_list(T * const element)229   static LinkedList make_list(T* const element) {
230     LinkedList<T, Allocator> one_element_list;
231     one_element_list.push_back(element);
232     return one_element_list;
233   }
234 
235  private:
236   LinkedListEntry<T>* head_;
237   LinkedListEntry<T>* tail_;
238   DISALLOW_COPY_AND_ASSIGN(LinkedList);
239 };
240 
241 #endif // __LINKED_LIST_H
242