使用Mutex实现线程安全的链表功能

1、Mutex是个简单的互斥排它锁
2、Node是链表的节点，没有节点都持有自己的Mutex锁
3、List是链表，在search方法中通过对节点的加锁和解锁达到同步的目的

public class Mutex {
 
  /** 是否锁定的状态位 **/
  protected boolean inuse_ = false;
 
  public void acquire() throws InterruptedException {
    if (Thread.interrupted()) throw new InterruptedException();
    synchronized(this) {
      try {
        while (inuse_) wait();
        inuse_ = true;
      }
      catch (InterruptedException ex) {
        notify();
        throw ex;
      }
    }
  }
 
  public synchronized void release()  {
    inuse_ = false;
    notify(); 
  }
 
}
 
 class Node { 
   Object item; //节点对象，实际使用时可以用领域对象进行替换
   Node next; 
   Mutex lock = new Mutex(); // 每个节点都保存自己的锁对象
 
   Node(Object x, Node n) { item = x; next = n; }
 }
 
 class List {
    protected Node head; 
 
    protected synchronized Node getHead() { return head; }
 
    boolean search(Object x) throws InterruptedException {
      Node p = getHead();
      if (p == null) return false;
 
 
      p.lock.acquire();              // 先加锁，再循环
 
      for (;;) {
        if (x.equals(p.item)) {
          p.lock.release();          // 找到直接释放锁
          return true;
        }
        else {
          Node nextp = p.next;
          if (nextp == null) {
            p.lock.release();       // 没有找到对象，也要释放锁
            return false;
          }
          else {
            try {
              nextp.lock.acquire(); // 给链表下一个节点加锁
            }
            catch (InterruptedException ex) {
              p.lock.release();    // 加锁如果失败，也要释放前一个节点的锁
              throw ex;
            }
            p.lock.release();      // 加锁成功，释放前一个节点的锁
            p = nextp;
          }
        }
      }
    }
 
    synchronized void add(Object x) { // simple prepend
      head = new Node(x, head);
    }
 
    // ...  
 }