• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
SmallPointerList(int capacity)47   explicit SmallPointerList(int capacity) : data_(kEmptyTag) {
48     Reserve(capacity);
49   }
50 
Reserve(int capacity)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 
Clear()68   void Clear() {
69     data_ = kEmptyTag;
70   }
71 
is_empty()72   bool is_empty() const { return length() == 0; }
73 
length()74   int length() const {
75     if ((data_ & kTagMask) == kEmptyTag) return 0;
76     if ((data_ & kTagMask) == kSingletonTag) return 1;
77     return list()->length();
78   }
79 
Add(T * pointer)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.
at(int i)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).
RemoveElement(T * pointer)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 
RemoveLast()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 
Rewind(int pos)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 
CountOccurrences(T * pointer,int start,int end)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 
single_value()170   T* single_value() const {
171     ASSERT((data_ & kTagMask) == kSingletonTag);
172     STATIC_ASSERT(kSingletonTag == 0);
173     return reinterpret_cast<T*>(data_);
174   }
175 
list()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