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) {
90 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
91 if (e->element != nullptr) {
92 action(e->element);
93 }
94 }
95 }
97 template<typename F>
98 void remove_if(F&& predicate) {
99 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
100 if (e->element != nullptr && predicate(e->element)) {
101 e->element = nullptr;
102 }
103 }
104 }
106 bool contains(const T* el) {
107 for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
108 if (e->element != nullptr && e->element == el) {
109 return true;
110 }
111 }
112 return false;
113 }
115 private:
116 LinkedListEntry<T>* head_;
117 LinkedListEntry<T>* tail_;
118 DISALLOW_COPY_AND_ASSIGN(LinkedList);
119 };
121 #endif // __LINKED_LIST_H