<repo_name>panost/StringCache<file_sep>/Bench/Intern.cs
﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
using ecl.Collections;

namespace Bench {
    [SimpleJob( RuntimeMoniker.Net50 )]
    public class InternTest {
        private string[] _array;
        public const int Count = 100;
        private Dictionary<string, string> _map;
        private StringCache _cache;
        [ GlobalSetup]
        public void GlobalSetup() {
            List<string> list = new List<string>();
            var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
            var random = new Random( 1253 );
            _map = new Dictionary<string, string>();
            _cache = new StringCache();
            char[] buffer = new char[ 32 ];
            while (true ) {
                int len = random.Next( 4, 30 );

                for ( int i = 0; i < len; i++ ) {
                    buffer[ i ] = chars[ random.Next( chars.Length ) ];
                }

                string str = new string( buffer, 0, len );
                if ( string.IsInterned( str ) == null ) {
                    if ( list.Count < Count ) {
                        string.Intern( str );
                        str = new string( buffer, 0, len );
                        list.Add( str );
                        _map.Add( str, str );
                        _cache.GetOrAdd( str );
                    } else if ( list.Count < Count*2 ) {
                        list.Add( str );
                    } else {
                        break;
                    }
                }
            }

            _array = list.ToArray();
        }

        [Benchmark]
        public int Dictionary() {
            int found = 0;
            foreach ( string s in _array ) {
                if ( _map.TryGetValue( s, out string f ) ) {
                    found++;
                }
            }
            return found;
        }
        [Benchmark]
        public int Intern() {
            int found = 0;
            foreach ( string s in _array ) {
                if ( string.IsInterned( s ) != null ) {
                    found++;
                }
            }
            return found;
        }
        [Benchmark]
        public int StringCache() {
            int found = 0;
            foreach ( string s in _array ) {
                if ( _cache.GetF( s ) != null ) {
                    found++;
                }
            }

            return found;
        }
    }
}
<file_sep>/README.md
# StringCache
A thread safe string cache that supports ReadOnlySpan
<file_sep>/StringCache/StringCache.Slot.cs
﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace ecl.Collections {

    partial class StringCache {

        [DebuggerDisplay( "Entry:{Key}, {HashCode}, {Next}" )]
        internal struct Entry {
            public int HashCode;
            public int Next;
            public string Key;

            public void Set( string key, int hashCode, int next ) {
                Key = key;
                HashCode = hashCode;
                Next = next;
            }
        }

        [MethodImpl( MethodImplOptions.AggressiveInlining )]
        public static uint FastMod( uint value, uint divisor, ulong multiplier ) {
            return (uint)( ( ( ( ( multiplier * value ) >> 32 ) + 1 ) * divisor ) >> 32 );
        }

        public static ulong GetFastModMultiplier( uint divisor ) =>
            ulong.MaxValue / divisor + 1;

        public static int NextOdd( int i ) {
            i |= 1;
            while ( i % 3 == 0 || i % 5 == 0 || i % 7 == 0 ) {
                i += 2;
            }
            return i;
        }

        private class Slot {
            public int Count;
            private readonly Entry[] _entries;
            private readonly int[] _buckets;
            private readonly ulong _fastModBucketsMultiplier;

            public Slot( int capacity, int prime ) {
                _fastModBucketsMultiplier = IntPtr.Size == 8 ? GetFastModMultiplier( (uint)prime ) : 0;
                _buckets = new int[ prime ];
                _entries = new Entry[ capacity ];
            }

            public Slot( HashSet<string> set ) {
                int capacity = set.Count;
                if ( capacity < 16 ) {
                    capacity = 16;
                }
                _entries = new Entry[ capacity ];
                _buckets = new int[ NextOdd( capacity ) ];
                _fastModBucketsMultiplier = IntPtr.Size == 8 ? GetFastModMultiplier( (uint)_buckets.Length ) : 0;
                foreach ( string s in set ) {
                    Add( s, GetOrdinalHashCode( s ) );
                }
            }

            public string this[ int index ] => _entries[ index ].Key;

            [MethodImpl( MethodImplOptions.AggressiveInlining )]
            private ref int GetBucketSlot( int hashCode ) {
                int[] buckets = _buckets;

                if ( IntPtr.Size == 8 ) {
                    return ref buckets[ FastMod( (uint)hashCode, (uint)buckets.Length, _fastModBucketsMultiplier ) ];
                }

                return ref buckets[ (uint)hashCode % (uint)buckets.Length ];
            }

            private void Add( string key, int hashCode ) {
                ref int i = ref GetBucketSlot( hashCode );
                _entries[ Count++ ].Set( key, hashCode, i );
                i = Count;
            }

            private void Add( Entry[] entries ) {
                for ( int j = 0; j < entries.Length; j++ ) {
                    ref Entry ptr = ref entries[ j ];
                    Add( ptr.Key, ptr.HashCode );
                }
            }

            public int IndexOf( ReadOnlySpan<char> key, int hashCode ) {
                int i = GetBucketSlot( hashCode );
                while ( i > 0 ) {
                    i--;
                    ref var ptr = ref _entries[ i ];

                    if ( ptr.HashCode == hashCode && key.SequenceEqual( ptr.Key ) )
                        return i;
                    i = ptr.Next;
                }

                return -1;
            }

            public string Find( ReadOnlySpan<char> key, int hashCode ) {
                int i = GetBucketSlot( hashCode );
                while ( i > 0 ) {
                    i--;
                    ref var ptr = ref _entries[ i ];

                    if ( ptr.HashCode == hashCode && key.SequenceEqual( ptr.Key ) )
                        return ptr.Key;
                    i = ptr.Next;
                }

                return null;
            }

            private Slot Resize() {
                int newCapacity = _entries.Length * 2;
                var slot = new Slot( newCapacity, NextOdd( newCapacity ) );
                slot.Add( _entries );
                return slot;
            }

            public string Insert( StringCache owner, ReadOnlySpan<char> key, int hashCode, string str ) {
                ref int lead = ref GetBucketSlot( hashCode );
                int i = lead;
                while ( i > 0 ) {
                    i--;
                    ref var ptr = ref _entries[ i ];

                    if ( ptr.HashCode == hashCode && key.SequenceEqual( ptr.Key ) )
                        return ptr.Key;
                    i = ptr.Next;
                }

                str ??= new string( key );

                if ( Count == _entries.Length ) {
                    var slot = Resize();
                    slot.Add( str, hashCode );
                    owner._slot = slot;
                } else {
                    _entries[ Count++ ].Set( str, hashCode, lead );
                    lead = Count;
                }

                return str;
            }

            public Enumerator GetEnumerator() {
                return new Enumerator( _entries, Count );
            }
        }
    }
}<file_sep>/StringCache/StringCache.cs
﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;
using System.Text;
using System.Threading;

