replace gimpy linear search with svelte binary search ;-)
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@63717 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Basic/SourceManager.cpp b/lib/Basic/SourceManager.cpp
index d9cf5e1..6381687 100644
--- a/lib/Basic/SourceManager.cpp
+++ b/lib/Basic/SourceManager.cpp
@@ -79,7 +79,14 @@
return E;
}
};
-
+
+inline bool operator<(const LineEntry &E, unsigned Offset) {
+ return E.FileOffset < Offset;
+}
+
+inline bool operator<(unsigned Offset, const LineEntry &E) {
+ return Offset < E.FileOffset;
+}
/// LineTableInfo - This class is used to hold and unique data used to
/// represent #line information.
@@ -160,13 +167,16 @@
const std::vector<LineEntry> &Entries = LineEntries[FID];
assert(!Entries.empty() && "No #line entries for this FID after all!");
+ // It is very common for the query to be after the last #line, check this
+ // first.
+ if (Entries.back().FileOffset <= Offset)
+ return &Entries.back();
- // FIXME: Dumb linear search.
- // Find the maximal element that is still before Offset.
- for (std::vector<LineEntry>::const_reverse_iterator I = Entries.rbegin(),
- E = Entries.rend(); I != E; ++I)
- if (I->FileOffset <= Offset) return &*I;
- return 0;
+ // Do a binary search to find the maximal element that is still before Offset.
+ std::vector<LineEntry>::const_iterator I =
+ std::upper_bound(Entries.begin(), Entries.end(), Offset);
+ if (I == Entries.begin()) return 0;
+ return &*--I;
}