1fb144a0716afe7ab8bf245f2391a9e53b3db3c89fschneider@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. 443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#ifndef V8_LIST_H_ 643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#define V8_LIST_H_ 743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 85de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org#include "src/checks.h" 9196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/utils.h" 10fb144a0716afe7ab8bf245f2391a9e53b3db3c89fschneider@chromium.org 1171affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace v8 { 1271affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace internal { 1343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 14196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.orgtemplate<typename T> class Vector; 1543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 1643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// ---------------------------------------------------------------------------- 1743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// The list is a template for very light-weight lists. We are not 1843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// using the STL because we want full control over space and speed of 1943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// the code. This implementation is based on code by Robert Griesemer 2043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// and Rob Pike. 2143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// 2243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// The list is parameterized by the type of its elements (T) and by an 2343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// allocation policy (P). The policy is used for allocating lists in 2443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// the C free store or the zone; see zone.h. 2543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 2643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen// Forward defined as 27400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org// template <typename T, 28400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org// class AllocationPolicy = FreeStoreAllocationPolicy> class List; 29400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgtemplate <typename T, class AllocationPolicy> 3043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansenclass List { 3143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen public: 32400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org explicit List(AllocationPolicy allocator = AllocationPolicy()) { 33400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(0, allocator); 34400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 35400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(explicit List(int capacity, 36400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy())) { 37400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(capacity, allocator); 38400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 3943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(~List()) { DeleteData(data_); } 4043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 41c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org // Deallocates memory used by the list and leaves the list in a consistent 42c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org // empty state. 43c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org void Free() { 44c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org DeleteData(data_); 45c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org Initialize(0); 46c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org } 47c514574143c1bf74d4fb6e7dccb175fe9ff2f5d3sgjesse@chromium.org 48400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void* operator new(size_t size, 49400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy())) { 50400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org return allocator.New(static_cast<int>(size)); 51400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 52400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void operator delete(void* p)) { 53400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy::Delete(p); 54c4c927273ae2b690c4a015b4640a2a469c9a1a69ager@chromium.org } 5543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 565a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org // Please the MSVC compiler. We should never have to execute this. 575a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org INLINE(void operator delete(void* p, AllocationPolicy allocator)) { 585a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org UNREACHABLE(); 595a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org } 605a11aaf63fdb7843c9b116fdb84ee35b0a980ea6yangguo@chromium.org 617be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // Returns a reference to the element at index i. This reference is 627be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // not safe to use after operations that can change the list's 632efb900e7350b14be905abdeab077f3a64c583cfulan@chromium.org // backing store (e.g. Add). 644a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org inline T& operator[](int i) const { 65e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(0 <= i); 66e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org SLOW_DCHECK(i < length_); 6743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen return data_[i]; 6843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen } 694a1fe7d5e92fdb673d5f05d5ddf7b1ed703ba18dwhesse@chromium.org inline T& at(int i) const { return operator[](i); } 70a1645e29968e70a41226edda2c49788fcea48b74ager@chromium.org inline T& last() const { return at(length_ - 1); } 71a1645e29968e70a41226edda2c49788fcea48b74ager@chromium.org inline T& first() const { return at(0); } 7243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 73bb8234d89692f5088ce3fe3ff5a8e8da2f038cfemachenbach@chromium.org typedef T* iterator; 74bb8234d89692f5088ce3fe3ff5a8e8da2f038cfemachenbach@chromium.org inline iterator begin() const { return &data_[0]; } 75bb8234d89692f5088ce3fe3ff5a8e8da2f038cfemachenbach@chromium.org inline iterator end() const { return &data_[length_]; } 76bb8234d89692f5088ce3fe3ff5a8e8da2f038cfemachenbach@chromium.org 7743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(bool is_empty() const) { return length_ == 0; } 7843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(int length() const) { return length_; } 7971daaf639544be2a6638e3566f78e0b14f05cd7bager@chromium.org INLINE(int capacity() const) { return capacity_; } 8043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 818e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org Vector<T> ToVector() const { return Vector<T>(data_, length_); } 8243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 83a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org Vector<const T> ToConstVector() { return Vector<const T>(data_, length_); } 84a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 8543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Adds a copy of the given 'element' to the end of the list, 8643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // expanding the list if necessary. 87400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void Add(const T& element, AllocationPolicy allocator = AllocationPolicy()); 8843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 8971affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org // Add all the elements from the argument list to this list. 90400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void AddAll(const List<T, AllocationPolicy>& other, 91400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 9271affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org 938e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org // Add all the elements from the vector to this list. 94400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void AddAll(const Vector<T>& other, 95400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 968e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org 97a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Inserts the element at the specific index. 98400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void InsertAt(int index, const T& element, 99400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 100a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 10157ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org // Overwrites the element at the specific index. 10257ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org void Set(int index, const T& element); 10357ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org 10443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Added 'count' elements with the value 'value' and returns a 10543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // vector that allows access to the elements. The vector is valid 10643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // until the next change is made to this list. 107400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Vector<T> AddBlock(T value, int count, 108400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy()); 10943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 11043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Removes the i'th element without deleting it even if T is a 11143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // pointer type; moves all elements above i "down". Returns the 1127be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // removed element. This function's complexity is linear in the 1137be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org // size of the list. 11443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen T Remove(int i); 11543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 116a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Remove the given element from the list. Returns whether or not 117a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // the input is included in the list in the first place. 118a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool RemoveElement(const T& elm); 119a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 12043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Removes the last element without deleting it even if T is a 12143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // pointer type. Returns the removed element. 12243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(T RemoveLast()) { return Remove(length_ - 1); } 12343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 124212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org // Deletes current list contents and allocates space for 'length' elements. 125400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void Allocate(int length, 126400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy())); 127212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org 12843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Clears the list by setting the length to zero. Even if T is a 12943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // pointer type, clearing the list doesn't delete the entries. 13043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(void Clear()); 13143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 13243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Drops all but the first 'pos' elements from the list. 13343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen INLINE(void Rewind(int pos)); 13443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 135a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org // Drop the last 'count' elements from the list. 136a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org INLINE(void RewindBy(int count)) { Rewind(length_ - count); } 137a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 13846a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org // Halve the capacity if fill level is less than a quarter. 13946a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org INLINE(void Trim(AllocationPolicy allocator = AllocationPolicy())); 14046a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org 141a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org bool Contains(const T& elm) const; 142a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int CountOccurrences(const T& elm, int start, int end) const; 143a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 14443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Iterate through all list entries, starting at index 0. 14543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void Iterate(void (*callback)(T* x)); 14626c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.org template<class Visitor> 14726c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.org void Iterate(Visitor* visitor); 14843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 14943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen // Sort all list entries (using QuickSort) 15043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen void Sort(int (*cmp)(const T* x, const T* y)); 151a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org void Sort(); 15243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 153400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void Initialize(int capacity, 154400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy allocator = AllocationPolicy())); 15543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 15643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen private: 15743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen T* data_; 15843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen int capacity_; 15943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen int length_; 16043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 161400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(T* NewData(int n, AllocationPolicy allocator)) { 162400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org return static_cast<T*>(allocator.New(n * sizeof(T))); 163400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 164400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org INLINE(void DeleteData(T* data)) { 165400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AllocationPolicy::Delete(data); 166400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org } 16743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 1685ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // Increase the capacity of a full list, and add an element. 1695ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // List must be full already. 170400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void ResizeAdd(const T& element, AllocationPolicy allocator); 1715ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org 1725ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // Inlined implementation of ResizeAdd, shared by inlined and 1735ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // non-inlined versions of ResizeAdd. 174400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void ResizeAddInternal(const T& element, AllocationPolicy allocator); 1755ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org 17671affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org // Resize the list. 177400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org void Resize(int new_capacity, AllocationPolicy allocator); 17871affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org 1799a4089a092cad9ff23b6416b92cd5d818dc101d1mads.s.ager@gmail.com DISALLOW_COPY_AND_ASSIGN(List); 18043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen}; 18143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 182ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org 183ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.orgtemplate<typename T, class P> 184ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.orgsize_t GetMemoryUsedByList(const List<T, P>& list) { 185ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org return list.length() * sizeof(T) + sizeof(list); 186ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org} 187ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org 188ddf3811f8018dfe9e8ec7d1b8f4a8be1122fd767machenbach@chromium.org 189ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.orgclass Map; 190034539689f9600e463cd5273725c6269d0f3b8cbmachenbach@chromium.orgtemplate<class> class TypeImpl; 191034539689f9600e463cd5273725c6269d0f3b8cbmachenbach@chromium.orgstruct HeapTypeConfig; 1926d26cbb00b8ff12ecf86400c59f4a18d3850f22dmachenbach@chromium.orgtypedef TypeImpl<HeapTypeConfig> HeapType; 193ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.orgclass Code; 194394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.comtemplate<typename T> class Handle; 195ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.orgtypedef List<Map*> MapList; 196ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.orgtypedef List<Code*> CodeList; 197394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.comtypedef List<Handle<Map> > MapHandleList; 1986d26cbb00b8ff12ecf86400c59f4a18d3850f22dmachenbach@chromium.orgtypedef List<Handle<HeapType> > TypeHandleList; 199394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.comtypedef List<Handle<Code> > CodeHandleList; 200ea91cc579ade536e3a08498a8157921dd4f533d1ager@chromium.org 20134e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org// Perform binary search for an element in an already sorted 20234e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org// list. Returns the index of the element of -1 if it was not found. 20328faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org// |cmp| is a predicate that takes a pointer to an element of the List 20428faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org// and returns +1 if it is greater, -1 if it is less than the element 20528faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org// being searched. 20628faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.orgtemplate <typename T, class P> 20728faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.orgint SortedListBSearch(const List<T>& list, P cmp); 20834e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.orgtemplate <typename T> 20934e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.orgint SortedListBSearch(const List<T>& list, T elem); 21034e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 211394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.com 21243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} } // namespace v8::internal 21343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 21434e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 21543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#endif // V8_LIST_H_ 216