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 template <typename T, class P>
 129 void List<T, P>::Swap(List<T, P>* list) {
 130   std::swap(data_, list->data_);
 131   std::swap(length_, list->length_);
 132   std::swap(capacity_, list->capacity_);
 133 }
 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   length_ = length;
 140 }
 141
 142
 143 template<typename T, class P>
 144 void List<T, P>::Clear() {
 145   DeleteData(data_);
 146   // We don't call Initialize(0) since that requires passing a Zone,
 147   // which we don't really need.
 148   data_ = NULL;
 149   capacity_ = 0;
 150   length_ = 0;
 151 }
 152
 153
 154 template<typename T, class P>
 155 void List<T, P>::Rewind(int pos) {
 156   DCHECK(0 <= pos && pos <= length_);
 157   length_ = pos;
 158 }
 159
 160
 161 template<typename T, class P>
 162 void List<T, P>::Trim(P alloc) {
 163   if (length_ < capacity_ / 4) {
 164     Resize(capacity_ / 2, alloc);
 165   }
 166 }
 167
 168
 169 template<typename T, class P>
 170 void List<T, P>::Iterate(void (*callback)(T* x)) {
 171   for (int i = 0; i < length_; i++) callback(&data_[i]);
 172 }
 173
 174
 175 template<typename T, class P>
 176 template<class Visitor>
 177 void List<T, P>::Iterate(Visitor* visitor) {
 178   for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
 179 }
 180
 181
 182 template<typename T, class P>
 183 bool List<T, P>::Contains(const T& elm) const {
 184   for (int i = 0; i < length_; i++) {
 185     if (data_[i] == elm)
 186       return true;
 187   }
 188   return false;
 189 }
 190
 191
 192 template<typename T, class P>
 193 int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
 194   int result = 0;
 195   for (int i = start; i <= end; i++) {
 196     if (data_[i] == elm) ++result;
 197   }
 198   return result;
 199 }
 200
 201
 202 template <typename T, class P>
 203 template <typename CompareFunction>
 204 void List<T, P>::Sort(CompareFunction cmp) {
 205   Sort(cmp, 0, length_);
 206 }
 207
 208
 209 template <typename T, class P>
 210 template <typename CompareFunction>
 211 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 #endif
 216 }
 217
 218
 219 template<typename T, class P>
 220 void List<T, P>::Sort() {
 221   ToVector().Sort();
 222 }
 223
 224
 225 template <typename T, class P>
 226 template <typename CompareFunction>
 227 void List<T, P>::StableSort(CompareFunction cmp) {
 228   StableSort(cmp, 0, length_);
 229 }
 230
 231
 232 template <typename T, class P>
 233 template <typename CompareFunction>
 234 void List<T, P>::StableSort(CompareFunction cmp, size_t s, size_t l) {
 235   ToVector().StableSort(cmp, s, l);
 236 #ifdef DEBUG
 237   for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
 238 #endif
 239 }
 240
 241
 242 template <typename T, class P>
 243 void List<T, P>::StableSort() {
 244   ToVector().StableSort();
 245 }
 246
 247
 248 template <typename T, class P>
 249 void List<T, P>::Initialize(int capacity, P allocator) {
 250   DCHECK(capacity >= 0);
 251   data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL;
 252   capacity_ = capacity;
 253   length_ = 0;
 254 }
 255
 256
 257 template <typename T, typename P>
 258 int SortedListBSearch(const List<T>& list, P cmp) {
 259   int low = 0;
 260   int high = list.length() - 1;
 261   while (low <= high) {
 262     int mid = (low + high) / 2;
 263     T mid_elem = list[mid];
 264
 265     if (cmp(&mid_elem) > 0) {
 266       high = mid - 1;
 267       continue;
 268     }
 269     if (cmp(&mid_elem) < 0) {
 270       low = mid + 1;
 271       continue;
 272     }
 273     // Found the elememt.
 274     return mid;
 275   }
 276   return -1;
 277 }
 278
 279
 280 template<typename T>
 281 class ElementCmp {
 282  public:
 283   explicit ElementCmp(T e) : elem_(e) {}
 284   int operator()(const T* other) {
 285     return PointerValueCompare(other, &elem_);
 286   }
 287  private:
 288   T elem_;
 289 };
 290
 291
 292 template <typename T>
 293 int SortedListBSearch(const List<T>& list, T elem) {
 294   return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem));
 295 }
 296
 297
 298 } }  // namespace v8::internal
 299
 300 #endif  // V8_LIST_INL_H_