Reviewers: danno,
Message:
PTAL.
Description:
Also use binary search to search through valid entries.
Please review this at https://chromiumcodereview.appspot.com/11028056/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files:
M src/objects-inl.h
Index: src/objects-inl.h
diff --git a/src/objects-inl.h b/src/objects-inl.h
index
fb3fe647f1a8be00eb543a54dfe8aecd69299fa6..f391af4356958133d080cf2bd9fd77ce78922d89
100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -1915,8 +1915,8 @@ void DescriptorArray::SetNumberOfDescriptors(int
number_of_descriptors) {
// Perform a binary search in a fixed array. Low and high are entry
indices. If
// there are three entries in this array it should be called with low=0 and
// high=2.
-template<typename T>
-int BinarySearch(T* array, String* name, int low, int high) {
+template<SearchMode search_mode, typename T>
+int BinarySearch(T* array, String* name, int low, int high, int
valid_entries) {
uint32_t hash = name->Hash();
int limit = high;
@@ -1938,7 +1938,12 @@ int BinarySearch(T* array, String* name, int low,
int high) {
int sort_index = array->GetSortedKeyIndex(low);
String* entry = array->GetKey(sort_index);
if (entry->Hash() != hash) break;
- if (entry->Equals(name)) return sort_index;
+ if (entry->Equals(name)) {
+ if (search_mode == ALL_ENTRIES || sort_index < valid_entries) {
+ return sort_index;
+ }
+ return T::kNotFound;
+ }
}
return T::kNotFound;
@@ -1982,13 +1987,12 @@ int Search(T* array, String* name, int
valid_entries) {
// Fast case: do linear search for small arrays.
const int kMaxElementsForLinearSearch = 8;
- if (search_mode == VALID_ENTRIES ||
- (search_mode == ALL_ENTRIES && nof < kMaxElementsForLinearSearch)) {
+ if (nof < kMaxElementsForLinearSearch) {
return LinearSearch<search_mode>(array, name, nof, valid_entries);
}
// Slow case: perform binary search.
- return BinarySearch(array, name, 0, nof - 1);
+ return BinarySearch<search_mode>(array, name, 0, nof - 1, valid_entries);
}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
