Class NonBlockingSetInt

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Iterable<java.lang.Integer>, java.util.Collection<java.lang.Integer>, java.util.Set<java.lang.Integer>

    public class NonBlockingSetInt
    extends java.util.AbstractSet<java.lang.Integer>
    implements java.io.Serializable
    A multi-threaded bit-vector set, implemented as an array of primitive longs. All operations are non-blocking and multi-threaded safe. contains(int) calls are roughly the same speed as a {load, mask} sequence. add(int) and remove(int) calls are a tad more expensive than a {load, mask, store} sequence because they must use a CAS. The bit-vector is auto-sizing.

    General note of caution: The Set API allows the use of Integer with silent autoboxing - which can be very expensive if many calls are being made. Since autoboxing is silent you may not be aware that this is going on. The built-in API takes lower-case ints and is much more efficient.

    Space: space is used in proportion to the largest element, as opposed to the number of elements (as is the case with hash-table based Set implementations). Space is approximately (largest_element/8 + 64) bytes. The implementation is a simple bit-vector using CAS for update.

    Since:
    1.5
    See Also:
    Serialized Form
    • Constructor Summary

      Constructors 
      Constructor Description
      NonBlockingSetInt()
      Create a new empty bit-vector
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(int i)
      Add i to the set.
      boolean add​(java.lang.Integer i)
      Add i to the set.
      private boolean CAS_nbsi​(NonBlockingSetInt.NBSI old, NonBlockingSetInt.NBSI nnn)  
      void clear()
      Empty the bitvector.
      boolean contains​(int i)
      Test if i is in the set.
      boolean contains​(java.lang.Object o)
      Test if o is in the set.
      java.util.Iterator<java.lang.Integer> iterator()
      Standard Java Iterator.
      int length()
      Approx largest element in set; at least as big (but max might be smaller).
      void print()
      Verbose printout of internal structure for debugging.
      private void readObject​(java.io.ObjectInputStream s)  
      boolean remove​(int i)
      Remove i from the set.
      boolean remove​(java.lang.Object o)
      Remove o from the set.
      int size()
      Current count of elements in the set.
      private void writeObject​(java.io.ObjectOutputStream s)  
      • Methods inherited from class java.util.AbstractSet

        equals, hashCode, removeAll
      • Methods inherited from class java.util.AbstractCollection

        addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Collection

        parallelStream, removeIf, stream, toArray
      • Methods inherited from interface java.lang.Iterable

        forEach
      • Methods inherited from interface java.util.Set

        addAll, containsAll, isEmpty, retainAll, spliterator, toArray, toArray
    • Constructor Detail

      • NonBlockingSetInt

        public NonBlockingSetInt()
        Create a new empty bit-vector
    • Method Detail

      • add

        public boolean add​(java.lang.Integer i)
        Add i to the set. Uppercase Integer version of add, requires auto-unboxing. When possible use the int version of add(int) for efficiency.
        Specified by:
        add in interface java.util.Collection<java.lang.Integer>
        Specified by:
        add in interface java.util.Set<java.lang.Integer>
        Overrides:
        add in class java.util.AbstractCollection<java.lang.Integer>
        Returns:
        true if i was added to the set.
        Throws:
        java.lang.IllegalArgumentException - if i is negative.
      • contains

        public boolean contains​(java.lang.Object o)
        Test if o is in the set. This is the uppercase Integer version of contains, requires a type-check and auto-unboxing. When possible use the int version of contains(int) for efficiency.
        Specified by:
        contains in interface java.util.Collection<java.lang.Integer>
        Specified by:
        contains in interface java.util.Set<java.lang.Integer>
        Overrides:
        contains in class java.util.AbstractCollection<java.lang.Integer>
        Returns:
        true if i was in the set.
      • remove

        public boolean remove​(java.lang.Object o)
        Remove o from the set. This is the uppercase Integer version of remove, requires a type-check and auto-unboxing. When possible use the int version of remove(int) for efficiency.
        Specified by:
        remove in interface java.util.Collection<java.lang.Integer>
        Specified by:
        remove in interface java.util.Set<java.lang.Integer>
        Overrides:
        remove in class java.util.AbstractCollection<java.lang.Integer>
        Returns:
        true if i was removed to the set.
      • add

        public boolean add​(int i)
        Add i to the set. This is the lower-case 'int' version of add(java.lang.Integer) - no autoboxing. Negative values throw IllegalArgumentException.
        Returns:
        true if i was added to the set.
        Throws:
        java.lang.IllegalArgumentException - if i is negative.
      • contains

        public boolean contains​(int i)
        Test if i is in the set. This is the lower-case 'int' version of contains(java.lang.Object) - no autoboxing.
        Returns:
        true if i was int the set.
      • remove

        public boolean remove​(int i)
        Remove i from the set. This is the fast lower-case 'int' version of remove(java.lang.Object) - no autoboxing.
        Returns:
        true if i was added to the set.
      • size

        public int size()
        Current count of elements in the set. Due to concurrent racing updates, the size is only ever approximate. Updates due to the calling thread are immediately visible to calling thread.
        Specified by:
        size in interface java.util.Collection<java.lang.Integer>
        Specified by:
        size in interface java.util.Set<java.lang.Integer>
        Specified by:
        size in class java.util.AbstractCollection<java.lang.Integer>
        Returns:
        count of elements.
      • length

        public int length()
        Approx largest element in set; at least as big (but max might be smaller).
      • clear

        public void clear()
        Empty the bitvector.
        Specified by:
        clear in interface java.util.Collection<java.lang.Integer>
        Specified by:
        clear in interface java.util.Set<java.lang.Integer>
        Overrides:
        clear in class java.util.AbstractCollection<java.lang.Integer>
      • print

        public void print()
        Verbose printout of internal structure for debugging.
      • iterator

        public java.util.Iterator<java.lang.Integer> iterator()
        Standard Java Iterator. Not very efficient because it auto-boxes the returned values.
        Specified by:
        iterator in interface java.util.Collection<java.lang.Integer>
        Specified by:
        iterator in interface java.lang.Iterable<java.lang.Integer>
        Specified by:
        iterator in interface java.util.Set<java.lang.Integer>
        Specified by:
        iterator in class java.util.AbstractCollection<java.lang.Integer>
      • writeObject

        private void writeObject​(java.io.ObjectOutputStream s)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • readObject

        private void readObject​(java.io.ObjectInputStream s)
                         throws java.io.IOException,
                                java.lang.ClassNotFoundException
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException