1fb144a0716afe7ab8bf245f2391a9e53b3db3c89fschneider@chromium.org// Copyright 2011 the V8 project authors. All rights reserved. 243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// Redistribution and use in source and binary forms, with or without 343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// modification, are permitted provided that the following conditions are 443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// met: 543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// 643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// * Redistributions of source code must retain the above copyright 743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// notice, this list of conditions and the following disclaimer. 843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// * Redistributions in binary form must reproduce the above 943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// copyright notice, this list of conditions and the following 1043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// disclaimer in the documentation and/or other materials provided 1143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// with the distribution. 1243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// * Neither the name of Google Inc. nor the names of its 1343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// contributors may be used to endorse or promote products derived 1443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// from this software without specific prior written permission. 1543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// 1643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 2843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#ifndef V8_LIST_H_ 2943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#define V8_LIST_H_ 3043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 31fb144a0716afe7ab8bf245f2391a9e53b3db3c89fschneider@chromium.org#include "utils.h" 32fb144a0716afe7ab8bf245f2391a9e53b3db3c89fschneider@chromium.org 3371affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace v8 { 3471affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace internal { 3543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 3643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 3743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// ---------------------------------------------------------------------------- 3843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// The list is a template for very light-weight lists. We are not 3943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// using the STL because we want full control over space and speed of 4043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// the code. This implementation is based on code by Robert Griesemer 4143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// and Rob Pike. 4243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// 4343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// The list is parameterized by the type of its elements (T) and by an 4443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// allocation policy (P). The policy is used for allocating lists in 4543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// the C free store or the zone; see zone.h. 4643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 4743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// Forward defined as 48400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org// template <typename T, 49400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org// class AllocationPolicy = FreeStoreAllocationPolicy> class List; 50400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate <typename T, class AllocationPolicy> 5143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansenclass List { 5243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen public: 53400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org explicit List(AllocationPolicy allocator = AllocationPolicy()) { 54400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(0, allocator); 55400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 56400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(explicit List(int capacity, 57400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy())) { 58400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(capacity, allocator); 59400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 6043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(~List()) { DeleteData(data_); } 6143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 62c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org // Deallocates memory used by the list and leaves the list in a consistent 63c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org // empty state. 64c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org void Free() { 65c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org DeleteData(data_); 66c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org Initialize(0); 67c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org } 68c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org 69400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void* operator new(size_t size, 70400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy())) { 71400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org return allocator.New(static_cast<int>(size)); 72400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 73400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void operator delete(void* p)) { 74400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy::Delete(p); 75c4c927273ae2b690c4a015b4640a2a469c9a1a69ager@chromium.org } 7643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 775a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org // Please the MSVC compiler. We should never have to execute this. 785a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org INLINE(void operator delete(void* p, AllocationPolicy allocator)) { 795a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org UNREACHABLE(); 805a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org } 815a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org 827be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // Returns a reference to the element at index i. This reference is 837be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // not safe to use after operations that can change the list's 842efb900e7350b14be905abdeab077f3a64c583cfulan@chromium.org // backing store (e.g. Add). 854a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org inline T& operator[](int i) const { 86b302e56e5b70c4504faa2adf4ec3efb64a9d3e38sgjesse@chromium.org ASSERT(0 <= i); 87ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.org SLOW_ASSERT(i < length_); 8843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen return data_[i]; 8943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen } 904a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org inline T& at(int i) const { return operator[](i); } 91a1645e29968e70a41226edda2c49788fcea48b74ager@chromium.org inline T& last() const { return at(length_ - 1); } 92a1645e29968e70a41226edda2c49788fcea48b74ager@chromium.org inline T& first() const { return at(0); } 9343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 9443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(bool is_empty() const) { return length_ == 0; } 9543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(int length() const) { return length_; } 9671daaf639544be2a6638e3566f78e0b14f05cd7bager@chromium.org INLINE(int capacity() const) { return capacity_; } 9743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 988e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org Vector<T> ToVector() const { return Vector<T>(data_, length_); } 9943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 100a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Vector<const T> ToConstVector() { return Vector<const T>(data_, length_); } 101a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 10243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Adds a copy of the given 'element' to the end of the list, 10343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // expanding the list if necessary. 104400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void Add(const T& element, AllocationPolicy allocator = AllocationPolicy()); 10543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 10671affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org // Add all the elements from the argument list to this list. 107400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void AddAll(const List<T, AllocationPolicy>& other, 108400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 10971affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org 1108e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org // Add all the elements from the vector to this list. 111400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void AddAll(const Vector<T>& other, 112400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 1138e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org 114a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Inserts the element at the specific index. 115400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void InsertAt(int index, const T& element, 116400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 117a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 11857ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org // Overwrites the element at the specific index. 11957ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org void Set(int index, const T& element); 12057ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org 12143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Added 'count' elements with the value 'value' and returns a 12243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // vector that allows access to the elements. The vector is valid 12343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // until the next change is made to this list. 124400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Vector<T> AddBlock(T value, int count, 125400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 12643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 12743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Removes the i'th element without deleting it even if T is a 12843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // pointer type; moves all elements above i "down". Returns the 1297be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // removed element. This function's complexity is linear in the 1307be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // size of the list. 13143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen T Remove(int i); 13243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 133a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Remove the given element from the list. Returns whether or not 134a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // the input is included in the list in the first place. 135a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool RemoveElement(const T& elm); 136a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 13743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Removes the last element without deleting it even if T is a 13843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // pointer type. Returns the removed element. 13943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(T RemoveLast()) { return Remove(length_ - 1); } 14043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 141212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org // Deletes current list contents and allocates space for 'length' elements. 142400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void Allocate(int length, 143400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy())); 144212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org 14543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Clears the list by setting the length to zero. Even if T is a 14643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // pointer type, clearing the list doesn't delete the entries. 14743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(void Clear()); 14843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 14943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Drops all but the first 'pos' elements from the list. 15043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(void Rewind(int pos)); 15143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 152a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Drop the last 'count' elements from the list. 153a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org INLINE(void RewindBy(int count)) { Rewind(length_ - count); } 154a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 15546a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org // Halve the capacity if fill level is less than a quarter. 15646a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org INLINE(void Trim(AllocationPolicy allocator = AllocationPolicy())); 15746a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org 158a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool Contains(const T& elm) const; 159a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int CountOccurrences(const T& elm, int start, int end) const; 160a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 16143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Iterate through all list entries, starting at index 0. 16243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void Iterate(void (*callback)(T* x)); 16326c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.org template<class Visitor> 16426c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.org void Iterate(Visitor* visitor); 16543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 16643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Sort all list entries (using QuickSort) 16743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void Sort(int (*cmp)(const T* x, const T* y)); 168a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void Sort(); 16943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 170400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void Initialize(int capacity, 171400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy())); 17243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 17343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen private: 17443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen T* data_; 17543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen int capacity_; 17643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen int length_; 17743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 178400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(T* NewData(int n, AllocationPolicy allocator)) { 179400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org return static_cast<T*>(allocator.New(n * sizeof(T))); 180400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 181400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void DeleteData(T* data)) { 182400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy::Delete(data); 183400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 18443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 1855ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // Increase the capacity of a full list, and add an element. 1865ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // List must be full already. 187400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void ResizeAdd(const T& element, AllocationPolicy allocator); 1885ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org 1895ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // Inlined implementation of ResizeAdd, shared by inlined and 1905ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // non-inlined versions of ResizeAdd. 191400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void ResizeAddInternal(const T& element, AllocationPolicy allocator); 1925ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org 19371affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org // Resize the list. 194400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void Resize(int new_capacity, AllocationPolicy allocator); 19571affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org 1969a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com DISALLOW_COPY_AND_ASSIGN(List); 19743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen}; 19843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 199ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org 200ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.orgtemplate<typename T, class P> 201ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.orgsize_t GetMemoryUsedByList(const List<T, P>& list) { 202ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org return list.length() * sizeof(T) + sizeof(list); 203ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org} 204ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org 205ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org 206ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.orgclass Map; 207af9cfcbed5daf6e636e189bce451c6fafdbb127dmachenbach@chromium.orgclass Type; 208ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.orgclass Code; 209394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.comtemplate<typename T> class Handle; 210ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.orgtypedef List<Map*> MapList; 211ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.orgtypedef List<Code*> CodeList; 212394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.comtypedef List<Handle<Map> > MapHandleList; 213af9cfcbed5daf6e636e189bce451c6fafdbb127dmachenbach@chromium.orgtypedef List<Handle<Type> > TypeHandleList; 214394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.comtypedef List<Handle<Code> > CodeHandleList; 215ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.org 21634e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org// Perform binary search for an element in an already sorted 21734e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org// list. Returns the index of the element of -1 if it was not found. 21828faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org// |cmp| is a predicate that takes a pointer to an element of the List 21928faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org// and returns +1 if it is greater, -1 if it is less than the element 22028faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org// being searched. 22128faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.orgtemplate <typename T, class P> 22228faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.orgint SortedListBSearch(const List<T>& list, P cmp); 22334e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.orgtemplate <typename T> 22434e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.orgint SortedListBSearch(const List<T>& list, T elem); 22534e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 226394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.com 22743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} } // namespace v8::internal 22843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 22934e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 23043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#endif // V8_LIST_H_ 231