Home | History | Annotate | Download | only in linker 
      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   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 
     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 
     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 
     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>
     89   void for_each(F action) {
     90     visit([&] (T* si) {
     91       action(si);
     92       return true;
     93     });
     94   }
     95 
     96   template<typename F>
     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>
    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 
    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 
    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