Line data Source code
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 56614223 : SmallPointerList() : data_(kEmptyTag) {}
23 :
24 3308 : SmallPointerList(int capacity, Zone* zone) : data_(kEmptyTag) {
25 3308 : Reserve(capacity, zone);
26 : }
27 :
28 179173 : void Reserve(int capacity, Zone* zone) {
29 179173 : if (capacity < 2) return;
30 15768 : if ((data_ & kTagMask) == kListTag) {
31 0 : if (list()->capacity() >= capacity) return;
32 0 : int old_length = list()->length();
33 0 : list()->AddBlock(NULL, capacity - list()->capacity(), zone);
34 : list()->Rewind(old_length);
35 : return;
36 : }
37 15768 : PointerList* list = new(zone) PointerList(capacity, zone);
38 15768 : if ((data_ & kTagMask) == kSingletonTag) {
39 : list->Add(single_value(), zone);
40 : }
41 : DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment));
42 15768 : data_ = reinterpret_cast<intptr_t>(list) | kListTag;
43 : }
44 :
45 : void Clear() {
46 550524 : data_ = kEmptyTag;
47 : }
48 :
49 89 : void Sort() {
50 89 : if ((data_ & kTagMask) == kListTag) {
51 : list()->Sort(compare_value);
52 : }
53 89 : }
54 :
55 : bool is_empty() const { return length() == 0; }
56 :
57 : int length() const {
58 4396427 : if ((data_ & kTagMask) == kEmptyTag) return 0;
59 2855515 : if ((data_ & kTagMask) == kSingletonTag) return 1;
60 291726 : return list()->length();
61 : }
62 :
63 270663 : void Add(T* pointer, Zone* zone) {
64 : DCHECK(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment));
65 270663 : if ((data_ & kTagMask) == kEmptyTag) {
66 234431 : data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag;
67 234431 : return;
68 : }
69 36232 : if ((data_ & kTagMask) == kSingletonTag) {
70 5 : 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 5 : data_ = reinterpret_cast<intptr_t>(list) | kListTag;
75 5 : 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 1821057 : if ((data_ & kTagMask) == kSingletonTag) {
85 : DCHECK(i == 0);
86 : return single_value();
87 : }
88 152741 : 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 1210 : void RemoveElement(T* pointer) {
96 1210 : if ((data_ & kTagMask) == kEmptyTag) return;
97 1210 : if ((data_ & kTagMask) == kSingletonTag) {
98 658 : if (pointer == single_value()) {
99 658 : data_ = kEmptyTag;
100 : }
101 : return;
102 : }
103 552 : 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 5 : static int compare_value(T* const* a, T* const* b) {
146 10 : 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 1668979 : return reinterpret_cast<T*>(data_);
161 : }
162 :
163 : PointerList* list() const {
164 : DCHECK((data_ & kTagMask) == kListTag);
165 481251 : 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_
|
