LCOV - code coverage report
Current view: top level - src - small-pointer-list.h (source / functions) Hit Total Coverage
Test: app.info Lines: 36 39 92.3 %
Date: 2017-04-26 Functions: 5 5 100.0 %

          Line data    Source code
       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/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    56614223 :   SmallPointerList() : data_(kEmptyTag) {}
      23             : 
      24        3308 :   SmallPointerList(int capacity, Zone* zone) : data_(kEmptyTag) {
      25        3308 :     Reserve(capacity, zone);
      26             :   }
      27             : 
      28      179173 :   void Reserve(int capacity, Zone* zone) {
      29      179173 :     if (capacity < 2) return;
      30       15768 :     if ((data_ & kTagMask) == kListTag) {
      31           0 :       if (list()->capacity() >= capacity) return;
      32           0 :       int old_length = list()->length();
      33           0 :       list()->AddBlock(NULL, capacity - list()->capacity(), zone);
      34             :       list()->Rewind(old_length);
      35             :       return;
      36             :     }
      37       15768 :     PointerList* list = new(zone) PointerList(capacity, zone);
      38       15768 :     if ((data_ & kTagMask) == kSingletonTag) {
      39             :       list->Add(single_value(), zone);
      40             :     }
      41             :     DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment));
      42       15768 :     data_ = reinterpret_cast<intptr_t>(list) | kListTag;
      43             :   }
      44             : 
      45             :   void Clear() {
      46      550524 :     data_ = kEmptyTag;
      47             :   }
      48             : 
      49          89 :   void Sort() {
      50          89 :     if ((data_ & kTagMask) == kListTag) {
      51             :       list()->Sort(compare_value);
      52             :     }
      53          89 :   }
      54             : 
      55             :   bool is_empty() const { return length() == 0; }
      56             : 
      57             :   int length() const {
      58     4396427 :     if ((data_ & kTagMask) == kEmptyTag) return 0;
      59     2855515 :     if ((data_ & kTagMask) == kSingletonTag) return 1;
      60      291726 :     return list()->length();
      61             :   }
      62             : 
      63      270663 :   void Add(T* pointer, Zone* zone) {
      64             :     DCHECK(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment));
      65      270663 :     if ((data_ & kTagMask) == kEmptyTag) {
      66      234431 :       data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag;
      67      234431 :       return;
      68             :     }
      69       36232 :     if ((data_ & kTagMask) == kSingletonTag) {
      70           5 :       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           5 :       data_ = reinterpret_cast<intptr_t>(list) | kListTag;
      75           5 :       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     1821057 :     if ((data_ & kTagMask) == kSingletonTag) {
      85             :       DCHECK(i == 0);
      86             :       return single_value();
      87             :     }
      88      152741 :     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        1210 :   void RemoveElement(T* pointer) {
      96        1210 :     if ((data_ & kTagMask) == kEmptyTag) return;
      97        1210 :     if ((data_ & kTagMask) == kSingletonTag) {
      98         658 :       if (pointer == single_value()) {
      99         658 :         data_ = kEmptyTag;
     100             :       }
     101             :       return;
     102             :     }
     103         552 :     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           5 :   static int compare_value(T* const* a, T* const* b) {
     146          10 :     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     1668979 :     return reinterpret_cast<T*>(data_);
     161             :   }
     162             : 
     163             :   PointerList* list() const {
     164             :     DCHECK((data_ & kTagMask) == kListTag);
     165      481251 :     return reinterpret_cast<PointerList*>(data_ & kValueMask);
     166             :   }
     167             : 
     168             :   intptr_t data_;
     169             : 
     170             :   DISALLOW_COPY_AND_ASSIGN(SmallPointerList);
     171             : };
     172             : 
     173             : }  // namespace internal
     174             : }  // namespace v8
     175             : 
     176             : #endif  // V8_SMALL_POINTER_LIST_H_

Generated by: LCOV version 1.10