6
\$\begingroup\$

I needed a data structure to quickly find all previously inserted values, that have the given string as key or substring (full text search).

At first, I tried out some tree structures (infix trie/tree) and was shocked by the slow insertion time and memory usage.

That's when I developed the InfixDictionary<T>, which is internally based on a Dictionary<string, Set<T>>. I previously used something like it at work and it worked flawlessly, now I rewrote it at home and wanted to get it reviewed.

I am especially afraid of synchronization/volatility issues. Is it enough to synchronize on the Dictionary itself to guarantee access without trouble? I know the internals of the Dictionary are not volatile.

An easy example of what exactly I want:

Imagine you have the contact 'Dr. Richard Stallman' with the phone number '\$+123456\$' who works for the 'fsf'. Now, you can only remember his first name: 'richard', that he works for the 'fsf', and he is a 'Dr.'. Your search-string to find him, would be, for example:

"fsf richard Dr."

You'd also find him searching for:

"ri ic ch ar ric chard f + 123"
using System;
using System.Collections.Generic;
using System.Linq;

namespace at.loup.CSUtilities.Collections
{
    public class InfixDictionary<T>
    {
        private readonly string[] splitStrings = null;
        private readonly Dictionary<string, HashSet<T>> data = new Dictionary<string, HashSet<T>>();

        private bool normalizeKeysToUpper;

        public InfixDictionary(bool normalizeKeysToUpper = true, params string[] splitStrings)
        {
            this.splitStrings = splitStrings;
            this.normalizeKeysToUpper = normalizeKeysToUpper;
        }

        public InfixDictionary(bool normalizeKeysToUpper = true)
        {
            splitStrings = splitStrings = new[] { " " };
            this.normalizeKeysToUpper = normalizeKeysToUpper;
        }

        #region diagnostics

        public int SubKeyCount
        {
            get { return data.Count; }
        }

        #endregion diagnostics

        #region lookup Operations

        /// <summary>
        /// Lookup the values associated with the subKeys contained in the given key.<para/>
        /// Never returns null
        /// </summary>
        /// <param name="key">
        /// Lookup key.<para/>
        /// Will be splitted to subKeys if splitStrings is not null.<para/>
        /// Will be normalized with .ToUpper() if normalizeKeysToUpper is true.<para/>
        /// If you give "B A" and splitStrings contains space (" ") all entries containing
        /// subKeys with "A" and "B" will return.<para/>
        /// SubKey order does not matter.<para/>
        /// </param>
        /// <returns>All objects having the subkeys of the splitted given key.</returns>
        public IEnumerable<T> Lookup(string key)
        {
            if (key == null || key.Length == 0)
                return new List<T>();

            if (normalizeKeysToUpper)
                key = key.ToUpper();

            HashSet<T> tmp = null;

            if (splitStrings != null)
            {
                HashSet<IEnumerable<T>> hashSets = new HashSet<IEnumerable<T>>();

                foreach (string subKey in key.Split(splitStrings, StringSplitOptions.RemoveEmptyEntries))
                {
                    if (!data.TryGetValue(subKey, out tmp))
                        return new List<T>();

                    hashSets.Add(tmp);
                }
                if (hashSets.Count == 0)
                    return new List<T>();
                if (hashSets.Count > 1)
                {
                    IEnumerable<IEnumerable<T>> hashSetsList = hashSets.ToList();

                    // first element is duplicated so we can later use a generic way ...
                    // to aggregate all collected hashsets with only one lock per ...
                    // aggregation
                    // it's necessary to explicitly acquire the first element to lock it
                    IEnumerable<T> first = hashSetsList.First();

                    lock (first) // lock HashSet element during duplication
                        first = new List<T>(first);

                    return hashSetsList
                        .Skip(1) // first element is the aggregation seed
                        .Aggregate(first,
                            (o, n) =>
                            {
                                lock (n)
                                {
                                    return o.Intersect(n);
                                }
                            });
                }
            }
            // if the key is never split we can simply lookup with it
            else if (!data.TryGetValue(key, out tmp))
                return new List<T>();

            lock (tmp)
                return tmp.ToList();
        }

