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  */
  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:
  34   LinkedList() : head_(nullptr), tail_(nullptr) {}
  35   ~LinkedList() {
  36     clear();
  37   }
  38
  39   LinkedList(LinkedList&& that) {
  40     this->head_ = that.head_;
  41     this->tail_ = that.tail_;
  42     that.head_ = that.tail_ = nullptr;
  43   }
  44
  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   }
  54
  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   }
  66
  67   T* pop_front() {
  68     if (head_ == nullptr) {
  69       return nullptr;
  70     }
  71
  72     LinkedListEntry<T>* entry = head_;
  73     T* element = entry->element;
  74     head_ = entry->next;
  75     Allocator::free(entry);
  76
  77     if (head_ == nullptr) {
  78       tail_ = nullptr;
  79     }
  80
  81     return element;
  82   }
  83
  84   T* front() const {
  85     if (head_ == nullptr) {
  86       return nullptr;
  87     }
  88
  89     return head_->element;
  90   }
  91
  92   void clear() {
  93     while (head_ != nullptr) {
  94       LinkedListEntry<T>* p = head_;
  95       head_ = head_->next;
  96       Allocator::free(p);
  97     }
  98
  99     tail_ = nullptr;
 100   }
 101
 102   template<typename F>
 103   void for_each(F action) const {
 104     visit([&] (T* si) {
 105       action(si);
 106       return true;
 107     });
 108   }
 109
 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   }
 119
 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   }
 138
 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     }
 144
 145     return sz;
 146   }
 147
 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   }
 156
 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   }
 162
 163  private:
 164   LinkedListEntry<T>* head_;
 165   LinkedListEntry<T>* tail_;
 166   DISALLOW_COPY_AND_ASSIGN(LinkedList);
 167 };
 168
 169 #endif // __LINKED_LIST_H