path: root/tests/plugins/org.eclipse.tcf.debug.test/src/org/eclipse/tcf/debug/test/util/RangeCache.java

/*******************************************************************************
 * Copyright (c) 2014 Wind River Systems, Inc. and others. All rights reserved.
 * This program and the accompanying materials are made available under the terms
 * of the Eclipse Public License v1.0 which accompanies this distribution, and is
 * available at http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     Wind River Systems - initial API and implementation
 *******************************************************************************/
package org.eclipse.tcf.debug.test.util;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.concurrent.ExecutionException;

import org.eclipse.tcf.protocol.Protocol;

/**
 * Cache for efficiently retrieving overlapping ranges of elements from an
 * asynchronous data source. The results of a range request (see
 * {@link #getRange(long, int)}) are kept around and reused in subsequent
 * requests. E.g., two individual, initial requests for 4 bytes at offsets 0 and
 * 4 will relieve a subsequent request for 4 bytes at offset 2 from having to
 * asynchronously retrieve the data from the source. The results from the first
 * two range requests are used to service the third.
 * 
 * <p>
 * Clients of this cache should call {@link #getRange(long, int)} to get a cache
 * for that given range of elements. Sub-classes must implement
 * {@link #retrieve(long, int, DataRequestMonitor)} to retrieve data from the
 * asynchronous data source.
 * 
 * 
 * 
 * @since 2.2
 */
abstract public class RangeCache<V> {
    
    private class Request extends CallbackCache<List<V>> implements Comparable<Request> {
        long fOffset;
        int fCount;
        @Override
        protected void retrieve(DataCallback<java.util.List<V>> rm) {
            RangeCache.this.retrieve(fOffset, fCount, rm); 
        }
        
        Request(long offset, int count) {
            fOffset = offset;
            fCount = count;
        }
        
        public int compareTo(RangeCache<V>.Request o) {
            if (fOffset > o.fOffset) {
                return 1;
            } else if (fOffset == o.fOffset) {
                return 0;
            } else /*if (fOffset < o.fOffset)*/ {
                return -1;
            }
        }
        
        @Override
        public boolean equals(Object _o) {
            if (_o instanceof RangeCache<?>.Request) {
                RangeCache<?>.Request o = (RangeCache<?>.Request)_o;
                return fOffset == o.fOffset && fCount == o.fCount;
            }
            return false;
        }
        
        @Override
        public int hashCode() {
            return (int)fOffset^fCount;
        }
        
        @Override
        public String toString() {
            return "" + fOffset + "(" + fCount + ") -> " + (fOffset + fCount); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
        }
    }

    /**
     * This transaction class implements the main logic of the range cache. 
     * It examines the current requests held by the cache and and creates 
     * requests ones as needed.  Once the requests are all valid it returns
     * the completed data to the client.
     */
    private class RangeTransaction extends Transaction<List<V>> { 
        
        long fOffset;
        int fCount;

        RangeTransaction(long offset, int count) {
            fOffset = offset;
            fCount = count;
        }
        @Override
        protected List<V> process() throws InvalidCacheException, ExecutionException {
            clearCanceledRequests();
            
            List<Request> transactionRequests = getRequests(fOffset, fCount);
            validate(transactionRequests);

            return makeElementsListFromRequests(transactionRequests, fOffset, fCount);
        }
                
        private void clearCanceledRequests() {
            for (Iterator<Request> itr = fRequests.iterator(); itr.hasNext();) {
                Request request = itr.next();
                if (!request.isValid() && request.isCanceled()) {
                    itr.remove();
                }
            }
        }
    }

    /**
     * Requests currently held by this cache.  The requests should be for 
     * non-overlapping ranges of elements.  
     */
    
    private SortedSet<Request> fRequests = new TreeSet<Request>(); 

    /**
     * Retrieves data from the data source. 
     * 
     * @param offset Offset in data range where the requested list of data should start.
     * @param count Number of elements requests.
     * @param rm Callback for the data.
     */
    protected abstract void retrieve(long offset, int count, DataCallback<List<V>> rm);
    
    /**
     * Returns a cache for the range of requested data.  The cache object needs 
     * to be retrieved from range cache every time that the cache is a
     * 
     * @param offset Offset in data range where the requested list of data should start.
     * @param count Number of elements requests.
     * @return Cache object for the requested data.  
     */
    public ICache<List<V>> getRange(final long offset, final int count) {
        assert Protocol.isDispatchThread();
        
        List<Request> requests = getRequests(offset, count);
        
        CallbackCache<List<V>> range = new CallbackCache<List<V>>() {
            @Override
            protected void retrieve(DataCallback<List<V>> rm) {
                new RangeTransaction(offset, count).request(rm);
            }
        };
        
        boolean valid = true;
        List<Throwable> errors = null; 
        for (ICache<?> request : requests) {
            if (request.isValid()) {
                if (request.getError() != null) {
                    errors = errors != null ? errors : new ArrayList<Throwable>(requests.size());
                    errors.add(request.getError());
                }
            } else {
                valid = false;
                break;
            }
        }
        
        if (valid) {
            if (errors == null) {
                range.set(makeElementsListFromRequests(requests, offset, count), null, true);
            } else {
                if (errors.size() == 1) {
                    range.set(null, errors.get(0), true);
                } else {
                    AggregateError aggregateError = new AggregateError("Multiple Errors");
                    for (Throwable error : errors) aggregateError.add(error);
                }
            }
        }
        
        return range; 
    }
    
