1
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
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
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 assert attribute.key.id() != id;
72 if (attribute.key.id() < id) {
73 break;
74 }
75 copy[i + 1] = sortedSrc[i];
76 }
77 copy[i + 1] = toInsert;
78 final int toCopy = i + 1;
79 if (toCopy > 0) {
80 System.arraycopy(sortedSrc, 0, copy, 0, toCopy);
81 }
82 }
83
84 private volatile DefaultAttribute[] attributes = EMPTY_ATTRIBUTES;
85
86 @SuppressWarnings("unchecked")
87 @Override
88 public <T> Attribute<T> attr(AttributeKey<T> key) {
89 ObjectUtil.checkNotNull(key, "key");
90 DefaultAttribute newAttribute = null;
91 for (;;) {
92 final DefaultAttribute[] attributes = this.attributes;
93 final int index = searchAttributeByKey(attributes, key);
94 final DefaultAttribute[] newAttributes;
95 if (index >= 0) {
96 final DefaultAttribute attribute = attributes[index];
97 assert attribute.key() == key;
98 if (!attribute.isRemoved()) {
99 return attribute;
100 }
101
102 if (newAttribute == null) {
103 newAttribute = new DefaultAttribute<T>(this, key);
104 }
105 final int count = attributes.length;
106 newAttributes = Arrays.copyOf(attributes, count);
107 newAttributes[index] = newAttribute;
108 } else {
109 if (newAttribute == null) {
110 newAttribute = new DefaultAttribute<T>(this, key);
111 }
112 final int count = attributes.length;
113 newAttributes = new DefaultAttribute[count + 1];
114 orderedCopyOnInsert(attributes, count, newAttributes, newAttribute);
115 }
116 if (ATTRIBUTES_UPDATER.compareAndSet(this, attributes, newAttributes)) {
117 return newAttribute;
118 }
119 }
120 }
121
122 @Override
123 public <T> boolean hasAttr(AttributeKey<T> key) {
124 ObjectUtil.checkNotNull(key, "key");
125 return searchAttributeByKey(attributes, key) >= 0;
126 }
127
128 private <T> void removeAttributeIfMatch(AttributeKey<T> key, DefaultAttribute<T> value) {
129 for (;;) {
130 final DefaultAttribute[] attributes = this.attributes;
131 final int index = searchAttributeByKey(attributes, key);
132 if (index < 0) {
133 return;
134 }
135 final DefaultAttribute attribute = attributes[index];
136 assert attribute.key() == key;
137 if (attribute != value) {
138 return;
139 }
140 final int count = attributes.length;
141 final int newCount = count - 1;
142 final DefaultAttribute[] newAttributes =
143 newCount == 0? EMPTY_ATTRIBUTES : new DefaultAttribute[newCount];
144
145 System.arraycopy(attributes, 0, newAttributes, 0, index);
146 final int remaining = count - index - 1;
147 if (remaining > 0) {
148 System.arraycopy(attributes, index + 1, newAttributes, index, remaining);
149 }
150 if (ATTRIBUTES_UPDATER.compareAndSet(this, attributes, newAttributes)) {
151 return;
152 }
153 }
154 }
155
156 @SuppressWarnings("serial")
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 }
214