src/3rdparty/v8/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
  33 namespace v8 {
  34 namespace internal {
  35
  36
  37 template<typename T, class P>
  38 void List<T, P>::Add(const T& element) {
  39   if (length_ < capacity_) {
  40     data_[length_++] = element;
  41   } else {
  42     List<T, P>::ResizeAdd(element);
  43   }
  44 }
  45
  46
  47 template<typename T, class P>
  48 void List<T, P>::AddAll(const List<T, P>& other) {
  49   AddAll(other.ToVector());
  50 }
  51
  52
  53 template<typename T, class P>
  54 void List<T, P>::AddAll(const Vector<T>& other) {
  55   int result_length = length_ + other.length();
  56   if (capacity_ < result_length) Resize(result_length);
  57   for (int i = 0; i < other.length(); i++) {
  58     data_[length_ + i] = other.at(i);
  59   }
  60   length_ = result_length;
  61 }
  62
  63
  64 // Use two layers of inlining so that the non-inlined function can
  65 // use the same implementation as the inlined version.
  66 template<typename T, class P>
  67 void List<T, P>::ResizeAdd(const T& element) {
  68   ResizeAddInternal(element);
  69 }
  70
  71
  72 template<typename T, class P>
  73 void List<T, P>::ResizeAddInternal(const T& element) {
  74   ASSERT(length_ >= capacity_);
  75   // Grow the list capacity by 100%, but make sure to let it grow
  76   // even when the capacity is zero (possible initial case).
  77   int new_capacity = 1 + 2 * capacity_;
  78   // Since the element reference could be an element of the list, copy
  79   // it out of the old backing storage before resizing.
  80   T temp = element;
  81   Resize(new_capacity);
  82   data_[length_++] = temp;
  83 }
  84
  85
  86 template<typename T, class P>
  87 void List<T, P>::Resize(int new_capacity) {
  88   T* new_data = List<T, P>::NewData(new_capacity);
  89   memcpy(new_data, data_, capacity_ * sizeof(T));
  90   List<T, P>::DeleteData(data_);
  91   data_ = new_data;
  92   capacity_ = new_capacity;
  93 }
  94
  95
  96 template<typename T, class P>
  97 Vector<T> List<T, P>::AddBlock(T value, int count) {
  98   int start = length_;
  99   for (int i = 0; i < count; i++) Add(value);
 100   return Vector<T>(&data_[start], count);
 101 }
 102
 103
 104 template<typename T, class P>
 105 void List<T, P>::InsertAt(int index, const T& elm) {
 106   ASSERT(index >= 0 && index <= length_);
 107   Add(elm);
 108   for (int i = length_ - 1; i > index; --i) {
 109     data_[i] = data_[i - 1];
 110   }
 111   data_[index] = elm;
 112 }
 113
 114
 115 template<typename T, class P>
 116 T List<T, P>::Remove(int i) {
 117   T element = at(i);
 118   length_--;
 119   while (i < length_) {
 120     data_[i] = data_[i + 1];
 121     i++;
 122   }
 123   return element;
 124 }
 125
 126
 127 template<typename T, class P>
 128 bool List<T, P>::RemoveElement(const T& elm) {
 129   for (int i = 0; i < length_; i++) {
 130     if (data_[i] == elm) {
 131       Remove(i);
 132       return true;
 133     }
 134   }
 135   return false;
 136 }
 137
 138
 139 template<typename T, class P>
 140 void List<T, P>::Allocate(int length) {
 141   DeleteData(data_);
 142   Initialize(length);
 143   length_ = length;
 144 }
 145
 146
 147 template<typename T, class P>
 148 void List<T, P>::Clear() {
 149   DeleteData(data_);
 150   Initialize(0);
 151 }
 152
 153
 154 template<typename T, class P>
 155 void List<T, P>::Rewind(int pos) {
 156   length_ = pos;
 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   Sort(PointerValueCompare<T>);
 206 }
 207
 208
 209 template<typename T, class P>
 210 void List<T, P>::Initialize(int capacity) {
 211   ASSERT(capacity >= 0);
 212   data_ = (capacity > 0) ? NewData(capacity) : 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) / 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_