        /// <summary>
        /// Looks up one value with the given key. If none is found returns default(<typeparamref name="T"/>)
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public T LookupOne(string key)
        {
            var lookedUpResults = Lookup(key);
            if (lookedUpResults.Count() != 0)
                return lookedUpResults.First();

            return default(T);
        }

        #endregion lookup Operations

        #region add Operations

        public void Add(T value, params string[] keys)
        {
            if (keys == null)
                return;

            if (keys.Length == 1)
            {
                if (splitStrings == null)
                    AddInternalThreadsafe(keys[0], value);
                else
                    foreach (string subKey in keys[0].Split(splitStrings, StringSplitOptions.RemoveEmptyEntries))
                        AddInternalThreadsafe(subKey, value);
            }
            else
            {
                if (splitStrings == null)
                    foreach (string key in keys)
                        AddInternalThreadsafe(key, value);
                else
                    foreach (string key in keys)
                        foreach (string subKey in key.Split(splitStrings, StringSplitOptions.RemoveEmptyEntries))
                            AddInternalThreadsafe(subKey, value);
            }

            return;
        }

        private void AddInternalThreadsafe(string key, T value)
        {
            if (normalizeKeysToUpper)
                key = key.ToUpper();
            for (int startIndex = 0; startIndex < key.Length; startIndex++)
            {
                for (int length = 1; length <= key.Length - startIndex; length++)
                {
                    string substring = key.Substring(startIndex, length);

                    HashSet<T> tmp;
                    if (!data.TryGetValue(substring, out tmp))
                        lock (data)
                            if (!data.TryGetValue(substring, out tmp))
                                data[substring] = tmp = new HashSet<T>();

                    lock (tmp)
                        tmp.Add(value);
                }
            }
        }

        /// <summary>
        /// Works exactly like Add(value, key);
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public T this[string key]
        {
            set
            {
                Add(value, key);
            }
        }

        #endregion add Operations

        #region cleaning Operations

        /// <summary>
        /// Purges the given value from the datastructure: This method is blocking the dictionary and slow.
        /// </summary>
        /// <param name="value"></param>
        public void Remove(T value)
        {
            List<string> emptySets = new List<string>();
            lock (data)
            {
                foreach (var tuple in data)
                    if (tuple.Value.Remove(value) && tuple.Value.Count == 0)
                        emptySets.Add(tuple.Key);

                foreach (string subKey in emptySets)
                    data.Remove(subKey);
            }
        }

        /// <summary>
        /// Removes given key (or it's subkeys if splitStrings != null) from the internal dictionary
        /// </summary>
        /// <param name="key"></param>
        public void PurgeKey(string key)
        {
            lock (data)
            {
                if (splitStrings == null)
                    for (int startIndex = 0; startIndex < key.Length; startIndex++)
                        for (int length = 1; length <= key.Length - startIndex; length++)
                            data[key.Substring(startIndex, length)] = null;
                else
                    foreach (string subKey in key.Split(splitStrings, StringSplitOptions.RemoveEmptyEntries))
                        for (int startIndex = 0; startIndex < subKey.Length; startIndex++)
                            for (int length = 1; length <= subKey.Length - startIndex; length++)
                                data[subKey.Substring(startIndex, length)] = null;
            }
        }

        public void Clear()
        {
            lock (data)
                data.Clear();
        }

        #endregion cleaning Operations
    }
}

As asked for, a few test cases:

