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: SmallPointerList()45 SmallPointerList() : data_(kEmptyTag) {} 46 is_empty()47 bool is_empty() const { return length() == 0; } 48 length()49 int length() const { 50 if ((data_ & kTagMask) == kEmptyTag) return 0; 51 if ((data_ & kTagMask) == kSingletonTag) return 1; 52 return list()->length(); 53 } 54 Add(T * pointer)55 void Add(T* pointer) { 56 ASSERT(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment)); 57 if ((data_ & kTagMask) == kEmptyTag) { 58 data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag; 59 return; 60 } 61 if ((data_ & kTagMask) == kSingletonTag) { 62 PointerList* list = new PointerList(2); 63 list->Add(single_value()); 64 list->Add(pointer); 65 ASSERT(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 66 data_ = reinterpret_cast<intptr_t>(list) | kListTag; 67 return; 68 } 69 list()->Add(pointer); 70 } 71 72 // Note: returns T* and not T*& (unlike List from list.h). 73 // This makes the implementation simpler and more const correct. at(int i)74 T* at(int i) const { 75 ASSERT((data_ & kTagMask) != kEmptyTag); 76 if ((data_ & kTagMask) == kSingletonTag) { 77 ASSERT(i == 0); 78 return single_value(); 79 } 80 return list()->at(i); 81 } 82 83 // See the note above. 84 T* operator[](int i) const { return at(i); } 85 86 // Remove the given element from the list (if present). RemoveElement(T * pointer)87 void RemoveElement(T* pointer) { 88 if ((data_ & kTagMask) == kEmptyTag) return; 89 if ((data_ & kTagMask) == kSingletonTag) { 90 if (pointer == single_value()) { 91 data_ = kEmptyTag; 92 } 93 return; 94 } 95 list()->RemoveElement(pointer); 96 } 97 RemoveLast()98 T* RemoveLast() { 99 ASSERT((data_ & kTagMask) != kEmptyTag); 100 if ((data_ & kTagMask) == kSingletonTag) { 101 T* result = single_value(); 102 data_ = kEmptyTag; 103 return result; 104 } 105 return list()->RemoveLast(); 106 } 107 Rewind(int pos)108 void Rewind(int pos) { 109 if ((data_ & kTagMask) == kEmptyTag) { 110 ASSERT(pos == 0); 111 return; 112 } 113 if ((data_ & kTagMask) == kSingletonTag) { 114 ASSERT(pos == 0 || pos == 1); 115 if (pos == 0) { 116 data_ = kEmptyTag; 117 } 118 return; 119 } 120 list()->Rewind(pos); 121 } 122 CountOccurrences(T * pointer,int start,int end)123 int CountOccurrences(T* pointer, int start, int end) const { 124 if ((data_ & kTagMask) == kEmptyTag) return 0; 125 if ((data_ & kTagMask) == kSingletonTag) { 126 if (start == 0 && end >= 0) { 127 return (single_value() == pointer) ? 1 : 0; 128 } 129 return 0; 130 } 131 return list()->CountOccurrences(pointer, start, end); 132 } 133 134 private: 135 typedef ZoneList<T*> PointerList; 136 137 static const intptr_t kEmptyTag = 1; 138 static const intptr_t kSingletonTag = 0; 139 static const intptr_t kListTag = 2; 140 static const intptr_t kTagMask = 3; 141 static const intptr_t kValueMask = ~kTagMask; 142 143 STATIC_ASSERT(kTagMask + 1 <= kPointerAlignment); 144 single_value()145 T* single_value() const { 146 ASSERT((data_ & kTagMask) == kSingletonTag); 147 STATIC_ASSERT(kSingletonTag == 0); 148 return reinterpret_cast<T*>(data_); 149 } 150 list()151 PointerList* list() const { 152 ASSERT((data_ & kTagMask) == kListTag); 153 return reinterpret_cast<PointerList*>(data_ & kValueMask); 154 } 155 156 intptr_t data_; 157 158 DISALLOW_COPY_AND_ASSIGN(SmallPointerList); 159 }; 160 161 } } // namespace v8::internal 162 163 #endif // V8_SMALL_POINTER_LIST_H_ 164