src/list-inl.h

   1 // Copyright 2006-2009 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef V8_LIST_INL_H_
   6 #define V8_LIST_INL_H_
   7
   8 #include "src/list.h"
   9
  10 #include "src/base/macros.h"
  11 #include "src/base/platform/platform.h"
  12
  13 namespace v8 {
  14 namespace internal {
  15
  16
  17 template<typename T, class P>
  18 void List<T, P>::Add(const T& element, P alloc) {
  19   if (length_ < capacity_) {
  20     data_[length_++] = element;
  21   } else {
  22     List<T, P>::ResizeAdd(element, alloc);
  23   }
  24 }
  25
  26
  27 template<typename T, class P>
  28 void List<T, P>::AddAll(const List<T, P>& other, P alloc) {
  29   AddAll(other.ToVector(), alloc);
  30 }
  31
  32
  33 template<typename T, class P>
  34 void List<T, P>::AddAll(const Vector<T>& other, P alloc) {
  35   int result_length = length_ + other.length();
  36   if (capacity_ < result_length) Resize(result_length, alloc);
  37   if (base::is_fundamental<T>()) {
  38     memcpy(data_ + length_, other.start(), sizeof(*data_) * other.length());
  39   } else {
  40     for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
  41   }
  42   length_ = result_length;
  43 }
  44
  45
  46 // Use two layers of inlining so that the non-inlined function can
  47 // use the same implementation as the inlined version.
  48 template<typename T, class P>
  49 void List<T, P>::ResizeAdd(const T& element, P alloc) {
  50   ResizeAddInternal(element, alloc);
  51 }
  52
  53
  54 template<typename T, class P>
  55 void List<T, P>::ResizeAddInternal(const T& element, P alloc) {
  56   DCHECK(length_ >= capacity_);
  57   // Grow the list capacity by 100%, but make sure to let it grow
  58   // even when the capacity is zero (possible initial case).
  59   int new_capacity = 1 + 2 * capacity_;
  60   // Since the element reference could be an element of the list, copy
  61   // it out of the old backing storage before resizing.
  62   T temp = element;
  63   Resize(new_capacity, alloc);
  64   data_[length_++] = temp;
  65 }
  66
  67
  68 template<typename T, class P>
  69 void List<T, P>::Resize(int new_capacity, P alloc) {
  70   DCHECK_LE(length_, new_capacity);
  71   T* new_data = NewData(new_capacity, alloc);
  72   MemCopy(new_data, data_, length_ * sizeof(T));
  73   List<T, P>::DeleteData(data_);
  74   data_ = new_data;
  75   capacity_ = new_capacity;
  76 }
  77
  78
  79 template<typename T, class P>
  80 Vector<T> List<T, P>::AddBlock(T value, int count, P alloc) {
  81   int start = length_;
  82   for (int i = 0; i < count; i++) Add(value, alloc);
  83   return Vector<T>(&data_[start], count);
  84 }
  85
  86
  87 template<typename T, class P>
  88 void List<T, P>::Set(int index, const T& elm) {
  89   DCHECK(index >= 0 && index <= length_);
  90   data_[index] = elm;
  91 }
  92
  93
  94 template<typename T, class P>
  95 void List<T, P>::InsertAt(int index, const T& elm, P alloc) {
  96   DCHECK(index >= 0 && index <= length_);
  97   Add(elm, alloc);
  98   for (int i = length_ - 1; i > index; --i) {
  99     data_[i] = data_[i - 1];
 100   }
 101   data_[index] = elm;
 102 }
 103
 104
 105 template<typename T, class P>
 106 T List<T, P>::Remove(int i) {
 107   T element = at(i);
 108   length_--;
 109   while (i < length_) {
 110     data_[i] = data_[i + 1];
 111     i++;
 112   }
 113   return element;
 114 }
 115
 116
 117 template<typename T, class P>
 118 bool List<T, P>::RemoveElement(const T& elm) {
 119   for (int i = 0; i < length_; i++) {
 120     if (data_[i] == elm) {
 121       Remove(i);
 122       return true;
 123     }
 124   }
 125   return false;
 126 }
 127
 128
 129 template<typename T, class P>
 130 void List<T, P>::Allocate(int length, P allocator) {
 131   DeleteData(data_);
 132   Initialize(length, allocator);
 133   length_ = length;
 134 }
 135
 136
 137 template<typename T, class P>
 138 void List<T, P>::Clear() {
 139   DeleteData(data_);
 140   // We don't call Initialize(0) since that requires passing a Zone,
 141   // which we don't really need.
 142   data_ = NULL;
 143   capacity_ = 0;
 144   length_ = 0;
 145 }
 146
 147
 148 template<typename T, class P>
 149 void List<T, P>::Rewind(int pos) {
 150   DCHECK(0 <= pos && pos <= length_);
 151   length_ = pos;
 152 }
 153
 154
 155 template<typename T, class P>
 156 void List<T, P>::Trim(P alloc) {
 157   if (length_ < capacity_ / 4) {
 158     Resize(capacity_ / 2, alloc);
 159   }
 160 }
 161
 162
 163 template<typename T, class P>
 164 void List<T, P>::Iterate(void (*callback)(T* x)) {
 165   for (int i = 0; i < length_; i++) callback(&data_[i]);
 166 }
 167
 168
 169 template<typename T, class P>
 170 template<class Visitor>
 171 void List<T, P>::Iterate(Visitor* visitor) {
 172   for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
 173 }
 174
 175
 176 template<typename T, class P>
 177 bool List<T, P>::Contains(const T& elm) const {
 178   for (int i = 0; i < length_; i++) {
 179     if (data_[i] == elm)
 180       return true;
 181   }
 182   return false;
 183 }
 184
 185
 186 template<typename T, class P>
 187 int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
 188   int result = 0;
 189   for (int i = start; i <= end; i++) {
 190     if (data_[i] == elm) ++result;
 191   }
 192   return result;
 193 }
 194
 195
 196 template <typename T, class P>
 197 template <typename CompareFunction>
 198 void List<T, P>::Sort(CompareFunction cmp) {
 199   Sort(cmp, 0, length_);
 200 }
 201
 202
 203 template <typename T, class P>
 204 template <typename CompareFunction>
 205 void List<T, P>::Sort(CompareFunction cmp, size_t s, size_t l) {
 206   ToVector().Sort(cmp, s, l);
 207 #ifdef DEBUG
 208   for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
 209 #endif
 210 }
 211
 212
 213 template<typename T, class P>
 214 void List<T, P>::Sort() {
 215   ToVector().Sort();
 216 }
 217
 218
 219 template <typename T, class P>
 220 template <typename CompareFunction>
 221 void List<T, P>::StableSort(CompareFunction cmp) {
 222   StableSort(cmp, 0, length_);
 223 }
 224
 225
 226 template <typename T, class P>
 227 template <typename CompareFunction>
 228 void List<T, P>::StableSort(CompareFunction cmp, size_t s, size_t l) {
 229   ToVector().StableSort(cmp, s, l);
 230 #ifdef DEBUG
 231   for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
 232 #endif
 233 }
 234
 235
 236 template <typename T, class P>
 237 void List<T, P>::StableSort() {
 238   ToVector().StableSort();
 239 }
 240
 241
 242 template <typename T, class P>
 243 void List<T, P>::Initialize(int capacity, P allocator) {
 244   DCHECK(capacity >= 0);
 245   data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL;
 246   capacity_ = capacity;
 247   length_ = 0;
 248 }
 249
 250
 251 template <typename T, typename P>
 252 int SortedListBSearch(const List<T>& list, P cmp) {
 253   int low = 0;
 254   int high = list.length() - 1;
 255   while (low <= high) {
 256     int mid = (low + high) / 2;
 257     T mid_elem = list[mid];
 258
 259     if (cmp(&mid_elem) > 0) {
 260       high = mid - 1;
 261       continue;
 262     }
 263     if (cmp(&mid_elem) < 0) {
 264       low = mid + 1;
 265       continue;
 266     }
 267     // Found the elememt.
 268     return mid;
 269   }
 270   return -1;
 271 }
 272
 273
 274 template<typename T>
 275 class ElementCmp {
 276  public:
 277   explicit ElementCmp(T e) : elem_(e) {}
 278   int operator()(const T* other) {
 279     return PointerValueCompare(other, &elem_);
 280   }
 281  private:
 282   T elem_;
 283 };
 284
 285
 286 template <typename T>
 287 int SortedListBSearch(const List<T>& list, T elem) {
 288   return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem));
 289 }
 290
 291
 292 } }  // namespace v8::internal
 293
 294 #endif  // V8_LIST_INL_H_