Add SETEND and BXJ instructions for disassembly only.

[oota-llvm.git] / lib / Support / StringRef.cpp

diff --git a/lib/Support/StringRef.cpp b/lib/Support/StringRef.cpp
index deaa19efe998632d21797544d0f7a27572f395f5..ae2640b5b9460da65779c3e91a9211bc78e01013 100644 (file)
--- a/lib/Support/StringRef.cpp
+++ b/lib/Support/StringRef.cpp
@@ -8,6 +8,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringRef.h"
+
 using namespace llvm;
 
 // MSVC emits references to this into the translation units which reference it.
@@ -15,6 +16,76 @@ using namespace llvm;
 const size_t StringRef::npos;
 #endif
 
+static char ascii_tolower(char x) {
+  if (x >= 'A' && x <= 'Z')
+    return x - 'A' + 'a';
+  return x;
+}
+
+/// compare_lower - Compare strings, ignoring case.
+int StringRef::compare_lower(StringRef RHS) const {
+  for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) {
+    char LHC = ascii_tolower(Data[I]);
+    char RHC = ascii_tolower(RHS.Data[I]);
+    if (LHC != RHC)
+      return LHC < RHC ? -1 : 1;
+  }
+
+  if (Length == RHS.Length)
+        return 0;
+  return Length < RHS.Length ? -1 : 1;
+}
+
+// Compute the edit distance between the two given strings.
+unsigned StringRef::edit_distance(llvm::StringRef Other, 
+                                  bool AllowReplacements) {
+  // The algorithm implemented below is the "classic"
+  // dynamic-programming algorithm for computing the Levenshtein
+  // distance, which is described here:
+  //
+  //   http://en.wikipedia.org/wiki/Levenshtein_distance
+  //
+  // Although the algorithm is typically described using an m x n
+  // array, only two rows are used at a time, so this implemenation
+  // just keeps two separate vectors for those two rows.
+  size_type m = size();
+  size_type n = Other.size();
+
+  const unsigned SmallBufferSize = 64;
+  unsigned SmallBuffer[SmallBufferSize];
+  unsigned *Allocated = 0;
+  unsigned *previous = SmallBuffer;
+  if (2*(n + 1) > SmallBufferSize)
+    Allocated = previous = new unsigned [2*(n+1)];
+  unsigned *current = previous + (n + 1);
+  
+  for (unsigned i = 0; i <= n; ++i) 
+    previous[i] = i;
+
+  for (size_type y = 1; y <= m; ++y) {
+    current[0] = y;
+    for (size_type x = 1; x <= n; ++x) {
+      if (AllowReplacements) {
+        current[x] = min(previous[x-1] + ((*this)[y-1] == Other[x-1]? 0u:1u),
+                         min(current[x-1], previous[x])+1);
+      }
+      else {
+        if ((*this)[y-1] == Other[x-1]) current[x] = previous[x-1];
+        else current[x] = min(current[x-1], previous[x]) + 1;
+      }
+    }
+    
+    unsigned *tmp = current;
+    current = previous;
+    previous = tmp;
+  }
+
+  unsigned Result = previous[n];
+  delete [] Allocated;
+  
+  return Result;
+}
+
 //===----------------------------------------------------------------------===//
 // String Searching
 //===----------------------------------------------------------------------===//
@@ -24,11 +95,11 @@ const size_t StringRef::npos;
 ///
 /// \return - The index of the first occurence of \arg Str, or npos if not
 /// found.
-size_t StringRef::find(const StringRef &Str) const {
+size_t StringRef::find(StringRef Str, size_t From) const {
   size_t N = Str.size();
   if (N > Length)
     return npos;
-  for (size_t i = 0, e = Length - N + 1; i != e; ++i)
+  for (size_t e = Length - N + 1, i = min(From, e); i != e; ++i)
     if (substr(i, N).equals(Str))
       return i;
   return npos;
@@ -38,7 +109,7 @@ size_t StringRef::find(const StringRef &Str) const {
 ///
 /// \return - The index of the last occurence of \arg Str, or npos if not
 /// found.
-size_t StringRef::rfind(const StringRef &Str) const {
+size_t StringRef::rfind(StringRef Str) const {
   size_t N = Str.size();
   if (N > Length)
     return npos;
@@ -50,19 +121,34 @@ size_t StringRef::rfind(const StringRef &Str) const {
   return npos;
 }
 
-/// find_first_of - Find the first character from the string 'Chars' in the
-/// current string or return npos if not in string.
-StringRef::size_type StringRef::find_first_of(StringRef Chars) const {
-  for (size_type i = 0, e = Length; i != e; ++i)
+/// find_first_of - Find the first character in the string that is in \arg
+/// Chars, or npos if not found.
+///
+/// Note: O(size() * Chars.size())
+StringRef::size_type StringRef::find_first_of(StringRef Chars,
+                                              size_t From) const {
+  for (size_type i = min(From, Length), e = Length; i != e; ++i)
     if (Chars.find(Data[i]) != npos)
       return i;
   return npos;
 }
 
 /// find_first_not_of - Find the first character in the string that is not
-/// in the string 'Chars' or return npos if all are in string. Same as find.
-StringRef::size_type StringRef::find_first_not_of(StringRef Chars) const {
-  for (size_type i = 0, e = Length; i != e; ++i)
+/// \arg C or npos if not found.
+StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const {
+  for (size_type i = min(From, Length), e = Length; i != e; ++i)
+    if (Data[i] != C)
+      return i;
+  return npos;
+}
+
+/// find_first_not_of - Find the first character in the string that is not
+/// in the string \arg Chars, or npos if not found.
+///
+/// Note: O(size() * Chars.size())
+StringRef::size_type StringRef::find_first_not_of(StringRef Chars,
+                                                  size_t From) const {
+  for (size_type i = min(From, Length), e = Length; i != e; ++i)
     if (Chars.find(Data[i]) == npos)
       return i;
   return npos;
@@ -75,7 +161,7 @@ StringRef::size_type StringRef::find_first_not_of(StringRef Chars) const {
 
 /// count - Return the number of non-overlapped occurrences of \arg Str in
 /// the string.
-size_t StringRef::count(const StringRef &Str) const {
+size_t StringRef::count(StringRef Str) const {
   size_t Count = 0;
   size_t N = Str.size();
   if (N > Length)