/*
  More tests of various singleton implementations
  last update: Mon Mar 26 20:19:39 2001  Doug Lea  (dl at gee)
*/


class TSS extends Thread {

  static abstract class Singleton {
    // a  field and method to prevent some compiler optimizations
    int aField = System.identityHashCode(this);
    int aMethod(int i) { return (i % 17) != 0 ? aField: i; }
  }

  static class EagerSingleton extends Singleton {
    static final EagerSingleton theInstance = new EagerSingleton();
    static EagerSingleton getInstance() {
      return theInstance;
    }
  }


  static class SynchedSingleton extends Singleton {
    static SynchedSingleton theInstance;
    static synchronized SynchedSingleton getInstance() {
      if (theInstance == null) 
        theInstance = new SynchedSingleton();
      return theInstance;
    }
  }

  static class ThreadLocalSingleton extends Singleton {
    static final ThreadLocal perThreadInstance = new ThreadLocal();
    static final Object lock = new Object();
    static ThreadLocalSingleton theInstance;

    static ThreadLocalSingleton getInstance() {
      ThreadLocalSingleton instance = (ThreadLocalSingleton)(perThreadInstance.get());
      if (instance == null) {

        synchronized(lock) {
          instance = theInstance;
          if (instance == null) 
            instance = theInstance = new ThreadLocalSingleton();
        }
        // copy global to per-thread
        perThreadInstance.set(instance);
      }
      return instance;
    }
  }

  static class SimulatedThreadLocalSingleton extends Singleton {
    static SimulatedThreadLocalSingleton theInstance;
    static final Object lock = new Object();
    static final Object key = new Object();

    static Singleton getInstance() {
      TSS t = (TSS)(Thread.currentThread());
      Singleton instance = (Singleton)(t.threadLocalHashtable.get(key));
      if (instance == null) {

        synchronized(lock) {
          instance = theInstance;
          if (instance == null) 
            instance = theInstance = new SimulatedThreadLocalSingleton();
        }
        // copy global to per-thread
        t.threadLocalHashtable.put(key, instance);
      }
      return instance;
    }
  }


  static class VolatileSingleton extends Singleton {
    static final Object lock = new Object();
    static volatile VolatileSingleton theInstance;

    static VolatileSingleton getInstance() {
      VolatileSingleton instance = theInstance;
      if (instance == null) {
        synchronized(lock) {
          instance = theInstance;
          if (instance == null) 
            instance = theInstance = new VolatileSingleton();
        }
      }
      return instance;
    }
  }

  static class DirectThreadFieldSingleton extends Singleton {
    static DirectThreadFieldSingleton theInstance;
    static final Object lock = new Object();

    static Singleton getInstance(TSS t) {
      Singleton instance = t.singleton;
      if (instance == null) {

        synchronized(lock) {
          instance = theInstance;
          if (instance == null) 
            instance = theInstance = new DirectThreadFieldSingleton();
        }
        // copy global to per-thread
        t.singleton = instance;
      }
      return instance;
    }
  }



  static class ThreadFieldSingleton extends Singleton {
    static final Object lock = new Object();
    static ThreadFieldSingleton theInstance;

    static Singleton getInstance() {
      TSS t = (TSS)(Thread.currentThread());
      Singleton instance = t.singleton;
      if (instance == null) {

        synchronized(lock) {
          instance = theInstance;
          if (instance == null) 
            instance = theInstance = new ThreadFieldSingleton();
        }
        // copy global to per-thread
        t.singleton = instance;
      }
      return instance;
    }
  }



  static final int ITERS = 1000000;
  static final int NTHREADS = 8;

  static int total; // accumulate calls to aMethod, to prevent overoptimizing


  final IDHashMap threadLocalHashtable = new IDHashMap(8);
  Singleton singleton;
  int mode;
  TSS(int md) { mode = md; }

