Robust/Transactions/dstm2/src/dstm2/benchmark/ListSnap.java

   1 /*
   2  * ListSnap.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 //import TransactionalIO.exceptions.AbortedException;
  35 import TransactionalIO.exceptions.*;//GracefulException;
  36 import dstm2.atomic;
  37 import dstm2.benchmark.IntSetBenchmark;
  38 import dstm2.Thread;
  39 import dstm2.factory.Factory;
  40 import dstm2.factory.Snapable;
  41 import java.lang.reflect.Method;
  42 import java.util.Iterator;
  43 import java.util.concurrent.Callable;
  44
  45 /**
  46  * @author Maurice Herlihy
  47  */
  48 public class ListSnap extends IntSetBenchmark {
  49
  50   static Factory<INode> factory = Thread.makeFactory(INode.class);
  51
  52   protected INode first;
  53
  54   protected void init() {
  55     INode firstList  = factory.create();
  56     firstList.setValue(Integer.MIN_VALUE);
  57     this.first = firstList;
  58     INode firstNext = factory.create();
  59     firstNext.setValue(Integer.MAX_VALUE);
  60     firstList.setNext(firstNext);
  61   }
  62
  63   /**
  64    * Tests wheter a value is in an the integer set.
  65    * @param v the integer value to insert into the set
  66    * @return true iff presence was confirmed.
  67    */
  68   public boolean contains(int v) {
  69     INode last = null;
  70     INode lastSnap = null;
  71     INode prev = this.first;
  72     INode prevSnap = ((Snapable<INode>)prev).snapshot();
  73     INode curr = prevSnap.getNext();
  74     INode currSnap = ((Snapable<INode>)curr).snapshot();
  75     while (currSnap.getValue()< v) {
  76       if (last != null) {
  77         ((Snapable<INode>)last).validate(lastSnap);
  78       }
  79       last = prev;
  80       lastSnap = prevSnap;
  81       prev = curr;
  82       prevSnap = currSnap;
  83       curr = prevSnap.getNext();
  84       currSnap = ((Snapable<INode>)curr).snapshot();
  85     }
  86     if (lastSnap != null) {
  87       ((Snapable<INode>)last).upgrade(lastSnap);
  88     }
  89     ((Snapable<INode>)prev).upgrade(prevSnap);
  90     ((Snapable<INode>)curr).upgrade(currSnap);
  91     return (curr.getValue()== v);
  92   }
  93
  94   /**
  95    * Removes an element from the integer set, if it is there.
  96    * @param v the integer value to delete from the set
  97    * @return true iff v was removed
  98    */
  99   public boolean remove(int v) {
 100     INode last = null;
 101     INode lastSnap = null;
 102     INode prev = this.first;
 103     INode prevSnap = ((Snapable<INode>)prev).snapshot();
 104     INode curr = prevSnap.getNext();
 105     INode currSnap = ((Snapable<INode>)curr).snapshot();
 106     while (currSnap.getValue()< v) {
 107       if (last != null) {
 108         ((Snapable<INode>)last).validate(lastSnap);
 109       }
 110       last = prev;
 111       lastSnap = prevSnap;
 112       prev = curr;
 113       prevSnap = currSnap;
 114       curr = prevSnap.getNext();
 115       currSnap = ((Snapable<INode>)curr).snapshot();
 116     }
 117     if (lastSnap != null) {
 118       ((Snapable<INode>)last).upgrade(lastSnap);
 119     }
 120     ((Snapable<INode>)prev).upgrade(prevSnap);
 121     ((Snapable<INode>)curr).upgrade(currSnap);
 122     if (curr.getValue()!= v) {
 123       return false;
 124     } else {
 125       prev.setNext(curr.getNext());
 126       return true;
 127     }
 128   }
 129
 130   public boolean insert(int v) {
 131     INode last = null;
 132     INode lastSnap = null;
 133     INode prev = this.first;
 134     Snapable<INode> prevS = (Snapable<INode>)prev;
 135     INode prevSnap = prevS.snapshot();
 136     INode curr = prevSnap.getNext();
 137     INode currSnap = ((Snapable<INode>)curr).snapshot();
 138     INode newNode = factory.create();
 139     while (currSnap.getValue()< v) {
 140       if (last != null) {
 141         ((Snapable<INode>)last).validate(lastSnap);
 142       }
 143       last = prev;
 144       lastSnap = prevSnap;
 145       prev = curr;
 146       prevSnap = currSnap;
 147       curr = prevSnap.getNext();
 148       currSnap = ((Snapable<INode>)curr).snapshot();
 149     }
 150     if (lastSnap != null) {
 151       ((Snapable<INode>)last).upgrade(lastSnap);
 152     }
 153     ((Snapable<INode>)prev).upgrade(prevSnap);
 154     ((Snapable<INode>)curr).upgrade(currSnap);
 155     if (currSnap.getValue()== v) {
 156       return false;
 157     } else {
 158       newNode.setNext(curr);
 159       prev.setNext(newNode);
 160       return true;
 161     }
 162   }
 163
 164   public Iterator<Integer> iterator() {
 165     return new Iterator<Integer>() {
 166       INode cursor = ListSnap.this.first.getNext();
 167       public boolean hasNext() {
 168         return cursor.getNext().getValue() == Integer.MAX_VALUE;
 169       }
 170       public Integer next() {
 171         INode node = cursor;
 172         cursor = cursor.getNext();
 173         return node.getValue();
 174       }
 175       public void remove() {
 176         throw new UnsupportedOperationException();
 177       }
 178
 179     };
 180   }
 181   protected class Neighborhood {
 182     public INode prev;
 183     public INode curr;
 184     public Neighborhood(INode prev, INode curr) {
 185       this.prev = prev;
 186       this.curr = curr;
 187     }
 188     public Neighborhood(INode prev) {
 189       this.prev = prev;
 190     }
 191   }
 192
 193   @atomic public interface INode {
 194     int getValue();
 195     void setValue(int value);
 196     INode getNext();
 197     void setNext(INode value);
 198   }
 199
 200     public Thread createThread(int which) {
 201         throw new UnsupportedOperationException("Not supported yet.");
 202     }
 203 }
 204