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 
push_front(T * const element)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   }
48 
push_back(T * const element)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   }
60 
pop_front()61   T* pop_front() {
62     if (head_ == nullptr) {
63       return nullptr;
64     }
65 
66     LinkedListEntry<T>* entry = head_;
67     T* element = entry->element;
68     head_ = entry->next;
69     Allocator::free(entry);
70 
71     if (head_ == nullptr) {
72       tail_ = nullptr;
73     }
74 
75     return element;
76   }
77 
clear()78   void clear() {
79     while (head_ != nullptr) {
80       LinkedListEntry<T>* p = head_;
81       head_ = head_->next;
82       Allocator::free(p);
83     }
84 
85     tail_ = nullptr;
86   }
87 
88   template<typename F>
for_each(F action)89   void for_each(F action) {
90     visit([&] (T* si) {
91       action(si);
92       return true;
93     });
94   }
95 
96   template<typename F>
visit(F action)97   bool visit(F action) {
98     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
99       if (!action(e->element)) {
100         return false;
101       }
102     }
103     return true;
104   }
105 
106   template<typename F>
remove_if(F predicate)107   void remove_if(F predicate) {
108     for (LinkedListEntry<T>* e = head_, *p = nullptr; e != nullptr;) {
109       if (predicate(e->element)) {
110         LinkedListEntry<T>* next = e->next;
111         if (p == nullptr) {
112           head_ = next;
113         } else {
114           p->next = next;
115         }
116         Allocator::free(e);
117         e = next;
118       } else {
119         p = e;
120         e = e->next;
121       }
122     }
123   }
124 
copy_to_array(T * array[],size_t array_length)125   size_t copy_to_array(T* array[], size_t array_length) const {
126     size_t sz = 0;
127     for (LinkedListEntry<T>* e = head_; sz < array_length && e != nullptr; e = e->next) {
128       array[sz++] = e->element;
129     }
130 
131     return sz;
132   }
133 
contains(const T * el)134   bool contains(const T* el) const {
135     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
136       if (e->element == el) {
137         return true;
138       }
139     }
140     return false;
141   }
142 
143  private:
144   LinkedListEntry<T>* head_;
145   LinkedListEntry<T>* tail_;
146   DISALLOW_COPY_AND_ASSIGN(LinkedList);
147 };
148 
149 #endif // __LINKED_LIST_H
150