Home | History | Annotate | Download | only in src 
      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 
     35 namespace v8 {
     36 namespace 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.
     42 template <typename T>
     43 class 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