Search for this pattern in str. Returns the offset into str if the pattern exists Returns -1 if the pattern is not found
| 79 | /// Returns the offset into str if the pattern exists |
| 80 | /// Returns -1 if the pattern is not found |
| 81 | int Search(const StringValue* str) const { |
| 82 | // Special cases |
| 83 | if (str == NULL || pattern_ == NULL || pattern_->Len() == 0) { |
| 84 | return -1; |
| 85 | } |
| 86 | StringValue::SimpleString pattern_s = pattern_->ToSimpleString(); |
| 87 | StringValue::SimpleString str_s = str->ToSimpleString(); |
| 88 | |
| 89 | int mlast = pattern_s.len - 1; |
| 90 | int w = str_s.len - pattern_s.len; |
| 91 | int n = str_s.len; |
| 92 | int m = pattern_s.len; |
| 93 | const char* s = str_s.ptr; |
| 94 | const char* p = pattern_s.ptr; |
| 95 | |
| 96 | // Special case if pattern->len == 1 |
| 97 | if (m == 1) { |
| 98 | const char* result = reinterpret_cast<const char*>(memchr(s, p[0], n)); |
| 99 | if (result != NULL) return result - s; |
| 100 | return -1; |
| 101 | } |
| 102 | |
| 103 | // General case. |
| 104 | int j; |
| 105 | // TODO: the original code seems to have an off by one error. It is possible |
| 106 | // to index at w + m which is the length of the input string. Checks have |
| 107 | // been added to make sure that w + m < str->len. |
| 108 | for (int i = 0; i <= w; i++) { |
| 109 | // note: using mlast in the skip path slows things down on x86 |
| 110 | if (s[i+m-1] == p[m-1]) { |
| 111 | // candidate match |
| 112 | for (j = 0; j < mlast; j++) |
| 113 | if (s[i+j] != p[j]) break; |
| 114 | if (j == mlast) { |
| 115 | return i; |
| 116 | } |
| 117 | // miss: check if next character is part of pattern |
| 118 | if (i + m < n && !BloomQuery(s[i+m])) |
| 119 | i = i + m; |
| 120 | else |
| 121 | i = i + skip_; |
| 122 | } else { |
| 123 | // skip: check if next character is part of pattern |
| 124 | if (i + m < n && !BloomQuery(s[i+m])) { |
| 125 | i = i + m; |
| 126 | } |
| 127 | } |
| 128 | } |
| 129 | return -1; |
| 130 | } |
| 131 | |
| 132 | /// Search for this pattern in str backwards. |
| 133 | /// Returns the offset into str if the pattern exists |