144f0eee88ff00398ff7f715fab053374d808c90dSteve Block// Copyright 2011 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 444f0eee88ff00398ff7f715fab053374d808c90dSteve Block 544f0eee88ff00398ff7f715fab053374d808c90dSteve Block#ifndef V8_SMALL_POINTER_LIST_H_ 644f0eee88ff00398ff7f715fab053374d808c90dSteve Block#define V8_SMALL_POINTER_LIST_H_ 744f0eee88ff00398ff7f715fab053374d808c90dSteve Block 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/base/logging.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/globals.h" 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/zone.h" 1144f0eee88ff00398ff7f715fab053374d808c90dSteve Block 1244f0eee88ff00398ff7f715fab053374d808c90dSteve Blocknamespace v8 { 1344f0eee88ff00398ff7f715fab053374d808c90dSteve Blocknamespace internal { 1444f0eee88ff00398ff7f715fab053374d808c90dSteve Block 1544f0eee88ff00398ff7f715fab053374d808c90dSteve Block// SmallPointerList is a list optimized for storing no or just a 1644f0eee88ff00398ff7f715fab053374d808c90dSteve Block// single value. When more values are given it falls back to ZoneList. 1744f0eee88ff00398ff7f715fab053374d808c90dSteve Block// 1844f0eee88ff00398ff7f715fab053374d808c90dSteve Block// The interface tries to be as close to List from list.h as possible. 1944f0eee88ff00398ff7f715fab053374d808c90dSteve Blocktemplate <typename T> 2044f0eee88ff00398ff7f715fab053374d808c90dSteve Blockclass SmallPointerList { 2144f0eee88ff00398ff7f715fab053374d808c90dSteve Block public: 2244f0eee88ff00398ff7f715fab053374d808c90dSteve Block SmallPointerList() : data_(kEmptyTag) {} 2344f0eee88ff00398ff7f715fab053374d808c90dSteve Block 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SmallPointerList(int capacity, Zone* zone) : data_(kEmptyTag) { 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Reserve(capacity, zone); 2669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 2769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Reserve(int capacity, Zone* zone) { 2969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch if (capacity < 2) return; 3069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch if ((data_ & kTagMask) == kListTag) { 3169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch if (list()->capacity() >= capacity) return; 3269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch int old_length = list()->length(); 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list()->AddBlock(NULL, capacity - list()->capacity(), zone); 3469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch list()->Rewind(old_length); 3569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch return; 3669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PointerList* list = new(zone) PointerList(capacity, zone); 3869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch if ((data_ & kTagMask) == kSingletonTag) { 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list->Add(single_value(), zone); 4069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 4269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch data_ = reinterpret_cast<intptr_t>(list) | kListTag; 4369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 4469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 4569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch void Clear() { 4669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch data_ = kEmptyTag; 4769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 4869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Sort() { 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if ((data_ & kTagMask) == kListTag) { 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list()->Sort(compare_value); 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5544f0eee88ff00398ff7f715fab053374d808c90dSteve Block bool is_empty() const { return length() == 0; } 5644f0eee88ff00398ff7f715fab053374d808c90dSteve Block 5744f0eee88ff00398ff7f715fab053374d808c90dSteve Block int length() const { 5844f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kEmptyTag) return 0; 5944f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kSingletonTag) return 1; 6044f0eee88ff00398ff7f715fab053374d808c90dSteve Block return list()->length(); 6144f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 6244f0eee88ff00398ff7f715fab053374d808c90dSteve Block 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Add(T* pointer, Zone* zone) { 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment)); 6544f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kEmptyTag) { 6644f0eee88ff00398ff7f715fab053374d808c90dSteve Block data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag; 6744f0eee88ff00398ff7f715fab053374d808c90dSteve Block return; 6844f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 6944f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kSingletonTag) { 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PointerList* list = new(zone) PointerList(2, zone); 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list->Add(single_value(), zone); 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list->Add(pointer, zone); 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 7444f0eee88ff00398ff7f715fab053374d808c90dSteve Block data_ = reinterpret_cast<intptr_t>(list) | kListTag; 7544f0eee88ff00398ff7f715fab053374d808c90dSteve Block return; 7644f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list()->Add(pointer, zone); 7844f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 7944f0eee88ff00398ff7f715fab053374d808c90dSteve Block 8044f0eee88ff00398ff7f715fab053374d808c90dSteve Block // Note: returns T* and not T*& (unlike List from list.h). 8144f0eee88ff00398ff7f715fab053374d808c90dSteve Block // This makes the implementation simpler and more const correct. 8244f0eee88ff00398ff7f715fab053374d808c90dSteve Block T* at(int i) const { 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK((data_ & kTagMask) != kEmptyTag); 8444f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kSingletonTag) { 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(i == 0); 8644f0eee88ff00398ff7f715fab053374d808c90dSteve Block return single_value(); 8744f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 8844f0eee88ff00398ff7f715fab053374d808c90dSteve Block return list()->at(i); 8944f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 9044f0eee88ff00398ff7f715fab053374d808c90dSteve Block 9144f0eee88ff00398ff7f715fab053374d808c90dSteve Block // See the note above. 9244f0eee88ff00398ff7f715fab053374d808c90dSteve Block T* operator[](int i) const { return at(i); } 9344f0eee88ff00398ff7f715fab053374d808c90dSteve Block 9444f0eee88ff00398ff7f715fab053374d808c90dSteve Block // Remove the given element from the list (if present). 9544f0eee88ff00398ff7f715fab053374d808c90dSteve Block void RemoveElement(T* pointer) { 9644f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kEmptyTag) return; 9744f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kSingletonTag) { 9844f0eee88ff00398ff7f715fab053374d808c90dSteve Block if (pointer == single_value()) { 9944f0eee88ff00398ff7f715fab053374d808c90dSteve Block data_ = kEmptyTag; 10044f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 10144f0eee88ff00398ff7f715fab053374d808c90dSteve Block return; 10244f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 10344f0eee88ff00398ff7f715fab053374d808c90dSteve Block list()->RemoveElement(pointer); 10444f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 10544f0eee88ff00398ff7f715fab053374d808c90dSteve Block 10644f0eee88ff00398ff7f715fab053374d808c90dSteve Block T* RemoveLast() { 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK((data_ & kTagMask) != kEmptyTag); 10844f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kSingletonTag) { 10944f0eee88ff00398ff7f715fab053374d808c90dSteve Block T* result = single_value(); 11044f0eee88ff00398ff7f715fab053374d808c90dSteve Block data_ = kEmptyTag; 11144f0eee88ff00398ff7f715fab053374d808c90dSteve Block return result; 11244f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 11344f0eee88ff00398ff7f715fab053374d808c90dSteve Block return list()->RemoveLast(); 11444f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 11544f0eee88ff00398ff7f715fab053374d808c90dSteve Block 11644f0eee88ff00398ff7f715fab053374d808c90dSteve Block void Rewind(int pos) { 11744f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kEmptyTag) { 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos == 0); 11944f0eee88ff00398ff7f715fab053374d808c90dSteve Block return; 12044f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 12144f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kSingletonTag) { 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(pos == 0 || pos == 1); 12344f0eee88ff00398ff7f715fab053374d808c90dSteve Block if (pos == 0) { 12444f0eee88ff00398ff7f715fab053374d808c90dSteve Block data_ = kEmptyTag; 12544f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 12644f0eee88ff00398ff7f715fab053374d808c90dSteve Block return; 12744f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 12844f0eee88ff00398ff7f715fab053374d808c90dSteve Block list()->Rewind(pos); 12944f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 13044f0eee88ff00398ff7f715fab053374d808c90dSteve Block 13144f0eee88ff00398ff7f715fab053374d808c90dSteve Block int CountOccurrences(T* pointer, int start, int end) const { 13244f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kEmptyTag) return 0; 13344f0eee88ff00398ff7f715fab053374d808c90dSteve Block if ((data_ & kTagMask) == kSingletonTag) { 13444f0eee88ff00398ff7f715fab053374d808c90dSteve Block if (start == 0 && end >= 0) { 13544f0eee88ff00398ff7f715fab053374d808c90dSteve Block return (single_value() == pointer) ? 1 : 0; 13644f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 13744f0eee88ff00398ff7f715fab053374d808c90dSteve Block return 0; 13844f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 13944f0eee88ff00398ff7f715fab053374d808c90dSteve Block return list()->CountOccurrences(pointer, start, end); 14044f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 14144f0eee88ff00398ff7f715fab053374d808c90dSteve Block 14244f0eee88ff00398ff7f715fab053374d808c90dSteve Block private: 14344f0eee88ff00398ff7f715fab053374d808c90dSteve Block typedef ZoneList<T*> PointerList; 14444f0eee88ff00398ff7f715fab053374d808c90dSteve Block 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static int compare_value(T* const* a, T* const* b) { 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Compare<T>(**a, **b); 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 14944f0eee88ff00398ff7f715fab053374d808c90dSteve Block static const intptr_t kEmptyTag = 1; 15044f0eee88ff00398ff7f715fab053374d808c90dSteve Block static const intptr_t kSingletonTag = 0; 15144f0eee88ff00398ff7f715fab053374d808c90dSteve Block static const intptr_t kListTag = 2; 15244f0eee88ff00398ff7f715fab053374d808c90dSteve Block static const intptr_t kTagMask = 3; 15344f0eee88ff00398ff7f715fab053374d808c90dSteve Block static const intptr_t kValueMask = ~kTagMask; 15444f0eee88ff00398ff7f715fab053374d808c90dSteve Block 15544f0eee88ff00398ff7f715fab053374d808c90dSteve Block STATIC_ASSERT(kTagMask + 1 <= kPointerAlignment); 15644f0eee88ff00398ff7f715fab053374d808c90dSteve Block 15744f0eee88ff00398ff7f715fab053374d808c90dSteve Block T* single_value() const { 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK((data_ & kTagMask) == kSingletonTag); 15944f0eee88ff00398ff7f715fab053374d808c90dSteve Block STATIC_ASSERT(kSingletonTag == 0); 16044f0eee88ff00398ff7f715fab053374d808c90dSteve Block return reinterpret_cast<T*>(data_); 16144f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 16244f0eee88ff00398ff7f715fab053374d808c90dSteve Block 16344f0eee88ff00398ff7f715fab053374d808c90dSteve Block PointerList* list() const { 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK((data_ & kTagMask) == kListTag); 16544f0eee88ff00398ff7f715fab053374d808c90dSteve Block return reinterpret_cast<PointerList*>(data_ & kValueMask); 16644f0eee88ff00398ff7f715fab053374d808c90dSteve Block } 16744f0eee88ff00398ff7f715fab053374d808c90dSteve Block 16844f0eee88ff00398ff7f715fab053374d808c90dSteve Block intptr_t data_; 16944f0eee88ff00398ff7f715fab053374d808c90dSteve Block 17044f0eee88ff00398ff7f715fab053374d808c90dSteve Block DISALLOW_COPY_AND_ASSIGN(SmallPointerList); 17144f0eee88ff00398ff7f715fab053374d808c90dSteve Block}; 17244f0eee88ff00398ff7f715fab053374d808c90dSteve Block 173014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 174014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 17544f0eee88ff00398ff7f715fab053374d808c90dSteve Block 17644f0eee88ff00398ff7f715fab053374d808c90dSteve Block#endif // V8_SMALL_POINTER_LIST_H_ 177