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