internal class Tests
{
    public static void Main(string[] args)
    {
        InfixDictionary<object> id = new InfixDictionary<object>();

        id.Add("Object 1", "Steve Jobs", "+123");
        id.Add("Object 2", "Steve Ballmer", "+1234");
        id.Add("Object 3", "Bill Gates", "+12345");
        id.Add("Object 4", "John Carmack ", "+123456");

        Test("TEST 1", () => (
            id.Lookup("Steve Jobs +123").Contains("Object 1") &&
            id.Lookup("Steve Jobs +123").Count() == 1
        ));

        Test("TEST 2", () => (
            id.Lookup("steve").Count() == 2
        ));

        Test("TEST 3", () => (
            id.Lookup("+").Count() == 4
        ));

        Test("TEST 4", () => (
            id.Lookup("S B O J  E V E T S 3 2 1 +").Contains("Object 1") &&
            id.Lookup("S B O J  E V E T S 3 2 1 +").Count() == 1
        ));

        Test("TEST 5", () => (
            id.Lookup("jobs+").Count() == 0
        ));

        // case insensitivity
        Test("TEST 5", () => (
            id.Lookup("jobs").Contains("Object 1") &&
            id.Lookup("JoBs OBs").Contains("Object 1") &&
            id.Lookup("jobs").Count() == 1
        ));


        Console.ReadKey();
    }

    public static void Test(string name, Func<bool> test)
    {
        Console.WriteLine("Test<{0}>: {1}", name, test() ? "OK" : "FAIL");
    }
}
\$\endgroup\$
2
\$\begingroup\$
lock (first) // lock HashSet element during duplication
    first = new List<T>(first);  

This will result in compiler warning

CS0728 C# Possibly incorrect assignment to local '' which is the argument to a using or lock statement. The Dispose call or unlocking will happen on the original value of the local.

Related to locking: https://stackoverflow.com/a/11775353/2655508

And basically I quite don't understand what you want to prevent with this. The hashSets variable is a method scoped variable. There won't happen any threading issues here.

A much easier way would be

IEnumerable<T> first = new List<T>(hashSetsList.First());

