Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LurchTable Insertion Order Not Working #12

Open
NightOwl888 opened this issue Nov 4, 2016 · 3 comments
Open

LurchTable Insertion Order Not Working #12

NightOwl888 opened this issue Nov 4, 2016 · 3 comments

Comments

@NightOwl888
Copy link

You have advertised LurchTable as a replacement for LinkedHashMap. Per this answer on StackOverflow:

LinkedHashMap will iterate in the order in which the entries were put into the map

Basically, the primary purpose of LinkedHashMap is to keep the insertion order regardless of deletions and re-additions, so I would expect this replacement for it should function the same way, but doesn't. Since there is an insertion order in the enumeration, but it doesn't function, I suspect this is a bug.

    class Program
    {
        static void Main(string[] args)
        {
            var lurchTable = new LurchTable<string, string>(16, LurchTableOrder.Insertion);

            for (int i = 0; i < 20; i++)
            {
                string entry = "entry" + i;
                lurchTable.Add(entry, entry);
            }

            foreach (var entry in lurchTable)
            {
                Console.WriteLine(entry.Key);
            }

            Console.ReadKey();
        }
    }

Results:

entry4
entry13
entry8
entry1
entry19
entry17
entry5
entry12
entry9
entry2
entry16
entry11
entry18
entry6
entry15
entry3
entry10
entry7
entry0
entry14

Unfortunately, it seems that .NET doesn't contain a dictionary that guarantees the results will be iterated in insertion order. Well, there is OrderedDictionary, but it is not generic.

@azhmur
Copy link

azhmur commented Dec 8, 2016

Actually, you incorrectly associate enumeration order with Dequeue order. They are not declared to be same. You can actually read link you have provided to find an answer. Author stated:

All enumerations of the LurchTable are thread-safe and in Hash-order. Due to the lockless nature of the internal linking, it is not possible to enumerate the contents of the collection in the linked order. Enumeration of the links could easily be added; however, it would not be thread-safe and thus is not currently implemented.

class Program
{
    static void Main(string[] args)
    {
        var lurchTable = new LurchTable<string, string>(16, LurchTableOrder.Insertion);

        for (int i = 0; i < 20; i++)
        {
            string entry = "entry" + i;
            lurchTable.Add(entry, entry);
        }

        KeyValuePair<string, string> pair;
        while (lurchTable.TryDequeue(out pair))
        {
            Console.WriteLine(pair.Key);
        }

        Console.ReadKey();
    }
}

@csharptest
Copy link
Owner

@NightOwl888 The user @azhmur has the right of it... enumerations are not ordered by the linked list. This was done to prevent deadlocks. The only reliable way one could achieve this is to prevent concurrent modifications for the duration of the enumeration, or to make a clone of the tree and then enumerate. The former is really a non-starter as it means allowing locks to be held while executing code in the enumeration which can cause all kinds of issues. The later amounts to placing a synchronization context around all write calls. If you are doing that a wrapper around Dictionary<K,V> and LinkedList would possibly be a better approach than using this class.

The design of this implementation was heavily influenced by it's intended use case as a high-contention write-through cache layer. Hope that helps and sorry for the confusion.

@NightOwl888
Copy link
Author

NightOwl888 commented Dec 8, 2016

Thanks. You might want to change that blog post then because this really isn't a replacement for LinkedHashMap, it is a replacement for one constructor overload of LinkedHashMap.

Since I posted this, I found another solution here that I adapted to work, but it didn't seem right to replace one class with two. But that is what we have ended up with and it is working great.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants