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;
}
}
}
|