Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
   * JBoss, Home of Professional Open Source
   * Copyright 2009, Red Hat Middleware LLC, and individual contributors
   * as indicated by the @author tags.
   * See the copyright.txt in the distribution for a
   * full listing of individual contributors.
   * This copyrighted material is made available to anyone wishing to use,
   * modify, copy, or redistribute it subject to the terms and conditions
   * of the GNU Lesser General Public License, v. 2.1.
  * This program is distributed in the hope that it will be useful, but WITHOUT A
  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
  * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
  * You should have received a copy of the GNU Lesser General Public License,
  * v.2.1 along with this distribution; if not, write to the Free Software
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  * MA  02110-1301, USA.
  * (C) 2009,
  * @author JBoss by Red Hat.
 package com.arjuna.ats.internal.arjuna.coordinator;
 import java.util.Map;
 import java.util.Set;
  * Encapsulation of a specialised data structure with API and performance characteristics
  * designed specifically for use by the transaction reaper.
  * ReaperElements represent transactions which need timing out. To do this, the reaper needs
  * to wake periodically and process any timeouts that are due. New elements are added on transaction
  * creation and will be removed prior to their timeout if they terminate normally.
  * For high concurrency, normal inserts and removes should not block. However, to determine the next element
  * which needs (will need) processing, the elements must be ordered or at least searched. These requirements
  * are in conflict, since ordering/searching requires stability i.e. locking.
  * To achieve the desired performance characteristics, we combine two data structures: an unsorted, concurrent
  * collection and a sorted, non-threadsafe one which is guarded by the the ReaperElementManager instance lock.
  * Inserts are done, potentially concurrently, to the unsorted hash set. Removes likewise check this first
  * and can return successfully without blocking if the element is found in this collection. Thus the insert/remove
  * are cheap operations.
  * When it is required to know the smallest (i.e. earliest to timeout) element, the contents
  * of the unsorted set are moved to the sorted set. Since this happens infrequently compared to the insert/delete,
  * only a fraction of the elements inserted should ever be copied - most will be removed without ever migrating.
  * Note that additional external synchronization will be needed to ensure first element does not change
  * between getFirst and any operation depending on its timeout value. This is the TransactionReaper's problem. 
  * The sorted set is maintained manually, rather than using Collections.sort or other comparator based structure.
  * This is because compareTo on reaper elements is relatively expensive and we wish to avoid liner scans to minimise
  * the number of such calls. Hence we prefer ArrayList with binary search, despite the higher insert/remove cost
  * compared to LinkedList.
  * Pay careful attention to locking and performance characteristics if altering this class.
  * @author Jonathan Halliday ( 2009-10
 public class ReaperElementManager

the first (i.e. earliest to time out) element of the colleciton or null if empty
     public synchronized ReaperElement getFirst() {
         flushPending(); // we need to order the elements before we can tell which is first.
         if(.isEmpty()) {
             return null;
         } else {
             return .get(0);
     // Note - unsynchronized for performance.
     public void add(ReaperElement reaperElementthrows IllegalStateException {
         if(.putIfAbsent(reaperElementreaperElement) != null) {
             // note this is best effort - we'll allow double inserts if the element is also in the ordered set.
             throw new IllegalStateException();


reaperElement the reaper element to reorder in the sorted set.
delayMillis the amount of time to increment the element's timeout by.
the new soonest timeout in the set (not necessarily that of the reordered element)
     public synchronized long reorder(ReaperElement reaperElementlong delayMillis) {
         // assume it must be in the sorted list, as it was likely obtained via getFirst...
         // we could add delay to the original timeout, but using current time is probably safer.
         reaperElement.setAbsoluteTimeout((System.currentTimeMillis() + delayMillis));
         // reinsert into its new position.
        // getFirst takes care of flushing the pending set for us.
        return getFirst().getAbsoluteTimeout();
    // use only for testing, it's nasty from a performance perspective.
    public synchronized int size() {
        return (.size() + .size());
    public synchronized boolean isEmpty() {
        return (.isEmpty() && .isEmpty());
    // strange hack to force instant expire of tx during shutdown.
    public synchronized void setAllTimeoutsToZero() {
        for(ReaperElement reaperElement : ) {
    // Note - mostly unsynchronized for performance.
    public void remove(ReaperElement reaperElement) {
        if(.remove(reaperElement) != null) {
        // we missed finding it in the unsorted set - perhaps it has already been copied to the sorted set...
        synchronized(this) {
    // Private methods and structures are guarded where needed by ReaperElementManager instance locks in the
    // public methods - see class header doc comments for concurrency/performance info.
    private void removeSorted(ReaperElement reaperElement) {
        int location = Collections.binarySearch(reaperElement);
        if(location >= 0) {
    private void insertSorted(ReaperElement reaperElement) {
        int location = Collections.binarySearch(reaperElement);
        if(location >= 0) {
            throw new IllegalStateException();
        int insertionPoint = -(location + 1);
    private void flushPending() {
        // purge the pending inserts before doing anything else. This is potentially expensive.
        // Future versions may prefer to insert only a portion of the pending set, or
        // iterate it each time to determine the smallest (head) element.
        if(entrySet != null) {
            Iterator<Map.Entry<ReaperElementReaperElement>> queueIter = entrySet.iterator();
            // iterator is weakly consistent - will traverse elements present at its time of creation,
            // may or may not see later updates.
            while(queueIter.hasNext()) {
                Map.Entry<ReaperElement,ReaperElemententry =;
                ReaperElement element = entry.getValue();
                // insert/remove not locked, so we are careful to check that we don't insert
                // an element that has been removed from the pending set by a concurrent thread.
                if(entrySet.remove(entry)) {
New to GrepCode? Check out our FAQ X