namespace ecl.Collections {
    public partial class StringCache : IEnumerable<string> {
        public readonly StringCache Parent;
        private Slot _slot;

        public StringCache( StringCache parent ) {
            Parent = parent;
            _slot = new Slot( 16, 13 );
        }

        public StringCache()
            : this( (StringCache)null ) {
        }

        public int Count => _slot.Count;

        public StringCache( IEnumerable<string> str, StringCache parent ) {
            HashSet<string> set;
            if ( parent != null ) {
                Parent = parent;
                set = new HashSet<string>();
                foreach ( var s in str ) {
                    if ( parent.Get( s ) == null ) {
                        set.Add( s );
                    }
                }
            } else {
                set = new HashSet<string>( str );
            }

            _slot = set.Count > 0 ? new Slot( set ) : new Slot( 16, 13 );
        }

        public StringCache( params string[] args )
            : this( args, (StringCache)null ) {
        }

        internal static readonly uint CaseSensitiveSeed = GetRandomUint( 0x15051505 );

        private static uint GetRandomUint( int someSeed ) {
#if DEBUG
            return (uint)someSeed;
#else
            var rnd = new Random( Environment.TickCount ^ someSeed );
            return (uint)HashCode.Combine( rnd.Next(), rnd.Next() );
#endif
        }

