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    *   http://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.netty.util;
17  
18  import java.util.concurrent.atomic.AtomicReference;
19  import java.util.concurrent.atomic.AtomicReferenceArray;
20  import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
21  
22  /**
23   * Default {@link AttributeMap} implementation which use simple synchronization per bucket to keep the memory overhead
24   * as low as possible.
25   */
26  public class DefaultAttributeMap implements AttributeMap {
27  
28      @SuppressWarnings("rawtypes")
29      private static final AtomicReferenceFieldUpdater<DefaultAttributeMap, AtomicReferenceArray> updater =
30              AtomicReferenceFieldUpdater.newUpdater(DefaultAttributeMap.class, AtomicReferenceArray.class, "attributes");
31  
32      private static final int BUCKET_SIZE = 4;
33      private static final int MASK = BUCKET_SIZE  - 1;
34  
35      // Initialize lazily to reduce memory consumption; updated by AtomicReferenceFieldUpdater above.
36      @SuppressWarnings("UnusedDeclaration")
37      private volatile AtomicReferenceArray<DefaultAttribute<?>> attributes;
38  
39      @SuppressWarnings("unchecked")
40      @Override
41      public <T> Attribute<T> attr(AttributeKey<T> key) {
42          if (key == null) {
43              throw new NullPointerException("key");
44          }
45          AtomicReferenceArray<DefaultAttribute<?>> attributes = this.attributes;
46          if (attributes == null) {
47              // Not using ConcurrentHashMap due to high memory consumption.
48              attributes = new AtomicReferenceArray<DefaultAttribute<?>>(BUCKET_SIZE);
49  
50              if (!updater.compareAndSet(this, null, attributes)) {
51                  attributes = this.attributes;
52              }
53          }
54  
55          int i = index(key);
56          DefaultAttribute<?> head = attributes.get(i);
57          if (head == null) {
58              // No head exists yet which means we may be able to add the attribute without synchronization and just
59              // use compare and set. At worst we need to fallback to synchronization and waste two allocations.
60              head = new DefaultAttribute();
61              DefaultAttribute<T> attr = new DefaultAttribute<T>(head, key);
62              head.next = attr;
63              attr.prev = head;
64              if (attributes.compareAndSet(i, null, head)) {
65                  // we were able to add it so return the attr right away
66                  return attr;
67              } else {
68                  head = attributes.get(i);
69              }
70          }
71  
72          synchronized (head) {
73              DefaultAttribute<?> curr = head;
74              for (;;) {
75                  DefaultAttribute<?> next = curr.next;
76                  if (next == null) {
77                      DefaultAttribute<T> attr = new DefaultAttribute<T>(head, key);
78                      curr.next = attr;
79                      attr.prev = curr;
80                      return attr;
81                  }
82  
83                  if (next.key == key && !next.removed) {
84                      return (Attribute<T>) next;
85                  }
86                  curr = next;
87              }
88          }
89      }
90  
91      @Override
92      public <T> boolean hasAttr(AttributeKey<T> key) {
93          if (key == null) {
94              throw new NullPointerException("key");
95          }
96          AtomicReferenceArray<DefaultAttribute<?>> attributes = this.attributes;
97          if (attributes == null) {
98              // no attribute exists
99              return false;
100         }
101 
102         int i = index(key);
103         DefaultAttribute<?> head = attributes.get(i);
104         if (head == null) {
105             // No attribute exists which point to the bucket in which the head should be located
106             return false;
107         }
108 
109         // We need to synchronize on the head.
110         synchronized (head) {
111             // Start with head.next as the head itself does not store an attribute.
112             DefaultAttribute<?> curr = head.next;
113             while (curr != null) {
114                 if (curr.key == key && !curr.removed) {
115                     return true;
116                 }
117                 curr = curr.next;
118             }
119             return false;
120         }
121     }
122 
123     private static int index(AttributeKey<?> key) {
124         return key.id() & MASK;
125     }
126 
127     @SuppressWarnings("serial")
128     private static final class DefaultAttribute<T> extends AtomicReference<T> implements Attribute<T> {
129 
130         private static final long serialVersionUID = -2661411462200283011L;
131 
132         // The head of the linked-list this attribute belongs to
133         private final DefaultAttribute<?> head;
134         private final AttributeKey<T> key;
135 
136         // Double-linked list to prev and next node to allow fast removal
137         private DefaultAttribute<?> prev;
138         private DefaultAttribute<?> next;
139 
140         // Will be set to true one the attribute is removed via getAndRemove() or remove()
141         private volatile boolean removed;
142 
143         DefaultAttribute(DefaultAttribute<?> head, AttributeKey<T> key) {
144             this.head = head;
145             this.key = key;
146         }
147 
148         // Special constructor for the head of the linked-list.
149         DefaultAttribute() {
150             head = this;
151             key = null;
152         }
153 
154         @Override
155         public AttributeKey<T> key() {
156             return key;
157         }
158 
159         @Override
160         public T setIfAbsent(T value) {
161             while (!compareAndSet(null, value)) {
162                 T old = get();
163                 if (old != null) {
164                     return old;
165                 }
166             }
167             return null;
168         }
169 
170         @Override
171         public T getAndRemove() {
172             removed = true;
173             T oldValue = getAndSet(null);
174             remove0();
175             return oldValue;
176         }
177 
178         @Override
179         public void remove() {
180             removed = true;
181             set(null);
182             remove0();
183         }
184 
185         private void remove0() {
186             synchronized (head) {
187                 if (prev == null) {
188                     // Removed before.
189                     return;
190                 }
191 
192                 prev.next = next;
193 
194                 if (next != null) {
195                     next.prev = prev;
196                 }
197 
198                 // Null out prev and next - this will guard against multiple remove0() calls which may corrupt
199                 // the linked list for the bucket.
200                 prev = null;
201                 next = null;
202             }
203         }
204     }
205 }