summaryrefslogtreecommitdiff
path: root/absl/strings/match.cc
diff options
context:
space:
mode:
authorGravatar Tsige Solomon <tsige@google.com>2023-06-12 15:56:24 -0700
committerGravatar Copybara-Service <copybara-worker@google.com>2023-06-12 15:57:58 -0700
commit77111e3d5b40df6019fedc85198f7376c120bffb (patch)
tree35a9976fce72969966300ae4968bbbbabed36fcc /absl/strings/match.cc
parentdfc7f46d9c8425933ffe2c275f982f956d33d06f (diff)
Functions added: FindLongestCommonSuffix, FindLongestCommonPrefix.
PiperOrigin-RevId: 539784770 Change-Id: Ie224afa04af023bbddc89b967e8c8440f9e8a887
Diffstat (limited to 'absl/strings/match.cc')
-rw-r--r--absl/strings/match.cc67
1 files changed, 66 insertions, 1 deletions
diff --git a/absl/strings/match.cc b/absl/strings/match.cc
index b65cbc67..3b81b2c0 100644
--- a/absl/strings/match.cc
+++ b/absl/strings/match.cc
@@ -13,8 +13,13 @@
// limitations under the License.
#include "absl/strings/match.h"
-#include "absl/strings/ascii.h"
+#include <algorithm>
+#include <cstdint>
+
+#include "absl/base/internal/endian.h"
+#include "absl/numeric/bits.h"
+#include "absl/strings/ascii.h"
#include "absl/strings/internal/memutil.h"
namespace absl {
@@ -61,5 +66,65 @@ bool EndsWithIgnoreCase(absl::string_view text,
EqualsIgnoreCase(text.substr(text.size() - suffix.size()), suffix);
}
+absl::string_view FindLongestCommonPrefix(absl::string_view a,
+ absl::string_view b) {
+ const absl::string_view::size_type limit = std::min(a.size(), b.size());
+ const char* const pa = a.data();
+ const char* const pb = b.data();
+ absl::string_view::size_type count = (unsigned) 0;
+
+ if (ABSL_PREDICT_FALSE(limit < 8)) {
+ while (ABSL_PREDICT_TRUE(count + 2 <= limit)) {
+ uint16_t xor_bytes = absl::little_endian::Load16(pa + count) ^
+ absl::little_endian::Load16(pb + count);
+ if (ABSL_PREDICT_FALSE(xor_bytes != 0)) {
+ if (ABSL_PREDICT_TRUE((xor_bytes & 0xff) == 0)) ++count;
+ return absl::string_view(pa, count);
+ }
+ count += 2;
+ }
+ if (ABSL_PREDICT_TRUE(count != limit)) {
+ if (ABSL_PREDICT_TRUE(pa[count] == pb[count])) ++count;
+ }
+ return absl::string_view(pa, count);
+ }
+
+ do {
+ uint64_t xor_bytes = absl::little_endian::Load64(pa + count) ^
+ absl::little_endian::Load64(pb + count);
+ if (ABSL_PREDICT_FALSE(xor_bytes != 0)) {
+ count += static_cast<uint64_t>(absl::countr_zero(xor_bytes) >> 3);
+ return absl::string_view(pa, count);
+ }
+ count += 8;
+ } while (ABSL_PREDICT_TRUE(count + 8 < limit));
+
+ count = limit - 8;
+ uint64_t xor_bytes = absl::little_endian::Load64(pa + count) ^
+ absl::little_endian::Load64(pb + count);
+ if (ABSL_PREDICT_TRUE(xor_bytes != 0)) {
+ count += static_cast<uint64_t>(absl::countr_zero(xor_bytes) >> 3);
+ return absl::string_view(pa, count);
+ }
+ return absl::string_view(pa, limit);
+}
+
+absl::string_view FindLongestCommonSuffix(absl::string_view a,
+ absl::string_view b) {
+ const absl::string_view::size_type limit = std::min(a.size(), b.size());
+ if (limit == 0) return absl::string_view();
+
+ const char* pa = a.data() + a.size() - 1;
+ const char* pb = b.data() + b.size() - 1;
+ absl::string_view::size_type count = (unsigned) 0;
+ while (count < limit && *pa == *pb) {
+ --pa;
+ --pb;
+ ++count;
+ }
+
+ return absl::string_view(++pa, count);
+}
+
ABSL_NAMESPACE_END
} // namespace absl