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

Unified Diff: src/objects-inl.h

Issue 725633002: Revert "TransitionArray::Search() now returns insertion index if the entry was not found." (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 6 years, 1 month 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 | « src/objects.h ('k') | src/transitions.h » ('j') | 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 c741ce34e132ad255a944f3a30110e88863cba0d..1c1aec3cf788b8091068b8af63b07a236c4adb69 100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -2853,10 +2853,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 <SearchMode search_mode, typename T>
-int BinarySearch(T* array, Name* name, int low, int high, int valid_entries,
- int* out_insertion_index) {
- DCHECK(search_mode == ALL_ENTRIES || out_insertion_index == NULL);
+template<SearchMode search_mode, typename T>
+int BinarySearch(T* array, Name* name, int low, int high, int valid_entries) {
uint32_t hash = name->Hash();
int limit = high;
@@ -2877,13 +2875,7 @@ int BinarySearch(T* array, Name* name, int low, int high, int valid_entries,
for (; low <= limit; ++low) {
int sort_index = array->GetSortedKeyIndex(low);
Name* entry = array->GetKey(sort_index);
- uint32_t current_hash = entry->Hash();
- if (current_hash != hash) {
- if (out_insertion_index != NULL) {
- *out_insertion_index = sort_index + (current_hash > hash ? 0 : 1);
- }
- return T::kNotFound;
- }
+ if (entry->Hash() != hash) break;
if (entry->Equals(name)) {
if (search_mode == ALL_ENTRIES || sort_index < valid_entries) {
return sort_index;
@@ -2892,45 +2884,37 @@ int BinarySearch(T* array, Name* name, int low, int high, int valid_entries,
}
}
- if (out_insertion_index != NULL) *out_insertion_index = limit + 1;
return T::kNotFound;
}
// Perform a linear search in this fixed array. len is the number of entry
// indices that are valid.
-template <SearchMode search_mode, typename T>
-int LinearSearch(T* array, Name* name, int len, int valid_entries,
- int* out_insertion_index) {
+template<SearchMode search_mode, typename T>
+int LinearSearch(T* array, Name* name, int len, int valid_entries) {
uint32_t hash = name->Hash();
if (search_mode == ALL_ENTRIES) {
for (int number = 0; number < len; number++) {
int sorted_index = array->GetSortedKeyIndex(number);
Name* entry = array->GetKey(sorted_index);
uint32_t current_hash = entry->Hash();
- if (current_hash > hash) {
- if (out_insertion_index != NULL) *out_insertion_index = sorted_index;
- return T::kNotFound;
- }
+ if (current_hash > hash) break;
if (current_hash == hash && entry->Equals(name)) return sorted_index;
}
- if (out_insertion_index != NULL) *out_insertion_index = len;
- return T::kNotFound;
} else {
DCHECK(len >= valid_entries);
- DCHECK_EQ(NULL, out_insertion_index); // Not supported here.
for (int number = 0; number < valid_entries; number++) {
Name* entry = array->GetKey(number);
uint32_t current_hash = entry->Hash();
if (current_hash == hash && entry->Equals(name)) return number;
}
- return T::kNotFound;
}
+ return T::kNotFound;
}
-template <SearchMode search_mode, typename T>
-int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) {
+template<SearchMode search_mode, typename T>
+int Search(T* array, Name* name, int valid_entries) {
if (search_mode == VALID_ENTRIES) {
SLOW_DCHECK(array->IsSortedNoDuplicates(valid_entries));
} else {
@@ -2938,10 +2922,7 @@ int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) {
}
int nof = array->number_of_entries();
- if (nof == 0) {
- if (out_insertion_index != NULL) *out_insertion_index = 0;
- return T::kNotFound;
- }
+ if (nof == 0) return T::kNotFound;
// Fast case: do linear search for small arrays.
const int kMaxElementsForLinearSearch = 8;
@@ -2949,18 +2930,16 @@ int Search(T* array, Name* name, int valid_entries, int* out_insertion_index) {
nof <= kMaxElementsForLinearSearch) ||
(search_mode == VALID_ENTRIES &&
valid_entries <= (kMaxElementsForLinearSearch * 3))) {
- return LinearSearch<search_mode>(array, name, nof, valid_entries,
- out_insertion_index);
+ return LinearSearch<search_mode>(array, name, nof, valid_entries);
}
// Slow case: perform binary search.
- return BinarySearch<search_mode>(array, name, 0, nof - 1, valid_entries,
- out_insertion_index);
+ return BinarySearch<search_mode>(array, name, 0, nof - 1, valid_entries);
}
int DescriptorArray::Search(Name* name, int valid_descriptors) {
- return internal::Search<VALID_ENTRIES>(this, name, valid_descriptors, NULL);
+ return internal::Search<VALID_ENTRIES>(this, name, valid_descriptors);
}
« no previous file with comments | « src/objects.h ('k') | src/transitions.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698