Robust/Transactions/jcarderbenchmarks/mysrc/dstm2/benchmark/ListRelease.java

   1 /*
   2  * ListRelease.java
   3  *
   4  * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
   5  * Clara, California 95054, U.S.A.  All rights reserved.
   6  *
   7  * Sun Microsystems, Inc. has intellectual property rights relating to
   8  * technology embodied in the product that is described in this
   9  * document.  In particular, and without limitation, these
  10  * intellectual property rights may include one or more of the
  11  * U.S. patents listed at http://www.sun.com/patents and one or more
  12  * additional patents or pending patent applications in the U.S. and
  13  * in other countries.
  14  *
  15  * U.S. Government Rights - Commercial software.
  16  * Government users are subject to the Sun Microsystems, Inc. standard
  17  * license agreement and applicable provisions of the FAR and its
  18  * supplements.  Use is subject to license terms.  Sun, Sun
  19  * Microsystems, the Sun logo and Java are trademarks or registered
  20  * trademarks of Sun Microsystems, Inc. in the U.S. and other
  21  * countries.
  22  *
  23  * This product is covered and controlled by U.S. Export Control laws
  24  * and may be subject to the export or import laws in other countries.
  25  * Nuclear, missile, chemical biological weapons or nuclear maritime
  26  * end uses or end users, whether direct or indirect, are strictly
  27  * prohibited.  Export or reexport to countries subject to
  28  * U.S. embargo or to entities identified on U.S. export exclusion
  29  * lists, including, but not limited to, the denied persons and
  30  * specially designated nationals lists is strictly prohibited.
  31  */
  32
  33 package dstm2.benchmark;
  34
  35 import dstm2.atomic;
  36 import dstm2.factory.Factory;
  37 import dstm2.Thread;
  38 import dstm2.factory.Releasable;
  39 import java.lang.reflect.Method;
  40 import java.util.Iterator;
  41
  42 /**
  43  * @author Maurice Herlihy
  44  */
  45 public class ListRelease extends IntSetBenchmark {
  46
  47   static Factory<INode> factory = Thread.makeFactory(INode.class);
  48
  49   protected INode first;
  50
  51   protected void init() {
  52     INode firstList  = factory.create();
  53     firstList.setValue(Integer.MIN_VALUE);
  54     this.first = firstList;
  55     INode firstNext = factory.create();
  56     firstNext.setValue(Integer.MAX_VALUE);
  57     firstList.setNext(firstNext);
  58   }
  59
  60   /**
  61    * This method does all the work. It returns a
  62    * <code>dstm.benchmark.IntSetBenchmark.Neighborhood</code> object containing
  63    * the transactional node with maximal value strictly less than v, and the
  64    * non-transactional TestFactory element containing v (or null, if none exists).
  65    * @param v value sought
  66    * @return neighborhood of value
  67    */
  68   protected Neighborhood find(int v) {
  69     INode last = null;
  70     INode prev = this.first;
  71     INode curr = prev.getNext();
  72     while (curr.getValue() < v) {
  73       if (last != null) {
  74         ((Releasable)last).release();
  75       }
  76       prev = curr;
  77       curr = prev.getNext();
  78     }
  79     if (curr.getValue() == v)
  80       return new Neighborhood(prev, curr);
  81     else
  82       return new Neighborhood(prev);
  83   }
  84
  85   /**
  86    * Add an element to the integer set, if it is not already there.
  87    * @param v the integer value to add from the set
  88    * @return true iff value was added.
  89    */
  90   public boolean insert(int v) {
  91     INode newNode = factory.create();
  92     newNode.setValue(v);
  93     Neighborhood hood = find(v);
  94     if (hood.curr != null) {
  95       return false;
  96     } else {
  97       INode prev = hood.prev;
  98       newNode.setNext(prev.getNext());
  99       prev.setNext(newNode);
 100       return true;
 101     }
 102   }
 103
 104   /**
 105    * Tests wheter a value is in an the integer set.
 106    * @param v the integer value to insert into the set
 107    * @return true iff presence was confirmed.
 108    */
 109   public boolean contains(int v) {
 110     Neighborhood hood = find(v);
 111     return hood.curr != null;
 112   }
 113
 114   /**
 115    * Removes an element from the integer set, if it is there.
 116    * @param v the integer value to delete from the set
 117    * @return true iff v was removed
 118    */
 119   public boolean remove(int v) {
 120     INode newNode = factory.create();
 121     newNode.setValue(v);
 122     Neighborhood hood = find(v);
 123     if (hood.curr == null) {
 124       return false;
 125     } else {
 126       INode prev = hood.prev;
 127       prev.setNext(hood.curr.getNext());
 128       return true;
 129     }
 130   }
 131
 132   @atomic public interface INode {
 133     int getValue();
 134     void setValue(int value);
 135     INode getNext();
 136     void setNext(INode value);
 137   }
 138
 139   public Iterator<Integer> iterator() {
 140     return new Iterator<Integer>() {
 141       INode cursor = ListRelease.this.first.getNext();
 142       public boolean hasNext() {
 143         return cursor.getNext().getValue() != Integer.MAX_VALUE;
 144       }
 145       public Integer next() {
 146         INode node = cursor;
 147         cursor = cursor.getNext();
 148         return node.getValue();
 149       }
 150       public void remove() {
 151         throw new UnsupportedOperationException();
 152       }
 153
 154     };
 155   }
 156   protected class Neighborhood {
 157     public INode prev;
 158     public INode curr;
 159     public Neighborhood(INode prev, INode curr) {
 160       this.prev = prev;
 161       this.curr = curr;
 162     }
 163     public Neighborhood(INode prev) {
 164       this.prev = prev;
 165     }
 166   }
 167
 168     public Thread createThread(int which) {
 169         throw new UnsupportedOperationException("Not supported yet.");
 170     }
 171 }