  public void run() {
    int sum = 0; // to prevent optimizations

    if (mode == 0) {
      for (int i = 0; i < ITERS; ++i) {
        sum += EagerSingleton.getInstance().aMethod(i);
      }
    }
    else if (mode == 1) {
      for (int i = 0; i < ITERS; ++i) {
        sum += ThreadLocalSingleton.getInstance().aMethod(i);
      }
    }
    else if (mode == 2) {
      for (int i = 0; i < ITERS; ++i) {
        sum += SimulatedThreadLocalSingleton.getInstance().aMethod(i);
      }
    }
    else if (mode == 3) {
      for (int i = 0; i < ITERS; ++i) {
        sum += VolatileSingleton.getInstance().aMethod(i);
      }
    }
    else if (mode == 4) {
      for (int i = 0; i < ITERS; ++i) {
        sum += SynchedSingleton.getInstance().aMethod(i);
      }
    }
    else if (mode == 5) {
      for (int i = 0; i < ITERS; ++i) {
        sum += DirectThreadFieldSingleton.getInstance(this).aMethod(i);
      }
    }
    else if (mode == 6) {
      for (int i = 0; i < ITERS; ++i) {
        sum += ThreadFieldSingleton.getInstance().aMethod(i);
      }
    }

    total += sum;
  }

  public static void main(String[] args) {

    Thread[] threads = new Thread[NTHREADS];

    for (int reps = 0; reps < 3; ++reps) {

      for (int i = 0; i < NTHREADS; ++i) 
        threads[i] = null;
      System.gc();

      for (int mode = 0; mode < 7; ++mode) {

        if (mode == 0) 
          System.out.print("Eager:            ");
        else if (mode == 1) 
          System.out.print("ThreadLocal:      ");
        else if (mode == 2)
          System.out.print("SimThreadLocal:   ");
        else if (mode == 3)
          System.out.print("Volatile (DCL):   ");
        else if (mode == 4)
          System.out.print("Synch:            ");
        else if (mode == 5)
          System.out.print("Direct Field:     ");
        else if (mode == 6)
          System.out.print("Thread Field:     ");

        long startTime = System.currentTimeMillis();

        for (int i = 0; i < NTHREADS; ++i) 
          threads[i] = new TSS(mode);
        
        for (int i = 0; i < NTHREADS; ++i) 
          threads[i].start();
        
        try {
          for (int i = 0; i < NTHREADS; ++i) 
            threads[i].join();
        }
        catch (InterruptedException ie) {
          System.out.println("Interrupted");
          return;
        }

        long elapsed = System.currentTimeMillis() - startTime;
        System.out.println(elapsed + "ms");

        if (total == 0) // ensure total is live to avoid optimizing away
          System.out.println("useless number = " + total);
        
      }
    }
  }
}


/*
  Renamed and hacked version of 1.4 IdentityHashMap so can test on pre-1.4
*/

class IDHashMap {
    /**
     * The initial capacity used by the no-args constructor.
     * MUST be a power of two.  The value 32 corresponds to the
     * (specified) expected maximum size of 21, given a load factor
     * of 2/3.
     */
    private static final int DEFAULT_CAPACITY = 32;

    /**
     * The minimum capacity, used if a lower value is implicitly specified
     * by either of the constructors with arguments.  The value 4 corresponds
     * to an expected maximum size of 2, given a load factor of 2/3.
     * MUST be a power of two.
     */
    private static final int MINIMUM_CAPACITY = 4;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<29.
     */
    private static final int MAXIMUM_CAPACITY = 1 << 29;

    /**
     * Special value used to mark slots as deleted.
     */
    private static final Object DELETED = new Object();

    /**
     * Special value used to mark slots as empty.
     */
    private static final Object EMPTY = new Object();

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    private transient Object[] table;

    /**
     * The number of key-value mappings contained in this identity hash map.
     *
     * @serial
     */
    private int size;


    /**
     * The next size value at which to resize (capacity * load factor).
     */
    private transient int threshold;

    /**
     * Constructs a new, empty identity hash map with a default expected
     * maximum size (21).
     */
    public IDHashMap() {
        init(DEFAULT_CAPACITY);
    }


