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