15ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org// Copyright 2006-2009 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_INL_H_ 643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#define V8_LIST_INL_H_ 743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 8196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/list.h" 95de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org 105de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org#include "src/base/platform/platform.h" 1143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 1271affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace v8 { 1371affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgnamespace internal { 1443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 1543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 1643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansentemplate<typename T, class P> 17400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::Add(const T& element, P alloc) { 187be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org if (length_ < capacity_) { 197be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org data_[length_++] = element; 207be3c996bea370e151c9fe4ecf7f779cdc5f87adkasperl@chromium.org } else { 21400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org List<T, P>::ResizeAdd(element, alloc); 2243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen } 2343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} 2443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 2543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 2671affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgtemplate<typename T, class P> 27400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::AddAll(const List<T, P>& other, P alloc) { 28400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org AddAll(other.ToVector(), alloc); 298e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org} 308e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org 318e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org 328e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.orgtemplate<typename T, class P> 33400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::AddAll(const Vector<T>& other, P alloc) { 348e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org int result_length = length_ + other.length(); 35400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org if (capacity_ < result_length) Resize(result_length, alloc); 368e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org for (int i = 0; i < other.length(); i++) { 378e8294a88dc7d58f579aee0ba08c19fc8a616e2dsgjesse@chromium.org data_[length_ + i] = other.at(i); 3871affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org } 3971affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org length_ = result_length; 4071affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org} 4171affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org 4271affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org 435ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org// Use two layers of inlining so that the non-inlined function can 445ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org// use the same implementation as the inlined version. 455ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.orgtemplate<typename T, class P> 46400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::ResizeAdd(const T& element, P alloc) { 47400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org ResizeAddInternal(element, alloc); 485ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org} 495ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org 505ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org 515ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.orgtemplate<typename T, class P> 52400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::ResizeAddInternal(const T& element, P alloc) { 53e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(length_ >= capacity_); 54ab7dad4f999df008b590c74c2fe3d2e2c67ef7ffjkummerow@chromium.org // Grow the list capacity by 100%, but make sure to let it grow 555ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org // even when the capacity is zero (possible initial case). 56ab7dad4f999df008b590c74c2fe3d2e2c67ef7ffjkummerow@chromium.org int new_capacity = 1 + 2 * capacity_; 5771affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org // Since the element reference could be an element of the list, copy 5871affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org // it out of the old backing storage before resizing. 5971affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org T temp = element; 60400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Resize(new_capacity, alloc); 6171affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org data_[length_++] = temp; 6271affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org} 6371affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org 6471affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.org 6571affb54842da76b24f0bb3184e9f0960523f89dkasperl@chromium.orgtemplate<typename T, class P> 66400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::Resize(int new_capacity, P alloc) { 67e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_LE(length_, new_capacity); 68400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org T* new_data = NewData(new_capacity, alloc); 69d06b9264b1c886fc80a100e9915cf8ae07fdb4e5machenbach@chromium.org MemCopy(new_data, data_, length_ * sizeof(T)); 705ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org List<T, P>::DeleteData(data_); 715ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org data_ = new_data; 725ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org capacity_ = new_capacity; 735ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org} 745ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org 755ec4892aef9cca42940d7d92302abf674365f6b7ager@chromium.org 7643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansentemplate<typename T, class P> 77400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgVector<T> List<T, P>::AddBlock(T value, int count, P alloc) { 7843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen int start = length_; 79400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org for (int i = 0; i < count; i++) Add(value, alloc); 8043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen return Vector<T>(&data_[start], count); 8143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} 8243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 8343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 8443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansentemplate<typename T, class P> 8557ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.orgvoid List<T, P>::Set(int index, const T& elm) { 86e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(index >= 0 && index <= length_); 8757ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org data_[index] = elm; 8857ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org} 8957ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org 9057ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.org 9157ff881caeb2e15b46ac9e4dfc00e378f7c5f929ulan@chromium.orgtemplate<typename T, class P> 92400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::InsertAt(int index, const T& elm, P alloc) { 93e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(index >= 0 && index <= length_); 94400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Add(elm, alloc); 95a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = length_ - 1; i > index; --i) { 96a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org data_[i] = data_[i - 1]; 97a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 98a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org data_[index] = elm; 99a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 100a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 101a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 102a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgtemplate<typename T, class P> 10343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansenT List<T, P>::Remove(int i) { 10443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen T element = at(i); 10543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen length_--; 10643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen while (i < length_) { 10743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen data_[i] = data_[i + 1]; 10843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen i++; 10943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen } 11043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen return element; 11143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} 11243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 11343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 11443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansentemplate<typename T, class P> 115a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool List<T, P>::RemoveElement(const T& elm) { 116a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = 0; i < length_; i++) { 117a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (data_[i] == elm) { 118a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org Remove(i); 119a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return true; 120a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 121a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 122a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return false; 123a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 124a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 125a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 126a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgtemplate<typename T, class P> 127400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::Allocate(int length, P allocator) { 128212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org DeleteData(data_); 129400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org Initialize(length, allocator); 130212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org length_ = length; 131212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org} 132212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org 133212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.org 134212d964d8f853ddb1fdf3a64037f3af294d55cf3jkummerow@chromium.orgtemplate<typename T, class P> 13543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansenvoid List<T, P>::Clear() { 13643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen DeleteData(data_); 1377028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org // We don't call Initialize(0) since that requires passing a Zone, 1387028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org // which we don't really need. 1397028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org data_ = NULL; 1407028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org capacity_ = 0; 1417028c05c1c71b9d5c5fe1bca01f2461d17a2dda7mmassi@chromium.org length_ = 0; 14243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} 14343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 14443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 14543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansentemplate<typename T, class P> 14643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansenvoid List<T, P>::Rewind(int pos) { 147e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(0 <= pos && pos <= length_); 14843d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen length_ = pos; 14943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} 15043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 15143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 15243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansentemplate<typename T, class P> 15346a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.orgvoid List<T, P>::Trim(P alloc) { 15446a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org if (length_ < capacity_ / 4) { 15546a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org Resize(capacity_ / 2, alloc); 15646a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org } 15746a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org} 15846a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org 15946a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.org 16046a2a51ad190697e0f62c3060ce02a9de5820a07yangguo@chromium.orgtemplate<typename T, class P> 16143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansenvoid List<T, P>::Iterate(void (*callback)(T* x)) { 16243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen for (int i = 0; i < length_; i++) callback(&data_[i]); 16343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} 16443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 16543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 16643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansentemplate<typename T, class P> 16726c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.orgtemplate<class Visitor> 16826c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.orgvoid List<T, P>::Iterate(Visitor* visitor) { 16926c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.org for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]); 17026c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.org} 17126c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.org 17226c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.org 17326c16f8ef35ec25d36420512a4ceaa74ea2e2b05vegorov@chromium.orgtemplate<typename T, class P> 174a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgbool List<T, P>::Contains(const T& elm) const { 175a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org for (int i = 0; i < length_; i++) { 176a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org if (data_[i] == elm) 177a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return true; 178a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org } 179a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org return false; 180a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org} 181a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 182a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 183a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgtemplate<typename T, class P> 184a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgint List<T, P>::CountOccurrences(const T& elm, int start, int end) const { 185a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org int result = 0; 186a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org for (int i = start; i <= end; i++) { 187a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org if (data_[i] == elm) ++result; 188a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org } 189a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org return result; 190a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org} 191a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 192a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.org 193a55512615f5adc085d23bc8589d155c4b579fb7bkasperl@chromium.orgtemplate<typename T, class P> 19443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansenvoid List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) { 195a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org ToVector().Sort(cmp); 19643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#ifdef DEBUG 19743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen for (int i = 1; i < length_; i++) 198e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0); 19943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#endif 20043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} 20143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 20243d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 20343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansentemplate<typename T, class P> 204a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgvoid List<T, P>::Sort() { 205ca29dd85fa02449d17188f5a6ff9a7cdf2ad9680danno@chromium.org ToVector().Sort(); 206a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org} 207a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 208a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.org 209a74f0daeb278665869b4b6a3bc2739e88fed93b1ager@chromium.orgtemplate<typename T, class P> 210400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.orgvoid List<T, P>::Initialize(int capacity, P allocator) { 211e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(capacity >= 0); 212400388edd471bd4d4a97b21c52c1024cd1cc5708rossberg@chromium.org data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL; 21343d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen capacity_ = capacity; 21443d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen length_ = 0; 21543d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} 21643d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 21743d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 21828faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.orgtemplate <typename T, typename P> 21928faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.orgint SortedListBSearch(const List<T>& list, P cmp) { 22034e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org int low = 0; 22134e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org int high = list.length() - 1; 22234e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org while (low <= high) { 2232b995c4171e67960088466af11110c6f6aeea4fcmachenbach@chromium.org int mid = (low + high) / 2; 22434e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org T mid_elem = list[mid]; 22534e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 22628faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org if (cmp(&mid_elem) > 0) { 22734e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org high = mid - 1; 22834e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org continue; 22934e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org } 23028faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org if (cmp(&mid_elem) < 0) { 23134e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org low = mid + 1; 23234e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org continue; 23334e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org } 23434e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org // Found the elememt. 23534e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org return mid; 23634e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org } 23734e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org return -1; 23834e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org} 23934e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 24034e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 24128faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.orgtemplate<typename T> 24228faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.orgclass ElementCmp { 24328faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org public: 24428faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org explicit ElementCmp(T e) : elem_(e) {} 24528faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org int operator()(const T* other) { 24628faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org return PointerValueCompare(other, &elem_); 24728faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org } 24828faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org private: 24928faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org T elem_; 25028faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org}; 25128faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org 25228faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org 25334e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.orgtemplate <typename T> 25434e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.orgint SortedListBSearch(const List<T>& list, T elem) { 25528faa982749c4aa9c090939453dea14bb118f613jkummerow@chromium.org return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem)); 25634e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org} 25734e60787ea1e76f3ee49e859f71f036170c21f0elrn@chromium.org 258394dbcf9009cf5203b6d85e8b515fcff072040f3erik.corry@gmail.com 25943d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen} } // namespace v8::internal 26043d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen 26143d26ecc3563a46f62a0224030667c8f8f3f6cebchristian.plesner.hansen#endif // V8_LIST_INL_H_ 262