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
22template<typename T>
23struct LinkedListEntry {
24  LinkedListEntry<T>* next;
25  T* element;
26};
27
28// ForwardInputIterator
29template<typename T>
30class LinkedListIterator {
31 public:
32  LinkedListIterator() : entry_(nullptr) {}
33  LinkedListIterator(const LinkedListIterator<T>& that) : entry_(that.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 */
65template<typename T, typename Allocator>
66class LinkedList {
67 public:
68  typedef LinkedListIterator<T> iterator;
69  typedef T* value_type;
70
71  LinkedList() : head_(nullptr), tail_(nullptr) {}
72  ~LinkedList() {
73    clear();
74  }
75
76  LinkedList(LinkedList&& that) {
77    this->head_ = that.head_;
78    this->tail_ = that.tail_;
79    that.head_ = that.tail_ = nullptr;
80  }
81
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
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
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
121  T* front() const {
122    if (head_ == nullptr) {
123      return nullptr;
124    }
125
126    return head_->element;
127  }
128
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>
140  void for_each(F action) const {
141    visit([&] (T* si) {
142      action(si);
143      return true;
144    });
145  }
146
147  template<typename F>
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>
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>
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
193  iterator begin() const {
194    return iterator(head_);
195  }
196
197  iterator end() const {
198    return iterator(nullptr);
199  }
200
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
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
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
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