Search for this pattern in str backwards. Returns the offset into str if the pattern exists Returns -1 if the pattern is not found
| 133 | /// Returns the offset into str if the pattern exists |
| 134 | /// Returns -1 if the pattern is not found |
| 135 | int RSearch(const StringValue* str) const { |
| 136 | // Special cases |
| 137 | if (str == NULL || pattern_ == NULL || pattern_->Len() == 0) { |
| 138 | return -1; |
| 139 | } |
| 140 | StringValue::SimpleString pattern_s = pattern_->ToSimpleString(); |
| 141 | StringValue::SimpleString str_s = str->ToSimpleString(); |
| 142 | |
| 143 | int mlast = pattern_s.len - 1; |
| 144 | int w = str_s.len - pattern_s.len; |
| 145 | int n = str_s.len; |
| 146 | int m = pattern_s.len; |
| 147 | const char* s = str_s.ptr; |
| 148 | const char* p = pattern_s.ptr; |
| 149 | |
| 150 | // Special case if pattern->len == 1 |
| 151 | if (m == 1) { |
| 152 | const char* result = reinterpret_cast<const char*>(memrchr(s, p[0], n)); |
| 153 | if (result != NULL) return result - s; |
| 154 | return -1; |
| 155 | } |
| 156 | |
| 157 | // General case. |
| 158 | int j; |
| 159 | for (int i = w; i >= 0; i--) { |
| 160 | if (s[i] == p[0]) { |
| 161 | // candidate match |
| 162 | for (j = mlast; j > 0; j--) |
| 163 | if (s[i + j] != p[j]) break; |
| 164 | if (j == 0) { |
| 165 | return i; |
| 166 | } |
| 167 | // miss: check if previous character is part of pattern |
| 168 | if (i > 0 && !BloomQuery(s[i - 1])) |
| 169 | i = i - m; |
| 170 | else |
| 171 | i = i - rskip_; |
| 172 | } else { |
| 173 | // skip: check if previous character is part of pattern |
| 174 | if (i > 0 && !BloomQuery(s[i - 1])) { |
| 175 | i = i - m; |
| 176 | } |
| 177 | } |
| 178 | } |
| 179 | return -1; |
| 180 | } |
| 181 | |
| 182 | private: |
| 183 | static const int BLOOM_WIDTH = 64; |