src/list-inl.h

   1 // Copyright 2006-2008 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 T& List<T, P>::Add(const T& element) {
  38   if (length_ >= capacity_) {
  39     // Grow the list capacity by 50%, but make sure to let it grow
  40     // even when the capacity is zero (possible initial case).
  41     int new_capacity = 1 + capacity_ + (capacity_ >> 1);
  42     T* new_data = NewData(new_capacity);
  43     memcpy(new_data, data_, capacity_ * sizeof(T));
  44     DeleteData(data_);
  45     data_ = new_data;
  46     capacity_ = new_capacity;
  47   }
  48   return data_[length_++] = element;
  49 }
  50
  51
  52 template<typename T, class P>
  53 Vector<T> List<T, P>::AddBlock(const T& element, int count) {
  54   int start = length_;
  55   for (int i = 0; i < count; i++)
  56     Add(element);
  57   return Vector<T>(&data_[start], count);
  58 }
  59
  60
  61 template<typename T, class P>
  62 T& List<T, P>::Insert(int i, const T& element) {
  63   int free_index = length_ - 1;
  64   Add(last());  // Add grows the list if necessary.
  65   while (free_index > i) {
  66     data_[free_index] = data_[free_index - 1];
  67     free_index--;
  68   }
  69   data_[free_index] = element;
  70 }
  71
  72
  73 template<typename T, class P>
  74 T List<T, P>::Remove(int i) {
  75   T element = at(i);
  76   length_--;
  77   while (i < length_) {
  78     data_[i] = data_[i + 1];
  79     i++;
  80   }
  81   return element;
  82 }
  83
  84
  85 template<typename T, class P>
  86 void List<T, P>::Clear() {
  87   DeleteData(data_);
  88   Initialize(0);
  89 }
  90
  91
  92 template<typename T, class P>
  93 void List<T, P>::Rewind(int pos) {
  94   length_ = pos;
  95 }
  96
  97
  98 template<typename T, class P>
  99 void List<T, P>::Iterate(void (*callback)(T* x)) {
 100   for (int i = 0; i < length_; i++) callback(&data_[i]);
 101 }
 102
 103
 104 template<typename T, class P>
 105 bool List<T, P>::Contains(const T& elm) {
 106   for (int i = 0; i < length_; i++) {
 107     if (data_[i] == elm)
 108       return true;
 109   }
 110   return false;
 111 }
 112
 113
 114 template<typename T, class P>
 115 void List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) {
 116   ToVector().Sort(cmp);
 117 #ifdef DEBUG
 118   for (int i = 1; i < length_; i++)
 119     ASSERT(cmp(&data_[i - 1], &data_[i]) <= 0);
 120 #endif
 121 }
 122
 123
 124 template<typename T, class P>
 125 void List<T, P>::Sort() {
 126   Sort(PointerValueCompare<T>);
 127 }
 128
 129
 130 template<typename T, class P>
 131 void List<T, P>::Initialize(int capacity) {
 132   ASSERT(capacity >= 0);
 133   data_ = (capacity > 0) ? NewData(capacity) : NULL;
 134   capacity_ = capacity;
 135   length_ = 0;
 136 }
 137
 138
 139 } }  // namespace v8::internal
 140
 141 #endif  // V8_LIST_INL_H_