Robust/Transactions/dstm2src/benchmark/List.java

   1 /*
   2  * List.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 java.util.Iterator;
  39
  40 /**
  41  * @author Maurice Herlihy
  42  */
  43 public class List extends IntSetBenchmark {
  44
  45   static Factory<INode> factory = Thread.makeFactory(INode.class);
  46
  47   protected INode first;
  48
  49   protected void init() {
  50     INode firstList  = factory.create();
  51     firstList.setValue(Integer.MIN_VALUE);
  52     this.first = firstList;
  53     INode firstNext = factory.create();
  54     firstNext.setValue(Integer.MAX_VALUE);
  55     firstList.setNext(firstNext);
  56   }
  57
  58   /**
  59    * This method does all the work. It returns a
  60    * <code>dstm.benchmark.IntSetBenchmark.Neighborhood</code> object containing
  61    * the transactional node with maximal value strictly less than v, and the
  62    * non-transactional TestFactory element containing v (or null, if none exists).
  63    * @param v value sought
  64    * @return neighborhood of value
  65    */
  66   protected Neighborhood find(int v) {
  67     INode prevNode = this.first;
  68     INode currNode = prevNode.getNext();
  69     while (currNode.getValue() < v) {
  70       prevNode = currNode;
  71       currNode = prevNode.getNext();
  72     }
  73     if (currNode.getValue() == v)
  74       return new Neighborhood(prevNode, currNode);
  75     else
  76       return new Neighborhood(prevNode);
  77   }
  78
  79   /**
  80    * Add an element to the integer set, if it is not already there.
  81    * @param v the integer value to add from the set
  82    * @return true iff value was added.
  83    */
  84   public boolean insert(int v) {
  85     INode newNode = factory.create();
  86     newNode.setValue(v);
  87     Neighborhood hood = find(v);
  88     if (hood.currNode != null) {
  89       return false;
  90     } else {
  91       INode prevNode = hood.prevNode;
  92       newNode.setNext(prevNode.getNext());
  93       prevNode.setNext(newNode);
  94       return true;
  95     }
  96   }
  97
  98   /**
  99    * Tests wheter a value is in an the integer set.
 100    * @param v the integer value to insert into the set
 101    * @return true iff presence was confirmed.
 102    */
 103   public boolean contains(int v) {
 104     Neighborhood hood = find(v);
 105     return hood.currNode != null;
 106   }
 107
 108   /**
 109    * Removes an element from the integer set, if it is there.
 110    * @param v the integer value to delete from the set
 111    * @return true iff v was removed
 112    */
 113   public boolean remove(int v) {
 114     INode newNode = factory.create();
 115     newNode.setValue(v);
 116     Neighborhood hood = find(v);
 117     if (hood.currNode == null) {
 118       return false;
 119     } else {
 120       INode prevNode = hood.prevNode;
 121       prevNode.setNext(hood.currNode.getNext());
 122       return true;
 123     }
 124   }
 125
 126   @atomic public interface INode {
 127     int getValue();
 128     void setValue(int value);
 129     INode getNext();
 130     void setNext(INode value);
 131   }
 132
 133   public Iterator<Integer> iterator() {
 134     return new Iterator<Integer>() {
 135       INode cursor = List.this.first.getNext();
 136       public boolean hasNext() {
 137         return cursor.getNext().getValue() != Integer.MAX_VALUE;
 138       }
 139       public Integer next() {
 140         INode node = cursor;
 141         cursor = cursor.getNext();
 142         return node.getValue();
 143       }
 144       public void remove() {
 145         throw new UnsupportedOperationException();
 146       }
 147
 148     };
 149   }
 150   protected class Neighborhood {
 151     public INode prevNode;
 152     public INode currNode;
 153     public Neighborhood(INode prevNode, INode currNode) {
 154       this.prevNode = prevNode;
 155       this.currNode = currNode;
 156     }
 157     public Neighborhood(INode prevNode) {
 158       this.prevNode = prevNode;
 159     }
 160   }
 161
 162     public Thread createThread(int which) {
 163         throw new UnsupportedOperationException("Not supported yet.");
 164     }
 165
 166
 167
 168
 169
 170 }