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