src/java.base/share/classes/java/lang/StringLatin1.java

rev 54615 : [mq]: 8222955-Optimize-String-replace-CharSequence-CharSequence-for-Latin1-encoded-strings

@@ -1,7 +1,7 @@
 /*
- * Copyright (c) 2015, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2015, 2019, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.  Oracle designates this

@@ -40,10 +40,18 @@
 import static java.lang.String.UTF16;
 import static java.lang.String.checkOffset;
 
 final class StringLatin1 {
 
+    /**
+     * The maximum size of array to allocate (unless necessary).
+     * Some VMs reserve some header words in an array.
+     * Attempts to allocate larger arrays may result in
+     * OutOfMemoryError: Requested array size exceeds VM limit
+     */
+    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
+
     public static char charAt(byte[] value, int index) {
         if (index < 0 || index >= value.length) {
             throw new StringIndexOutOfBoundsException(index);
         }
         return (char)(value[index] & 0xff);

@@ -328,10 +336,72 @@
             }
         }
         return null; // for string to return this;
     }
 
+    /**
+     * Precondition: targLen > 0
+     */
+    public static String replace(byte[] value, int valLen, byte[] targ,
+                                 int targLen, byte[] repl, int replLen)
+    {
+        int i;
+        if (valLen == 0 || (i = indexOf(value, valLen, targ, targLen, 0)) < 0) {
+            return null; // for string to return this;
+        }
+
+        // find and store indices of substrings to replace
+        int p = 0, j;
+        int[] pos = new int[16];
+        pos[0] = i;
+        i += targLen;
+        while ((j = indexOf(value, valLen, targ, targLen, i)) > 0) {
+            if (++p == pos.length) {
+                int cap = p << 1;
+                // overflow-conscious code
+                if (p >= MAX_ARRAY_SIZE - p) {
+                    if (p == MAX_ARRAY_SIZE) {
+                        throw new OutOfMemoryError();
+                    }
+                    cap = MAX_ARRAY_SIZE;
+                }
+                pos = Arrays.copyOf(pos, cap);
+            }
+            pos[p] = j;
+            i = j + targLen;
+        }
+
+        int deltaLen = replLen - targLen;
+        // overflow-conscious code
+        int resultLen = valLen + (++p) * deltaLen;
+        if (Integer.MAX_VALUE / p < deltaLen ||
+                Integer.MAX_VALUE - resultLen < 0) {
+            throw new OutOfMemoryError();
+        }
+        if (resultLen == 0) {
+            return "";
+        }
+
+        byte[] result = new byte[resultLen];
+        int posFrom = 0, posTo = 0;
+        for (int q = 0; q < p; ++q) {
+            int nextPos = pos[q];
+            while (posFrom < nextPos) {
+                result[posTo++] = value[posFrom++];
+            }
+            posFrom += targLen;
+            for (int k = 0; k < replLen; ++k) {
+                result[posTo++] = repl[k];
+            }
+        }
+        while (posFrom < valLen) {
+            result[posTo++] = value[posFrom++];
+        }
+
+        return new String(result, LATIN1);
+    }
+
     // case insensitive
     public static boolean regionMatchesCI(byte[] value, int toffset,
                                           byte[] other, int ooffset, int len) {
         int last = toffset + len;
         while (toffset < last) {