Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  //  The contents of this file are subject to the Mozilla Public License
  //  Version 1.1 (the "License"); you may not use this file except in
  //  compliance with the License. You may obtain a copy of the License
  //  at
  //  Software distributed under the License is distributed on an "AS IS"
  //  basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
  //  the License for the specific language governing rights and
  //  limitations under the License.
 //  The Original Code is RabbitMQ.
 //  The Initial Developer of the Original Code is VMware, Inc.
 //  Copyright (c) 2007-2011 VMware, Inc.  All rights reserved.
 package com.rabbitmq.utility;
A class for allocating integers from a given range that uses a java.util.BitSet representation of the free integers.

Concurrent 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 the 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.

 public class IntAllocator {
     private final int loRange// the integer bit 0 represents
     private final int hiRange// the integer(+1) the highest bit represents
     private final int numberOfBits// relevant in freeSet
     private int lastIndex = 0; // for searching for FREE integers
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 final BitSet freeSet;

Creates an IntAllocator allocating integer IDs within the inclusive range [bottom, top].

bottom lower end of range
top upper end of range (inclusive)
     public IntAllocator(int bottomint top) {
         this. = bottom;
         this. = top + 1;
         this. =  - ;
         this. = new BitSet(this.);
         this..set(0, this.); // All integers FREE initially

Allocate an unallocated integer from the range, or return -1 if no more integers are available.

the allocated integer, or -1
     public int allocate() {
         int setIndex = this..nextSetBit(this.);
         if (setIndex<0) { // means none found in trailing part
             setIndex = this..nextSetBit(0);
         if (setIndex<0) return -1;
         this. = setIndex;
         return setIndex + this.;

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.

reservation the previously allocated integer to free
     public void free(int reservation) {
         this..set(reservation - this.);

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.

reservation the integer to be allocated, if possible
true if allocated, false if already allocated
    public boolean reserve(int reservation) {
        int index = reservation - this.;
        if (this..get(index)) { // FREE
            return true;
        } else {
            return false;
    public String toString() {
        StringBuilder sb
            = new StringBuilder("IntAllocator{allocated = [");
        int firstClearBit = this..nextClearBit(0);
        if (firstClearBit < this.) {
            int firstSetAfterThat = this..nextSetBit(firstClearBit+1);
            if (firstSetAfterThat < 0)
                firstSetAfterThat = this.;
            for (int i = this..nextClearBit(firstSetAfterThat+1);
                     i < this.;
                     i = this..nextClearBit(i+1)) {
                int nextSet = this..nextSetBit(i);
                if (nextSet<0) nextSet = this.;
                stringInterval(sb.append(", "), inextSet);
                i = nextSet;
        return sb.toString();
    private void stringInterval(StringBuilder sbint i1int i2) {
        sb.append(i1 + this.);
        if (i1+1 != i2) {
            sb.append("..").append(i2-1 + this.);
New to GrepCode? Check out our FAQ X