Home | History | Annotate | Download | only in internal 
      1 /*
      2  * Copyright 2017, OpenCensus Authors
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * 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,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 package io.opencensus.implcore.trace.internal;
     18 
     19 import static com.google.common.base.Preconditions.checkArgument;
     20 
     21 import io.opencensus.implcore.internal.CheckerFrameworkUtils;
     22 import io.opencensus.implcore.trace.internal.ConcurrentIntrusiveList.Element;
     23 import java.util.ArrayList;
     24 import java.util.Collection;
     25 import java.util.List;
     26 import javax.annotation.Nullable;
     27 import javax.annotation.concurrent.ThreadSafe;
     28 
     29 /**
     30  * An {@code ConcurrentIntrusiveList<T>} is a doubly-linked list where the link pointers are
     31  * embedded in the elements. This makes insertion and removal into a known position constant time.
     32  *
     33  * <p>Elements must derive from the {@code Element<T extends Element<T>>} interface:
     34  *
     35  * <pre><code>
     36  * class MyClass implements {@code Element<MyClass>} {
     37  *   private MyClass next = null;
     38  *   private MyClass prev = null;
     39  *
     40  *  {@literal @}Override
     41  *   MyClass getNext() {
     42  *     return next;
     43  *   }
     44  *
     45  *  {@literal @}Override
     46  *   void setNext(MyClass element) {
     47  *     next = element;
     48  *   }
     49  *
     50  *  {@literal @}Override
     51  *   MyClass getPrev() {
     52  *     return prev;
     53  *   }
     54  *
     55  *  {@literal @}Override
     56  *   void setPrev(MyClass element) {
     57  *     prev = element;
     58  *   }
     59  * }
     60  * </code></pre>
     61  */
     62 @ThreadSafe
     63 public final class ConcurrentIntrusiveList<T extends Element<T>> {
     64   private int size = 0;
     65   @Nullable private T head = null;
     66 
     67   public ConcurrentIntrusiveList() {}
     68 
     69   /**
     70    * Adds the given {@code element} to the list.
     71    *
     72    * @param element the element to add.
     73    * @throws IllegalArgumentException if the element is already in a list.
     74    */
     75   public synchronized void addElement(T element) {
     76     checkArgument(
     77         element.getNext() == null && element.getPrev() == null && element != head,
     78         "Element already in a list.");
     79     size++;
     80     if (head == null) {
     81       head = element;
     82     } else {
     83       head.setPrev(element);
     84       element.setNext(head);
     85       head = element;
     86     }
     87   }
     88 
     89   /**
     90    * Removes the given {@code element} from the list.
     91    *
     92    * @param element the element to remove.
     93    * @throws IllegalArgumentException if the element is not in the list.
     94    */
     95   public synchronized void removeElement(T element) {
     96     checkArgument(
     97         element.getNext() != null || element.getPrev() != null || element == head,
     98         "Element not in the list.");
     99     size--;
    100     if (element.getPrev() == null) {
    101       // This is the first element
    102       head = element.getNext();
    103       if (head != null) {
    104         // If more than one element in the list.
    105         head.setPrev(null);
    106         element.setNext(null);
    107       }
    108     } else if (element.getNext() == null) {
    109       // This is the last element, and there is at least another element because
    110       // element.getPrev() != null.
    111       CheckerFrameworkUtils.castNonNull(element.getPrev()).setNext(null);
    112       element.setPrev(null);
    113     } else {
    114       CheckerFrameworkUtils.castNonNull(element.getPrev()).setNext(element.getNext());
    115       CheckerFrameworkUtils.castNonNull(element.getNext()).setPrev(element.getPrev());
    116       element.setNext(null);
    117       element.setPrev(null);
    118     }
    119   }
    120 
    121   /**
    122    * Returns the number of elements in this list.
    123    *
    124    * @return the number of elements in this list.
    125    */
    126   public synchronized int size() {
    127     return size;
    128   }
    129 
    130   /**
    131    * Returns all the elements from this list.
    132    *
    133    * @return all the elements from this list.
    134    */
    135   public synchronized Collection<T> getAll() {
    136     List<T> all = new ArrayList<T>(size);
    137     for (T e = head; e != null; e = e.getNext()) {
    138       all.add(e);
    139     }
    140     return all;
    141   }
    142 
    143   /**
    144    * This is an interface that must be implemented by any element that uses {@link
    145    * ConcurrentIntrusiveList}.
    146    *
    147    * @param <T> the element that will be used for the list.
    148    */
    149   public interface Element<T extends Element<T>> {
    150 
    151     /**
    152      * Returns a reference to the next element in the list.
    153      *
    154      * @return a reference to the next element in the list.
    155      */
    156     @Nullable
    157     T getNext();
    158 
    159     /**
    160      * Sets the reference to the next element in the list.
    161      *
    162      * @param element the reference to the next element in the list.
    163      */
    164     void setNext(@Nullable T element);
    165 
    166     /**
    167      * Returns a reference to the previous element in the list.
    168      *
    169      * @return a reference to the previous element in the list.
    170      */
    171     @Nullable
    172     T getPrev();
    173 
    174     /**
    175      * Sets the reference to the previous element in the list.
    176      *
    177      * @param element the reference to the previous element in the list.
    178      */
    179     void setPrev(@Nullable T element);
    180   }
    181 }
    182