Interval lock Implementation

As @c0der suggested I've made an implementation that simply tracks the locked intervals.

My code implies a Range class that ...

• is immutable
• has a lower and upper bound (extending to unbounded ranges shouldn't be too hard)
• properly implements equals() and hashCode()

The RangeLock class currently only implements a blocking lock method. Unlocking is done through a returned Unlocker instance. This is to avoid threads not having acquired the lock, being able to unlock a given Range.

public class RangeLock<T extends Comparable<? super T>> {

    private final SortedSet<Range<T>> locked = new TreeSet<>(Comparator.comparing(Range::lower));
    private final Object lock = new Object();

    public Unlocker lock(Range<T> range) throws InterruptedException {
        synchronized (lock) {
            while (!available(range)) {
                lock.wait();
            }
            locked.add(range);
            return () -> {
                synchronized (lock) {
                    locked.remove(range);
                    lock.notifyAll();
                }
            };
        }
    }

    private boolean available(Range<T> range) {
        SortedSet<Range<T>> tailSet = locked.tailSet(range);
        SortedSet<Range<T>> headSet = locked.headSet(range);
        return (tailSet.isEmpty() || !tailSet.first().overlaps(range)) && (headSet.isEmpty() || !headSet.last().overlaps(range));
    }

    public interface Unlocker {
        void unlock();
    }
}

I think the question is essentially about an efficient way to have a thread wait and retry.
How about listening to changes in the

array of existing granted intervals

and retry only when it has changed ?
The following should not be considered a proper implementation (my experience with thread is very limited), but a demonstration of the proposed mechanism:

Ranges.java and Range.java

//represents all ranges
//see also: https://stackoverflow.com/a/7721388/3992939
public class Ranges {

    private List<Range> ranges = new ArrayList<>();
    private PropertyChangeSupport rangeChangedProperty = new PropertyChangeSupport(this);

    public Range getRange(int rangeStart, int rangeEnd) {

        if(contains(rangeStart) || contains(rangeEnd)) {
            return null;
        }
        Range range = new Range(rangeStart, rangeEnd);
        range.addListener( (observable, oldValue, newValue) -> {
                rangeChangedProperty.firePropertyChange("Range", "-" , "changed");
            }
        );
        ranges.add(range);
        return range;
    }

    private boolean contains(int number){
        for(Range range : ranges) {
            if(range.contains(number)) {return true;}
        }
        return false;
    }

    public boolean removeRange(Range range) {

        boolean isContains = ranges.remove(range);
        rangeChangedProperty.firePropertyChange("Range", "-" , "removed");
        return isContains;
    }

    /**
     * Listen to {@link #rangeChangedProperty}. Fires whenever a range changes
     * or removed.
     * <br/>A client and a listener and when it fires, notify all threads.
     */
    public void addChangeListener(PropertyChangeListener listener) {
        rangeChangedProperty.addPropertyChangeListener(listener);
    }

    //represents a single range
    //It is muttable 
    //can be implemented using ValueRange (https://stackoverflow.com/a/40716042/3992939)
    class Range{

        private SimpleIntegerProperty low = new SimpleIntegerProperty();
        private SimpleIntegerProperty high = new SimpleIntegerProperty();
        private SimpleObjectProperty<int[]> rangeProperty = new SimpleObjectProperty<>();

        private Range(int rangeStart, int rangeEnd){

            low.set(rangeStart) ; high.set(rangeEnd);
            updateRange();
            low.addListener((observable, oldValue, newValue) -> { updateRange(); });
            high.addListener((observable, oldValue, newValue) -> { updateRange(); });
        }

        /**
         * Listen to {@link #rangeProperty} that changes whenever the range changes
         */
        void addListener(ChangeListener<int[]> listener) {
            rangeProperty.addListener(listener);
        }

        private void updateRange() {rangeProperty.set(new int[] {low.get(), high.get()});}

        public int getRangeStart() { return low.get(); }

        public void setRangeStart(int rangeStart) { low.set(rangeStart);}

        public int getRangeEnd() {return high.get();}

        public void setRangeEnd(int rangeEnd) { high.set(rangeEnd);}

        public boolean contains(int number){
            int min = Math.min(low.get(), high.get());
            int max = Math.max(low.get(), high.get());
            return ((number >= min) && (number <= max));
        }
    }
}

GetRange.java

//used to simulate a thread trying to get a range 
public class GetRange implements Runnable{

    private Ranges ranges;
    private int low, high;
    private String id;

    GetRange(Ranges ranges, int low, int high, String id) {
        this.ranges = ranges;
        this.low = low; this.high = high; this.id = id;
    }

    @Override
    public void run() {
        synchronized (ranges) {
            while(ranges.getRange(low,high) == null) {
                System.out.println("Tread "+ id + " is waiting");
                try {
                    ranges.wait();
                } catch (InterruptedException ex) { ex.printStackTrace();}
            }
        }
        System.out.println("Tread "+ id + " got range. All done");
    }
}

Test is with :

//test
public static void main(String[] args) throws InterruptedException {
    Ranges ranges = new Ranges();
    ranges.addChangeListener( (evt) -> {
        synchronized (ranges) {
            ranges.notifyAll();
            System.out.println(evt.getPropertyName() + " "+ evt.getNewValue());
        }
    });

    Range range1 = ranges.getRange(10,15);
    Range range2 = ranges.getRange(20,25);

    new Thread(new GetRange(ranges, 10, 12, "A")).start();
    new Thread(new GetRange(ranges, 21, 28, "B")).start();
    new Thread(new GetRange(ranges, 10, 12, "C")).start();

    Thread.sleep(50);
    System.out.println("-- Changing end of range 1. Threads notifyied and keep waiting -----");
    range1.setRangeEnd(16);   //no thread effected
    Thread.sleep(50);
    System.out.println("-- Changing start of range 1. Threads notifyied and A or C get range -----");
    range1.setRangeStart(13); //effects thread A or C
    Thread.sleep(50);
    System.out.println("-- Removing range 2. Threads notifyied and B get range -----");
    ranges.removeRange(range2);//effects thread B
    Thread.sleep(50);
    System.exit(1);
}

Output:

Tread A is waiting
Tread C is waiting
Tread B is waiting
-- Changing end of range 1. Threads notifyied and keep waiting -----
Range changed
Tread B is waiting
Tread C is waiting
Tread A is waiting
-- Changing start of range 1. Threads notifyied and A or C get range -----
Range changed Tread A got range. All done
Thread C is waiting
Tread B is waiting
-- Removing range 2. Threads notifyied and B get range -----
Range removed
Tread B got range. All done
Tread C is waiting

Guava's Striped locks may be of interest to you.

If you have a function int key(int p) which returns the index i of the interval [x_i,y_i] which p belongs to, you could probably use a Striped lock to achieve your goal.

For instance, if we had as interval bounds the points x_1, x_2, ... x_n such that x_i < x_(i+1) and x_(i+1) - x_i remains constant over all i from 1 to n, we could use something like key(p) = p -> (p - x_1) / n.

However, based on the notation you chose, this assumption may not hold and the function key be not as straightforward - but hopefully a lock striping solution will work for you.

This is my implementation for IntervalLock that supports Read and Write locks. Reads may acquire locks that have ranges overlapped, while a write must wait if its range overlaps with any other read or write. The basic idea is to use an interval tree to store the ranges. At a given time, each range may hold a write lock or multiple read locks. Insertion and deletion ranges from the tree must done carefully to prevent any race conditions. The code uses an implementation of interval tree from here.

SemaphoreInterval.java

package intervallock;

import java.util.ArrayList;
import java.util.concurrent.Semaphore;

import datastructures.Interval;

public class SemaphoreInterval implements Interval {
    private ArrayList<Semaphore> semaphores;
    private int start;
    private int end;
    private int mode;

    public SemaphoreInterval(int start, int end, int mode) {
        this.semaphores = new ArrayList<>(1);
        this.start = start;
        this.end = end;
        this.mode = mode;
    }

    public int getMode() {
        return mode;
    }

    public ArrayList<Semaphore> getSemaphores() {
        return semaphores;
    }

    @Override
    public int start() {
        return start;
    }

    @Override
    public int end() {
        return end+1;
    }
}

IntervalLock.java

package intervallock;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.Semaphore;

import datastructures.IntervalTree;

/**
 * An implementation of Interval Lock
 * 
 * @author Hieu
 *
 */
public class IntervalLock {
    public IntervalTree<SemaphoreInterval> tree;
    private Semaphore treeLock;
    private int maxPermits;

    public static final int READ = 0;
    public static final int WRITE = 1;

    public IntervalLock(int maxPermits) {
        tree = new IntervalTree<>();
        treeLock = new Semaphore(1);
        this.maxPermits = maxPermits;
    }

    /**
     * Acquire a lock on range [start, end] with the specified mode.
     * @param start The start of the interval
     * @param end   The end of the interval
     * @param mode  The mode, either IntervalLock.READ or IntervalLock.WRITE.
     * @return The SemaphoreInterval instance.
     */
    public SemaphoreInterval acquire(int start, int end, int mode) {
        SemaphoreInterval si = new SemaphoreInterval(start, end, mode);
        Set<Semaphore> semaphores = new HashSet<>();

        try {
            treeLock.acquire();
        } catch (InterruptedException e) {
            e.printStackTrace(System.out);
            System.exit(-1);
        }

        Iterator<SemaphoreInterval> overlappers = tree.overlappers(si);
        while (overlappers.hasNext()) {
            SemaphoreInterval i = overlappers.next();
            if (i == null) {
                System.out.println("Error: Getting a null interval");
                System.exit(-1);
            }

            if (i.compareTo(si) == 0)
                continue;

            switch (i.getMode()) {
            case READ:
                if (mode == WRITE) 
                    semaphores.addAll(i.getSemaphores());
                break;
            case WRITE:
                semaphores.addAll(i.getSemaphores());
                break;
            }
        }

        SemaphoreInterval result = tree.insert(si);
        if (result != null)
            si = result;
        si.getSemaphores().add(new Semaphore(0));
        treeLock.release();

        for (Semaphore s: semaphores) {
            try {
                s.acquire();
            } catch (InterruptedException e) {
                e.printStackTrace(System.out);
                System.exit(-1);
            }
        }

        return si;
    }

    /**
     * Release the range lock hold on specified SemaphoreInterval.
     * @param si The semaphore interval returned by the acquire().
     */
    public void release(SemaphoreInterval si) {
        try {
            treeLock.acquire();
        } catch (InterruptedException e) {
            e.printStackTrace(System.out);
            System.exit(-1);
        }
        if (si.getSemaphores() == null || si.getSemaphores().size() == 0) {
            System.out.println("Error: Empty array of semaphores");
            treeLock.release();
            return;
        }
        Semaphore sm = si.getSemaphores().remove(0);
        if (si.getSemaphores().size() == 0) {
            boolean success = tree.delete(si);
            if (!success) {
                System.out.println("Error: Cannot remove an interval.");
                treeLock.release();
                return;
            }
        }
        treeLock.release();
        sm.release(maxPermits);
    }
}

Usage

// init the lock with the max permits per semaphore (should be the max number of threads)
public static final IntervalLock lock = new IntervalLock(1000);

// ...

// acquire the lock on range [a, b] (inclusive), with mode (either IntervalLock.READ or IntervalLock.WRITE)
// it returns a SemaphoreInterval instance
SemaphoreInterval si = lock.acquire(a, b, mode);

// ...

// release the acquired lock
lock.release(si);