but if you really are concerned about thread safety, you really should use the ConcurrentDictionary<TKey, TValue>.


           foreach (string subKey in key.Split(splitStrings, StringSplitOptions.RemoveEmptyEntries))
            {
                if (!data.TryGetValue(subKey, out tmp))
                    return new List<T>();

                hashSets.Add(tmp);
            }
            if (hashSets.Count == 0)
                return new List<T>();
            if (hashSets.Count > 1)
            {
                IEnumerable<IEnumerable<T>> hashSetsList = hashSets.ToList();

I don't see a reason to check for hashSets.Count > 1. What else could Count be at this place ?

A better way to write this would be to store the result of the Split() in a variable and return a new List<T> if Length == 0. In this way neither of these checks about the Count property would be needed.

The else if as itself isn't needed at all because if splitStrings != null it won't be reached. So changing it to a simple if will make it more obvious that the condition is about the TryGetValue.

Like so

public IEnumerable<T> Lookup(string key)
{
    if (key == null || key.Length == 0)
    {
        return new List<T>();
    }

    if (normalizeKeysToUpper)
    {
        key = key.ToUpper();
    }

    HashSet<T> tmp = null;

    if (splitStrings != null)
    {
        HashSet<IEnumerable<T>> hashSets = new HashSet<IEnumerable<T>>();
        string[] subkeys = key.Split(splitStrings, StringSplitOptions.RemoveEmptyEntries);
        if (subkeys.Length == 0)
        {
            return new List<T>();
        }

        foreach (string subKey in subkeys)
        {
            if (!data.TryGetValue(subKey, out tmp))
            {
                return new List<T>();
            }
            hashSets.Add(tmp);
        }
        IEnumerable<IEnumerable<T>> hashSetsList = hashSets.ToList();

        // first element is duplicated so we can later use a generic way ...
        // to aggregate all collected hashsets with only one lock per ...
        // aggregation
        // it's necessary to explicitly acquire the first element to lock it
        IEnumerable<T> first = new List<T>(hashSetsList.First());

        return hashSetsList
            .Skip(1) // first element is the aggregation seed
            .Aggregate(first,
                (o, n) =>
                {
                    lock (n)
                    {
                        return o.Intersect(n);
                    }
                });

    }
    // if the key is never split we can simply lookup with it

    if (!data.TryGetValue(key, out tmp))
    {
        return new List<T>();
    }

    lock (tmp)
    {
        return tmp.ToList();
    }
}

Using braces {} would make your code easier to read and also less error prone.


public void Add(T value, params string[] keys)
{
    if (keys == null)
        return;

    if (keys.Length == 1)
    {
        if (splitStrings == null)
            AddInternalThreadsafe(keys[0], value);
        else
            foreach (string subKey in keys[0].Split(splitStrings, StringSplitOptions.RemoveEmptyEntries))
                AddInternalThreadsafe(subKey, value);
    }
    else
    {
        if (splitStrings == null)
            foreach (string key in keys)
                AddInternalThreadsafe(key, value);
        else
            foreach (string key in keys)
                foreach (string subKey in key.Split(splitStrings, StringSplitOptions.RemoveEmptyEntries))
                    AddInternalThreadsafe(subKey, value);
    }

    return;
}  

here you have duplicated code which can be easily removed like so

public void Add(T value, params string[] keys)
{
    if (keys == null)
    {
        return;
    }

    if (splitStrings == null)
    {
        foreach (string key in keys)
        {
            AddInternalThreadsafe(key, value);
        }
        return;
    }


    foreach (string key in keys)
    {
        foreach (string subKey in key.Split(splitStrings, StringSplitOptions.RemoveEmptyEntries))
        {
            AddInternalThreadsafe(subKey, value);
        }
    }

}  

Regions

Please read are-regions-an-antipattern-or-code-smell

Is there a good use for regions?

No. There was a legacy use: generated code. Still, code generation tools just have to use partial classes instead. If C# has regions support, it's mostly because this legacy use, and because now that too many people used regions in their code, it would be impossible to remove them without breaking existent codebases.

Think about it as about goto. The fact that the language or the IDE supports a feature doesn't mean that it should be used daily. StyleCop SA1124 rule is clear: you should not use regions. Never.


Edit regarding the comments

I am locking the HashSet, because List and HashSet constructors use the Iterator of the given IEnumerable: There could be a InvalidOperationException if a HashSet was changed during the construction of the copy, no?

Let us see what you are doing:

You query the data dictionary for the keys/subkeys and if you find matching keys you will add the value which is a HashSet to HashSet<IEnumerable<T>> hashSets = new HashSet<IEnumerable<T>>();.

Then you call ToList() on this hashset which is followed by a call to First() to get the first hashset in this HashSet<HashSet<T>>.

Then you are doing the lock(first) for duplication.

Now let us assume the data dictionary, which isn't threadsafe, will now be changed in a way that for exactly this first HashSet<T> all items will be set to null. So calling lock(first) won't help anything in this szenario because the underlaying items are the same objects like in the data dictionary.

Any other change of first like removing items can't happen, because you have called ToList() on a method scoped variable ( hashSetsList = hashSets.ToList();) before you called First() on it.

There is the hidden case of hashSet.Count being 1, in which case a copy of tmp is returned at the end of the method

DON'T DO SOMETHING LIKE THIS really. Hidden cases are hard to find and a lot harder to maintain . If you would have to fix a bug in 6 months, you wouldn't know about this hidden "feature" of your code anymore.

No let us fix this hidden "feature" by adding one condition checking Count ==1 on the hashSets variable and by removing the useless locks like so

   public IEnumerable<T> Lookup(string key)
    {
        if (key == null || key.Length == 0)
        {
            return new List<T>();
        }

        if (normalizeKeysToUpper)
        {
            key = key.ToUpper();
        }

        if (splitStrings != null)
        {
            HashSet<IEnumerable<T>> hashSets = new HashSet<IEnumerable<T>>();
            string[] subkeys = key.Split(splitStrings, StringSplitOptions.RemoveEmptyEntries);
            if (subkeys.Length == 0)
            {
                return new List<T>();
            }

            foreach (string subKey in subkeys)
            {
                HashSet<T> currentKeySet;
                if (!data.TryGetValue(subKey, out currentKeySet))
                {
                    return new List<T>();
                }
                hashSets.Add(currentKeySet);
            }


            IEnumerable<IEnumerable<T>> hashSetsList = hashSets.ToList();

            // first element is duplicated so we can later use a generic way ...
            // to aggregate all collected hashsets with only one lock per ...
            // aggregation
            // it's necessary to explicitly acquire the first element to lock it
            IEnumerable<T> first = new List<T>(hashSetsList.First());

            if (hashSets.Count == 1)
            {
                return first;
            }

            return hashSetsList
            .Skip(1) // first element is the aggregation seed
            .Aggregate(first,
                (o, n) =>
                {
                    lock (n)
                    {
                        return o.Intersect(n);
                    }
                });

        }
        // if the key is never split we can simply lookup with it
        HashSet<T> tmp = null;
        if (!data.TryGetValue(key, out tmp))
        {
            return new List<T>();
        }

        return tmp.ToList();

    }

To keep thread safety I would like to suggest to use a ConcurrentDictionary<string, ConcurrentBag<T> instead of the Dictionary<string, HashSet<T>), but you will need to change the adding of an item, because a ConcurrentBag can have duplicates. In this way not only the "dictionary" is threadsafe, but also the values of the "dictionary".

