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/*
29 * Represents linked list of objects of type T
30 */
31template<typename T, typename Allocator>
32class LinkedList {
33 public:
34  LinkedList() : head_(nullptr), tail_(nullptr) {}
35
36  void push_front(T* const element) {
37    LinkedListEntry<T>* new_entry = Allocator::alloc();
38    new_entry->next = head_;
39    new_entry->element = element;
40    head_ = new_entry;
41    if (tail_ == nullptr) {
42      tail_ = new_entry;
43    }
44  }
45
46  void push_back(T* const element) {
47    LinkedListEntry<T>* new_entry = Allocator::alloc();
48    new_entry->next = nullptr;
49    new_entry->element = element;
50    if (tail_ == nullptr) {
51      tail_ = head_ = new_entry;
52    } else {
53      tail_->next = new_entry;
54      tail_ = new_entry;
55    }
56  }
57
58  T* pop_front() {
59    if (head_ == nullptr) {
60      return nullptr;
61    }
62
63    LinkedListEntry<T>* entry = head_;
64    T* element = entry->element;
65    head_ = entry->next;
66    Allocator::free(entry);
67
68    if (head_ == nullptr) {
69      tail_ = nullptr;
70    }
71
72    return element;
73  }
74
75  void clear() {
76    while (head_ != nullptr) {
77      LinkedListEntry<T>* p = head_;
78      head_ = head_->next;
79      Allocator::free(p);
80    }
81
82    tail_ = nullptr;
83  }
84
85  template<typename F>
86  void for_each(F&& action) {
87    for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
88      if (e->element != nullptr) {
89        action(e->element);
90      }
91    }
92  }
93
94  template<typename F>
95  void remove_if(F&& predicate) {
96    for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
97      if (e->element != nullptr && predicate(e->element)) {
98        e->element = nullptr;
99      }
100    }
101  }
102
103  bool contains(const T* el) {
104    for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
105      if (e->element != nullptr && e->element == el) {
106        return true;
107      }
108    }
109    return false;
110  }
111
112 private:
113  LinkedListEntry<T>* head_;
114  LinkedListEntry<T>* tail_;
115  DISALLOW_COPY_AND_ASSIGN(LinkedList);
116};
117
118#endif // __LINKED_LIST_H
119