1 // Copyright 2011 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_SMALL_POINTER_LIST_H_ 29 #define V8_SMALL_POINTER_LIST_H_ 30 31 #include "checks.h" 32 #include "v8globals.h" 33 #include "zone.h" 34 35 namespace v8 { 36 namespace internal { 37 38 // SmallPointerList is a list optimized for storing no or just a 39 // single value. When more values are given it falls back to ZoneList. 40 // 41 // The interface tries to be as close to List from list.h as possible. 42 template <typename T> 43 class SmallPointerList { 44 public: 45 SmallPointerList() : data_(kEmptyTag) {} 46 47 explicit SmallPointerList(int capacity) : data_(kEmptyTag) { 48 Reserve(capacity); 49 } 50 51 void Reserve(int capacity) { 52 if (capacity < 2) return; 53 if ((data_ & kTagMask) == kListTag) { 54 if (list()->capacity() >= capacity) return; 55 int old_length = list()->length(); 56 list()->AddBlock(NULL, capacity - list()->capacity()); 57 list()->Rewind(old_length); 58 return; 59 } 60 PointerList* list = new PointerList(capacity); 61 if ((data_ & kTagMask) == kSingletonTag) { 62 list->Add(single_value()); 63 } 64 ASSERT(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 65 data_ = reinterpret_cast<intptr_t>(list) | kListTag; 66 } 67 68 void Clear() { 69 data_ = kEmptyTag; 70 } 71 72 bool is_empty() const { return length() == 0; } 73 74 int length() const { 75 if ((data_ & kTagMask) == kEmptyTag) return 0; 76 if ((data_ & kTagMask) == kSingletonTag) return 1; 77 return list()->length(); 78 } 79 80 void Add(T* pointer) { 81 ASSERT(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment)); 82 if ((data_ & kTagMask) == kEmptyTag) { 83 data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag; 84 return; 85 } 86 if ((data_ & kTagMask) == kSingletonTag) { 87 PointerList* list = new PointerList(2); 88 list->Add(single_value()); 89 list->Add(pointer); 90 ASSERT(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 91 data_ = reinterpret_cast<intptr_t>(list) | kListTag; 92 return; 93 } 94 list()->Add(pointer); 95 } 96 97 // Note: returns T* and not T*& (unlike List from list.h). 98 // This makes the implementation simpler and more const correct. 99 T* at(int i) const { 100 ASSERT((data_ & kTagMask) != kEmptyTag); 101 if ((data_ & kTagMask) == kSingletonTag) { 102 ASSERT(i == 0); 103 return single_value(); 104 } 105 return list()->at(i); 106 } 107 108 // See the note above. 109 T* operator[](int i) const { return at(i); } 110 111 // Remove the given element from the list (if present). 112 void RemoveElement(T* pointer) { 113 if ((data_ & kTagMask) == kEmptyTag) return; 114 if ((data_ & kTagMask) == kSingletonTag) { 115 if (pointer == single_value()) { 116 data_ = kEmptyTag; 117 } 118 return; 119 } 120 list()->RemoveElement(pointer); 121 } 122 123 T* RemoveLast() { 124 ASSERT((data_ & kTagMask) != kEmptyTag); 125 if ((data_ & kTagMask) == kSingletonTag) { 126 T* result = single_value(); 127 data_ = kEmptyTag; 128 return result; 129 } 130 return list()->RemoveLast(); 131 } 132 133 void Rewind(int pos) { 134 if ((data_ & kTagMask) == kEmptyTag) { 135 ASSERT(pos == 0); 136 return; 137 } 138 if ((data_ & kTagMask) == kSingletonTag) { 139 ASSERT(pos == 0 || pos == 1); 140 if (pos == 0) { 141 data_ = kEmptyTag; 142 } 143 return; 144 } 145 list()->Rewind(pos); 146 } 147 148 int CountOccurrences(T* pointer, int start, int end) const { 149 if ((data_ & kTagMask) == kEmptyTag) return 0; 150 if ((data_ & kTagMask) == kSingletonTag) { 151 if (start == 0 && end >= 0) { 152 return (single_value() == pointer) ? 1 : 0; 153 } 154 return 0; 155 } 156 return list()->CountOccurrences(pointer, start, end); 157 } 158 159 private: 160 typedef ZoneList<T*> PointerList; 161 162 static const intptr_t kEmptyTag = 1; 163 static const intptr_t kSingletonTag = 0; 164 static const intptr_t kListTag = 2; 165 static const intptr_t kTagMask = 3; 166 static const intptr_t kValueMask = ~kTagMask; 167 168 STATIC_ASSERT(kTagMask + 1 <= kPointerAlignment); 169 170 T* single_value() const { 171 ASSERT((data_ & kTagMask) == kSingletonTag); 172 STATIC_ASSERT(kSingletonTag == 0); 173 return reinterpret_cast<T*>(data_); 174 } 175 176 PointerList* list() const { 177 ASSERT((data_ & kTagMask) == kListTag); 178 return reinterpret_cast<PointerList*>(data_ & kValueMask); 179 } 180 181 intptr_t data_; 182 183 DISALLOW_COPY_AND_ASSIGN(SmallPointerList); 184 }; 185 186 } } // namespace v8::internal 187 188 #endif // V8_SMALL_POINTER_LIST_H_ 189
