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.h"
11
12namespace v8 {
13namespace 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.
19template <typename T>
20class 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 v8::internal
174
175#endif  // V8_SMALL_POINTER_LIST_H_
176