17979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org// Copyright 2011 the V8 project authors. All rights reserved. 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// Use of this source code is governed by a BSD-style license that can be 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// found in the LICENSE file. 47979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 57979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org#ifndef V8_SMALL_POINTER_LIST_H_ 67979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org#define V8_SMALL_POINTER_LIST_H_ 77979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 85de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org#include "src/base/logging.h" 9196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/globals.h" 10196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/zone.h" 117979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 127979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.orgnamespace v8 { 137979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.orgnamespace internal { 147979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 157979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org// SmallPointerList is a list optimized for storing no or just a 167979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org// single value. When more values are given it falls back to ZoneList. 177979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org// 187979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org// The interface tries to be as close to List from list.h as possible. 197979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.orgtemplate <typename T> 207979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.orgclass SmallPointerList { 217979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org public: 227979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org SmallPointerList() : data_(kEmptyTag) {} 237979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 247028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org SmallPointerList(int capacity, Zone* zone) : data_(kEmptyTag) { 257028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org Reserve(capacity, zone); 26ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org } 27ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org 287028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org void Reserve(int capacity, Zone* zone) { 29ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org if (capacity < 2) return; 30ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org if ((data_ & kTagMask) == kListTag) { 31ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org if (list()->capacity() >= capacity) return; 32ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org int old_length = list()->length(); 337028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org list()->AddBlock(NULL, capacity - list()->capacity(), zone); 34ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org list()->Rewind(old_length); 35ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org return; 36ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org } 377028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org PointerList* list = new(zone) PointerList(capacity, zone); 38ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org if ((data_ & kTagMask) == kSingletonTag) { 397028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org list->Add(single_value(), zone); 40ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org } 41e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 42ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org data_ = reinterpret_cast<intptr_t>(list) | kListTag; 43ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org } 44ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org 45ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org void Clear() { 46ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org data_ = kEmptyTag; 47ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org } 48ddd545c4c343dcf4331b9d80d2a0bdfa373a4a0fricow@chromium.org 491456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org void Sort() { 501456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org if ((data_ & kTagMask) == kListTag) { 511456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org list()->Sort(compare_value); 521456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org } 531456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org } 541456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org 557979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org bool is_empty() const { return length() == 0; } 567979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 577979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org int length() const { 587979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kEmptyTag) return 0; 597979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kSingletonTag) return 1; 607979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return list()->length(); 617979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 627979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 637028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org void Add(T* pointer, Zone* zone) { 64e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(IsAligned(reinterpret_cast<intptr_t>(pointer), kPointerAlignment)); 657979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kEmptyTag) { 667979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org data_ = reinterpret_cast<intptr_t>(pointer) | kSingletonTag; 677979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return; 687979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 697979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kSingletonTag) { 707028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org PointerList* list = new(zone) PointerList(2, zone); 717028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org list->Add(single_value(), zone); 727028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org list->Add(pointer, zone); 73e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(IsAligned(reinterpret_cast<intptr_t>(list), kPointerAlignment)); 747979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org data_ = reinterpret_cast<intptr_t>(list) | kListTag; 757979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return; 767979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 777028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org list()->Add(pointer, zone); 787979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 797979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 807979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org // Note: returns T* and not T*& (unlike List from list.h). 817979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org // This makes the implementation simpler and more const correct. 827979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org T* at(int i) const { 83e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK((data_ & kTagMask) != kEmptyTag); 847979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kSingletonTag) { 85e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(i == 0); 867979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return single_value(); 877979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 887979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return list()->at(i); 897979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 907979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 917979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org // See the note above. 927979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org T* operator[](int i) const { return at(i); } 937979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 947979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org // Remove the given element from the list (if present). 957979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org void RemoveElement(T* pointer) { 967979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kEmptyTag) return; 977979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kSingletonTag) { 987979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if (pointer == single_value()) { 997979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org data_ = kEmptyTag; 1007979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1017979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return; 1027979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1037979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org list()->RemoveElement(pointer); 1047979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1057979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1067979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org T* RemoveLast() { 107e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK((data_ & kTagMask) != kEmptyTag); 1087979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kSingletonTag) { 1097979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org T* result = single_value(); 1107979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org data_ = kEmptyTag; 1117979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return result; 1127979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1137979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return list()->RemoveLast(); 1147979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1157979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1167979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org void Rewind(int pos) { 1177979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kEmptyTag) { 118e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(pos == 0); 1197979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return; 1207979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1217979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kSingletonTag) { 122e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(pos == 0 || pos == 1); 1237979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if (pos == 0) { 1247979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org data_ = kEmptyTag; 1257979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1267979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return; 1277979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1287979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org list()->Rewind(pos); 1297979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1307979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1317979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org int CountOccurrences(T* pointer, int start, int end) const { 1327979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kEmptyTag) return 0; 1337979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if ((data_ & kTagMask) == kSingletonTag) { 1347979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org if (start == 0 && end >= 0) { 1357979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return (single_value() == pointer) ? 1 : 0; 1367979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1377979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return 0; 1387979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1397979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return list()->CountOccurrences(pointer, start, end); 1407979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1417979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1427979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org private: 1437979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org typedef ZoneList<T*> PointerList; 1447979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1451456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org static int compare_value(T* const* a, T* const* b) { 1461456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org return Compare<T>(**a, **b); 1471456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org } 1481456e708d277e725ca42a03463af16fe471c9210jkummerow@chromium.org 1497979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org static const intptr_t kEmptyTag = 1; 1507979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org static const intptr_t kSingletonTag = 0; 1517979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org static const intptr_t kListTag = 2; 1527979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org static const intptr_t kTagMask = 3; 1537979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org static const intptr_t kValueMask = ~kTagMask; 1547979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1557979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org STATIC_ASSERT(kTagMask + 1 <= kPointerAlignment); 1567979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1577979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org T* single_value() const { 158e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK((data_ & kTagMask) == kSingletonTag); 1597979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org STATIC_ASSERT(kSingletonTag == 0); 1607979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return reinterpret_cast<T*>(data_); 1617979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1627979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1637979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org PointerList* list() const { 164e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK((data_ & kTagMask) == kListTag); 1657979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org return reinterpret_cast<PointerList*>(data_ & kValueMask); 1667979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org } 1677979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1687979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org intptr_t data_; 1697979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1707979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org DISALLOW_COPY_AND_ASSIGN(SmallPointerList); 1717979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org}; 1727979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1737979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org} } // namespace v8::internal 1747979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org 1757979bbb1df2eaff193e85d44c8da1ffa1525b7fcfschneider@chromium.org#endif // V8_SMALL_POINTER_LIST_H_ 176