1a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Copyright 2006-2009 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. 4a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 5a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#ifndef V8_LIST_INL_H_ 6a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#define V8_LIST_INL_H_ 7a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/list.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/base/platform/platform.h" 11a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 12a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace v8 { 13a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace internal { 14a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 15a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 16a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::Add(const T& element, P alloc) { 18a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (length_ < capacity_) { 19a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block data_[length_++] = element; 20a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch List<T, P>::ResizeAdd(element, alloc); 22a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 23a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 24a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 25a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 26a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::AddAll(const List<T, P>& other, P alloc) { 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AddAll(other.ToVector(), alloc); 29257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch} 30257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 31257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 32257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdochtemplate<typename T, class P> 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::AddAll(const Vector<T>& other, P alloc) { 34257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch int result_length = length_ + other.length(); 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (capacity_ < result_length) Resize(result_length, alloc); 36257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch for (int i = 0; i < other.length(); i++) { 37257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch data_[length_ + i] = other.at(i); 38a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length_ = result_length; 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Use two layers of inlining so that the non-inlined function can 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// use the same implementation as the inlined version. 45a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::ResizeAdd(const T& element, P alloc) { 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ResizeAddInternal(element, alloc); 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 50a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::ResizeAddInternal(const T& element, P alloc) { 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(length_ >= capacity_); 543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Grow the list capacity by 100%, but make sure to let it grow 55a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // even when the capacity is zero (possible initial case). 563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int new_capacity = 1 + 2 * capacity_; 57a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Since the element reference could be an element of the list, copy 58a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // it out of the old backing storage before resizing. 59a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T temp = element; 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Resize(new_capacity, alloc); 61a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block data_[length_++] = temp; 62a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 63a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 64a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 65a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::Resize(int new_capacity, P alloc) { 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_LE(length_, new_capacity); 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T* new_data = NewData(new_capacity, alloc); 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MemCopy(new_data, data_, length_ * sizeof(T)); 70a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block List<T, P>::DeleteData(data_); 71a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block data_ = new_data; 72a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block capacity_ = new_capacity; 73a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 74a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 75a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 76a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochVector<T> List<T, P>::AddBlock(T value, int count, P alloc) { 78a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block int start = length_; 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < count; i++) Add(value, alloc); 80a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(&data_[start], count); 81a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 82a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 83a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 84a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::Set(int index, const T& elm) { 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(index >= 0 && index <= length_); 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch data_[index] = elm; 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<typename T, class P> 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::InsertAt(int index, const T& elm, P alloc) { 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(index >= 0 && index <= length_); 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Add(elm, alloc); 95b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = length_ - 1; i > index; --i) { 96b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch data_[i] = data_[i - 1]; 97b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 98b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch data_[index] = elm; 99b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 100b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 101b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 102b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochtemplate<typename T, class P> 103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockT List<T, P>::Remove(int i) { 104a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T element = at(i); 105a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length_--; 106a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (i < length_) { 107a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block data_[i] = data_[i + 1]; 108a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block i++; 109a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 110a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return element; 111a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 112a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 113a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 114a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 115b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool List<T, P>::RemoveElement(const T& elm) { 116b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < length_; i++) { 117b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (data_[i] == elm) { 118b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch Remove(i); 119b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return true; 120b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 121b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 122b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return false; 123b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 124b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 125b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 126b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochtemplate<typename T, class P> 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::Allocate(int length, P allocator) { 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DeleteData(data_); 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Initialize(length, allocator); 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch length_ = length; 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<typename T, class P> 135a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvoid List<T, P>::Clear() { 136a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block DeleteData(data_); 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // We don't call Initialize(0) since that requires passing a Zone, 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // which we don't really need. 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch data_ = NULL; 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch capacity_ = 0; 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch length_ = 0; 142a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 143a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 144a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 145a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 146a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvoid List<T, P>::Rewind(int pos) { 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(0 <= pos && pos <= length_); 148a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length_ = pos; 149a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 150a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 151a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 152a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::Trim(P alloc) { 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (length_ < capacity_ / 4) { 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Resize(capacity_ / 2, alloc); 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<typename T, class P> 161a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvoid List<T, P>::Iterate(void (*callback)(T* x)) { 162a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (int i = 0; i < length_; i++) callback(&data_[i]); 163a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 164a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 165a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 166a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 167756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merricktemplate<class Visitor> 168756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrickvoid List<T, P>::Iterate(Visitor* visitor) { 169756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrick for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]); 170756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrick} 171756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrick 172756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrick 173756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merricktemplate<typename T, class P> 174b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochbool List<T, P>::Contains(const T& elm) const { 175a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (int i = 0; i < length_; i++) { 176a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (data_[i] == elm) 177a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return true; 178a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 179a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return false; 180a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 181a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 182a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 183a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 184b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochint List<T, P>::CountOccurrences(const T& elm, int start, int end) const { 185b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch int result = 0; 186b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = start; i <= end; i++) { 187b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch if (data_[i] == elm) ++result; 188b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 189b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return result; 190b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch} 191b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 192b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 193b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochtemplate<typename T, class P> 194a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvoid List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) { 195a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ToVector().Sort(cmp); 196a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#ifdef DEBUG 197a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (int i = 1; i < length_; i++) 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0); 199a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#endif 200a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 201a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 202a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 203a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 204a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvoid List<T, P>::Sort() { 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ToVector().Sort(); 206a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 207a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 208a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 209a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<typename T, class P> 210b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid List<T, P>::Initialize(int capacity, P allocator) { 211b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(capacity >= 0); 212b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL; 213a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block capacity_ = capacity; 214a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length_ = 0; 215a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 216a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 217a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <typename T, typename P> 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochint SortedListBSearch(const List<T>& list, P cmp) { 220589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch int low = 0; 221589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch int high = list.length() - 1; 222589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch while (low <= high) { 223589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch int mid = (low + high) / 2; 224589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch T mid_elem = list[mid]; 225589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 226b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (cmp(&mid_elem) > 0) { 227589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch high = mid - 1; 228589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch continue; 229589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (cmp(&mid_elem) < 0) { 231589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch low = mid + 1; 232589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch continue; 233589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } 234589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch // Found the elememt. 235589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch return mid; 236589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } 237589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch return -1; 238589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch} 239589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 240589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 241b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<typename T> 242b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass ElementCmp { 243b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 244b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit ElementCmp(T e) : elem_(e) {} 245b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int operator()(const T* other) { 246b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return PointerValueCompare(other, &elem_); 247b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 248b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 249b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T elem_; 250b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 251b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 253589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdochtemplate <typename T> 254589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdochint SortedListBSearch(const List<T>& list, T elem) { 255b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem)); 256589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch} 257589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 2583ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 259a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} } // namespace v8::internal 260a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 261a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#endif // V8_LIST_INL_H_ 262