src/list-inl.h

   1 // Copyright 2006-2009 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #ifndef V8_LIST_INL_H_
  29 #define V8_LIST_INL_H_
  30
  31 #include "list.h"
  32 #include "platform.h"
  33
  34 namespace v8 {
  35 namespace internal {
  36
  37
  38 template<typename T, class P>
  39 void List<T, P>::Add(const T& element, P alloc) {
  40   if (length_ < capacity_) {
  41     data_[length_++] = element;
  42   } else {
  43     List<T, P>::ResizeAdd(element, alloc);
  44   }
  45 }
  46
  47
  48 template<typename T, class P>
  49 void List<T, P>::AddAll(const List<T, P>& other, P alloc) {
  50   AddAll(other.ToVector(), alloc);
  51 }
  52
  53
  54 template<typename T, class P>
  55 void List<T, P>::AddAll(const Vector<T>& other, P alloc) {
  56   int result_length = length_ + other.length();
  57   if (capacity_ < result_length) Resize(result_length, alloc);
  58   for (int i = 0; i < other.length(); i++) {
  59     data_[length_ + i] = other.at(i);
  60   }
  61   length_ = result_length;
  62 }
  63
  64
  65 // Use two layers of inlining so that the non-inlined function can
  66 // use the same implementation as the inlined version.
  67 template<typename T, class P>
  68 void List<T, P>::ResizeAdd(const T& element, P alloc) {
  69   ResizeAddInternal(element, alloc);
  70 }
  71
  72
  73 template<typename T, class P>
  74 void List<T, P>::ResizeAddInternal(const T& element, P alloc) {
  75   ASSERT(length_ >= capacity_);
  76   // Grow the list capacity by 100%, but make sure to let it grow
  77   // even when the capacity is zero (possible initial case).
  78   int new_capacity = 1 + 2 * capacity_;
  79   // Since the element reference could be an element of the list, copy
  80   // it out of the old backing storage before resizing.
  81   T temp = element;
  82   Resize(new_capacity, alloc);
  83   data_[length_++] = temp;
  84 }
  85
  86
  87 template<typename T, class P>
  88 void List<T, P>::Resize(int new_capacity, P alloc) {
  89   ASSERT_LE(length_, new_capacity);
  90   T* new_data = NewData(new_capacity, alloc);
  91   OS::MemCopy(new_data, data_, length_ * sizeof(T));
  92   List<T, P>::DeleteData(data_);
  93   data_ = new_data;
  94   capacity_ = new_capacity;
  95 }
  96
  97
  98 template<typename T, class P>
  99 Vector<T> List<T, P>::AddBlock(T value, int count, P alloc) {
 100   int start = length_;
 101   for (int i = 0; i < count; i++) Add(value, alloc);
 102   return Vector<T>(&data_[start], count);
 103 }
 104
 105
 106 template<typename T, class P>
 107 void List<T, P>::Set(int index, const T& elm) {
 108   ASSERT(index >= 0 && index <= length_);
 109   data_[index] = elm;
 110 }
 111
 112
 113 template<typename T, class P>
 114 void List<T, P>::InsertAt(int index, const T& elm, P alloc) {
 115   ASSERT(index >= 0 && index <= length_);
 116   Add(elm, alloc);
 117   for (int i = length_ - 1; i > index; --i) {
 118     data_[i] = data_[i - 1];
 119   }
 120   data_[index] = elm;
 121 }
 122
 123
 124 template<typename T, class P>
 125 T List<T, P>::Remove(int i) {
 126   T element = at(i);
 127   length_--;
 128   while (i < length_) {
 129     data_[i] = data_[i + 1];
 130     i++;
 131   }
 132   return element;
 133 }
 134
 135
 136 template<typename T, class P>
 137 bool List<T, P>::RemoveElement(const T& elm) {
 138   for (int i = 0; i < length_; i++) {
 139     if (data_[i] == elm) {
 140       Remove(i);
 141       return true;
 142     }
 143   }
 144   return false;
 145 }
 146
 147
 148 template<typename T, class P>
 149 void List<T, P>::Allocate(int length, P allocator) {
 150   DeleteData(data_);
 151   Initialize(length, allocator);
 152   length_ = length;
 153 }
 154
 155
 156 template<typename T, class P>
 157 void List<T, P>::Clear() {
 158   DeleteData(data_);
 159   // We don't call Initialize(0) since that requires passing a Zone,
 160   // which we don't really need.
 161   data_ = NULL;
 162   capacity_ = 0;
 163   length_ = 0;
 164 }
 165
 166
 167 template<typename T, class P>
 168 void List<T, P>::Rewind(int pos) {
 169   ASSERT(pos <= length_);
 170   length_ = pos;
 171 }
 172
 173
 174 template<typename T, class P>
 175 void List<T, P>::Trim(P alloc) {
 176   if (length_ < capacity_ / 4) {
 177     Resize(capacity_ / 2, alloc);
 178   }
 179 }
 180
 181
 182 template<typename T, class P>
 183 void List<T, P>::Iterate(void (*callback)(T* x)) {
 184   for (int i = 0; i < length_; i++) callback(&data_[i]);
 185 }
 186
 187
 188 template<typename T, class P>
 189 template<class Visitor>
 190 void List<T, P>::Iterate(Visitor* visitor) {
 191   for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
 192 }
 193
 194
 195 template<typename T, class P>
 196 bool List<T, P>::Contains(const T& elm) const {
 197   for (int i = 0; i < length_; i++) {
 198     if (data_[i] == elm)
 199       return true;
 200   }
 201   return false;
 202 }
 203
 204
 205 template<typename T, class P>
 206 int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
 207   int result = 0;
 208   for (int i = start; i <= end; i++) {
 209     if (data_[i] == elm) ++result;
 210   }
 211   return result;
 212 }
 213
 214
 215 template<typename T, class P>
 216 void List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) {
 217   ToVector().Sort(cmp);
 218 #ifdef DEBUG
 219   for (int i = 1; i < length_; i++)
 220     ASSERT(cmp(&data_[i - 1], &data_[i]) <= 0);
 221 #endif
 222 }
 223
 224
 225 template<typename T, class P>
 226 void List<T, P>::Sort() {
 227   ToVector().Sort();
 228 }
 229
 230
 231 template<typename T, class P>
 232 void List<T, P>::Initialize(int capacity, P allocator) {
 233   ASSERT(capacity >= 0);
 234   data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL;
 235   capacity_ = capacity;
 236   length_ = 0;
 237 }
 238
 239
 240 template <typename T, typename P>
 241 int SortedListBSearch(const List<T>& list, P cmp) {
 242   int low = 0;
 243   int high = list.length() - 1;
 244   while (low <= high) {
 245     int mid = (low + high) / 2;
 246     T mid_elem = list[mid];
 247
 248     if (cmp(&mid_elem) > 0) {
 249       high = mid - 1;
 250       continue;
 251     }
 252     if (cmp(&mid_elem) < 0) {
 253       low = mid + 1;
 254       continue;
 255     }
 256     // Found the elememt.
 257     return mid;
 258   }
 259   return -1;
 260 }
 261
 262
 263 template<typename T>
 264 class ElementCmp {
 265  public:
 266   explicit ElementCmp(T e) : elem_(e) {}
 267   int operator()(const T* other) {
 268     return PointerValueCompare(other, &elem_);
 269   }
 270  private:
 271   T elem_;
 272 };
 273
 274
 275 template <typename T>
 276 int SortedListBSearch(const List<T>& list, T elem) {
 277   return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem));
 278 }
 279
 280
 281 } }  // namespace v8::internal
 282
 283 #endif  // V8_LIST_INL_H_