Class IntAllocator


  • public class IntAllocator
    extends java.lang.Object

    A class for allocating integers from a given range that uses a BitSet representation of the free integers.

    Concurrency Semantics:

    This class is not thread safe.

    Implementation notes:

    This was originally an ordered chain of non-overlapping Intervals, together with a fixed size array cache for freed integers.

    reserve(int) was expensive in this scheme, whereas in the present implementation it is O(1), as is free(int).

    Although allocate() is slightly slower than O(1) and in the worst case could be O(N), the use of a "lastIndex" field for starting the next scan for free integers means this is negligible.

    The data representation overhead is O(N) where N is the size of the allocation range. One long is used for every 64 integers in the range.

    Very little Object creation and destruction occurs in use.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.BitSet freeSet
      A bit is SET in freeSet if the corresponding integer is FREE
      A bit is UNSET in freeSet if the corresponding integer is ALLOCATED
      private int hiRange  
      private int lastIndex  
      private int loRange  
      private int numberOfBits  
    • Constructor Summary

      Constructors 
      Constructor Description
      IntAllocator​(int bottom, int top)
      Creates an IntAllocator allocating integer IDs within the inclusive range [bottom, top].
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int allocate()
      Allocate an unallocated integer from the range, or return -1 if no more integers are available.
      void free​(int reservation)
      Make the provided integer available for allocation again.
      boolean reserve​(int reservation)
      Attempt to reserve the provided ID as if it had been allocated.
      private void stringInterval​(java.lang.StringBuilder sb, int i1, int i2)  
      java.lang.String toString()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • loRange

        private final int loRange
      • hiRange

        private final int hiRange
      • numberOfBits

        private final int numberOfBits
      • lastIndex

        private int lastIndex
      • freeSet

        private final java.util.BitSet freeSet
        A bit is SET in freeSet if the corresponding integer is FREE
        A bit is UNSET in freeSet if the corresponding integer is ALLOCATED
    • Constructor Detail

      • IntAllocator

        public IntAllocator​(int bottom,
                            int top)
        Creates an IntAllocator allocating integer IDs within the inclusive range [bottom, top].
        Parameters:
        bottom - lower end of range
        top - upper end of range (inclusive)
    • Method Detail

      • allocate

        public int allocate()
        Allocate an unallocated integer from the range, or return -1 if no more integers are available.
        Returns:
        the allocated integer, or -1
      • free

        public void free​(int reservation)
        Make the provided integer available for allocation again. This operation runs in O(1) time. No error checking is performed, so if you double free or free an integer that was not originally allocated the results are undefined.
        Parameters:
        reservation - the previously allocated integer to free
      • reserve

        public boolean reserve​(int reservation)
        Attempt to reserve the provided ID as if it had been allocated. Returns true if it is available, false otherwise. This operation runs in O(1) time.
        Parameters:
        reservation - the integer to be allocated, if possible
        Returns:
        true if allocated, false if already allocated
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • stringInterval

        private void stringInterval​(java.lang.StringBuilder sb,
                                    int i1,
                                    int i2)