Revert "Revert "Fix dlsym(3) to do breadth first search.""
This reverts commit 1b1966d9448e979d1503a3d8843708bfa8880dc6.
Change-Id: I05d6d3481aaf8f3e260d2e5e950248519a1d347f
diff --git a/linker/linked_list.h b/linker/linked_list.h
index 52af0f1..7f8c901 100644
--- a/linker/linked_list.h
+++ b/linker/linked_list.h
@@ -31,13 +31,45 @@
template<typename T, typename Allocator>
class LinkedList {
public:
- LinkedList() : head_(nullptr) {}
+ LinkedList() : head_(nullptr), tail_(nullptr) {}
void push_front(T* const element) {
LinkedListEntry<T>* new_entry = Allocator::alloc();
new_entry->next = head_;
new_entry->element = element;
head_ = new_entry;
+ if (tail_ == nullptr) {
+ tail_ = new_entry;
+ }
+ }
+
+ void push_back(T* const element) {
+ LinkedListEntry<T>* new_entry = Allocator::alloc();
+ new_entry->next = nullptr;
+ new_entry->element = element;
+ if (tail_ == nullptr) {
+ tail_ = head_ = new_entry;
+ } else {
+ tail_->next = new_entry;
+ tail_ = new_entry;
+ }
+ }
+
+ T* pop_front() {
+ if (head_ == nullptr) {
+ return nullptr;
+ }
+
+ LinkedListEntry<T>* entry = head_;
+ T* element = entry->element;
+ head_ = entry->next;
+ Allocator::free(entry);
+
+ if (head_ == nullptr) {
+ tail_ = nullptr;
+ }
+
+ return element;
}
void clear() {
@@ -46,6 +78,8 @@
head_ = head_->next;
Allocator::free(p);
}
+
+ tail_ = nullptr;
}
template<typename F>
@@ -68,6 +102,7 @@
private:
LinkedListEntry<T>* head_;
+ LinkedListEntry<T>* tail_;
DISALLOW_COPY_AND_ASSIGN(LinkedList);
};