list-inl.h 6.45 KB
Newer Older
1
// Copyright 2006-2009 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

#ifndef V8_LIST_INL_H_
#define V8_LIST_INL_H_

8
#include "src/list.h"
9

10
#include "src/base/macros.h"
11
#include "src/base/platform/platform.h"
12

13 14
namespace v8 {
namespace internal {
15 16


17
template<typename T, class P>
18
void List<T, P>::Add(const T& element, P alloc) {
19 20
  if (length_ < capacity_) {
    data_[length_++] = element;
21
  } else {
22
    List<T, P>::ResizeAdd(element, alloc);
23 24 25 26
  }
}


27
template<typename T, class P>
28 29
void List<T, P>::AddAll(const List<T, P>& other, P alloc) {
  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 38 39 40
  if (base::is_fundamental<T>()) {
    memcpy(data_ + length_, other.start(), sizeof(*data_) * other.length());
  } else {
    for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
41
  }
42
  length_ = result_length;
43 44 45
}


46 47 48
// Use two layers of inlining so that the non-inlined function can
// use the same implementation as the inlined version.
template<typename T, class P>
49 50
void List<T, P>::ResizeAdd(const T& element, P alloc) {
  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 61 62
  // Since the element reference could be an element of the list, copy
  // it out of the old backing storage before resizing.
  T temp = element;
63
  Resize(new_capacity, alloc);
64 65 66 67 68
  data_[length_++] = temp;
}


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 74 75 76 77 78
  List<T, P>::DeleteData(data_);
  data_ = new_data;
  capacity_ = new_capacity;
}


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 84 85 86
  return Vector<T>(&data_[start], count);
}


87 88
template<typename T, class P>
void List<T, P>::Set(int index, const T& elm) {
89
  DCHECK(index >= 0 && index <= length_);
90 91 92 93
  data_[index] = elm;
}


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 99 100 101 102 103 104
  for (int i = length_ - 1; i > index; --i) {
    data_[i] = data_[i - 1];
  }
  data_[index] = elm;
}


105 106 107 108 109 110 111 112 113 114 115 116
template<typename T, class P>
T List<T, P>::Remove(int i) {
  T element = at(i);
  length_--;
  while (i < length_) {
    data_[i] = data_[i + 1];
    i++;
  }
  return element;
}


117 118 119 120 121 122 123 124 125 126 127
template<typename T, class P>
bool List<T, P>::RemoveElement(const T& elm) {
  for (int i = 0; i < length_; i++) {
    if (data_[i] == elm) {
      Remove(i);
      return true;
    }
  }
  return false;
}

128 129 130 131 132 133
template <typename T, class P>
void List<T, P>::Swap(List<T, P>* list) {
  std::swap(data_, list->data_);
  std::swap(length_, list->length_);
  std::swap(capacity_, list->capacity_);
}
134

135
template<typename T, class P>
136
void List<T, P>::Allocate(int length, P allocator) {
137
  DeleteData(data_);
138
  Initialize(length, allocator);
139 140 141 142
  length_ = length;
}


143 144 145
template<typename T, class P>
void List<T, P>::Clear() {
  DeleteData(data_);
146 147 148 149 150
  // We don't call Initialize(0) since that requires passing a Zone,
  // which we don't really need.
  data_ = NULL;
  capacity_ = 0;
  length_ = 0;
151 152 153 154 155
}


template<typename T, class P>
void List<T, P>::Rewind(int pos) {
156
  DCHECK(0 <= pos && pos <= length_);
157 158 159 160
  length_ = pos;
}


161 162 163 164 165 166 167 168
template<typename T, class P>
void List<T, P>::Trim(P alloc) {
  if (length_ < capacity_ / 4) {
    Resize(capacity_ / 2, alloc);
  }
}


169 170 171 172 173 174
template<typename T, class P>
void List<T, P>::Iterate(void (*callback)(T* x)) {
  for (int i = 0; i < length_; i++) callback(&data_[i]);
}


175 176 177 178 179 180 181
template<typename T, class P>
template<class Visitor>
void List<T, P>::Iterate(Visitor* visitor) {
  for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
}


182
template<typename T, class P>
183
bool List<T, P>::Contains(const T& elm) const {
184 185 186 187 188 189 190 191
  for (int i = 0; i < length_; i++) {
    if (data_[i] == elm)
      return true;
  }
  return false;
}


192 193 194 195 196 197 198 199 200 201
template<typename T, class P>
int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
  int result = 0;
  for (int i = start; i <= end; i++) {
    if (data_[i] == elm) ++result;
  }
  return result;
}


202 203 204
template <typename T, class P>
template <typename CompareFunction>
void List<T, P>::Sort(CompareFunction cmp) {
205 206 207 208 209
  Sort(cmp, 0, length_);
}


template <typename T, class P>
210 211
template <typename CompareFunction>
void List<T, P>::Sort(CompareFunction cmp, size_t s, size_t l) {
212
  ToVector().Sort(cmp, s, l);
213
#ifdef DEBUG
214
  for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
215 216 217 218
#endif
}


219 220
template<typename T, class P>
void List<T, P>::Sort() {
221
  ToVector().Sort();
222 223 224
}


225
template <typename T, class P>
226 227
template <typename CompareFunction>
void List<T, P>::StableSort(CompareFunction cmp) {
228 229 230 231 232
  StableSort(cmp, 0, length_);
}


template <typename T, class P>
233 234
template <typename CompareFunction>
void List<T, P>::StableSort(CompareFunction cmp, size_t s, size_t l) {
235 236 237 238 239 240 241 242 243 244 245 246 247
  ToVector().StableSort(cmp, s, l);
#ifdef DEBUG
  for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
#endif
}


template <typename T, class P>
void List<T, P>::StableSort() {
  ToVector().StableSort();
}


248 249
template <typename T, typename P>
int SortedListBSearch(const List<T>& list, P cmp) {
250 251 252
  int low = 0;
  int high = list.length() - 1;
  while (low <= high) {
253
    int mid = low + (high - low) / 2;
254 255
    T mid_elem = list[mid];

256
    if (cmp(&mid_elem) > 0) {
257 258 259
      high = mid - 1;
      continue;
    }
260
    if (cmp(&mid_elem) < 0) {
261 262 263 264 265 266 267 268 269 270
      low = mid + 1;
      continue;
    }
    // Found the elememt.
    return mid;
  }
  return -1;
}


271 272 273 274 275 276 277 278 279 280 281 282
template<typename T>
class ElementCmp {
 public:
  explicit ElementCmp(T e) : elem_(e) {}
  int operator()(const T* other) {
    return PointerValueCompare(other, &elem_);
  }
 private:
  T elem_;
};


283 284
template <typename T>
int SortedListBSearch(const List<T>& list, T elem) {
285
  return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem));
286 287
}

288

289 290
}  // namespace internal
}  // namespace v8
291 292

#endif  // V8_LIST_INL_H_