View Javadoc
1   /*
2    * Copyright 2012 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   https://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  package io.netty5.util;
17  
18  import java.util.Arrays;
19  import java.util.concurrent.atomic.AtomicReference;
20  import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
21  
22  import static java.util.Objects.requireNonNull;
23  
24  /**
25   * Default {@link AttributeMap} implementation which not exibit any blocking behaviour on attribute lookup while using a
26   * copy-on-write approach on the modify path.<br> Attributes lookup and remove exibit {@code O(logn)} time worst-case
27   * complexity, hence {@code attribute::set(null)} is to be preferred to {@code remove}.
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       * Similarly to {@code Arrays::binarySearch} it perform a binary search optimized for this use case, in order to
37       * save polymorphic calls (on comparator side) and unnecessary class checks.
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          // let's walk backward, because as a rule of thumb, toInsert.key.id() tends to be higher for new keys
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          requireNonNull(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                 // let's try replace the removed attribute with a new one
102                 if (newAttribute == null) {
103                     newAttribute = new DefaultAttribute<>(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<>(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         requireNonNull(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             // perform 2 bulk copies
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 }