Reviewers: Søren Gjesse,
Description:
Use binary search in GetScriptLineNumber.
Patch by Ilya Tikhonovsky <[email protected]>
Original issue http://codereview.chromium.org/593108
[email protected]
Please review this at http://codereview.chromium.org/608012
Affected files:
M src/handles.cc
M test/cctest/test-compiler.cc
Index: src/handles.cc
diff --git a/src/handles.cc b/src/handles.cc
index
936177dbba393ce28de4d6f11a90b1f57b75973b..2186c516ab1b19076d860dcf3e49c6e34658d581
100644
--- a/src/handles.cc
+++ b/src/handles.cc
@@ -483,25 +483,25 @@ void InitScriptLineEnds(Handle<Script> script) {
int GetScriptLineNumber(Handle<Script> script, int code_pos) {
InitScriptLineEnds(script);
AssertNoAllocation no_allocation;
- FixedArray* line_ends_array =
- FixedArray::cast(script->line_ends());
+ FixedArray* line_ends_array = FixedArray::cast(script->line_ends());
const int line_ends_len = line_ends_array->length();
- int line = -1;
- if (line_ends_len > 0 &&
- code_pos <= (Smi::cast(line_ends_array->get(0)))->value()) {
- line = 0;
- } else {
- for (int i = 1; i < line_ends_len; ++i) {
- if ((Smi::cast(line_ends_array->get(i - 1)))->value() < code_pos &&
- code_pos <= (Smi::cast(line_ends_array->get(i)))->value()) {
- line = i;
- break;
- }
+ if (!line_ends_len)
+ return -1;
+
+ if ((Smi::cast(line_ends_array->get(0)))->value() > code_pos)
+ return script->line_offset()->value();
+
+ int left = 0;
+ int right = line_ends_len;
+ while (int half = (right - left) / 2) {
+ if ((Smi::cast(line_ends_array->get(left + half)))->value() >
code_pos) {
+ right -= half;
+ } else {
+ left += half;
}
}
-
- return line != -1 ? line + script->line_offset()->value() : line;
+ return right + script->line_offset()->value();
}
Index: test/cctest/test-compiler.cc
diff --git a/test/cctest/test-compiler.cc b/test/cctest/test-compiler.cc
index
05c29d7107eed6ad4ceea59d1b91de396ec2b1cc..da675d741de6c6f09fcdbdcdd88aaa65e8efde14
100644
--- a/test/cctest/test-compiler.cc
+++ b/test/cctest/test-compiler.cc
@@ -317,3 +317,27 @@ TEST(Regression236) {
CHECK_EQ(-1, GetScriptLineNumber(script, 100));
CHECK_EQ(-1, GetScriptLineNumber(script, -1));
}
+
+
+TEST(GetScriptLineNumber) {
+ LocalContext env;
+ v8::HandleScope scope;
+ v8::ScriptOrigin origin = v8::ScriptOrigin(v8::String::New("test"));
+ const char function_f[] = "function f() {}";
+ const int max_rows = 1000;
+ const int buffer_size = max_rows + sizeof(function_f);
+ ScopedVector<char> buffer(buffer_size);
+ memset(buffer.start(), '\n', buffer_size - 1);
+ buffer[buffer_size - 1] = '\0';
+
+ for (int i = 0; i < max_rows; ++i) {
+ if (i > 0)
+ buffer[i - 1] = '\n';
+ memcpy(&buffer[i], function_f, sizeof(function_f) - 1);
+ v8::Handle<v8::String> script_body = v8::String::New(buffer.start());
+ v8::Script::Compile(script_body, &origin)->Run();
+ v8::Local<v8::Function> f = v8::Local<v8::Function>::Cast(
+ env->Global()->Get(v8::String::New("f")));
+ CHECK_EQ(i, f->GetScriptLineNumber());
+ }
+}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
