src/small-pointer-list.h

   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
  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   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_