1 files changed, 181 insertions, 0 deletions
diff --git a/impl_core/src/main/java/io/opencensus/implcore/trace/internal/ConcurrentIntrusiveList.java b/impl_core/src/main/java/io/opencensus/implcore/trace/internal/ConcurrentIntrusiveList.java
new file mode 100644
index 00000000..22d8e41a
--- /dev/null
+++ b/impl_core/src/main/java/io/opencensus/implcore/trace/internal/ConcurrentIntrusiveList.java
@@ -0,0 +1,181 @@
+/*
+ * Copyright 2017, OpenCensus Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package io.opencensus.implcore.trace.internal;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+import io.opencensus.implcore.internal.CheckerFrameworkUtils;
+import io.opencensus.implcore.trace.internal.ConcurrentIntrusiveList.Element;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.ThreadSafe;
+
+/**
+ * An {@code ConcurrentIntrusiveList<T>} is a doubly-linked list where the link pointers are
+ * embedded in the elements. This makes insertion and removal into a known position constant time.
+ *
+ * <p>Elements must derive from the {@code Element<T extends Element<T>>} interface:
+ *
+ * <pre><code>
+ * class MyClass implements {@code Element<MyClass>} {
+ *   private MyClass next = null;
+ *   private MyClass prev = null;
+ *
+ *  {@literal @}Override
+ *   MyClass getNext() {
+ *     return next;
+ *   }
+ *
+ *  {@literal @}Override
+ *   void setNext(MyClass element) {
+ *     next = element;
+ *   }
+ *
+ *  {@literal @}Override
+ *   MyClass getPrev() {
+ *     return prev;
+ *   }
+ *
+ *  {@literal @}Override
+ *   void setPrev(MyClass element) {
+ *     prev = element;
+ *   }
+ * }
+ * </code></pre>
+ */
+@ThreadSafe
+public final class ConcurrentIntrusiveList<T extends Element<T>> {
+  private int size = 0;
+  @Nullable private T head = null;
+
+  public ConcurrentIntrusiveList() {}
+
+  /**
+   * Adds the given {@code element} to the list.
+   *
+   * @param element the element to add.
+   * @throws IllegalArgumentException if the element is already in a list.
+   */
+  public synchronized void addElement(T element) {
+    checkArgument(
+        element.getNext() == null && element.getPrev() == null && element != head,
+        "Element already in a list.");
+    size++;
+    if (head == null) {
+      head = element;
+    } else {
+      head.setPrev(element);
+      element.setNext(head);
+      head = element;
+    }
+  }
+
+  /**
+   * Removes the given {@code element} from the list.
+   *
+   * @param element the element to remove.
+   * @throws IllegalArgumentException if the element is not in the list.
+   */
+  public synchronized void removeElement(T element) {
+    checkArgument(
+        element.getNext() != null || element.getPrev() != null || element == head,
+        "Element not in the list.");
+    size--;
+    if (element.getPrev() == null) {
+      // This is the first element
+      head = element.getNext();
+      if (head != null) {
+        // If more than one element in the list.
+        head.setPrev(null);
+        element.setNext(null);
+      }
+    } else if (element.getNext() == null) {
+      // This is the last element, and there is at least another element because
+      // element.getPrev() != null.
+      CheckerFrameworkUtils.castNonNull(element.getPrev()).setNext(null);
+      element.setPrev(null);
+    } else {
+      CheckerFrameworkUtils.castNonNull(element.getPrev()).setNext(element.getNext());
+      CheckerFrameworkUtils.castNonNull(element.getNext()).setPrev(element.getPrev());
+      element.setNext(null);
+      element.setPrev(null);
+    }
+  }
+
+  /**
+   * Returns the number of elements in this list.
+   *
+   * @return the number of elements in this list.
+   */
+  public synchronized int size() {
+    return size;
+  }
+
+  /**
+   * Returns all the elements from this list.
+   *
+   * @return all the elements from this list.
+   */
+  public synchronized Collection<T> getAll() {
+    List<T> all = new ArrayList<T>(size);
+    for (T e = head; e != null; e = e.getNext()) {
+      all.add(e);
+    }
+    return all;
+  }
+
+  /**
+   * This is an interface that must be implemented by any element that uses {@link
+   * ConcurrentIntrusiveList}.
+   *
+   * @param <T> the element that will be used for the list.
+   */
+  public interface Element<T extends Element<T>> {
+
+    /**
+     * Returns a reference to the next element in the list.
+     *
+     * @return a reference to the next element in the list.
+     */
+    @Nullable
+    T getNext();
+
+    /**
+     * Sets the reference to the next element in the list.
+     *
+     * @param element the reference to the next element in the list.
+     */
+    void setNext(@Nullable T element);
+
+    /**
+     * Returns a reference to the previous element in the list.
+     *
+     * @return a reference to the previous element in the list.
+     */
+    @Nullable
+    T getPrev();
+
+    /**
+     * Sets the reference to the previous element in the list.
+     *
+     * @param element the reference to the previous element in the list.
+     */
+    void setPrev(@Nullable T element);
+  }
+}