summaryrefslogtreecommitdiff
path: root/src/mscorlib/src/System/Diagnostics/Eventing/TraceLogging/ConcurrentSet.cs
blob: 76c01c6c0683628466401b4e431910e9683b2757 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System;
using Interlocked = System.Threading.Interlocked;

#if ES_BUILD_STANDALONE
namespace Microsoft.Diagnostics.Tracing
#else
namespace System.Diagnostics.Tracing
#endif
{
    /// <summary>
    /// TraceLogging: A very simple lock-free add-only dictionary.
    /// Warning: this is a copy-by-value type. Copying performs a snapshot.
    /// Accessing a readonly field always makes a copy of the field, so the
    /// GetOrAdd method will not work as expected if called on a readonly field.
    /// </summary>
    /// <typeparam name="KeyType">
    /// The type of the key, used for TryGet.
    /// </typeparam>
    /// <typeparam name="ItemType">
    /// The type of the item, used for GetOrAdd.
    /// </typeparam>
    internal struct ConcurrentSet<KeyType, ItemType>
        where ItemType : ConcurrentSetItem<KeyType, ItemType>
    {
        private ItemType[] items;

        public ItemType TryGet(KeyType key)
        {
            ItemType item;
            var oldItems = this.items;

            if (oldItems != null)
            {
                var lo = 0;
                var hi = oldItems.Length;
                do
                {
                    int i = (lo + hi) / 2;
                    item = oldItems[i];

                    int cmp = item.Compare(key);
                    if (cmp == 0)
                    {
                        goto Done;
                    }
                    else if (cmp < 0)
                    {
                        lo = i + 1;
                    }
                    else
                    {
                        hi = i;
                    }
                }
                while (lo != hi);
            }

            item = null;

        Done:

            return item;
        }

        public ItemType GetOrAdd(ItemType newItem)
        {
            ItemType item;
            var oldItems = this.items;
            ItemType[] newItems;

        Retry:

            if (oldItems == null)
            {
                newItems = new ItemType[] { newItem };
            }
            else
            {
                var lo = 0;
                var hi = oldItems.Length;
                do
                {
                    int i = (lo + hi) / 2;
                    item = oldItems[i];

                    int cmp = item.Compare(newItem);
                    if (cmp == 0)
                    {
                        goto Done;
                    }
                    else if (cmp < 0)
                    {
                        lo = i + 1;
                    }
                    else
                    {
                        hi = i;
                    }
                }
                while (lo != hi);

                int oldLength = oldItems.Length;
                newItems = new ItemType[oldLength + 1];
                Array.Copy(oldItems, 0, newItems, 0, lo);
                newItems[lo] = newItem;
                Array.Copy(oldItems, lo, newItems, lo + 1, oldLength - lo);
            }

            newItems = Interlocked.CompareExchange(ref this.items, newItems, oldItems);
            if (oldItems != newItems)
            {
                oldItems = newItems;
                goto Retry;
            }

            item = newItem;

        Done:

            return item;
        }
    }
}