    /**
     * Constructs a new, empty map with the specified expected maximum size.
     * Putting more than the expected number of key-value mappings into
     * the map may cause the internal data structure to grow, which may be
     * somewhat time-consuming.
     *
     * @param expectedMaxSize the expected maximum size of the map.
     * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
     */
    public IDHashMap(int expectedMaxSize) {
        if (expectedMaxSize < 0)
            throw new IllegalArgumentException("expectedMaxSize is negative");

        init(capacity(expectedMaxSize));
    }

    /**
     * Returns the appropriate capacity for the specified expected maximum
     * size.  Returns the smallest power of two between MINIMUM_CAPACITY
     * and MAXIMUM_CAPACITY, inclusive, that is greater than
     * (3 * expectedMaxSize)/2, if such a number exists.  Otherwise
     * returns MAXIMUM_CAPACITY.  If (3 * expectedMaxSize)/2 is negative, it
     * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
     */
    private int capacity(int expectedMaxSize) {
        // Compute min capacity for expectedMaxSize given a load factor of 2/3
        int minCapacity = (3 * expectedMaxSize)/2;

        // Compute the appropriate capacity
        int result;
        if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
            result = MAXIMUM_CAPACITY;
        } else {
            result = MINIMUM_CAPACITY;
            while (result < minCapacity)
                result <<= 1;
        }
        return result;
    }

    /**
     * Initialize object to be an empty map with the specified initial
     * capacity, which is assumed to be a power of two between
     * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
     */
    private void init(int initCapacity) {
        // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
        // assert initCapacity >= MINIMUM_CAPACITY;
        // assert initCapacity <= MAXIMUM_CAPACITY;

        threshold = (initCapacity * 2)/3;
        table = new Object[2 * initCapacity];
        for (int i = 0; i < table.length; i += 2)
            table[i] = EMPTY;
    }

    /**
     * Returns the number of key-value mappings in this identity hash map.
     *
     * @return the number of key-value mappings in this map.
     */
    public int size() {
        return size;
    }

    /**
     * Returns <tt>true</tt> if this identity hash map contains no key-value
     * mappings.
     *
     * @return <tt>true</tt> if this identity hash map contains no key-value
     *         mappings.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Return index for Object x given table size len, where len is a power of
     * two. 
     */
    private static int hash(Object x, int len) {
        int h = System.identityHashCode(x);
        return h & (len-2);
    }

    /**
     * Returns the value to which the specified key is mapped in this identity
     * hash map, or <tt>null</tt> if the map contains no mapping for
     * this key.  A return value of <tt>null</tt> does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it is also
     * possible that the map explicitly maps the key to <tt>null</tt>. The
     * <tt>containsKey</tt> method may be used to distinguish these two
     * cases.
     *
     * @param   key the key whose associated value is to be returned.
     * @return  the value to which this map maps the specified key, or
     *          <tt>null</tt> if the map contains no mapping for this key.
     * @see #put(Object, Object)
     */
    public Object get(Object key) {
        int i = hash(key, table.length);
        while (true) {
            Object item = table[i];
            if (item == key) 
                return table[i+1];
            if (item == EMPTY)
                return null;
            if ((i+=2) >= table.length)
                i = 0;
        }
    }

    /**
     * Associates the specified value with the specified key in this identity
     * hash map.  If the map previously contained a mapping for this key, the
     * old value is replaced.
     *
     * @param key the key with which the specified value is to be associated.
     * @param value the value to be associated with the specified key.
     * @return the previous value associated with <tt>key</tt>, or
     *	       <tt>null</tt> if there was no mapping for <tt>key</tt>.  (A
     *         <tt>null</tt> return can also indicate that the map previously
     *         associated <tt>null</tt> with the specified key.)
     * @see     Object#equals(Object)
     * @see     #get(Object)
     * @see     #containsKey(Object)
     */
    public Object put(Object key, Object value) {
        /*
         * insertionIndex is the index of the first DELETED
         * entry passed over while checking if x is already
         * present. If such a slot exists, we should use it
         * rather than trailing null slot
         */
        int insertionIndex = -1; 
        int i = hash(key, table.length); 

        while (true) {
            Object item = table[i];

            if (item == EMPTY) {
                if (insertionIndex < 0)
                    insertionIndex = i;
                table[insertionIndex] = key;
                table[insertionIndex+1] = value;

                if (++size >= threshold) resize();
                return null;
            } else if (item == key) {
                Object oldValue = table[++i];
                table[i] = value;
                return oldValue;
            } else if (item == DELETED && insertionIndex < 0) {
                insertionIndex = i; 
            }
           if ((i+=2) >= table.length)
                i = 0;
        }
    }

    /**
     *  Double the size of the table
     */
    private void resize() {
        int oldTableSize = table.length;
        if (oldTableSize == 2*MAXIMUM_CAPACITY) { // can't expand any further
            if (threshold == MAXIMUM_CAPACITY-1)
                throw new IllegalStateException("Capacity exhausted.");
            threshold = MAXIMUM_CAPACITY-1;  // Gigantic map!
            return;
        }

        int newSize = 2 * oldTableSize;
        threshold = (oldTableSize * 2)/3;

        Object[] oldTable = table;
        table = new Object[newSize];
        for (int i = 0; i < table.length; i +=2)
            table[i] = EMPTY;

        for (int j = 0; j < oldTable.length; j+=2) {
            Object key = oldTable[j];
            if (key != EMPTY && key != DELETED) {
                Object value = oldTable[j+1];

                int i = hash(key, table.length);  
                while (table[i] != EMPTY) {
                    if ((i+=2) == table.length)
                        i = 0;
                }
        
                table[i] = key;
                table[i+1] = value;
            }
        }
    }

    /**
     * Removes the mapping for this key from this map if present.
     *
     * @param key key whose mapping is to be removed from the map.
     * @return previous value associated with specified key, or <tt>null</tt>
     *	       if there was no entry for key.  (A <tt>null</tt> return can
     *	       also indicate that the map previously associated <tt>null</tt>
     *	       with the specified key.)
     */
    public Object remove(Object key) {
        int i = hash(key, table.length);
        while (true) {
            Object item = table[i];
            if (item == EMPTY) 
                return null;
            else if (item == key) {
                Object oldValue = table[i+1];
                markAsDeleted(i);
                return oldValue;
            }
            if ((i+=2) >= table.length)
                i = 0;
        }
    }


    /**
     * Mark table[index] as either DELETED or, if possible, EMPTY.
     */
    private void markAsDeleted(int index) {
        /*
         * Because table[index] could have been between two real items
         * without an intervening EMPTY, it must normally be marked as
         * DELETED so that linear probing continues to work. But if it is
         * part of a sequence of DELETEDs ending in a EMPTY, table[index] and
         * other members of the sequence can be set to EMPTY, which will
         * shorten subsequent searches, especially after bursts of
         * removals. It also guarantees that an empty table has no DELETED
         * markers. In practice, this keeps the number of DELETED markers
         * low enough to not hurt search times much in the presence of
         * deletions.
         *
         * Note that the alternative of re-inserting old elements rather
         * than using a DELETED marker cannot be used here because this
         * could re-arrange items in the midst of an iteration.
         */
        --size;

        table[index+1] = null; // null out value;

        int j = index;
        while (true) { // Traverse starting at next slot after index
            if ((j+=2) == table.length)
                j = 0;

            Object item = table[j];
            if (item == EMPTY)           // Found a sequence ending in EMPTY
                break;

            else if (item != DELETED) { // no such luck
                table[index] = DELETED;
                return;
            }
        }

        while (true) {                   // Run backwards until not DELETED
            if ((j-=2) < 0)
                j = table.length - 2;

            if (j == index || table[j] == DELETED)
                table[j] = EMPTY;
            else
                return;
        }
    }

    /**
     * Removes all mappings from this map.
     */
    public void clear() {
        for (int i = 0; i < table.length; i+=2)
            table[i] = EMPTY;
        for (int i = 1; i < table.length; i+=2)
            table[i] = null;
        size = 0;
    }


}