    /**
     * Sets the given list and status to the cache.  Subsequent range requests 
     * that fall in its the range will return the given data.  Requests outside 
     * of its range will trigger a call to {@link #retrieve(long, int, DataRequestMonitor)}.<br>
     * The given data parameter can be <code>null</code> if the given status 
     * parameter contains an error.  In this case all requests in the given 
     * range will return the error. 
     * 
     * @param offset Offset of the given data to set to cache.
     * @param count Count of the given data to set to cache.
     * @param data List of elements to set to cache.  Can be <code>null</code>. 
     * @param error Error object to set to cache or <code>null</code> if none.
     */
    public void set(long offset, int count, List<V> data, Throwable error) {
        for (Request request : fRequests) {
            if (!request.isValid()) {
                request.set(null, null, false);
            }
        }
        fRequests.clear();
        Request request = new Request(offset, count);
        request.set(data, error, true);
        fRequests.add(request);
    }
    
    /**
     * Forces the cache into an invalid state.  If there are any pending 
     * requests, their will continue and their results will be cached. 
     */
    protected void reset() {
        for (Iterator<Request> itr = fRequests.iterator(); itr.hasNext();) {
            Request request = itr.next();
            if (request.isValid()) {
                request.reset();
                itr.remove();
            }
        }
    }
    
    private List<Request> getRequests(long fOffset, int fCount) {
        List<Request> requests = new ArrayList<Request>(1);
        
        // Create a new request for the data to retrieve.
        Request current = new Request(fOffset, fCount);
        
        current = adjustRequestHead(current, requests, fOffset, fCount);
        if (current != null) {
            current = adjustRequestTail(current, requests, fOffset, fCount);
        }
        if (current != null) {
            requests.add(current);
            fRequests.add(current);
        }
        return requests;
    }
    
    // Adjust the beginning of the requested range of data.  If there 
    // is already an overlapping range in front of the requested range, 
    // then use it.
    private Request adjustRequestHead(Request request, List<Request> transactionRequests, long offset, int count) {
        SortedSet<Request> headRequests = fRequests.headSet(request);
        if (!headRequests.isEmpty()) {
            Request headRequest = headRequests.last();
            long headEndOffset = headRequest.fOffset + headRequest.fCount;
            if (headEndOffset > offset) {
                transactionRequests.add(headRequest);
                request.fCount = (int)(request.fCount - (headEndOffset - offset));
                request.fOffset = headEndOffset;
            }
        }
        if (request.fCount > 0) {
            return request;
        } else {
            return null;
        }
    }

    /**
     * Adjust the end of the requested range of data.
     * @param current
     * @param transactionRequests
     * @return
     */
    private Request adjustRequestTail(Request current, List<Request> transactionRequests, long offset, int count) {
        // Create a duplicate of the tailSet, in order to avoid a concurrent modification exception.
        List<Request> tailSet = new ArrayList<Request>(fRequests.tailSet(current));
        
        // Iterate through the matching requests and add them to the requests list.
        for (Request tailRequest : tailSet) {
            if (tailRequest.fOffset < current.fOffset + count) {
                // found overlapping request add it to list
                if (tailRequest.fOffset <= current.fOffset) {
                    // next request starts off at the beginning of current request
                    transactionRequests.add(tailRequest);
                    current.fOffset = tailRequest.fOffset + tailRequest.fCount;
                    current.fCount = ((int)(offset - current.fOffset)) + count ;
                    if (current.fCount <= 0) {
                        return null;
                    }
                } else {
                    current.fCount = (int)(tailRequest.fOffset - current.fOffset);
                    transactionRequests.add(current);
                    fRequests.add(current);
                    current = null;
                    transactionRequests.add(tailRequest);
                    long tailEndOffset = tailRequest.fOffset + tailRequest.fCount;
                    long rangeEndOffset = offset + count;
                    if (tailEndOffset >= rangeEndOffset) {
                        return null;
                    } else {
                        current = new Request(tailEndOffset, (int)(rangeEndOffset - tailEndOffset));
                    }
                }
            } else {
                break;
            }
        }
        return current;
    }
    
    private List<V> makeElementsListFromRequests(List<Request> requests, long offset, int count) {
        List<V> retVal = new ArrayList<V>(count);
        long index = offset;
        long end = offset + count;
        int requestIdx = 0;
        while (index < end ) {
            Request request = requests.get(requestIdx);
            if (index < request.fOffset + request.fCount) {
                int dataIndex = (int)(index - request.fOffset);
                if (dataIndex < request.getData().size()) {
                    retVal.add( request.getData().get(dataIndex) );
                } else {
                    // If request didnt' return enough data, pad range with nulls.
                    retVal.add(null);
                }
                index ++;
            } else {
                requestIdx++;
            }
        }
        return retVal;
    }    
}