Strings: efficient Replace implementation

Author: Serge Billault

Download

SinglePassReplace

Description

Heap memory efficient, single pass strings replacements.

The code take advantage of the fact that the modified string length can easily be known in advance and allocated only once.

The user has the option to hint the code with the expected range of occurences in which case there will be exactly one, and only one single heap allocation.

Usage

Copy script into your Asset folder

Code ( StringExtension.cs )

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
 
 
//********************************************************************************************************
//
//********************************************************************************************************
 
namespace YOUR_NAMESPACE
{
    static public class StringExtension
    {
        //************************************************************************************************
        //
        //************************************************************************************************
 
        static private readonly char[] hex = "0123456789ABCDEF".ToCharArray();
 
        //************************************************************************************************
        //
        //************************************************************************************************
 
        static public string LongToHexStr( ulong val )
        {
            char[] dst = new char[ 18 ];
 
		    dst[  0 ] = '0';
		    dst[  1 ] = 'X';
		    dst[  2 ] = hex[ ( val >> 60 ) & 0XF ];
		    dst[  3 ] = hex[ ( val >> 56 ) & 0XF ];
		    dst[  4 ] = hex[ ( val >> 52 ) & 0XF ];
		    dst[  5 ] = hex[ ( val >> 48 ) & 0XF ];
		    dst[  6 ] = hex[ ( val >> 44 ) & 0XF ];
		    dst[  7 ] = hex[ ( val >> 40 ) & 0XF ];
		    dst[  8 ] = hex[ ( val >> 36 ) & 0XF ];
		    dst[  9 ] = hex[ ( val >> 32 ) & 0XF ];
		    dst[ 10 ] = hex[ ( val >> 28 ) & 0XF ];
		    dst[ 11 ] = hex[ ( val >> 24 ) & 0XF ];
		    dst[ 12 ] = hex[ ( val >> 20 ) & 0XF ];
		    dst[ 13 ] = hex[ ( val >> 16 ) & 0XF ];
		    dst[ 14 ] = hex[ ( val >> 12 ) & 0XF ];
		    dst[ 15 ] = hex[ ( val >> 8  ) & 0XF ];
		    dst[ 16 ] = hex[ ( val >> 4  ) & 0XF ];
		    dst[ 17 ] = hex[ ( val >> 0  ) & 0XF ];
 
            return new string( dst );
        }
 
        //************************************************************************************************
        //
        //************************************************************************************************
 
        private const int LITTERAL_BASE_UPPER = 'A' + 10;
 
        private const int LITTERAL_BASE_LOWER = 'a' + 10;
 
        static public ulong HexStrToLong( string str )
        {
            ulong val = 0;
 
            for( int c = str.Length - 1, s = 0; c >= 0; --c, s += 4 )
            {
                char chr = str[ c ];
 
                if     ( ( chr >= '0' ) && ( chr <= '9' ) ) val |= ( ( ulong )( chr - '0' )                 << s );
 
                else if( ( chr >= 'A' ) && ( chr <= 'F' ) ) val |= ( ( ulong )( chr - LITTERAL_BASE_UPPER ) << s );
 
                else if( ( chr >= 'a' ) && ( chr <= 'f' ) ) val |= ( ( ulong )( chr - LITTERAL_BASE_LOWER ) << s );
 
                else break;
            }
 
            return val;
        }
 
 	    //********************************************************************************************
	    //
	    //********************************************************************************************
 
        static public string SinglePassReplace( this string str, string occ, string with, StringComparison opt = StringComparison.Ordinal, int expected = 0 )
        {
            if( string.IsNullOrEmpty( str ) ) return str;
 
            if( string.IsNullOrEmpty( occ ) ) return str;
 
            if( str.Length   <   occ.Length ) return str;
 
            if( with == null )                return str;
 
 
            int   occ_len  = occ.Length;
 
            int   capacity = Mathf.Max( 32, expected );
 
            int   count    = 0;
 
            int[] replacements = new int[ capacity ];
 
            for( int pos = 0; ; pos += occ_len )
            {
                if( ( pos = str.IndexOf( occ, pos, opt ) ) < 0 ) break;
 
                if( count >= capacity ) System.Array.Resize( ref replacements, capacity << 1 );
 
                replacements[ count++ ] = pos;
            }
 
 
            if( count > 0 )
            {
                int    rpl_len = with.Length;
 
                int    dlt     = rpl_len - occ_len;
 
                int    src     = 0;
 
                int    dst     = 0;
 
                int    dst_len = str.Length + ( count * dlt );
 
                char[] content = new char[ dst_len ];
 
                for( int rpl = 0; rpl < count; ++rpl, src += occ_len )
                {
                    int pos = replacements[ rpl ] + ( rpl * dlt );
 
                    for( ; dst < pos;                ) content[ dst++ ] = str [ src++ ]; // memcpy if eumlated by IL generator (1).
 
                    for( int ins = 0; ins < rpl_len; ) content[ dst++ ] = with[ ins++ ]; // memcpy if eumlated by IL generator (1).
                }
 
                while( dst < dst_len ) content[ dst++ ] = str[ src++ ];                  // memcpy if eumlated by IL generator (1).
 
                return new string( content );                                            // (1): check with your compiler's authors if they translate the cpy_blk instruction
            }
                                                                                         // to intrinsics on your target platforms when emulating memcpy.
            return str;
        }
    }
}