| 75 | namespace Implementation |
| 76 | { |
| 77 | const char* stringFindString(const char* data, const std::size_t size, const char* const substring, const std::size_t substringSize) { |
| 78 | // If the substring is not larger than the string we search in |
| 79 | if (substringSize > 0 && substringSize <= size) { |
| 80 | if (size == 0) return data; |
| 81 | |
| 82 | // Otherwise compare it with the string at all possible positions in the string until we have a match |
| 83 | /*for (const char* const max = data + size - substringSize; data <= max; ++data) { |
| 84 | if (std::memcmp(data, substring, substringSize) == 0) |
| 85 | return data; |
| 86 | }*/ |
| 87 | |
| 88 | // Simplified Boyer-Moore algorithm should be faster than std::memcmp() |
| 89 | std::size_t substringSize_1 = substringSize - 1; |
| 90 | char lastNeedle = substring[substringSize_1]; |
| 91 | |
| 92 | // Boyer-Moore skip value for the last char in the needle |
| 93 | // Zero is not a valid value, skip will be computed the first time it's needed |
| 94 | std::size_t skip = 0; |
| 95 | const char* begin = data; |
| 96 | const char* end = data + size - substringSize_1; |
| 97 | |
| 98 | while (begin < end) { |
| 99 | // Boyer-Moore: match the last element in the needle |
| 100 | while (begin[substringSize_1] != lastNeedle) { |
| 101 | if (++begin == end) { |
| 102 | return {}; |
| 103 | } |
| 104 | } |
| 105 | // Here we know that the last char matches, continue in pedestrian mode |
| 106 | for (std::size_t j = 0; ; ) { |
| 107 | if (begin[j] != substring[j]) { |
| 108 | // Not found, we can skip, compute the skip value lazily |
| 109 | if (skip == 0) { |
| 110 | skip = 1; |
| 111 | while (skip <= substringSize_1 && substring[substringSize_1 - skip] != lastNeedle) { |
| 112 | ++skip; |
| 113 | } |
| 114 | } |
| 115 | begin += skip; |
| 116 | break; |
| 117 | } |
| 118 | |
| 119 | if (++j == substringSize) { |
| 120 | return begin; |
| 121 | } |
| 122 | } |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | // If the substring is larger or no match was found, fail |
| 127 | return {}; |
| 128 | } |
| 129 | } |
| 130 | |
| 131 | template<class T> Array<BasicStringView<T>> BasicStringView<T>::split(const StringView delimiter) const { |