Support gethostbyname_r_ERANGE.
[android-sdk/platform-bionic.git] / linker / linked_list.h
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   LinkedList(LinkedList&& that) {
40     this->head_ = that.head_;
41     this->tail_ = that.tail_;
42     that.head_ = that.tail_ = nullptr;
43   }
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   }
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   }
67   T* pop_front() {
68     if (head_ == nullptr) {
69       return nullptr;
70     }
72     LinkedListEntry<T>* entry = head_;
73     T* element = entry->element;
74     head_ = entry->next;
75     Allocator::free(entry);
77     if (head_ == nullptr) {
78       tail_ = nullptr;
79     }
81     return element;
82   }
84   T* front() const {
85     if (head_ == nullptr) {
86       return nullptr;
87     }
89     return head_->element;
90   }
92   void clear() {
93     while (head_ != nullptr) {
94       LinkedListEntry<T>* p = head_;
95       head_ = head_->next;
96       Allocator::free(p);
97     }
99     tail_ = nullptr;
100   }
102   template<typename F>
103   void for_each(F action) const {
104     visit([&] (T* si) {
105       action(si);
106       return true;
107     });
108   }
110   template<typename F>
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   }
120   template<typename F>
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   }
139   size_t copy_to_array(T* array[], size_t array_length) const {
140     size_t sz = 0;
141     for (LinkedListEntry<T>* e = head_; sz < array_length && e != nullptr; e = e->next) {
142       array[sz++] = e->element;
143     }
145     return sz;
146   }
148   bool contains(const T* el) const {
149     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
150       if (e->element == el) {
151         return true;
152       }
153     }
154     return false;
155   }
157   static LinkedList make_list(T* const element) {
158     LinkedList<T, Allocator> one_element_list;
159     one_element_list.push_back(element);
160     return one_element_list;
161   }
163  private:
164   LinkedListEntry<T>* head_;
165   LinkedListEntry<T>* tail_;
166   DISALLOW_COPY_AND_ASSIGN(LinkedList);
167 };
169 #endif // __LINKED_LIST_H