1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package io.netty.util;
17
18 import io.netty.util.internal.ObjectUtil;
19
20 import java.util.Arrays;
21 import java.util.concurrent.atomic.AtomicReference;
22 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
23
24
25
26
27
28
29 public class DefaultAttributeMap implements AttributeMap {
30
31 private static final AtomicReferenceFieldUpdater<DefaultAttributeMap, DefaultAttribute[]> ATTRIBUTES_UPDATER =
32 AtomicReferenceFieldUpdater.newUpdater(DefaultAttributeMap.class, DefaultAttribute[].class, "attributes");
33 private static final DefaultAttribute[] EMPTY_ATTRIBUTES = new DefaultAttribute[0];
34
35
36
37
38
39 private static int searchAttributeByKey(DefaultAttribute[] sortedAttributes, AttributeKey<?> key) {
40 int low = 0;
41 int high = sortedAttributes.length - 1;
42
43 while (low <= high) {
44 int mid = low + high >>> 1;
45 DefaultAttribute midVal = sortedAttributes[mid];
46 AttributeKey midValKey = midVal.key;
47 if (midValKey == key) {
48 return mid;
49 }
50 int midValKeyId = midValKey.id();
51 int keyId = key.id();
52 assert midValKeyId != keyId;
53 boolean searchRight = midValKeyId < keyId;
54 if (searchRight) {
55 low = mid + 1;
56 } else {
57 high = mid - 1;
58 }
59 }
60
61 return -(low + 1);
62 }
63
64 private static void orderedCopyOnInsert(DefaultAttribute[] sortedSrc, int srcLength, DefaultAttribute[] copy,
65 DefaultAttribute toInsert) {
66
67 final int id = toInsert.key.id();
68 int i;
69 for (i = srcLength - 1; i >= 0; i--) {
70 DefaultAttribute attribute = sortedSrc[i];
71 int attributeKeyId = attribute.key.id();
72 assert attributeKeyId != id;
73 if (attributeKeyId < id) {
74 break;
75 }
76 copy[i + 1] = attribute;
77 }
78 copy[i + 1] = toInsert;
79 final int toCopy = i + 1;
80 if (toCopy > 0) {
81 System.arraycopy(sortedSrc, 0, copy, 0, toCopy);
82 }
83 }
84
85 private volatile DefaultAttribute[] attributes = EMPTY_ATTRIBUTES;
86
87 @SuppressWarnings("unchecked")
88 @Override
89 public <T> Attribute<T> attr(AttributeKey<T> key) {
90 ObjectUtil.checkNotNull(key, "key");
91 DefaultAttribute newAttribute = null;
92 for (;;) {
93 final DefaultAttribute[] attributes = this.attributes;
94 final int index = searchAttributeByKey(attributes, key);
95 final DefaultAttribute[] newAttributes;
96 if (index >= 0) {
97 final DefaultAttribute attribute = attributes[index];
98 assert attribute.key() == key;
99 if (!attribute.isRemoved()) {
100 return attribute;
101 }
102
103 if (newAttribute == null) {
104 newAttribute = new DefaultAttribute<T>(this, key);
105 }
106 final int count = attributes.length;
107 newAttributes = Arrays.copyOf(attributes, count);
108 newAttributes[index] = newAttribute;
109 } else {
110 if (newAttribute == null) {
111 newAttribute = new DefaultAttribute<T>(this, key);
112 }
113 final int count = attributes.length;
114 newAttributes = new DefaultAttribute[count + 1];
115 orderedCopyOnInsert(attributes, count, newAttributes, newAttribute);
116 }
117 if (ATTRIBUTES_UPDATER.compareAndSet(this, attributes, newAttributes)) {
118 return newAttribute;
119 }
120 }
121 }
122
123 @Override
124 public <T> boolean hasAttr(AttributeKey<T> key) {
125 ObjectUtil.checkNotNull(key, "key");
126 return searchAttributeByKey(attributes, key) >= 0;
127 }
128
129 private <T> void removeAttributeIfMatch(AttributeKey<T> key, DefaultAttribute<T> value) {
130 for (;;) {
131 final DefaultAttribute[] attributes = this.attributes;
132 final int index = searchAttributeByKey(attributes, key);
133 if (index < 0) {
134 return;
135 }
136 final DefaultAttribute attribute = attributes[index];
137 assert attribute.key() == key;
138 if (attribute != value) {
139 return;
140 }
141 final int count = attributes.length;
142 final int newCount = count - 1;
143 final DefaultAttribute[] newAttributes =
144 newCount == 0? EMPTY_ATTRIBUTES : new DefaultAttribute[newCount];
145
146 System.arraycopy(attributes, 0, newAttributes, 0, index);
147 final int remaining = count - index - 1;
148 if (remaining > 0) {
149 System.arraycopy(attributes, index + 1, newAttributes, index, remaining);
150 }
151 if (ATTRIBUTES_UPDATER.compareAndSet(this, attributes, newAttributes)) {
152 return;
153 }
154 }
155 }
156
157 private static final class DefaultAttribute<T> extends AtomicReference<T> implements Attribute<T> {
158
159 private static final AtomicReferenceFieldUpdater<DefaultAttribute, DefaultAttributeMap> MAP_UPDATER =
160 AtomicReferenceFieldUpdater.newUpdater(DefaultAttribute.class,
161 DefaultAttributeMap.class, "attributeMap");
162 private static final long serialVersionUID = -2661411462200283011L;
163
164 private volatile DefaultAttributeMap attributeMap;
165 private final AttributeKey<T> key;
166
167 DefaultAttribute(DefaultAttributeMap attributeMap, AttributeKey<T> key) {
168 this.attributeMap = attributeMap;
169 this.key = key;
170 }
171
172 @Override
173 public AttributeKey<T> key() {
174 return key;
175 }
176
177 private boolean isRemoved() {
178 return attributeMap == null;
179 }
180
181 @Override
182 public T setIfAbsent(T value) {
183 while (!compareAndSet(null, value)) {
184 T old = get();
185 if (old != null) {
186 return old;
187 }
188 }
189 return null;
190 }
191
192 @Override
193 public T getAndRemove() {
194 final DefaultAttributeMap attributeMap = this.attributeMap;
195 final boolean removed = attributeMap != null && MAP_UPDATER.compareAndSet(this, attributeMap, null);
196 T oldValue = getAndSet(null);
197 if (removed) {
198 attributeMap.removeAttributeIfMatch(key, this);
199 }
200 return oldValue;
201 }
202
203 @Override
204 public void remove() {
205 final DefaultAttributeMap attributeMap = this.attributeMap;
206 final boolean removed = attributeMap != null && MAP_UPDATER.compareAndSet(this, attributeMap, null);
207 set(null);
208 if (removed) {
209 attributeMap.removeAttributeIfMatch(key, this);
210 }
211 }
212 }
213 }