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   int result_length = length_ + other.length_;
  50   if (capacity_ < result_length) Resize(result_length);
  51   for (int i = 0; i < other.length_; i++) {
  52     data_[length_ + i] = other.data_[i];
  53   }
  54   length_ = result_length;
  55 }
  56
  57
  58 // Use two layers of inlining so that the non-inlined function can
  59 // use the same implementation as the inlined version.
  60 template<typename T, class P>
  61 void List<T, P>::ResizeAdd(const T& element) {
  62   ResizeAddInternal(element);
  63 }
  64
  65
  66 template<typename T, class P>
  67 void List<T, P>::ResizeAddInternal(const T& element) {
  68   ASSERT(length_ >= capacity_);
  69   // Grow the list capacity by 50%, but make sure to let it grow
  70   // even when the capacity is zero (possible initial case).
  71   int new_capacity = 1 + capacity_ + (capacity_ >> 1);
  72   // Since the element reference could be an element of the list, copy
  73   // it out of the old backing storage before resizing.
  74   T temp = element;
  75   Resize(new_capacity);
  76   data_[length_++] = temp;
  77 }
  78
  79
  80 template<typename T, class P>
  81 void List<T, P>::Resize(int new_capacity) {
  82   T* new_data = List<T, P>::NewData(new_capacity);
  83   memcpy(new_data, data_, capacity_ * sizeof(T));
  84   List<T, P>::DeleteData(data_);
  85   data_ = new_data;
  86   capacity_ = new_capacity;
  87 }
  88
  89
  90 template<typename T, class P>
  91 Vector<T> List<T, P>::AddBlock(T value, int count) {
  92   int start = length_;
  93   for (int i = 0; i < count; i++) Add(value);
  94   return Vector<T>(&data_[start], count);
  95 }
  96
  97
  98 template<typename T, class P>
  99 void List<T, P>::InsertAt(int index, const T& elm) {
 100   ASSERT(index >= 0 && index <= length_);
 101   Add(elm);
 102   for (int i = length_ - 1; i > index; --i) {
 103     data_[i] = data_[i - 1];
 104   }
 105   data_[index] = elm;
 106 }
 107
 108
 109 template<typename T, class P>
 110 T List<T, P>::Remove(int i) {
 111   T element = at(i);
 112   length_--;
 113   while (i < length_) {
 114     data_[i] = data_[i + 1];
 115     i++;
 116   }
 117   return element;
 118 }
 119
 120
 121 template<typename T, class P>
 122 bool List<T, P>::RemoveElement(const T& elm) {
 123   for (int i = 0; i < length_; i++) {
 124     if (data_[i] == elm) {
 125       Remove(i);
 126       return true;
 127     }
 128   }
 129   return false;
 130 }
 131
 132
 133 template<typename T, class P>
 134 void List<T, P>::Clear() {
 135   DeleteData(data_);
 136   Initialize(0);
 137 }
 138
 139
 140 template<typename T, class P>
 141 void List<T, P>::Rewind(int pos) {
 142   length_ = pos;
 143 }
 144
 145
 146 template<typename T, class P>
 147 void List<T, P>::Iterate(void (*callback)(T* x)) {
 148   for (int i = 0; i < length_; i++) callback(&data_[i]);
 149 }
 150
 151
 152 template<typename T, class P>
 153 template<class Visitor>
 154 void List<T, P>::Iterate(Visitor* visitor) {
 155   for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
 156 }
 157
 158
 159 template<typename T, class P>
 160 bool List<T, P>::Contains(const T& elm) const {
 161   for (int i = 0; i < length_; i++) {
 162     if (data_[i] == elm)
 163       return true;
 164   }
 165   return false;
 166 }
 167
 168
 169 template<typename T, class P>
 170 int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
 171   int result = 0;
 172   for (int i = start; i <= end; i++) {
 173     if (data_[i] == elm) ++result;
 174   }
 175   return result;
 176 }
 177
 178
 179 template<typename T, class P>
 180 void List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) {
 181   ToVector().Sort(cmp);
 182 #ifdef DEBUG
 183   for (int i = 1; i < length_; i++)
 184     ASSERT(cmp(&data_[i - 1], &data_[i]) <= 0);
 185 #endif
 186 }
 187
 188
 189 template<typename T, class P>
 190 void List<T, P>::Sort() {
 191   Sort(PointerValueCompare<T>);
 192 }
 193
 194
 195 template<typename T, class P>
 196 void List<T, P>::Initialize(int capacity) {
 197   ASSERT(capacity >= 0);
 198   data_ = (capacity > 0) ? NewData(capacity) : NULL;
 199   capacity_ = capacity;
 200   length_ = 0;
 201 }
 202
 203
 204 } }  // namespace v8::internal
 205
 206 #endif  // V8_LIST_INL_H_