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