        public static int GetOrdinalHashCode( ReadOnlySpan<char> span ) {
            uint hash = CaseSensitiveSeed;
            foreach ( var ch in span ) {
                hash = ( BitOperations.RotateLeft( hash, 5 ) + hash ) ^ ch;
            }

            return (int)hash;
        }


        public string Get( ReadOnlySpan<byte> key ) {
            if ( key.Length < 256 ) {
                Span<char> name = stackalloc char[ 512 ];
                if ( Encoding.UTF8.GetChars( key, name ) == key.Length ) {
                    return Get( name );
                }
            }

            return null;
        }
        public string GetF( ReadOnlySpan<char> key, int hashCode ) {
            return _slot.Find( key, hashCode ) ?? Parent?.GetF( key, hashCode );
        }
        public string GetF( ReadOnlySpan<char> key ) {
            int hashCode = GetOrdinalHashCode( key );
            return GetF( key, hashCode );
        }
        private string Get( ReadOnlySpan<char> key, int hashCode ) {
            var slot = Volatile.Read( ref _slot );
            int idx = slot.IndexOf( key, hashCode );
            return idx >= 0 ? slot[ idx ] : Parent?.Get( key, hashCode );
        }

        public string Get( ReadOnlySpan<char> key ) {
            return Get( key, GetOrdinalHashCode( key ) );
        }

        public string GetOrAdd( ReadOnlySpan<char> key ) {
            var hashCode = GetOrdinalHashCode( key );
            return Get( key, hashCode ) ?? Add( key, hashCode );
        }

        public string GetOrAdd( ReadOnlySpan<byte> key ) {
            if ( key.Length < 256 ) {
                Span<char> name = stackalloc char[ 512 ];
                if ( Encoding.UTF8.GetChars( key, name ) == key.Length ) {
                    return GetOrAdd( name );
                }
            }

            return null;
        }

        public string GetOrAdd( string key ) {
            var hashCode = GetOrdinalHashCode( key );
            return Get( key, hashCode ) ?? Add( key, hashCode );
        }

        private readonly object _addition = new();

        private string Add( ReadOnlySpan<char> key, int hashCode ) {
            lock ( _addition ) {
                return _slot.Insert( this, key, hashCode, null );
            }
        }

        private string Add( string key, int hashCode ) {
            lock ( _addition ) {
                return _slot.Insert( this, key, hashCode, key );
            }
        }

        public struct Enumerator : IEnumerator<string> {
            private readonly Entry[] _entries;
            private readonly int _count;
            private int _index;
            internal Enumerator( Entry[] entries, int count ) {
                _entries = entries;
                _count = count;
                _index = -1;
            }

            public bool MoveNext() {
                int idx = _index + 1;
                if ( idx < _count ) {
                    _index = idx;
                    return true;
                }

                return false;
            }

            public void Reset() {
                _index = -1;
            }

            public string Current => (uint)_index < (uint)_entries.Length? _entries[ _index ].Key:null;

            object IEnumerator.Current => Current;


            void IDisposable.Dispose() {
            }

        }
        public Enumerator GetEnumerator() {
            return _slot.GetEnumerator();
        }

        #region Implementation of IEnumerable

        IEnumerator<string> IEnumerable<string>.GetEnumerator() {
            return GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        #endregion
    }
}<file_sep>/Bench/Program.cs
﻿using System;
using System.Diagnostics;
using BenchmarkDotNet.Running;

namespace Bench {
    class Program {
        static void Main( string[] args ) {
#if DEBUG
            Test();
#else
            BenchmarkRunner.Run( typeof( InternTest ) );
#endif
        }

        static void Test() {
            var t = new InternTest();
            t.GlobalSetup();
            if ( t.Dictionary() != InternTest.Count ) {
                Debug.WriteLine( "Dictionary" );
            }
            if ( t.Intern() != InternTest.Count ) {
                Debug.WriteLine( "Intern" );
            }
            if ( t.StringCache() != InternTest.Count ) {
                Debug.WriteLine( "StringCache" );
            }
        }
    }
}