Keep in mind the remarks of ConcurrentBag<T>

Bags are useful for storing objects when ordering doesn't matter, and unlike sets, bags support duplicates. ConcurrentBag is a thread-safe bag implementation, optimized for scenarios where the same thread will be both producing and consuming data stored in the bag.

\$\endgroup\$
  • \$\begingroup\$ The compiler warning is incorrect in this case: What is in first no longer needs to be locked as soon as first is reassigned. I am locking the HashSet, because List and HashSet constructors use the Iterator of the given IEnumerable: There could be a InvalidOperationException if a HashSet was changed during the construction of the copy, no? I am not locking the hashSets variable by the way! cont. \$\endgroup\$ – Traubenfuchs Aug 27 '15 at 16:53
  • \$\begingroup\$ The ConcurrentDictionary is a great idea and should make most things much easier! There is the hidden case of hashSet.Count being 1, in which case a copy of tmp is returned at the end of the method. \$\endgroup\$ – Traubenfuchs Aug 27 '15 at 16:56
  • \$\begingroup\$ I actually only added the regions to make my code look less embarrassing: Most open source C# code I read contained them! \$\endgroup\$ – Traubenfuchs Aug 27 '15 at 16:56
1
\$\begingroup\$

I'll look more into it later but here's what I have now.

I did some refactoring too. You really should use the {}.

The two main changes I made are to derive your class from the CuncurrentDictionary and to use Linq Parallel for generating substrings. It also should be adapted to use it for removing keys because there are two very ugly loops.

public class InfixDictionary<T> : ConcurrentDictionary<string, HashSet<T>>
{
    private readonly string[] _delimiters = null;

    private readonly bool _normalizeKeys;

    public InfixDictionary(bool normalizeKeys = true, params string[] delimiters)
    {
        _delimiters = delimiters;
        _normalizeKeys = normalizeKeys;
    }

    public InfixDictionary(bool normalizeKeys = true)
    {
        _delimiters = new[] { " " };
        _normalizeKeys = normalizeKeys;
    }

    #region lookup Operations

