refactor: avoid quadratic behavior in backslash_halve() (#27827)

The original implementation has a worst-case of O(n^2). Every time
rem_backslash() is true, it calculates the length of the rest of the
string, and shift the rest of it to the left; backslash_halve_save()
copies the original string before doing backslash_halve().

The new implementation is O(n). It will find the first character where
rem_backslash() is true (it will do nothing if it's always false), and
shift the characters in-place; backslash_halve_save() avoids copying the
original string before doing backslash_halve().

1 files changed, 24 insertions, 6 deletions

diff --git a/src/nvim/charset.c b/src/nvim/charset.c
index 20bd364c7e..2e6f24b2d5 100644
--- a/src/nvim/charset.c
+++ b/src/nvim/charset.c
@@ -1457,10 +1457,20 @@ bool rem_backslash(const char *str)
 /// @param p
 void backslash_halve(char *p)
 {
-  for (; *p; p++) {
-    if (rem_backslash(p)) {
-      STRMOVE(p, p + 1);
+  for (; *p && !rem_backslash(p); p++) {}
+  if (*p != NUL) {
+    char *dst = p;
+    goto start;
+    while (*p != NUL) {
+      if (rem_backslash(p)) {
+start:
+        *dst++ = *(p + 1);
+        p += 2;
+      } else {
+        *dst++ = *p++;
+      }
     }
+    *dst = '\0';
   }
 }
 
@@ -1472,8 +1482,16 @@ void backslash_halve(char *p)
 char *backslash_halve_save(const char *p)
   FUNC_ATTR_NONNULL_ALL FUNC_ATTR_NONNULL_RET
 {
-  // TODO(philix): simplify and improve backslash_halve_save algorithm
-  char *res = xstrdup(p);
-  backslash_halve(res);
+  char *res = xmalloc(strlen(p) + 1);
+  char *dst = res;
+  while (*p != NUL) {
+    if (rem_backslash(p)) {
+      *dst++ = *(p + 1);
+      p += 2;
+    } else {
+      *dst++ = *p++;
+    }
+  }
+  *dst = '\0';
   return res;
 }