small-pointer-list.h 4.71 KB
Newer Older
1
// Copyright 2011 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

#ifndef V8_SMALL_POINTER_LIST_H_
#define V8_SMALL_POINTER_LIST_H_

8
#include "src/base/logging.h"
9
#include "src/globals.h"
10
#include "src/zone/zone.h"
11 12 13 14 15 16 17 18 19 20 21 22 23

namespace v8 {
namespace internal {

// SmallPointerList is a list optimized for storing no or just a
// single value. When more values are given it falls back to ZoneList.
//
// The interface tries to be as close to List from list.h as possible.
template <typename T>
class SmallPointerList {
 public:
  SmallPointerList() : data_(kEmptyTag) {}

24 25
  SmallPointerList(int capacity, Zone* zone) : data_(kEmptyTag) {
    Reserve(capacity, zone);
26 27
  }

28
  void Reserve(int capacity, Zone* zone) {
29 30 31 32
    if (capacity < 2) return;
    if ((data_ & kTagMask) == kListTag) {
      if (list()->capacity() >= capacity) return;
      int old_length = list()->length();
33
      list()->AddBlock(NULL, capacity - list()->capacity(), zone);
34 35 36
      list()->Rewind(old_length);
      return;
    }
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 43 44 45 46 47 48
    data_ = reinterpret_cast<intptr_t>(list) | kListTag;
  }

  void Clear() {
    data_ = kEmptyTag;
  }

49 50 51 52 53 54
  void Sort() {
    if ((data_ & kTagMask) == kListTag) {
      list()->Sort(compare_value);
    }
  }

55 56 57 58 59 60 61 62
  bool is_empty() const { return length() == 0; }

  int length() const {
    if ((data_ & kTagMask) == kEmptyTag) return 0;
    if ((data_ & kTagMask) == kSingletonTag) return 1;
    return list()->length();
  }

63
  void Add(T* pointer, Zone* zone) {
64
    DCHECK(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment));
65 66 67 68 69
    if ((data_ & kTagMask) == kEmptyTag) {
      data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag;
      return;
    }
    if ((data_ & kTagMask) == kSingletonTag) {
70 71 72
      PointerList* list = new(zone) PointerList(2, zone);
      list->Add(single_value(), zone);
      list->Add(pointer, zone);
73
      DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment));
74 75 76
      data_ = reinterpret_cast<intptr_t>(list) | kListTag;
      return;
    }
77
    list()->Add(pointer, zone);
78 79 80 81 82
  }

  // Note: returns T* and not T*& (unlike List from list.h).
  // This makes the implementation simpler and more const correct.
  T* at(int i) const {
83
    DCHECK((data_ & kTagMask) != kEmptyTag);
84
    if ((data_ & kTagMask) == kSingletonTag) {
85
      DCHECK(i == 0);
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
      return single_value();
    }
    return list()->at(i);
  }

  // See the note above.
  T* operator[](int i) const { return at(i); }

  // Remove the given element from the list (if present).
  void RemoveElement(T* pointer) {
    if ((data_ & kTagMask) == kEmptyTag) return;
    if ((data_ & kTagMask) == kSingletonTag) {
      if (pointer == single_value()) {
        data_ = kEmptyTag;
      }
      return;
    }
    list()->RemoveElement(pointer);
  }

  T* RemoveLast() {
107
    DCHECK((data_ & kTagMask) != kEmptyTag);
108 109 110 111 112 113 114 115 116 117
    if ((data_ & kTagMask) == kSingletonTag) {
      T* result = single_value();
      data_ = kEmptyTag;
      return result;
    }
    return list()->RemoveLast();
  }

  void Rewind(int pos) {
    if ((data_ & kTagMask) == kEmptyTag) {
118
      DCHECK(pos == 0);
119 120 121
      return;
    }
    if ((data_ & kTagMask) == kSingletonTag) {
122
      DCHECK(pos == 0 || pos == 1);
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
      if (pos == 0) {
        data_ = kEmptyTag;
      }
      return;
    }
    list()->Rewind(pos);
  }

  int CountOccurrences(T* pointer, int start, int end) const {
    if ((data_ & kTagMask) == kEmptyTag) return 0;
    if ((data_ & kTagMask) == kSingletonTag) {
      if (start == 0 && end >= 0) {
        return (single_value() == pointer) ? 1 : 0;
      }
      return 0;
    }
    return list()->CountOccurrences(pointer, start, end);
  }

 private:
  typedef ZoneList<T*> PointerList;

145 146 147 148
  static int compare_value(T* const* a, T* const* b) {
    return Compare<T>(**a, **b);
  }

149 150 151 152 153 154 155 156 157
  static const intptr_t kEmptyTag = 1;
  static const intptr_t kSingletonTag = 0;
  static const intptr_t kListTag = 2;
  static const intptr_t kTagMask = 3;
  static const intptr_t kValueMask = ~kTagMask;

  STATIC_ASSERT(kTagMask + 1 <= kPointerAlignment);

  T* single_value() const {
158
    DCHECK((data_ & kTagMask) == kSingletonTag);
159 160 161 162 163
    STATIC_ASSERT(kSingletonTag == 0);
    return reinterpret_cast<T*>(data_);
  }

  PointerList* list() const {
164
    DCHECK((data_ & kTagMask) == kListTag);
165 166 167 168 169 170 171 172
    return reinterpret_cast<PointerList*>(data_ & kValueMask);
  }

  intptr_t data_;

  DISALLOW_COPY_AND_ASSIGN(SmallPointerList);
};

173 174
}  // namespace internal
}  // namespace v8
175 176

#endif  // V8_SMALL_POINTER_LIST_H_