    /// <summary>
    /// Lookup the values associated with the subKeys contained in the given key.<para/>
    /// Never returns null
    /// </summary>
    /// <param name="key">
    /// Lookup key.<para/>
    /// Will be splitted to subKeys if delimiters is not null.<para/>
    /// Will be normalized with .ToUpper() if _normalizeKeys is true.<para/>
    /// If you give "B A" and delimiters contains space (" ") all entries containing
    /// subKeys with "A" and "B" will return.<para/>
    /// SubKey order does not matter.<para/>
    /// </param>
    /// <returns>All objects having the subkeys of the splitted given key.</returns>
    public IEnumerable<T> Lookup(string key)
    {
        if (string.IsNullOrEmpty(key))
        {
            return Enumerable.Empty<T>();
        }

        if (_normalizeKeys)
        {
            key = key.ToUpper();
        }

        HashSet<T> tmp = null;

        // if the key is never split we can simply lookup with it
        if (_delimiters == null)
        {
            if (!TryGetValue(key, out tmp))
            {
                return Enumerable.Empty<T>();
            }
        }

        var hashSets = new HashSet<IEnumerable<T>>();

        var tokens = key.Split(_delimiters, StringSplitOptions.RemoveEmptyEntries);
        foreach (var token in tokens)
        {
            if (!TryGetValue(token, out tmp))
            {
                return Enumerable.Empty<T>();
            }

            hashSets.Add(tmp);
        }

        if (hashSets.Count == 0)
        {
            return Enumerable.Empty<T>();
        }

        if (hashSets.Count <= 1)
        {
            return tmp;
        }

        IEnumerable<IEnumerable<T>> hashSetsList = hashSets.ToList();

        // first element is duplicated so we can later use a generic way ...
        // to aggregate all collected hashsets with only one lock per ...
        // aggregation
        // it's necessary to explicitly acquire the first element to lock it
        var first = hashSetsList.First();

        // lock HashSet element during duplication
        lock (first)
        {
            first = new List<T>(first);
        }

        return hashSetsList
            .Skip(1) // first element is the aggregation seed
            .Aggregate(first,
                (o, n) =>
                {
                    lock (n)
                    {
                        return o.Intersect(n);
                    }
                });
    }

    /// <summary>
    /// Looks up one value with the given key. If none is found returns default(<typeparamref name="T"/>)
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public T LookupOne(string key)
    {
        var lookedUpResults = Lookup(key);
        return lookedUpResults.FirstOrDefault();
    }

    #endregion lookup Operations

    #region add Operations

    public void Add(T value, params string[] keys)
    {
        if (keys == null)
        {
            return;
        }

        var splittted =
            keys
            .Select(k => k.Split(_delimiters, StringSplitOptions.RemoveEmptyEntries))
            .SelectMany(k => k)
            .Select(k => _normalizeKeys ? k.ToUpper() : k);

        var substrings =
            splittted
                .AsParallel()
                .Select(GenerateSubstrings)
                .SelectMany(s => s)
                .ToList();

        foreach (var substring in substrings)
        {
            HashSet<T> values;
            if (!TryGetValue(substring, out values))
            {
                this[substring] = values = new HashSet<T>();
            }

            values.Add(value);
        }
    }

    private static IEnumerable<string> GenerateSubstrings(string key)
    {
        for (var startIndex = 0; startIndex < key.Length; startIndex++)
        {
            for (var length = 1; length <= key.Length - startIndex; length++)
            {
                yield return key.Substring(startIndex, length);
            }
        }
    }        

    #endregion add Operations

    #region cleaning Operations

    /// <summary>
    /// Purges the given value from the datastructure: This method is blocking the dictionary and slow.
    /// </summary>
    /// <param name="value"></param>
    public void Remove(T value)
    {
        var emptySets = new List<string>();
        lock (this)
        {
            foreach (var tuple in this)
            {
                if (tuple.Value.Remove(value) && tuple.Value.Count == 0)
                {
                    emptySets.Add(tuple.Key);
                }
            }

            foreach (var subKey in emptySets)
            {
                //this.Remove(subKey);
            }
        }
    }

    /// <summary>
    /// Removes given key (or it's subkeys if delimiters != null) from the internal dictionary
    /// </summary>
    /// <param name="key"></param>
    public void PurgeKey(string key)
    {
        lock (this)
        {
            if (_delimiters == null)
            {
                for (var startIndex = 0; startIndex < key.Length; startIndex++)
                {
                    for (var length = 1; length <= key.Length - startIndex; length++)
                    {
                        this[key.Substring(startIndex, length)] = null;
                    }
                }
            }
            else
            {
                foreach (string subKey in key.Split(_delimiters, StringSplitOptions.RemoveEmptyEntries))
                {
                    for (var startIndex = 0; startIndex < subKey.Length; startIndex++)
                    {
                        for (var length = 1; length <= subKey.Length - startIndex; length++)
                        {
                            this[subKey.Substring(startIndex, length)] = null;
                        }
                    }
                }
            }
        }
    }

    #endregion cleaning Operations
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.