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   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 size() const {
 126     size_t sz = 0;
 127     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
 128       ++sz;
 129     }
 130
 131     return sz;
 132   }
 133
 134   size_t copy_to_array(T* array[], size_t array_length) const {
 135     size_t sz = 0;
 136     for (LinkedListEntry<T>* e = head_; sz < array_length && e != nullptr; e = e->next) {
 137       array[sz++] = e->element;
 138     }
 139
 140     return sz;
 141   }
 142
 143   bool contains(const T* el) const {
 144     for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
 145       if (e->element == el) {
 146         return true;
 147       }
 148     }
 149     return false;
 150   }
 151
 152  private:
 153   LinkedListEntry<T>* head_;
 154   LinkedListEntry<T>* tail_;
 155   DISALLOW_COPY_AND_ASSIGN(LinkedList);
 156 };
 157
 158 #endif // __LINKED_LIST_H