1 // Copyright 2011 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_SMALL_POINTER_LIST_H_ 6 #define V8_SMALL_POINTER_LIST_H_ 7 8 #include "src/base/logging.h" 9 #include "src/globals.h" 10 #include "src/zone/zone.h" 11 12 namespace v8 { 13 namespace internal { 14 15 // SmallPointerList is a list optimized for storing no or just a 16 // single value. When more values are given it falls back to ZoneList. 17 // 18 // The interface tries to be as close to List from list.h as possible. 19 template <typename T> 20 class SmallPointerList { 21 public: 22 SmallPointerList() : data_(kEmptyTag) {} 23 24 SmallPointerList(int capacity, Zone* zone) : data_(kEmptyTag) { 25 Reserve(capacity, zone); 26 } 27 28 void Reserve(int capacity, Zone* zone) { 29 if (capacity < 2) return; 30 if ((data_ & kTagMask) == kListTag) { 31 if (list()->capacity() >= capacity) return; 32 int old_length = list()->length(); 33 list()->AddBlock(NULL, capacity - list()->capacity(), zone); 34 list()->Rewind(old_length); 35 return; 36 } 37 PointerList* list = new(zone) PointerList(capacity, zone); 38 if ((data_ & kTagMask) == kSingletonTag) { 39 list->Add(single_value(), zone); 40 } 41 DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 42 data_ = reinterpret_cast<intptr_t>(list) | kListTag; 43 } 44 45 void Clear() { 46 data_ = kEmptyTag; 47 } 48 49 void Sort() { 50 if ((data_ & kTagMask) == kListTag) { 51 list()->Sort(compare_value); 52 } 53 } 54 55 bool is_empty() const { return length() == 0; } 56 57 int length() const { 58 if ((data_ & kTagMask) == kEmptyTag) return 0; 59 if ((data_ & kTagMask) == kSingletonTag) return 1; 60 return list()->length(); 61 } 62 63 void Add(T* pointer, Zone* zone) { 64 DCHECK(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment)); 65 if ((data_ & kTagMask) == kEmptyTag) { 66 data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag; 67 return; 68 } 69 if ((data_ & kTagMask) == kSingletonTag) { 70 PointerList* list = new(zone) PointerList(2, zone); 71 list->Add(single_value(), zone); 72 list->Add(pointer, zone); 73 DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 74 data_ = reinterpret_cast<intptr_t>(list) | kListTag; 75 return; 76 } 77 list()->Add(pointer, zone); 78 } 79 80 // Note: returns T* and not T*& (unlike List from list.h). 81 // This makes the implementation simpler and more const correct. 82 T* at(int i) const { 83 DCHECK((data_ & kTagMask) != kEmptyTag); 84 if ((data_ & kTagMask) == kSingletonTag) { 85 DCHECK(i == 0); 86 return single_value(); 87 } 88 return list()->at(i); 89 } 90 91 // See the note above. 92 T* operator[](int i) const { return at(i); } 93 94 // Remove the given element from the list (if present). 95 void RemoveElement(T* pointer) { 96 if ((data_ & kTagMask) == kEmptyTag) return; 97 if ((data_ & kTagMask) == kSingletonTag) { 98 if (pointer == single_value()) { 99 data_ = kEmptyTag; 100 } 101 return; 102 } 103 list()->RemoveElement(pointer); 104 } 105 106 T* RemoveLast() { 107 DCHECK((data_ & kTagMask) != kEmptyTag); 108 if ((data_ & kTagMask) == kSingletonTag) { 109 T* result = single_value(); 110 data_ = kEmptyTag; 111 return result; 112 } 113 return list()->RemoveLast(); 114 } 115 116 void Rewind(int pos) { 117 if ((data_ & kTagMask) == kEmptyTag) { 118 DCHECK(pos == 0); 119 return; 120 } 121 if ((data_ & kTagMask) == kSingletonTag) { 122 DCHECK(pos == 0 || pos == 1); 123 if (pos == 0) { 124 data_ = kEmptyTag; 125 } 126 return; 127 } 128 list()->Rewind(pos); 129 } 130 131 int CountOccurrences(T* pointer, int start, int end) const { 132 if ((data_ & kTagMask) == kEmptyTag) return 0; 133 if ((data_ & kTagMask) == kSingletonTag) { 134 if (start == 0 && end >= 0) { 135 return (single_value() == pointer) ? 1 : 0; 136 } 137 return 0; 138 } 139 return list()->CountOccurrences(pointer, start, end); 140 } 141 142 private: 143 typedef ZoneList<T*> PointerList; 144 145 static int compare_value(T* const* a, T* const* b) { 146 return Compare<T>(**a, **b); 147 } 148 149 static const intptr_t kEmptyTag = 1; 150 static const intptr_t kSingletonTag = 0; 151 static const intptr_t kListTag = 2; 152 static const intptr_t kTagMask = 3; 153 static const intptr_t kValueMask = ~kTagMask; 154 155 STATIC_ASSERT(kTagMask + 1 <= kPointerAlignment); 156 157 T* single_value() const { 158 DCHECK((data_ & kTagMask) == kSingletonTag); 159 STATIC_ASSERT(kSingletonTag == 0); 160 return reinterpret_cast<T*>(data_); 161 } 162 163 PointerList* list() const { 164 DCHECK((data_ & kTagMask) == kListTag); 165 return reinterpret_cast<PointerList*>(data_ & kValueMask); 166 } 167 168 intptr_t data_; 169 170 DISALLOW_COPY_AND_ASSIGN(SmallPointerList); 171 }; 172 173 } // namespace internal 174 } // namespace v8 175 176 #endif // V8_SMALL_POINTER_LIST_H_ 177
