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
35namespace v8 {
36namespace 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.
42template <typename T>
43class SmallPointerList {
44 public:
45  SmallPointerList() : data_(kEmptyTag) {}
46
47  SmallPointerList(int capacity, Zone* zone) : data_(kEmptyTag) {
48    Reserve(capacity, zone);
49  }
50
51  void Reserve(int capacity, Zone* zone) {
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(), zone);
57      list()->Rewind(old_length);
58      return;
59    }
60    PointerList* list = new(zone) PointerList(capacity, zone);
61    if ((data_ & kTagMask) == kSingletonTag) {
62      list->Add(single_value(), zone);
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  void Sort() {
73    if ((data_ & kTagMask) == kListTag) {
74      list()->Sort(compare_value);
75    }
76  }
77
78  bool is_empty() const { return length() == 0; }
79
80  int length() const {
81    if ((data_ & kTagMask) == kEmptyTag) return 0;
82    if ((data_ & kTagMask) == kSingletonTag) return 1;
83    return list()->length();
84  }
85
86  void Add(T* pointer, Zone* zone) {
87    ASSERT(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment));
88    if ((data_ & kTagMask) == kEmptyTag) {
89      data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag;
90      return;
91    }
92    if ((data_ & kTagMask) == kSingletonTag) {
93      PointerList* list = new(zone) PointerList(2, zone);
94      list->Add(single_value(), zone);
95      list->Add(pointer, zone);
96      ASSERT(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment));
97      data_ = reinterpret_cast<intptr_t>(list) | kListTag;
98      return;
99    }
100    list()->Add(pointer, zone);
101  }
102
103  // Note: returns T* and not T*& (unlike List from list.h).
104  // This makes the implementation simpler and more const correct.
105  T* at(int i) const {
106    ASSERT((data_ & kTagMask) != kEmptyTag);
107    if ((data_ & kTagMask) == kSingletonTag) {
108      ASSERT(i == 0);
109      return single_value();
110    }
111    return list()->at(i);
112  }
113
114  // See the note above.
115  T* operator[](int i) const { return at(i); }
116
117  // Remove the given element from the list (if present).
118  void RemoveElement(T* pointer) {
119    if ((data_ & kTagMask) == kEmptyTag) return;
120    if ((data_ & kTagMask) == kSingletonTag) {
121      if (pointer == single_value()) {
122        data_ = kEmptyTag;
123      }
124      return;
125    }
126    list()->RemoveElement(pointer);
127  }
128
129  T* RemoveLast() {
130    ASSERT((data_ & kTagMask) != kEmptyTag);
131    if ((data_ & kTagMask) == kSingletonTag) {
132      T* result = single_value();
133      data_ = kEmptyTag;
134      return result;
135    }
136    return list()->RemoveLast();
137  }
138
139  void Rewind(int pos) {
140    if ((data_ & kTagMask) == kEmptyTag) {
141      ASSERT(pos == 0);
142      return;
143    }
144    if ((data_ & kTagMask) == kSingletonTag) {
145      ASSERT(pos == 0 || pos == 1);
146      if (pos == 0) {
147        data_ = kEmptyTag;
148      }
149      return;
150    }
151    list()->Rewind(pos);
152  }
153
154  int CountOccurrences(T* pointer, int start, int end) const {
155    if ((data_ & kTagMask) == kEmptyTag) return 0;
156    if ((data_ & kTagMask) == kSingletonTag) {
157      if (start == 0 && end >= 0) {
158        return (single_value() == pointer) ? 1 : 0;
159      }
160      return 0;
161    }
162    return list()->CountOccurrences(pointer, start, end);
163  }
164
165 private:
166  typedef ZoneList<T*> PointerList;
167
168  static int compare_value(T* const* a, T* const* b) {
169    return Compare<T>(**a, **b);
170  }
171
172  static const intptr_t kEmptyTag = 1;
173  static const intptr_t kSingletonTag = 0;
174  static const intptr_t kListTag = 2;
175  static const intptr_t kTagMask = 3;
176  static const intptr_t kValueMask = ~kTagMask;
177
178  STATIC_ASSERT(kTagMask + 1 <= kPointerAlignment);
179
180  T* single_value() const {
181    ASSERT((data_ & kTagMask) == kSingletonTag);
182    STATIC_ASSERT(kSingletonTag == 0);
183    return reinterpret_cast<T*>(data_);
184  }
185
186  PointerList* list() const {
187    ASSERT((data_ & kTagMask) == kListTag);
188    return reinterpret_cast<PointerList*>(data_ & kValueMask);
189  }
190
191  intptr_t data_;
192
193  DISALLOW_COPY_AND_ASSIGN(SmallPointerList);
194};
195
196} }  // namespace v8::internal
197
198#endif  // V8_SMALL_POINTER_LIST_H_
199