Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(469)

Unified Diff: src/objects-inl.h

Issue 11028056: Also use binary search to search through valid entries. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: In case of VALID_ENTRIES, check valid_entries <= kMax Created 8 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/objects-inl.h
diff --git a/src/objects-inl.h b/src/objects-inl.h
index fb3fe647f1a8be00eb543a54dfe8aecd69299fa6..38104f5ad237975f116be79cf4bd2759386827c7 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,15 @@ 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 ((search_mode == ALL_ENTRIES &&
+ nof <= kMaxElementsForLinearSearch) ||
+ (search_mode == VALID_ENTRIES &&
+ valid_entries <= 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);
}
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698